Codeforces Round #128 (Div. 二)

2012-08-13

Codeforces Round #128 (Div. 2)转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmodecontents

Codeforces Round #128 (Div. 2)

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

A:Two Problems

很坑的题目，好多人栽了，有两道题，初始分数为a，每分钟分值降da,另外一道题初始为b，每分钟降db。问一个人能不能刚好拿到X分。

X可能为0，这让好多人都WA，X为0这是肯定可以的，两题都没做出来。

之后O（t）的做法还是一直WA，无语，无奈下直接O（t*t）暴力了。

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<stack>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-6#define LL long long#define LD long double#define pi acos(-1.0)#define inf 1LL<<60using namespace std;int flag[605];int main(){int x,t,a,da,b,db,i,j,aa,bb;scanf("%d%d%d%d%d%d",&x,&t,&a,&b,&da,&db);if(x==0)puts("YES");else{for(i=0;i<t;i++)for(j=0;j<t;j++){aa=a-i*da;bb=b-j*db;if(aa==x || bb==x || aa+bb==x){puts("YES");return 0;}}puts("NO");}return 0;}

B:Game on Paper

竟然最后没有过评测。做法是放入一个棋子，以这个棋子的为中心的九宫格为中心判断是否形成3*3。由于棋子最多为10W，10W*9*9还是可以接受的。注意在main里面的枚举，是9个位置，当时就是挂在这地方。

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<stack>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-6#define LL long long#define LD long double#define pi acos(-1.0)#define inf 1LL<<60using namespace std;bool flag[1005][1005];int way[9][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1},{0,0}};bool check(int x,int y){if(flag[x][y]==false)return false;for(int i=0;i<8;i++)if(flag[x+way[i][0]][y+way[i][1]]==false)return false;return true;}int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){memset(flag,false,sizeof(flag));int x,y;int ans=-1;for(int t=1;t<=m;t++){scanf("%d%d",&x,&y);flag[x][y]=true;int i;if(ans!=-1)continue;for(i=0;i<9;i++){if(check(x+way[i][0],y+way[i][1])){ans=t;break;}}}printf("%d\n",ans);}return 0;}

C：Photographer

比较简单，贪心。先满足要求比较小的顾客就行了，按总消费递增排序。

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<stack>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-6#define LL long long#define LD long double#define pi acos(-1.0)#define inf 1LL<<60using namespace std;int n,A,B,d;struct Node{int x,y;int cost;int idx;}a[100005];bool cmp(Node n1,Node n2){return n1.cost<n2.cost;}int main(){while(scanf("%d%d",&n,&d)!=EOF){scanf("%d%d",&A,&B);for(int i=0;i<n;i++){scanf("%d%d",&a[i].x,&a[i].y);a[i].cost=A*a[i].x+B*a[i].y;a[i].idx=i+1;}sort(a,a+n,cmp);int ans[100005],cnt=0;for(int i=0;i<n;i++)if(d>=a[i].cost){ans[cnt++]=a[i].idx;d-=a[i].cost;}elsebreak;printf("%d\n",cnt);if(cnt!=0){for(int i=0;i<cnt-1;i++)printf("%d ",ans[i]);printf("%d\n",ans[cnt-1]);}}return 0;}

D:Hit Ball

题目乱七八糟的解释。就是一个走廊里，站在(a/2,m,0)没着向量(vx,vy,vz)扔出一个球，问最后砸在门上的什么位置。门宽为a,门高为b,走廊两侧有墙，上侧有天花板，撞击后会反射。

首先根据y轴方向，速度在y轴上的分量一直是vy,并不由撞击产生改变，可以算出时间-m/vy;

由于每次反射并不改变速度的分量，只是改变了方向，比如和墙撞击，速度由vx变为-vx，已知时间就可以算出X轴方向运动的距离，然后再折合到0-a范围内。

#include<iostream>#include<iomanip>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#include<map>#include<stack>#include<set>#include<queue>#include<string>#include<vector>#define eps 1e-7#define LL long long#define LD long double#define pi acos(-1.0)#define inf 1LL<<60using namespace std;int a,b,m;int vx,vy,vz;int main(){while(scanf("%d%d%d%d%d%d",&a,&b,&m,&vx,&vy,&vz)!=EOF){double t=m*(-1.0)/vy;double X=t*vx+a/2.0,ansx;if(X<eps){X=-X;int cx=(int)(X/a);ansx=X-cx*a;if(cx&1)ansx=a-ansx;}else if(X>a+eps){X-=a;int cx=(int)(X/a);ansx=X-cx*a;if(!(cx&1))ansx=a-ansx;}elseansx=X;double Z=t*vz;int cz=(int)(Z/b);double ansz=Z-cz*b;if(cz&1)ansz=b-ansz;printf("%.10f %.10f\n",ansx,ansz);}return 0;}

E：号称readforces，有时间再看题吧，不过英语着实很差

热点排行

编程

Codeforces Round #128 (Div. 二)