2015 ACM / ICPC EC – Final
A. Boxes and Balls
题意：有不超过n个球放在若干袋子里，每次操作拿一个新的袋子，从现有的所有袋子中各拿一个求放进新的袋子里，去掉空袋子
问最多可以放多少个球，使得每次操作之后，所有袋子球数构成情况不变
容易发现，恒定不变的状态为1,12,123…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; int T; LL n; int main() { cin>>T; for(int cas=1;cas<=T;cas++) { cin>>n; LL L=1,R=3000000000LL; while(L<R) { LL mid=(L+R+1)>>1; if(mid*(mid+1)/2<=n) L=mid; else R=mid-1; } cout<<"Case #"<<cas<<": "<<L*(L+1)/2<<endl; } return 0; } |
B.Business Cycle
题意：给定一个n个结点的环，编号0~n-1，每个点有一定的权值，从点0出发沿编号走，到达某一个节点则把目前总权值加上这个节点的权值，如果结果小于0则变成0。现在给你最多可以走的步数P和最大需要到达的权值大小G，问你需要的最小的初始权值为多少，能在P步内能够产生的最大权值大于等于G
初始权值越大，经过同样步数之后得到的权值越大，考虑二分，但是步数太大无法模拟
如果走第一圈的时候在某一点上x变成0，等价于初始权值为0，接着从x开始，每走一圈的变化值是相同的
否则每走一圈的变化值都相同
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int MAXN=200010; typedef long long LL; int T,n; LL L,R,G,P,w[MAXN]; bool check(LL x,LL k,LL tar) { if(k<=n) { LL ans=x; for(int i=1;i<=k;i++) x=max(0LL,x+w[i]),ans=max(ans,x); if(ans>=tar) return true; return false; } if(k<=2*n) { LL ans=x; for(int i=1;i<=n;i++) x=max(0LL,x+w[i]),ans=max(ans,x); for(int i=1;i<=k-n;i++) x=max(0LL,x+w[i]),ans=max(ans,x); if(ans>=tar) return true; return false; } if(k<=3*n) { LL ans=x; for(int i=1;i<=n;i++) x=max(0LL,x+w[i]),ans=max(ans,x); for(int i=1;i<=n;i++) x=max(0LL,x+w[i]),ans=max(ans,x); for(int i=1;i<=k-n-n;i++) x=max(0LL,x+w[i]),ans=max(ans,x); if(ans>=tar) return true; return false; } LL ans=x,x0; for(int i=1;i<=n;i++) x=max(0LL,x+w[i]),ans=max(ans,x); x0=x; LL res=ans; for(int i=1;i<=n;i++) x=max(0LL,x+w[i]),res=max(res,x); LL c=k/n,r=k%n,ret=max(res,x),x1=x; c--; for(int i=1;i<=n;i++) x=max(0LL,x+w[i]),ret=max(ret,x); for(int i=1;i<=r;i++) x=max(0LL,x+w[i]),ret=max(ret,x); if(x1>x0) { if(c-2>=(tar-ret+x1-x0-1)/(x1-x0)) return true; else return false; } else { if(ret>=tar) return true; else return false; } return false; } int main() { scanf("%d",&T); for(int cas=1;cas<=T;cas++) { scanf("%d%lld%lld",&n,&G,&P); for(int i=1;i<=n;i++) scanf("%lld",&w[i]); L=0,R=G; while(L<R) { LL mid=(L+R)>>1; bool res=check(mid,P,G); if(!res) L=mid+1; else R=mid; } printf("Case #%d: %lld\n",cas,L); } return 0; } |
D.Change
题意：现有一台售货机，要破开一张人民币，目标是一张更小面值的人民币
每次可以买任意价值的东西，返还币值类型随机，问至少花多少钱一定能获得想要的面值
结论：若B为0.01,0.1,1,10且A不等于2B，答案0.02，否则答案0.01
考虑B=0.01，那么花0.01，则一定会找回一张0.02，再把0.02破成0.01即可
其余类似
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include<cstdio> using namespace std; double A,B; int main() { int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { printf("Case #%d: ",cas); scanf("%lf%lf",&A,&B); double ans; if(B==0.01) { if(A==0.02)ans=0.01; else ans=0.02; } else if(B==0.1) { if(A==0.2)ans=0.01; else ans=0.02; } else if(B==1) { if(A==2)ans=0.01; else ans=0.02; } else if(B==10) { if(A==20)ans=0.01; else ans=0.02; } else ans=0.01; printf("%.2lf\n",ans); } return 0; } |
F.Hungry Game of Ants
每只蚂蚁运动速度为1，两种蚂蚁相遇时，体重大的蚂蚁吃掉小的（体重相同时左侧蚂蚁获胜），体重增量为所食蚂蚁的体重，运动到边界的蚂蚁折返
蚂蚁的初始朝向有2^n种可能，问其中有多少种使得第K只蚂蚁最终存活
第K只蚂蚁一定初始方向朝左，否则一定会被吃
考虑K的左侧，设离K最近的向左的蚂蚁为x，\([x+1,K-1]\)的所有蚂蚁依次被K吃掉，1到x最终会合成一只体重为\((1+x)*x/2\)的向右的蚂蚁
那么要满足条件\((1+2+…+x)\leq [(x+1) + (x+2) + … + K]\)
考虑K的右侧，设右侧的所有向左的蚂蚁为\(x_1,x_2…x_m\)，要符合在K吃完其左侧的所有蚂蚁后
\([K+1,x_1]\)的所有蚂蚁会合成一只后被K吃掉，接着\([x_1+1,x_2]\)的所有蚂蚁被K吃掉，以此类推
故右侧用一个简单的dp，\(F(i)\)表示前i只蚂蚁都被K吃掉的方案数，用前缀和优化转移
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef long long LL; const int MOD=1000000007; int T,n,k; LL pow2[1000010]; LL f[1000010],s[1000010]; LL sum(LL l,LL r) { return (l+r)*(r-l+1)/2; } int main() { pow2[0]=1; for(int i=1;i<=1000000;i++) pow2[i]=(pow2[i-1]+pow2[i-1])%MOD; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) f[i]=0,s[i]=0; printf("Case #%d: ",cas); if(n==1) {puts("2");continue;} if(k==1) {puts("0");continue;} if(k==n) { LL ans=0; for(int i=1;i<k;i++) { LL winner=sum(i+1,k); LL left=sum(1,i); if(left>=winner) continue; if(i==1) ans=(ans+pow2[i-1])%MOD; ans=(ans+pow2[i-1])%MOD; } ans=(ans+ans)%MOD; printf("%lld\n",ans); continue; } LL ans=0; f[k]=1,s[k]=1; int gp=k; for(int i=k+1;i<=n;i++) { while(sum(1,gp)<sum(gp+1,i)) gp++; f[i]=(s[i-1]-s[gp-1]+MOD)%MOD; s[i]=(s[i-1]+f[i])%MOD; } LL tmp=0; for(int i=k;i<=n;i++) if(sum(1,i)>=sum(i+1,n)) tmp=(tmp+f[i])%MOD; for(int i=1;i<k;i++) { LL winner=sum(i+1,k); LL left=sum(1,i); if(left>=winner) continue; winner+=left; if(i==1) ans=(ans+(pow2[i-1]*tmp)%MOD)%MOD; ans=(ans+(pow2[i-1]*tmp)%MOD)%MOD; } printf("%lld\n",ans); } return 0; } |
J.Dome and Steles
题意：有n个同宽的长方体，可以调换长方体的顺序，使得能用一个尽量小的半球包含所有的长方体
问最小半径
二分答案，计算每个长方体可以放置的横坐标范围，排序贪心
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int SIZEN=100010; const double INF = 1e6; class Stele{ public: double a,b; double L2; void read(void){ scanf("%lf%lf",&a,&b); if(a>b) swap(a,b); L2=a*a+b*b/4.0; } }; bool operator < (const Stele &S,const Stele &T){ return S.L2<T.L2; } int N; Stele S[SIZEN]; bool check(double R){ double low=-R,high=R; for(int i=1;i<=N;i++){ double d = R*R-S[i].L2; if(d<=0) return false; d=sqrt(d); double l1 = max(low,-d); double r1 = min(high,d); if(-l1>=r1){ low = l1+1; if(fabs(low)>d||low>high) return false; } else{ high = r1-1; if(fabs(high)>d||high<low) return false; } } return true; } void work(void){ static int kase=0; int tot=0; double l=0,r=INF; while(tot++<110){ double mid = (l+r)/2; if(check(mid)) r=mid; else l=mid; } printf("Case #%d: %.10lf\n",++kase,l); } void read(void){ scanf("%d",&N); for(int i=1;i<=N;i++) S[i].read(); sort(S+1,S+1+N); } int main(void){ int T;scanf("%d",&T); while(T--){ read(); work(); } return 0; } |
L.Multiplication Table
题意：给一张无限大的表格
1 2 3 4 …
2 4 6 8 …
给定一个R*C的表格（可能有些非确定元素），问其是否可能是原表的一部分
拿一个确定的元素x，考虑它的所有约数d，x元素可能在原表的第d行第x/d列
根据其它元素与它的相对位置，check一下选定的d是否合适
由于每个元素只符合于一个d，所以复杂度是O(TRC)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #define ll long long using namespace std; int T,n,m,cnt; char ch[15]; struct data{ int x,y,v; }a[1000005]; bool check(int x,int y) { if(x<a[1].x||y<a[1].y)return 0; for(int i=1;i<=cnt;i++) { int tx=x+a[i].x-a[1].x,ty=y+a[i].y-a[1].y; if((ll)tx*ty!=a[i].v)return 0; } return 1; } int main() { scanf("%d",&T); for(int cas=1;cas<=T;cas++) { cnt=0; printf("Case #%d: ",cas); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%s",ch+1); int l=strlen(ch+1),tmp=0; if(ch[1]!='?') { for(int k=1;k<=l;k++) tmp=tmp*10+ch[k]-'0'; a[++cnt].x=i;a[cnt].y=j;a[cnt].v=tmp; } } if(!cnt){ puts("Yes"); continue; } bool flag=0; for(int i=1;i<=sqrt(a[1].v);i++) if(a[1].v%i==0) { if(check(i,a[1].v/i)){flag=1;break;} else if(check(a[1].v/i,i)){flag=1;break;} } if(flag)puts("Yes"); else puts("No"); } return 0; } |
M.November 11th
题意：有一个R*S的电影院，B个损坏的座椅
两个人不会并排坐在一起，问至多能坐下多少人？至少坐多少人以后不能再坐下更多的人？
连续n张座椅，至多可以坐(n+1)/2人，至少(n+2)/3人
每一行是独立的，依次处理即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int least_occupy(int n){ return (n+2)/3; } int most_seat(int n){ return (n+1)/2; } const int SIZEN=1010; int H,W; bool broken[SIZEN][SIZEN]; void work(void){ static int kase=0; int ans_seat=0,ans_occupy=0; for(int x=0;x<H;x++){ int j=0; while(j<W){ while(j<W&&broken[x][j]) j++; int j1=j; while(j1<W&&!broken[x][j1]) j1++; ans_seat += most_seat(j1-j); ans_occupy += least_occupy(j1-j); j=j1; } } printf("Case #%d: %d %d\n",++kase,ans_seat,ans_occupy); } void read(void){ scanf("%d%d",&H,&W);//rows,columns memset(broken,0,sizeof(broken)); int B,r,s;scanf("%d",&B); for(int i=0;i<B;i++){ scanf("%d%d",&r,&s); broken[r][s]=true; } } int main(void){ int T;scanf("%d",&T); while(T--){ read(); work(); } return 0; } |
计数器 9786207
OI 课件=>
OI 课件=>
分享是美德，谢谢博主的分享。