转载请注明出处,谢谢 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<<60 using 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<<60 using 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<<60 using 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; } else break; 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<<60 using 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; } else ansx=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,有时间再看题吧,不过英语着实很差