Category Archives: DefaultCategory

[BeiJing2010]取数游戏 game

Posted on by

[BeiJing2010]取数游戏 game

Time Limit:10000MS Memory Limit:65536K
Total Submit:16 Accepted:9
Case Time Limit:1000MS

Description

小 C 刚学了辗转相除法，正不亦乐乎，这小 P 又出来捣乱，给小 C 留了个
难题。
给 N 个数，用 a1,a2…an来表示。现在小 P 让小 C 依次取数，第一个数可以
随意取。假使目前取得 aj，下一个数取ak(k>j)，则ak必须满足gcd(aj,ak)≥L。
到底要取多少个数呢？自然是越多越好！
不用多说，这不仅是给小 C 的难题，也是给你的难题。

Input

第一行包含两个数N 和 L。
接下来一行，有 N 个数用空格隔开，依次是 a1,a2…an。

Output

仅包含一行一个数，表示按上述取法，最多可以取的数的个数。

Sample Input

Sample Output

Hint

选取 3个数16、24、6。gcd(16,24)=8，gcd(24,6)=6。

2≤L≤ai≤1 000 000；
30% 的数据N≤1000；
100% 的数据 N≤50 000

Source
额。。这题感觉跟VIJOS上一题一样。。记Dpi表示以i的倍数为结尾的最长长度。。然后Dp一下就可以了。。

#include <algorithm>#include <cstdio>#define rep(i,n) for(int i=0;i<n;i++)const int inf=~0U>>1,maxw=1000000,maxp=10000;using namespace std;int Dp[maxw+1]={},n,L,List[maxp];int main(){ scanf("%d%d",&n,&L); rep(i,n) { int x,tmp=0,c=0; scanf("%d",&x); for(int i=1;i*i<=x;i++) if(x%i==0) { if(i>=L)List[c++]=i; if(x/i>=L)List[c++]=x/i; } rep(i,c)tmp=max(tmp,Dp[List[i]]);tmp++; rep(i,c)Dp[List[i]]=tmp; } int ans=0; rep(i,maxw+1)ans=max(ans,Dp[i]); printf("%dn",ans);}35 6 7 16 9 24 6

[POI2007]Zap

Posted on by

[POI2007]Zap

Time Limit:10000MS Memory Limit:165536K
Total Submit:176 Accepted:34
Case Time Limit:2000MS

Description

FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且 gcd(x,y)=d。
作为FGD的同学，FGD希望得到你的帮助。

Input

第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）
接下来n行，每行表示一个询问，每行三个正整数，分别为a,b,d。（1<=d<=a,b<=50000）

Output

对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。

Sample Input

Sample Output

Hint

对于第一组询问，满足条件的整数对有(2,2)，（2,4），（4，2）。
对于第二组询问，满足条件的整数对有（6,3），（3,3）。

Source
额。。这题十分的那个啥。。。。Orz oimaster神牛！！！
首先对付这种复杂的问题只有容斥原理了。。
只需要算出G(x,y):1<=i<=a,1<=j<=b且(i,j)=1的就可以了。。
F(a,b,k)表示1<=i<=a,1<=j<=b且(i,j)>=k的对数，很显然为a/k*b/k。。
那么G(a,b)=1*F(a,b,1)-F(a,b,2)….注意对每个k来说，无论a和b，系数是固定的。。
同时a/k*b/k按相同值分段可以分成Sqrt级别。。所以预处理一下系数的部分和就OK了。。
代码长度最短囧。。。

#include <algorithm>#include <cstdio>#define rep(i,n) for(int i=0;i<n;i++)const int maxn=50000+10;using namespace std;int P[maxn]={};int get(int i){ int s=1; for(int x=2;x*x<=i;x++)if(i%x==0) { i/=x;if(i%x==0)return 0; s*=-1; } if(i>1)s*=-1; return s;}int main(){ for(int i=1;i<=maxn;i++)P[i]=P[i-1]+get(i); int a,b,k,n;scanf("%d",&n); rep(i,n) { scanf("%d%d%d",&a,&b,&k);a/=k;b/=k; if(a>b)swap(a,b); int ans=0; for(int t=1;t<=a;t++) { int m=min(a/(a/t),b/(b/t))-t; ans+=(P[t+m]-P[t-1])*(a/t)*(b/t); t+=m; } printf("%dn",ans); }}3224 5 26 4 3

[POI2006]Szk-Schools

Posted on by

[POI2006]Szk-Schools

Time Limit:5000MS Memory Limit:65536K
Total Submit:34 Accepted:21
Case Time Limit:1000MS

Description

Input

Output

如果有可行解, 输出最小代价,否则输出NIE.

Sample Input

Sample Output

Source
费用流TLE。。只好学了个KM算法来对付这题囧。。

