首页 > 代码库 > 2015 ACM/ICPC EC-Final
2015 ACM/ICPC EC-Final
A. Boxes and Balls
二分找到最大的不超过$n$的$\frac{x(x+1)}{2}$形式的数即可。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;void solve () { LL n ; scanf ( "%lld" , &n ) ; LL l = 1 , r = 2e9 ; while ( l < r ) { LL m = l + r + 1 >> 1 ; LL t = m * ( m + 1 ) / 2 ; if ( t <= n ) l = m ; else r = m - 1 ; } printf ( "%lld\n" , l * ( l + 1 ) / 2 ) ;}int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
B. Business Cycle
二分答案，然后暴力模拟，如果没有爆负，则说明进入了循环节，后面直接算，注意最后要预留若干轮暴力模拟。
#include <bits/stdc++.h>using namespace std ;typedef long long ll ;int n,i;ll G,P,l,r,mid,ans,a[1111111];bool check(ll have){ if(have>=G)return 1; ll ret=P; ll old=-1; while(ret){ ll st=have; bool flag=0; for(int i=0;i<n;i++){ have+=a[i]; if(have<0)flag=1,have=0; if(have>=G)return 1; ret--; if(!ret)return 0; } if(flag)continue; if(have<=st)return 0; old=have-st; break; } ll p=ret/n; p-=3; if(p<0)p=0; if(p>(G-have)/old)return 1; have+=p*old; ret-=p*n; if(have>=G)return 1; int i=0; while(ret--){ have=max(0LL,have+a[i]); i++; i%=n; if(have>=G)return 1; } return 0;}void solve(){ scanf("%d%lld%lld",&n,&G,&P); for(i=0;i<n;i++)scanf("%lld",&a[i]); l=0,r=G-1,ans=G; while(l<=r){ if(check(mid=(l+r)>>1))r=(ans=mid)-1;else l=mid+1; } printf("%lld\n",ans);}int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
C. Suffixes and Palindromes
根据Manacher算法可以得到$O(n)$对相等和不等关系，然后按照$sa$数组逐个构造。
首先$sa[1]$必然填$‘a‘$，然后对于$sa[i]$，首先通过$rank$数组判断它能否和$sa[i-1]$相等，如果它可以相等，但是因为不等关系矛盾，那么它只能大于$sa[i-1]$。
如此可以在$O(n)$时间内构造字典序最小的一组解，注意无解的处理。
#include <bits/stdc++.h>using namespace std ;typedef long long ll ;const int N=1000110;int n,m,i,j,r,p,f[N];char a[N],s[N];int len[N],e[N],fa[N],g[N],G[N],v[N],nxt[N],ed;int sa[N],rk[N],col[N];void NIE(){ puts("Wrong calculation!");}inline void addedge(int x,int y){ v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}inline void addedge2(int x,int y){ v[++ed]=y;nxt[ed]=G[x];G[x]=ed;}int F(int x){return fa[x]==x?x:fa[x]=F(fa[x]);}inline bool makesame(int x,int y){ if(x<0||y>m)return 0; if(x==y)return 1; if(x==0||y==m)return 0; if(x%2!=y%2)return 0; if(x%2==1)return 1; x>>=1; y>>=1; if(F(x)!=F(y))fa[fa[x]]=fa[y]; //printf("same %d %d\n",x,y); return 1;}inline bool makediff(int x,int y){ if(x==y)return 0; if(x<0||y>m)return 1; if(x==0||y==m)return 1; if(x%2!=y%2)return 1; if(x%2==1)return 0; x>>=1; y>>=1; addedge(x,y); addedge(y,x); //printf("diff %d %d\n",x,y); return 1;}inline bool bigger(int x,int y){//suffix[x] > suffix[y]? if(x>n)return 0; if(y>n)return 1; return rk[x]>rk[y];}void solve(){ scanf("%d",&n); //scanf("%s",a+1); //for(i=1;i<=n;i++)s[i<<1]=a[i],s[i<<1|1]=‘#‘; s[0]=‘$‘; s[1]=‘#‘; s[m=(n+1)<<1]=‘@‘; /*for(r=p=0,f[1]=1,i=2;i<m;i++){ for(f[i]=r>i?min(r-i,f[p*2-i]):1;s[i-f[i]]==s[i+f[i]];f[i]++); if(i+f[i]>r)r=i+f[i],p=i; } for(i=1;i<=m;i++)putchar(s[i]);puts(""); for(i=1;i<=m;i++)printf("%d",f[i]);puts(""); */ for(i=1;i<=n;i++)scanf("%d",&sa[i]),sa[i]++; for(i=1;i<=n*2-1;i++){ scanf("%d",&len[i]); } for(i=1;i<=n*2-1;i++){ if(i&1){ if(len[i]%2==0){ NIE(); return; } }else{ if(len[i]%2){ NIE(); return; } } e[i+1]=len[i]+1; } e[1]=1; e[m-1]=e[m]=1; for(i=1;i<=n;i++)fa[i]=i; for(ed=0,i=1;i<=n;i++)g[i]=G[i]=0; for(r=p=0,f[1]=1,i=2;i<m;i++){ for(f[i]=r>i?min(r-i,f[p*2-i]):1;f[i]<e[i];f[i]++){ int x=i-f[i],y=i+f[i]; if(!makesame(x,y)){ NIE(); return; } } if(f[i]!=e[i]){ NIE(); return; } int x=i-f[i],y=i+f[i]; if(!makediff(x,y)){ NIE(); return; } if(i+f[i]>r)r=i+f[i],p=i; } for(i=1;i<=n;i++)F(i); for(i=1;i<=n;i++)for(j=g[i];j;j=nxt[j]){ if(fa[i]==fa[v[j]]){ NIE(); return; } addedge2(fa[i],fa[v[j]]); } for(i=1;i<=n;i++)rk[sa[i]]=i; for(i=1;i<=n;i++)col[i]=0; col[fa[sa[1]]]=1; for(i=2;i<=n;i++){ int x=sa[i]; bool cansame=1; if(bigger(sa[i-1]+1,x+1))cansame=0; //printf("%d %d\n",i,cansame); int pre=col[fa[sa[i-1]]]; if(col[fa[x]]){ if(cansame){ if(col[fa[x]]<pre){ NIE(); return; } }else{ if(col[fa[x]]<=pre){ NIE(); return; } } continue; } for(j=G[fa[x]];j;j=nxt[j])if(col[v[j]]==pre)cansame=0; if(!cansame)pre++; if(pre>26){ NIE(); return; } col[fa[x]]=pre; } for(i=1;i<=n;i++)putchar(‘a‘+col[fa[i]]-1); puts("");}int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
D. Change
分类讨论即可。
#include <bits/stdc++.h>using namespace std ;void solve () { double x , y ; scanf ( "%lf%lf" , &x , &y ) ; int a = x * 100 + 0.5 ; int b = y * 100 + 0.5 ; if ( b == 1 || b == 10 || b == 100 || b == 1000 || b == 10000 ) { if ( a == 2 * b ) printf ( "0.01\n" ) ; else printf ( "0.02\n" ) ; } else printf ( "0.01\n" ) ;}int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
E. Colorful Floor
留坑。
F. Hungry Game of Ants
DP出每只蚂蚁往左往右吃完的方案数，用前缀和优化即可。时间复杂度$O(n)$。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;const int MAXN = 1000005 ;const int mod = 1e9 + 7 ;LL dp[MAXN] , f[MAXN] , sum[MAXN] ;int n , k ;void up ( LL& x , LL y ) { x += y ; if ( x >= mod ) x -= mod ;}void solve () { scanf ( "%d%d" , &n , &k ) ; if ( k == 1 ) { printf ( "0\n" ) ; return ; } for ( int i = 0 ; i <= n ; ++ i ) { dp[i] = f[i] = 0 ; if ( i ) sum[i] = sum[i - 1] + i ; } LL ans = 2 , p = 1 ; for ( int i = 2 ; i < k ; ++ i ) { up ( p , p ) ; if ( sum[i] < sum[k] - sum[i] ) up ( ans , p ) ; } if ( k == n ) { printf ( "%lld\n" , ans * 2 % mod ) ; return ; } dp[k] = f[k] = ans ; for ( int i = 1 , j = 1 ; i <= n ; ++ i ) { while ( sum[i] > 2 * sum[j] ) ++ j ; up ( dp[i] , ( f[i - 1] - f[j - 1] + mod ) % mod ) ; up ( f[i] , ( f[i - 1] + dp[i] ) % mod ) ; } printf ( "%lld\n" , dp[n] ) ;}int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
G. Legacy of the Void
留坑。
H. Open Face Chinese Poker
留坑。
I. Champions League
留坑。
J. Dome and Steles
二分答案，然后解出每个砖块能放的范围，按范围从大到小放，每次贪心放大的那一侧即可。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;const int Maxn = 100005 ;const double eps=1e-10;double a[Maxn],ned[Maxn];int n;double sqr(double x){return x*x;}int dcmp(double x){if(fabs(x)<eps)return 0;if(x>eps)return 1;return -1;}bool check(double md){ for(int i=0;i<n;i++){ if(dcmp(md*md-a[i])<=0)return 0; } //for(int i=0;i<n;i++)printf("%.3f ",ned[i]);puts(""); double l=md,r=md; for(int i=0;i<n;i++){ if(l<r)swap(l,r); l=min(l,sqrt(md*md-a[i])); if(dcmp(l-1)>=0){l-=1;continue;} else{ if(dcmp(l+r-1)<0)return 0; if((1-l)*(1-l)+a[i]>md*md)return 0; if(i!=(n-1))return 0; } } return 1;}void solve () { scanf("%d",&n); for(int i=0;i<n;i++){ double x,y; scanf("%lf%lf",&x,&y); a[i]=min(sqr(x)+sqr(y/2),sqr(y)+sqr(x/2)); } sort(a,a+n); double l=0,r=1e6; for(int i=0;i<200;i++){ double md=(l+r)/2; if(check(md))r=md; else l=md; } printf("%.12f\n",r); }int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
K. Convex Polyhedron
求出三维凸包之后，假如知道了投影方向向量，那么根据叉积的正负号贪心把所有正的法向量加起来即可。于是随机枚举10000个方向向量即可。
#include <bits/stdc++.h>using namespace std ;#define PR 1e-8 #define N 620struct TPoint { double x , y , z ; TPoint () {} TPoint ( double x , double y , double z ) : x ( x ) , y ( y ) , z ( z ) {} TPoint operator+(const TPoint p){return TPoint(x+p.x,y+p.y,z+p.z);} TPoint operator-(const TPoint p){return TPoint(x-p.x,y-p.y,z-p.z);} TPoint operator*(const TPoint p){ return TPoint(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x); } TPoint operator*(double p){return TPoint(x*p,y*p,z*p);} TPoint operator/(double p){return TPoint(x/p,y/p,z/p);} double operator^(const TPoint p){return x * p.x + y * p.y + z * p.z ;} void show (){ printf ( "%.2f %.2f %.2f\n" , x , y , z ) ; }}center;struct fac{ int a , b , c ; bool ok ;} ;struct T3dhull{ int n ; TPoint ply[N]; int trianglecnt; fac tri[N] ; int vis[N][N]; double dist(TPoint a ) { return sqrt ( a.x * a.x + a.y * a.y + a.z * a.z ) ; } double area( TPoint a , TPoint b , TPoint c ) { return dist ( ( b - a ) * ( c - a ) ) ; } TPoint fa(TPoint a,TPoint b,TPoint c){ return (b-a)*(c-a); } double volume ( TPoint a , TPoint b , TPoint c , TPoint d ) { return ( b - a ) * ( c - a ) ^ ( d - a ) ; } double ptoplane ( TPoint &p , fac& f ) { TPoint m = ply[f.b]-ply[f.a],n=ply[f.c]-ply[f.a],t=p-ply[f.a]; return (m*n)^t; } void deal(int p,int a,int b ){ int f = vis[a][b]; fac add; if(tri[f].ok){ if((ptoplane(ply[p],tri[f]))>PR)dfs(p,f);else{ add.a=b,add.b=a,add.c=p,add.ok=1; vis[p][b]=vis[a][p]=vis[b][a]=trianglecnt; tri[trianglecnt++]=add; } } } void dfs(int p,int cnt ) { tri[cnt].ok = 0 ; deal(p,tri[cnt].b,tri[cnt].a); deal(p,tri[cnt].c,tri[cnt].b); deal(p,tri[cnt].a,tri[cnt].c); } bool same ( int s , int e ) { TPoint a = ply[tri[s].a],b=ply[tri[s].b],c=ply[tri[s].c]; return fabs ( volume(a , b , c , ply[tri[e].a] ) ) < PR && fabs( volume(a , b , c , ply[tri[e].b]))<PR && fabs( volume(a , b ,c , ply[tri[e].c]))<PR; } void construct(){ int i,j; trianglecnt=0; if ( n < 4 ) return ; bool tmp = 1 ; for ( i = 1 ; i < n ; ++ i ) { if ( ( dist(ply[0]-ply[i]))>PR){ swap ( ply[1],ply[i]); tmp=0; break ; } } if ( tmp ) return ; tmp = 1 ; for ( i = 2 ; i < n ; ++ i ) { if ( ( dist((ply[0]-ply[1])*(ply[1]-ply[i])))>PR){ swap ( ply[2],ply[i]); tmp=0; break; } } if(tmp)return; tmp=1; for(i=3;i<n;++i){ if(fabs((ply[0]-ply[1])*(ply[1]-ply[2])^(ply[0]-ply[i]))>PR){ swap(ply[3],ply[i]); tmp=0; break; } } if(tmp)return; tmp=1; fac add; for(i=0;i<4;++i){ add.a=(i+1)%4,add.b=(i+2)%4,add.c=(i+3)%4,add.ok=1; if((ptoplane(ply[i],add))>0)swap(add.b,add.c); vis[add.a][add.b]=vis[add.b][add.c]=vis[add.c][add.a]=trianglecnt; tri[trianglecnt++]=add; } for(i=4;i<n;++i){ for(j=0;j<trianglecnt;++j){ if(tri[j].ok&&(ptoplane(ply[i],tri[j]))>PR){ dfs(i,j); break; } } } int cnt = trianglecnt; trianglecnt=0; for(i=0;i<cnt;++i){ if(tri[i].ok){ tri[trianglecnt++]=tri[i]; } } } void show(){ for ( int i = 0 ; i < trianglecnt;++i){ printf ( "------%d------\n" , i ) ; ply[tri[i].a].show () ; ply[tri[i].b].show () ; ply[tri[i].c].show () ; } } double check(TPoint mydi){ TPoint ret=TPoint(.0,.0,.0); for(int i=0;i<trianglecnt;i++){ TPoint cur=fa(ply[tri[i].a],ply[tri[i].b],ply[tri[i].c]); if((mydi^cur)>=0)ret=ret+cur; } return dist(ret); } int getrand(){ int ret=rand()%200; if(rand()%2)ret=-ret; return ret; } void solve(){ double ans=0; for(int i=0;i<10000;i++){ TPoint mydi; mydi.x=getrand(); mydi.y=getrand(); mydi.z=getrand(); ans=max(ans,check(mydi)); } printf("%.12f\n",ans/2); }} a;void solve () { scanf ( "%d",&a.n); for ( int i = 0 ; i < a.n ; ++ i ) { scanf ( "%lf%lf%lf" , &a.ply[i].x,&a.ply[i].y,&a.ply[i].z); } a.construct(); //a.show(); a.solve();}int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
L. Multiplication Table
枚举约数然后检验。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;int n,m;int a[1020][1020];struct Node{ int x,y,z; Node(){} Node(int x,int y,int z):x(x),y(y),z(z){}}nd[1000020];int cnt;int csx,csy;bool check(int ox,int oy,int rx,int ry){ if(rx-(ox-1)<1)return 0; if(ry-(oy-1)<1)return 0; for(int i=0;i<cnt;i++){ int x=nd[i].x,y=nd[i].y,z=nd[i].z; if(1LL*(rx+(x-ox))*(ry+(y-oy))!=z)return 0; } return 1;}void solve () { scanf("%d%d",&n,&m); cnt=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ char s[20]; scanf("%s",s); if(s[0]==‘?‘)continue; int x=0; for(int k=0;s[k];k++){ x=x*10+s[k]-‘0‘; } nd[cnt++]=Node(i,j,x); } } if(!cnt){puts("Yes");return;} bool flag=0; int num=nd[0].z; csx=nd[0].x,csy=nd[0].y; for(int i=1;i<cnt;i++){ if(num>nd[i].z){ num=nd[i].z; csx=nd[i].x; csy=nd[i].y; } } for(int i=1;i<=num/i&&!flag;i++){ if(num%i==0){ if(check(csx,csy,i,num/i)){flag=1;break;} if(i*i!=num&&check(csx,csy,num/i,i)){flag=1;break;} } } puts(flag?"Yes":"No");}int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
M. November 11th
对于长度为$n$的长条，对最小值的贡献为$\lfloor\frac{n+1}{2}\rfloor$，对最大值的贡献为$\lfloor\frac{n+2}{3}\rfloor$。
#include <bits/stdc++.h>using namespace std ;typedef long long LL ;int n,m,i,j,k,x,y,f[1111][1111],ans0,ans1;inline int F(int n){ return (n+1)/2;}inline int G(int n){ if(n==1)return 1; return (n+2)/3;}void solve () { scanf("%d%d",&n,&m); for(i=1;i<=n;i++)for(j=1;j<=m;j++)f[i][j]=1; scanf("%d",&k); while(k--)scanf("%d%d",&x,&y),f[x+1][y+1]=0; ans0=ans1=0; for(i=1;i<=n;i++){ j=1; for(;j<=m;){ if(!f[i][j]){j++;continue;} for(k=j;k<=m&&f[i][k];k++); ans0+=F(k-j); ans1+=G(k-j); j=k; } } printf("%d %d\n",ans0,ans1);}int main () { int T ; scanf ( "%d" , &T ) ; for ( int i = 1 ; i <= T ; ++ i ) { printf ( "Case #%d: " , i ) ; solve () ; } return 0 ;}
总结：
- B题忘记考虑预留的情况，导致WA5发。
- C题对无解的判断不足以及数组开少一半，导致WA。
- M题没有想清楚，导致WA。
2015 ACM/ICPC EC-Final
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。