首页 > 代码库 > Codeforces Round #280 (Div. 2)
Codeforces Round #280 (Div. 2)
A. Vanya and Cubes
手速不够快，被别人抢先了。。。
#include<bits/stdc++.h>#define eps 1e-9#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,num,w,t,u,v;bool flag;int main(){ scanf("%d",&n); j=0; for (i=0;;i++) { j+=i; ans+=j; if (ans>n) { printf("%d\n",i-1); return 0; } } return 0;}B. Vanya and Lanterns
一条长为l的线段，上边有几个点，每个点向左d长度，向右d长度均被覆盖，问完全覆盖线段的最小d是多少。
排序后求出最大距离，除以2就行了。边界的话特判一下就可以了
#include<bits/stdc++.h>#define eps 1e-9#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,cas,num,w,t,u,v,a[1005],l;bool flag;double big;int main(){ scanf("%d%d",&n,&l); for (i=0;i<n;i++) { scanf("%d",&a[i]); } sort(a,a+n); big=0; for (i=0;i<n-1;i++) { big=max(big,(double)(a[i+1]-a[i])); } big/=2; big=max((double)a[0],big); big=max((double)(l-a[n-1]),big); printf("%f\n",big); return 0;}C. Vanya and Exams
给出n个课程的成绩，以及每个课程加1分的代价，问最终成绩平均值达到avg的最小代价。
这贪心算法也太明显了。
#include<bits/stdc++.h>#define eps 1e-9#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;struct node{ LL a,b;}s[100005];LL i,j,k,n,m,x,y,T,ans,big,cas,num,w,t,u,v,sco,tar,avg,r;bool flag;bool cmp(node x,node y){ return x.b<y.b;}int main(){ scanf("%I64d%I64d%I64d",&n,&r,&avg); tar=avg*n; for (i=0;i<n;i++) { scanf("%I64d%I64d",&s[i].a,&s[i].b); tar-=s[i].a; } sort(s,s+n,cmp); for (i=0;tar>0;i++) { sco=r-s[i].a; if (sco<=tar) { tar-=sco; ans+=sco*s[i].b; } else { ans+=tar*s[i].b; break; } } printf("%I64d\n",ans); return 0;}D. Vanya and Computer Game
Vanya和Vova打怪物，其中Vanya每1/x秒使所有活着的怪掉1格血，Vova每1/y使所有活着的怪掉1格血，问每个怪最后一击是谁发出的，同时则输出Both。
暴力+优化
比赛时竟然看错题了= =||，我看成了每1/x秒杀x格血，并且一次只能杀一只怪物 = =|| 前者是我看错了，后者就是题目上也没有说清，还是看数据才明白的。。。其他很多人也Wrong Answer on pretest 3，说明看错题的人不少。。。
显然他们杀怪是有周期性的，每一周期使所有怪各掉G = (x+y)/gcd(x,y)血，所以事先所有怪的血模上G即可。这样就简化了数据。
然后模拟杀怪的过程即可。10^6也不会超时、
#include<bits/stdc++.h>#define eps 1e-9#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;LL i,j,k,n,m,x,y,T,ans,big,cas,num,w,t,u,v,maxhp,g,numx,numy,pi,pj,hp,monster,cur;bool flag;struct node{ LL hp,i,r;}h[100005];int gcd(LL a,LL b){ return b==0?a:gcd(b,a%b);}bool cmp(node x,node y){ return x.hp<y.hp;}bool cmp2(node x,node y){ return x.i<y.i;}int main(){ scanf("%I64d%I64d%I64d",&n,&x,&y); g=gcd(x,y); maxhp=(x+y)/g; for (i=0;i<n;i++) { scanf("%I64d",&h[i].hp); h[i].hp%=maxhp; h[i].i=i; } sort(h,h+n,cmp); pi=y;pj=x; cur=0; monster=0; while (monster<n&&h[monster].hp==0) h[monster++].r=3; while (monster<n) { if (pi<pj) { cur++; while (monster<n&&h[monster].hp<=cur) { h[monster++].r=1; } pi+=y; }else if (pi>pj) { cur++; while (monster<n&&h[monster].hp<=cur) { h[monster++].r=2; } pj+=x; }else { cur+=2; while (monster<n&&h[monster].hp<=cur) { h[monster++].r=3; } pi=y; pj=x; } } sort(h,h+n,cmp2); for (i=0;i<n;i++) { if (h[i].r==1) printf("Vanya\n");else if (h[i].r==2) printf("Vova\n");else printf("Both\n"); } return 0;}E. Vanya and Field
【描述】给n*n个格子，一共有m个苹果，给了每个苹果的坐标，vanya如果当前在(x,y)，则下一步在((x+dx)mod n,(y+dy) mod n)，其中gcd(n,dx)=gcd(n,dy)=1，每当他走到之前走过的结点就停止，求vanya的起点(x,y)使得获得的苹果数最大
【解释】数论
根据gcd(n,dx)=gcd(n,dy)=1，由费马小定理dx^(n-1)=1(mod n)，dy^(n-1)=1(mod n)，即至少走n步会回到原点。
我们先假设起点是(0,0)，那么每步走过的点为(k*dx(mod n),k*dy(mod n)) (k=0,1,2…,n-1)，
由于k*dx可以跑遍模n剩余系，所以可以假设(i,r[i])表示k*dx(mod n)等于i时，k*dy的取值
如果起点是(0,s) s=0,1,2…n-1，那么就可以表示为(i,(r[i]+s)mod n)，
可以发现，起点为(0,s) s=0,1,2…n-1的这n个点集没有交集，并且并集正好是n^2。
那么，设定n个集合，就把给定的苹果所在的点分别划分到对应的集合中，最后看哪个集合苹果数量最多即可。
#include<bits/stdc++.h>#define eps 1e-9#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;LL i,j,k,n,m,x,y,T,ans[1000005],big,cas,num,w,t,u,v,cur,ansx,r[1000005],dx,dy;bool flag;int main(){ scanf("%I64d%I64d",&n,&m); scanf("%I64d%I64d",&dx,&dy); for (i=0;i<n;i++) { r[(dx*i)%n]=(dy*i)%n; } for (i=1;i<=m;i++) { scanf("%I64d%I64d",&x,&y); ans[(y-r[x]+n)%n]++; } cur=0; for (i=0;i<n;i++) { if (ans[i]>cur) { ansx=i; cur=ans[i]; } } printf("0 %I64d\n",ansx); return 0;}printf("%I64d\n",0) 这样输出是不对的 = = 有一发挂在了这里
不知怎么的，这次比赛出奇地简单呀。。
Codeforces Round #280 (Div. 2)