#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_back#define Debug(x) cout<<#x<<"="<<x<<endl;#define For(i,l,r) for(int i=l;i<=r;i++)const int inf=~0U>>2,maxn=200;using namespace std;typedef long long ll;typedef unsigned long long ull;int Lx[maxn],Ly[maxn],w[maxn][maxn],Link[maxn],Slack[maxn],n;bool VisX[maxn],VisY[maxn];bool Find(int x){ VisX[x]=true; rep(y,n)if(!VisY[y]) { int t=Lx[x]+Ly[y]-w[x][y]; if(!t) { VisY[y]=true; if(Link[y]==-1||Find(Link[y])) return Link[y]=x,true; } else Slack[y]=min(Slack[y],t); } return false;}void KM(){ memset(Link,-1,sizeof Link); rep(i,n)Lx[i]=-inf; memset(Ly,0,sizeof Ly); rep(i,n)rep(j,n)Lx[i]=max(Lx[i],w[i][j]); rep(x,n) { rep(y,n)Slack[y]=inf; for(;;) { memset(VisX,0,sizeof VisX); memset(VisY,0,sizeof VisY); if(Find(x))break; int d=inf; rep(y,n)if(!VisY[y])d=min(d,Slack[y]); rep(x,n)if(VisX[x])Lx[x]-=d; rep(y,n)if(VisY[y])Ly[y]+=d;else Slack[y]-=d; } }}void InIt(){ cin>>n;int m,a,b,k; rep(x,n)rep(y,n)w[x][y]=-inf; rep(x,n) { scanf("%d%d%d%d",&m,&a,&b,&k);–a;–b;–m; for(int y=a;y<=b;y++) w[x][y]=-abs(y-m)*k; }}int main(){ //freopen("in","r",stdin); InIt();KM();int ans=0; rep(i,n) { int tmp; if((tmp=w[Link[i]][i])==-inf){cout<<"NIE"<<endl;return 0;} ans-=tmp; } cout<<ans<<endl;}951 1 2 31 1 5 13 2 5 54 1 5 103 3 3 1

网易有道在线赛

Posted on by

好吧这个比赛的题目太BT了。。完全没有思路。。。
A想了半天想出了个贪心。。就是从A开始像PRIM最小生成树一样计算最小生成树，
每次扩展离ch最远的节点。。只有21分。。（后来我交这个有81分。。我怀疑数据在变。。）
然后我只好想办法骗点分。。我想了半天只能搜索。。每次搜索扩展那个节点，然后判断一下ch是不是能到达所有的没有扩展到节点。。。我感觉效率非常烂。。肯定要挂。然后我想到原来那个贪心。。决定按离ch的距离从小到大搜。。结果24分。。然后我改掉了几个错误，45分了。。看了一会儿。。又改掉了几个错误。。81分了。。。
此时突然发现有个回溯后的恢复没有加上，加上后TLE到3分。。
震惊了。。
然后我灵感爆发，决定随机化恢复不恢复回溯，一开始是1/2不恢复，87，
1/8 93
1/256 96
1/2048 99
就这么AC了。。。
B题目都没看。。
C一开始就觉得要考虑各种各样的情况，非常的复杂，用Java写了半天都要吐了。。。最后看到A改成部分分了。。果断放弃去骗A的分。。
教主真是太神了！！！Orz到极点啊！！！！！
BS有道啊，什么有道难题啊，全是难题啊。。。
发现C居然是CTSC的题目。。。无语到极点。。。

[Shoi2007]Setstack 集合堆栈机

Posted on by

[Shoi2007]Setstack 集合堆栈机

Time Limit:1000MS Memory Limit:65536K
Total Submit:22 Accepted:8

Description

中学数学里集合的元素往往是具体的数字，比如A = {1,2,3}，B = {}（空集）等等。但是要特别注意，集合的元素也可以是另一个集合，比如说C = {{}}，即说明C有且仅有一个元素——空集B，所以称B是C的子集或者称B是C的元素都是正确的。所谓一个集合的势，就是这个集合的元素个数，一般记为|S|，空集的势为0。在上例中，|A| = 3，|B| = 0，|C| = 1。
鉴于集合论是现代数学的基础理论这一事实，一群异想天开的科学家开始着手建造一台新式的超级计算机——集合堆栈机Alpha，这台机器操作的将是集合而不是数字。不过由于Alpha的竣工之日遥遥无期，科学家们希望你为他们编写一台虚拟机，好让他们检查自己的原型设计是否合理。
Alpha的存储设备只有一个栈，栈的每个单元都只能放置一个集合。一开始，栈是空的，在每个操作结束后，计算机就会输出位于栈顶单元的那个集合的势。Alpha拥有五种不同的指令，分别为：PUSH、DUP、UNION、INTERSECT和ADD，他们的功能如下：

Input

第一行只有一个整数n（0≤n≤2000），代表将要执行的指令条数。接下来有n行，每行有包含一条大写的指令，我们保证每条指令都是上述五条指令中的一条，并且虚拟机总是能正确执行完所有的指令。

Output

