[关闭]
@Scarlet 2017-01-23T04:44:53.000000Z 字数 10941 阅读 591

POI 2005

POI 2005 OI 解题报告


Cash Dispenser (Stage I)

题意:求长度为的若干序列的公共子序列个数。
听说是搜索好题QAQ


Points (Stage I)


Toy Cars (Stage I)

题意:不会概括

记录下每个玩具下次出现的位置,每次要删的话选一个最远的删掉
用堆维护这一过程

From hzwer

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 500010
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. #define pa pair<int,int>
  10. #define mp make_pair
  11. inline int read()
  12. {
  13. int x=0,f=1;char G;
  14. while(c>57||c<48){if(c=='-')f=-1;G;}
  15. while(c>47&&c<58)x=x*10+c-48,G;
  16. return x*f;
  17. }
  18. int n,K,p,ans,a[maxn],nxt[maxn],last[maxn];
  19. bool m[maxn];
  20. priority_queue<pa,vector<pa> >q;
  21. int main()
  22. {
  23. n=read();K=read(),p=read();
  24. for(int i=1;i<=n;i++)last[i]=p+1;
  25. for(int i=1;i<=p;i++)a[i]=read();
  26. for(int i=p;i;i--)nxt[i]=last[a[i]],last[a[i]]=i;
  27. for(int i=1;i<=p;i++)
  28. {
  29. if(m[a[i]]){q.push(mp(nxt[i],a[i]));continue;}
  30. if(K)
  31. {
  32. ans++;q.push(mp(nxt[i],a[i]));
  33. m[a[i]]=1;
  34. K--;
  35. }
  36. else
  37. {
  38. while(m[q.top().second]==0)q.pop();
  39. m[q.top().second]=0;
  40. q.pop();
  41. ans++;q.push(mp(nxt[i],a[i]));
  42. m[a[i]]=1;
  43. }
  44. }
  45. printf("%d",ans);
  46. return 0;
  47. }

Piggy Banks (Stage I)

题意:求联通块个数

并查集后数

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<cstdio>
  5. #define N 1000005
  6. using namespace std;
  7. inline int read()
  8. {
  9. int x=0;char ch=getchar();
  10. while(ch<'0'||ch>'9'){if(ch=='-')ch=getchar();}
  11. while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  12. return x;
  13. }
  14. int n,ans,fa[N],x,p,q;
  15. int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
  16. int main()
  17. {
  18. n=read();
  19. for(int i=1;i<=n;i++)fa[i]=i;
  20. for(int i=1;i<=n;i++)
  21. {
  22. x=read(),p=find(i),q=find(x);
  23. if(p!=q)fa[q]=i;
  24. }
  25. for(int i=1;i<=n;i++)if(fa[i]==i)ans++;
  26. printf("%d",ans);
  27. return 0;
  28. }

Knights (Stage I)


A Journey to Mars (Stage II - day 0)

题意:环形轨道,车有一定的油,相邻城市有距离,每个城市能续命,问从多少个城市出发可以环绕所有城市

问题转化后就是环上每个点切开来后问最小子段和,单调队列可以直接艹。
代码不是我写的所以不是很懂细节。

  1. #include<bits/stdc++.h>
  2. #define maxn 2000100
  3. using namespace std;
  4. typedef long long LL;
  5. #define G c=getchar()
  6. inline LL read()
  7. {
  8. LL x=0,f=1;char G;
  9. while(c>57||c<48){if(c=='-')f=-1;G;}
  10. while(c>47&&c<58)x=x*10+c-48,G;
  11. return x*f;
  12. }
  13. struct rec{int x,y;}a[maxn];
  14. int b[maxn],sta[maxn],r[maxn],res,n;
  15. bool can[2][maxn];
  16. void work(int k)
  17. {
  18. b[0]=0;
  19. for(int i=1;i<=n;i++)b[i]=b[i-1]+a[i].x-a[i].y;
  20. for(int i=1;i<=n;i++)b[n+i]=b[n+i-1]+a[i].x-a[i].y;
  21. int top=0;b[2*n+1]=-1000000000;
  22. for(int i=0;i<=(n<<1)+1;i++)
  23. {
  24. while(top&&b[i]<b[sta[top]])r[sta[top--]]=i-1;
  25. sta[++top]=i;
  26. }
  27. for(int i=0;i<=n-1;i++)if(r[i]-i+1>=n)can[k][i+1]=1;
  28. }
  29. int main()
  30. {
  31. n=read();
  32. for(int i=1;i<=n;i++)
  33. a[i].x=read(),a[i].y=read(),res+=a[i].x-a[i].y;
  34. if(res<0)
  35. {
  36. for(int i=1;i<=n;i++)printf("NIE\n");
  37. return 0;
  38. }
  39. work(0);
  40. for(int i=1;i<=n>>1;i++)
  41. swap(a[i],a[n+1-i]);
  42. int t=a[1].y;
  43. for(int i=1;i<=n-1;i++)
  44. a[i].y=a[i+1].y;
  45. a[n].y=t;
  46. work(1);
  47. for(int i=1;i<=n;i++)
  48. if(can[0][i]||can[1][n+1-i])printf("TAK\n");
  49. else printf("NIE\n");
  50. return 0;
  51. }

Bank Notes (Stage II - day 1)

题意:种硬币凑成的最少硬币数

傻逼背包,倍增优化。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define M 20200
  6. using namespace std;
  7. #define G c=getchar()
  8. inline int read()
  9. {
  10. int x=0,f=1;char G;
  11. while(c>57||c<48){if(c=='-')f=-1;G;}
  12. while(c>47&&c<58)x=x*10+c-48,G;
  13. return x*f;
  14. }
  15. int n,k,b[220],c[220],f[M];
  16. int main()
  17. {
  18. n=read();
  19. for(int i=1;i<=n;i++)b[i]=read();
  20. for(int i=1;i<=n;i++)c[i]=read();
  21. k=read();
  22. memset(f,0x3f,sizeof f);
  23. f[0]=0;
  24. for(int i=1,j;i<=n;i++)
  25. {
  26. for(j=1;j<=c[i];j<<=1)
  27. {
  28. for(int k=::k;k>=b[i]*j;k--)
  29. f[k]=min(f[k],f[k-b[i]*j]+j);
  30. c[i]-=j;
  31. }
  32. if(!c[i]) continue;
  33. j=c[i];
  34. for(int k=::k;k>=b[i]*j;k--)
  35. f[k]=min(f[k],f[k-b[i]*j]+j);
  36. }
  37. printf("%d",f[k]);
  38. return 0;
  39. }

Fibonacci Sums (Stage II - day 1)

题意:求两个斐波那契进制数之和

两个性质:

1.对于f[i]>=2的情况:
可以根据2*f[i]==f[i]+f[i-1]+f[i-2]=f[i+1]+f[i-2]
转化为f[i-2]++,f[i+1]++.

2.对于f[i]=1&&f[i+1]=1的情况:
根据f[i+2]=f[i]+f[i+1]转化为给f[i+2]++

之后玄学调整

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 1000100
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. inline int read()
  10. {
  11. int x=0,f=1;char G;
  12. while(c>57||c<48){if(c=='-')f=-1;G;}
  13. while(c>47&&c<58)x=x*10+c-48,G;
  14. return x*f;
  15. }
  16. int a[maxn],b[maxn],c[maxn];
  17. void Up(int k)
  18. {
  19. while(c[k])
  20. {
  21. c[k]=c[k-1]=0;
  22. c[k+1]++;
  23. k+=2;
  24. }
  25. }
  26. void trans(int i)
  27. {
  28. if(c[i]<2)return;
  29. int k=i-2;
  30. if(i==2)k++;
  31. if(i>1)c[k]++;
  32. c[i+1]++;
  33. c[i]-=2;
  34. }
  35. int main()
  36. {
  37. int n=read();for(int i=1;i<=n;i++)a[i]=read();
  38. int m=read();for(int j=1;j<=m;j++)b[j]=read();
  39. int len=max(m,n);
  40. for(int i=len;i>=1;i--)
  41. {
  42. c[i]+=a[i]+b[i];
  43. if(c[i]>=2)
  44. {
  45. trans(i);
  46. trans(i+1);
  47. if(i==1)trans(1);
  48. }
  49. if(c[i])Up(i+1);
  50. if(c[i+1])Up(i+2);
  51. if(c[i+2])Up(i+3);
  52. }
  53. while(c[len+1])len++;
  54. if(c[len+2])len+=2;
  55. while(c[len+1])len++;
  56. printf("%d ",len);
  57. for(int i=1;i<=len;i++)
  58. printf("%d ",c[i]);
  59. return 0;
  60. }

Dicing (Stage II - day 2)

题意:个选手,举行场比赛后,赢的最多的那个选手最少会赢多少场

十分明显的最大流模型:二分答案,源点向每场比赛连INF的边。每场比赛连向两个选手,容量为,表示每场只有一个人赢。每个选手连向汇点容量为的边,表示最多赢场。当流量为时答案可行。