输出虚拟机的输出结果即可。每行输出一个大于或等于0的整数，代表虚拟机执行该条指令后的输出。选手们务必仔细考量程序的执行效率。

Sample Input

Sample Output

Hint

对于20%的数据，n ≤ 10。
对于100%的数据，n ≤ 2000。

Source
额。。这道题目只要给每个集合设计一个Hash函数就好办了。。我看oimaster大神说的是
全部xor一个值然后乘起来。。然后我自己也想了一个。。就是把所有的子集的Hash值排序一下
然后直接效仿Rabin—Karp..关键是如果这么搞全是0.。。所以再加个修正值。。。神奇的1A囧。。
Code：
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define All(x) x.begin(),x.end()
const int seed=13331;
using namespace std;
typedef unsigned long long ull;
typedef vector<ull> set;
ull Code(const set&s)
{
    ull ret=0;
    rep(i,s.size())ret*=seed,ret+=s[i]+78;
    return ret;
}
void Normal(set&s)
{
    sort(All(s));
    s.resize(unique(All(s))-s.begin());
}
stack<set> S;
int main()
{
    int n;scanf("%d",&n);char cmd[10];set a,b;
    while(n–)
    {
        scanf("%s",cmd);
        switch(cmd[0])
        {
            case ‘P’:S.push(set());break;
            case ‘D’:S.push(S.top());break;
            case ‘A’:a=S.top();S.pop();b=S.top();S.pop();b.pb(Code(a));
                    Normal(b);S.push(b);break;
            default:a=S.top();S.pop();b=S.top();S.pop();set c(a.size()+b.size());
                if(cmd[0]==’U’)c.resize(set_union(All(a),All(b),c.begin())-c.begin());
                else c.resize(set_intersection(All(a),All(b),c.begin())-c.begin());
                Normal(c);S.push(c);break;
        }
        printf("%dn",S.top().size());
    }
}

001011222

9PUSHDUPADDPUSHADDDUPADDDUPUNION

[CQOI2007]余数之和sum

Posted on by

[CQOI2007]余数之和sum

Time Limit:5000MS Memory Limit:165536K
Total Submit:41 Accepted:17
Case Time Limit:1000MS

Description

给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。
例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

输入仅一行，包含两个整数n, k。

Output

输出仅一行，即j(n, k)。

Sample Input

Sample Output

Hint

50%的数据满足：1<=n, k<=1000
100%的数据满足：1<=n ,k<=10^9

Source
额。。k mod i=k-(k/i)*i。。。
那么对于一段k/i相等的可以一起计算。。
可以证明最多分成sqrt（n）段。。
Code：

#include <iostream>using namespace std;typedef long long ll;int main(){ int n,k;cin>>n>>k;ll ans=0; for(int i=1;i<=n;i++) { int a=k/i,l=k/(a+1)+1,r=a?k/a:n; if(r>=n)r=n; ans+=ll(k)*(r-l+1)-ll(a)*(l+r)*(r-l+1)/2; i=r; } cout<<ans<<endl;}75 3

[JSOI2009]火星藏宝图

Posted on by

[JSOI2009]火星藏宝图

Time Limit:5000MS Memory Limit:65536K
Total Submit:38 Accepted:17
Case Time Limit:1000MS

Description

Input

Output

Sample Input

Sample Output

Hint

Source

JSOI2009Day2

囧啊。。看上去很难的题目。。首先肯定是要DP的。但是暴力Dp是N^2额囧。。
显然要优化。。怎么优化呢？Dp的复杂度=状态数*每个状态计算需要的时间。。。
状态数肯定变变不了，是N个。。考虑减少后一项，
也就是当前需要考虑的过去状态个数，注意到加入A可以到达B，B可以到达C的话，
显然不会用A来更新C。。。从上到下，从左到右考虑，那么每列最多一个是有用的。。
就可以弄出一个NM的算法了。。。
Code：

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxn=1000,maxm=200000,inf=~0U>>2;int M[maxn],X[maxn]={},n,m;struct Land{ int i,j,v; Land(){} Land(int _i,int _j,int _v):i(_i),j(_j),v(_v){} bool operator<(const Land&o)const { if(i!=o.i)return i<o.i; return j<o.j; }}A[maxm];inline int Dist(int a,int b,int i,int j){ return (a-i)*(a-i)+(b-j)*(b-j);}int main(){ //freopen("in","r",stdin); scanf("%d%d",&n,&m);int x,y,v; rep(i,m)M[i]=-inf; rep(i,n) { scanf("%d%d%d",&x,&y,&v);–x;–y; A[i]=Land(x,y,v); } sort(A,A+n);int ret; M[0]=A[0].v; for(int i=1;i<n;i++) { x=A[i].i;y=A[i].j;v=A[i].v; ret=-inf; rep(j,y+1) ret>?=M[j]-Dist(x,y,X[j],j); ret+=v; M[y]=ret;X[y]=x; } printf("%dn",ret);}-44 101 1 2010 10 103 5 605 3 30