实测ISAP的时间是dinic的4倍。不是很懂波兰人的出数据技巧。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 20010
  6. #define maxm 100010
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. #define AE(u,v,w) E[Si]=(Ed){v,w},nxt[Si]=idx[u],idx[u]=Si++
  18. #define Add(u,v,w) AE(u,v,w),AE(v,u,0)
  19. #define INF 1000000000
  20. struct Ed{int v,w;}E[maxm];
  21. int idx[maxn],nxt[maxm],Si,S,T,h[maxn],q[maxn],n,m,ans;
  22. bool bfs()
  23. {
  24. memset(h,-1,sizeof(h));q[0]=h[0]=0;
  25. for(int l=0,r=1;l<r;)
  26. for(int u=q[l++],i=idx[u];i+1;i=nxt[i])
  27. if(E[i].w&&h[E[i].v]==-1)h[E[i].v]=h[u]+1,q[r++]=E[i].v;
  28. return h[T]+1;
  29. }
  30. int dfs(int x,int f)
  31. {
  32. if(x==T)return f;
  33. int ret=0,w;
  34. for(int i=idx[x];i+1;i=nxt[i])
  35. if(E[i].w&&h[E[i].v]==h[x]+1)
  36. {
  37. w=dfs(E[i].v,min(f-ret,E[i].w));
  38. E[i].w-=w;E[i^1].w+=w;
  39. if((ret+=w)==f)return f;
  40. }
  41. if(!ret)h[x]=-1;
  42. return ret;
  43. }
  44. int dinic(){for(ans=0;bfs();)ans+=dfs(S,INF);return ans;}
  45. int e[maxn][2];
  46. void build(int x)
  47. {
  48. memset(idx,-1,sizeof(idx)),Si=0;
  49. for(int i=1;i<=n;i++)
  50. Add(S,i,x);
  51. for(int i=1;i<=m;i++)
  52. Add(n+i,T,1),Add(e[i][0],n+i,1),Add(e[i][1],n+i,1);
  53. }
  54. int main()
  55. {
  56. n=read(),m=read();//这行前面写了int调了1h你敢信。
  57. S=0,T=n+m+1;
  58. for(int i=1;i<=m;i++)
  59. e[i][0]=read(),e[i][1]=read();
  60. int l=1,r=m,ans,mid;
  61. for(;l<=r;)
  62. mid=l+r>>1,build(mid),dinic()==m?r=mid-1,ans=mid:l=mid+1;
  63. printf("%d",ans);
  64. return 0;
  65. }

Template (Stage II - day 2)

题意:见题目及样例

简单来说,先用扩展KMP求出每个后缀和原串的最长公共前缀,记为F[i].
然后转化问题:求最小的K,使相邻两个F值大于K的点距离不超过K。

然后用链表简单地XJB维护一下就好了。

一开始写了个sort,讲道理复杂度是的,而且sort常数挺小,但是为什么会跑得这么慢呢?

后来我发现计数排序就可以了,我好菜啊。
观察了一下发现还是没上榜,原来跑得快的都是二分答案怼过去的。
上不了榜了so sad

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 1000010
  6. using namespace std;
  7. int n,k,p,F[maxn];
  8. char s[maxn],ch;
  9. void KMP(int n,char *a)
  10. {
  11. int j=0,k=1;
  12. for(;1+j<n&&a[j]==a[1+j];j++);
  13. F[1]=j;
  14. for(int i=2,Len,L;i<n;i++)
  15. {
  16. Len=k+F[k],L=F[i-k];
  17. if(L<Len-i)F[i]=L;
  18. else
  19. {
  20. for(j=max(0,Len-i);i+j<n&&a[j]==a[i+j];j++);
  21. F[k=i]=j;
  22. }
  23. }
  24. }
  25. int NXT[maxn],PRE[maxn];
  26. #define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  27. int idx[maxn],nxt[maxn],to[maxn],Si=1;
  28. int main()
  29. {
  30. scanf("%s",s);
  31. n=strlen(s);
  32. KMP(n,s);
  33. for(int i=0;i<=n;i++)
  34. NXT[i]=i+1,PRE[i]=i-1;
  35. F[0]=n;
  36. F[n]=n+1;
  37. for(int i=0;i<=n;i++)
  38. AE(F[i],i);
  39. int K=1,mx=1;
  40. for(;K<=n;K++)
  41. {
  42. for(int i=idx[K-1],L,R;i;i=nxt[i])
  43. L=PRE[to[i]],R=NXT[to[i]],NXT[L]=R,PRE[R]=L,mx=max(mx,R-L);
  44. if(mx<=K)break;
  45. }
  46. printf("%d\n",K);
  47. }

Hollows (Stage III - day 0)


Special Forces Manoeuvres (Stage III - day 1)

题意:每次插入一个圆,判断集合内所有圆之交是否为空,是则退出,否则继续

找到了一个挺神的做法:
考虑一个圆交,它的形状十分奇怪,但是一定是一个凸包。所以我们可以考虑维护这个圆交横坐标最大的点。显然这个点要么是某两个圆的交点,要么是某个圆圆心右边的点,就很好维护了,最后检查这个维护的这个点能否被圆集内的圆全都覆盖。

复杂度是常数较小的。在BZOJ随便交了一发Rank2,Rank1是陈老师比我高到不知道哪里去了。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 2010
  6. #define S(J) ((J)*(J))
  7. using namespace std;
  8. typedef long long LL;
  9. typedef double DB;
  10. #define G c=getchar()
  11. inline int read()
  12. {
  13. int x=0,f=1;char G;
  14. while(c>57||c<48){if(c=='-')f=-1;G;}
  15. while(c>47&&c<58)x=x*10+c-48,G;
  16. return x*f;
  17. }
  18. DB x[maxn],y[maxn],r[maxn];
  19. bool InC(DB X,DB Y,int w){return S(X-x[w])+S(Y-y[w])<=S(r[w])+0.00001;}
  20. void mx(DB&X,DB&Y,DB x,DB y){if(x>X)X=x,Y=y;}
  21. void mn(DB&X,DB&Y,DB x,DB y){if(x<X)X=x,Y=y;}
  22. void c2point(DB x1,DB y1,DB r1,DB x2,DB y2,DB r2,DB &rx1,DB &ry1,DB &rx2,DB &ry2)
  23. {
  24. DB a,b,r;
  25. a=x2-x1;
  26. b=y2-y1;
  27. r=(a*a+b*b+r1*r1-r2*r2)/2;
  28. if(a==0&&b!=0)
  29. {
  30. ry1=ry2=r/b;
  31. rx1=sqrt(r1*r1-ry1*ry1);
  32. rx2=-rx1;
  33. }
  34. else if(a!=0&&b==0)
  35. {
  36. rx1=rx2=r/a;
  37. ry1=sqrt(r1*r1-rx1*rx2);
  38. ry2=-ry1;
  39. }
  40. else if(a!=0&&b!=0)
  41. {
  42. DB delta;
  43. delta=b*b*r*r-(a*a+b*b)*(r*r-r1*r1*a*a);
  44. ry1=(b*r+sqrt(delta))/(a*a+b*b);
  45. ry2=(b*r-sqrt(delta))/(a*a+b*b);
  46. rx1=(r-b*ry1)/a;
  47. rx2=(r-b*ry2)/a;
  48. }
  49. rx1+=x1;
  50. ry1+=y1;
  51. rx2+=x1;
  52. ry2+=y1;
  53. }
  54. int main()
  55. {
  56. int n=read(),ans;
  57. for(int i=1;i<=n;i++)
  58. x[i]=read(),y[i]=read(),r[i]=read();
  59. DB MX=x[1]+r[1],MY=y[1];
  60. int f=0;
  61. for(int i=2;i<=n;i++)
  62. {
  63. if(InC(MX,MY,i))continue;
  64. for(int j=1;j<i;j++)
  65. {
  66. DB NX=-100000000,NY=-10000000,sx,sy,tx,ty;sx=sy=tx=ty=0;
  67. if(S(x[i]-x[j])+S(y[i]-y[j])>S(r[i]+r[j])){MX=NX,MY=NY;break;}//相离
  68. if(InC(x[j]+r[j],y[j],i))mx(NX,NY,x[j]+r[j],y[j]);
  69. if(InC(x[i]+r[i],y[i],j))mx(NX,NY,x[i]+r[i],y[i]);
  70. if(S(x[i]-x[j])+S(y[i]-y[j])>S(r[i]-r[j]))//相交
  71. {
  72. c2point(x[i],y[i],r[i],x[j],y[j],r[j],sx,sy,tx,ty);
  73. mx(NX,NY,sx,sy);
  74. mx(NX,NY,tx,ty);
  75. }
  76. if(MX>NX)MX=NX,MY=NY;
  77. }
  78. for(int j=1;j<=i;j++)
  79. if(!InC(MX,MY,j)){f=1;break;}
  80. if(f){ans=i;break;}
  81. }
  82. if(!f)puts("NIE");
  83. else printf("%d",ans);
  84. return 0;
  85. }

Two Parties (Stage III - day 1)


Double-row (Stage III - day 1)

题意:个数站成两排(每个数最多出现两遍),一个操作可以交换一列中两个数,求使每行数不重复的最少操作数。

据说把每列看成一个点,把有相同数的点连边,那么会得到一个坨环+链。通过一些巧妙的思考,发现一个联通块中只有两个稳定状态。然后就每个联通块中枚举某处交不交换,dfs然后取min。

鈤狗了,在main上爆了5波OJ,两发没删注释,一发忘关文件,还小开数组WA了一发。
复健后总算自己写了一题w。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 50010
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. inline int read()
  10. {
  11. int x=0,f=1;char G;
  12. while(c>57||c<48){if(c=='-')f=-1;G;}
  13. while(c>47&&c<58)x=x*10+c-48,G;
  14. return x*f;
  15. }
  16. int vis[maxn<<1],st,num,cnt,sum,n,ans,t;
  17. int a[2][maxn],to[2][maxn],gg[maxn<<1];
  18. void dfs(int x)
  19. {
  20. if(vis[x])return;
  21. sum++;vis[x]=1;
  22. if(a[st][x]==num)cnt++,num=a[!st][x],dfs(to[!st][x]);
  23. else num=a[st][x],dfs(to[st][x]);
  24. }
  25. int main()
  26. {
  27. n=read();
  28. memset(vis,-1,sizeof(vis));
  29. int tot=0;
  30. for(int i=0;i<2;i++)for(int j=1;j<=n;j++)a[i][j]=read(),gg[tot++]=a[i][j];
  31. sort(gg,gg+tot);
  32. tot=unique(gg,gg+tot)-gg;
  33. for(int i=0;i<2;i++)
  34. for(int j=1;j<=n;j++)
  35. {
  36. a[i][j]=lower_bound(gg,gg+tot,a[i][j])-gg+1;
  37. if(vis[a[i][j]]==-1)vis[a[i][j]]=n*i+j-1;
  38. else to[i][j]=vis[a[i][j]]%n+1,to[vis[a[i][j]]/n][vis[a[i][j]]%n+1]=j;
  39. }
  40. memset(vis,0,sizeof(vis));
  41. vis[0]=1;
  42. for(int i=1;i<=n;i++)
  43. if(!vis[i])
  44. {
  45. cnt=sum=0;
  46. num=a[st=0][i];dfs(to[st][i]);
  47. num=a[st=1][i];dfs(to[st][i]);
  48. if(!vis[i])vis[i]=1,sum++;ans+=min(cnt,sum-cnt);
  49. }
  50. printf("%d",ans);
  51. return 0;
  52. }

The Bus (Stage III - day 2)

题意:边长方格内的走一次的方格取数

离散化后按排序扫描,用树状数组加速dp,闭着眼睛过。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100010
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. inline int read()
  10. {
  11. int x=0,f=1;char G;
  12. while(c>57||c<48){if(c=='-')f=-1;G;}
  13. while(c>47&&c<58)x=x*10+c-48,G;
  14. return x*f;
  15. }
  16. struct poi{int x,y,s;}q[maxn];
  17. inline bool cmp(const poi &a,const poi &b){return a.x==b.x?a.y<b.y:a.x<b.x;}
  18. int c[maxn],xg[maxn],yg[maxn],xc,yc;
  19. void add(int x,int v)
  20. {
  21. for(;x<maxn;x+=x&-x)c[x]=max(c[x],v);
  22. }
  23. int ask(int x)
  24. {
  25. int ret=0;
  26. for(;x;x-=x&-x)ret=max(ret,c[x]);
  27. return ret;
  28. }
  29. int main()
  30. {
  31. freopen("w.in","r",stdin);
  32. int n=read(),m=read(),k=read();
  33. for(int i=0;i<k;i++)
  34. xg[i]=read(),yg[i]=read(),q[i]=(poi){xg[i],yg[i],read()};
  35. sort(xg,xg+k);xc=unique(xg,xg+k)-xg;
  36. sort(yg,yg+k);yc=unique(yg,yg+k)-yg;
  37. for(int i=0;i<k;i++)
  38. q[i].x=lower_bound(xg,xg+xc,q[i].x)-xg+1,
  39. q[i].y=lower_bound(yg,yg+yc,q[i].y)-yg+1;
  40. sort(q,q+k,cmp);
  41. for(int i=0;i<k;i++)
  42. {
  43. int w=ask(q[i].y)+q[i].s;
  44. add(q[i].y,w);
  45. }
  46. printf("%d\n",ask(maxn-1));
  47. return 0;
  48. }

Mirror Trap (Stage III - day 2)


Dextrogyrate Camel (Stage III - day 2)


Next:POI 2006

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注