[关闭]
@Scarlet 2017-01-12T12:07:21.000000Z 字数 6719 阅读 540

POI 2006

POI 2006 OI 解题报告


The Disks (Stage I)

题意:查询数组中最前面的小于的数的位置,要求答案递减(详见题面)

维护前缀min,单调扫一遍。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 300010
  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];
  17. int main()
  18. {
  19. int n=read(),m=read();a[0]=23333333;
  20. for(int i=1;i<=n;i++)a[i]=min(read(),a[i-1]);
  21. int i=n,x;
  22. for(;m--;i--)for(x=read();a[i]<x&&i;i--);
  23. printf("%d",i<0?0:i+1);
  24. return 0;
  25. }

Periods of Words (Stage I)

题意:求一个字符串所有前缀的最大周期长度之和,这里的周期长度不一定要整除原长

又是kmp好题辣。
先求next,最后发现指向0之前的那个next就是最长循环节了,感觉不难证明。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define N 1000010
  6. using namespace std;
  7. typedef long long LL;
  8. int n,ne[N];char s[N];
  9. int main()
  10. {
  11. scanf("%d\n%s",&n,s);
  12. ne[0]=-1;int i=0,j=-1;
  13. while(i<n)if(j==-1||s[i]==s[j])ne[++i]=++j;else j=ne[j];
  14. LL ans=0;
  15. for(i=1;i<=n;i++)if(ne[i])while(ne[ne[i]])ne[i]=ne[ne[i]];
  16. for(i=1;i<=n;i++)if(ne[i]!=0)ans+=i-ne[i];
  17. printf("%lld\n",ans);
  18. }

Professor Szu (Stage I)


Tetris 3D (Stage I)

题意:每次在平面内查询,将子矩形内所有值修改为其中最大值。

二维线段树好题,标记永久化一下,每次在最大值上进行查询、修改即可。
代码似乎是改自hzwer的?

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 3005
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. #define CI const int&
  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 ls k<<1
  18. #define rs k<<1|1
  19. int D,S,N,ql,qr,qd,qu;
  20. struct segx{
  21. int v[maxn],tag[maxn];
  22. void add(int k,int l,int r,int x,int y,CI val){
  23. v[k]=max(v[k],val);
  24. if(l==x&&y==r){tag[k]=max(tag[k],val);return;}
  25. int mid=(l+r)>>1;
  26. if(x<=mid)add(ls,l,mid,x,min(mid,y),val);
  27. if(y>mid)add(rs,mid+1,r,max(x,mid+1),y,val);
  28. }
  29. int query(int k,int l,int r,int x,int y){
  30. if(l==x&&y==r)return v[k];
  31. int mid=(l+r)>>1,ans=tag[k];
  32. if(x<=mid)ans=max(ans,query(ls,l,mid,x,min(mid,y)));
  33. if(y>mid)ans=max(ans,query(rs,mid+1,r,max(x,mid+1),y));
  34. return ans;
  35. }
  36. };
  37. struct segy{
  38. segx v[maxn],tag[maxn];
  39. void add(int k,int l,int r,int x,int y,CI val){
  40. v[k].add(1,1,S,qd,qu,val);
  41. if(l==x&&y==r){tag[k].add(1,1,S,qd,qu,val);return;}
  42. int mid=(l+r)>>1;
  43. if(x<=mid)add(ls,l,mid,x,min(mid,y),val);
  44. if(y>mid)add(rs,mid+1,r,max(x,mid+1),y,val);
  45. }
  46. int query(int k,int l,int r,int x,int y){
  47. if(l==x&&y==r)return v[k].query(1,1,S,qd,qu);
  48. int mid=(l+r)>>1,ans=tag[k].query(1,1,S,qd,qu);;
  49. if(x<=mid)ans=max(ans,query(ls,l,mid,x,min(mid,y)));
  50. if(y>mid)ans=max(ans,query(rs,mid+1,r,max(x,mid+1),y));
  51. return ans;
  52. }
  53. }T;
  54. int main()
  55. {
  56. D=read();S=read();N=read();
  57. int d,s,w,x,y;
  58. for(int i=1;i<=N;i++)
  59. {
  60. d=read();s=read();w=read();x=read();y=read();
  61. ql=x+1;qr=x+d;qd=y+1;qu=y+s;
  62. int ans=T.query(1,1,D,ql,qr);
  63. T.add(1,1,D,ql,qr,ans+w);
  64. }
  65. qd=1;qu=S;
  66. printf("%d\n",T.query(1,1,D,1,D));
  67. return 0;
  68. }

Frogs (Stage I)


Warehouse (Stage II - day 0)


Schools (Stage II - day 0)

见题目
KM好题

  1. /*
  2. Author:lbn187
  3. */
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define inf 1e9
  8. using namespace std;typedef long long LL;LL ans;
  9. int lx[201],ly[201],slf[201],w[201][201],lk[201],n,k,i,j,x,l,r,c;
  10. bool vx[201],vy[201];
  11. bool find(int x){
  12. vx[x]=1;
  13. for(int y=1;y<=n;y++)if(!vy[y])
  14. if(lx[x]+ly[y]==w[x][y]){
  15. vy[y]=1;
  16. if(lk[y]==0||find(lk[y])){
  17. lk[y]=x;
  18. return 1;
  19. }
  20. }else slf[y]=min(slf[y],lx[x]+ly[y]-w[x][y]);
  21. return 0;
  22. }
  23. int main(){
  24. for(scanf("%d",&n),i=1;i<=n;i++){
  25. lx[i]=-inf;
  26. scanf("%d%d%d%d",&x,&l,&r,&c);
  27. for(j=l;j<=r;j++)w[i][j]=inf-abs(j-x)*c;
  28. }
  29. for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(w[i][j]>lx[i])lx[i]=w[i][j];
  30. for(k=1;k<=n;k++){
  31. memset(slf,63,sizeof(slf));
  32. for(;;){
  33. memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));
  34. if(find(k))break;int d=inf;
  35. for(i=1;i<=n;i++)if(!vy[i]&&d>slf[i])d=slf[i];
  36. for(i=1;i<=n;i++){
  37. if(vx[i])lx[i]=lx[i]-d;
  38. if(vy[i])ly[i]=ly[i]+d;else slf[i]=slf[i]-d;
  39. }
  40. }
  41. }
  42. for(i=1;i<=n;i++)ans=ans+w[lk[i]][i];ans=(LL)inf*n-ans;
  43. ans>=inf?puts("NIE"):printf("%lld",ans); 
  44. }

Subway (Stage II - day 1)


The Invasion (Stage II - day 1)


The Postman (Stage II - day 2)


Ploughing (Stage II - day 2)


Dancing in Circles (Stage III - day 0)


Aesthetic Text (Stage III - day 1)

题意:一次排版,每行长度不可超过m,n个单词依序排下来,求相邻两行长度差之和的最小值

一看就是DP啦,先要写出这样的一个方程:
f[i][j]=min(f[i][j],f[k][i-1]+abs(s[j]-s[i-1]*2+s[k-1]));

可以利用单调性存两个从大转移最小值和从小转移最小值的数组,就可以在时间内出解了。
题解来自lbn187

  1. #include<bits/stdc++.h>
  2. #define maxn 2020
  3. using namespace std;
  4. int m,n,ans=2e9,k,a[maxn];
  5. int f[maxn][maxn],g[maxn][maxn],h[maxn][maxn];
  6. int main()
  7. {
  8. memset(f,63,sizeof(f));memset(g,63,sizeof(g));memset(h,63,sizeof(h));
  9. g[0][0]=0;
  10. scanf("%d%d",&m,&n);m++;
  11. for(int i=1,j;i<=n;i++)
  12. {
  13. scanf("%d",&a[i]);
  14. a[i]+=a[i-1]+1;
  15. for(j=k=i-1;j>=0&&a[i]-a[j]<=m;j--)
  16. {
  17. for(;a[i]-a[j]>=a[j]-a[k]&&k>=0;k--);
  18. f[i][j]=g[j][k+1]+a[i]-a[j];
  19. if(!j)f[i][j]=0;
  20. if(k>=0)f[i][j]=min(f[i][j],h[j][k]+a[j]-a[i]);
  21. g[i][j]=min(g[i][j+1],f[i][j]+a[j]-a[i]);
  22. }
  23. for(j++;j<=i;j++)
  24. h[i][j]=min(h[i][j-1],f[i][j]+a[i]-a[j]);
  25. }
  26. for(int i=0;i<=n;i++)
  27. ans=min(ans,f[n][i]);
  28. printf("%d",ans);
  29. }

Crystals (Stage III - day 1)

题意:给定数组,问有多少组同时满足

看到异或大概就是数位Dp DarkFantasy了嘛。
怎么按位DP啊。考虑到整数的连续性,如果某一位本来能取1,但你取了0,那么接下去若干位就任意了,这就可以大力计算了

  1. /*
  2. Author:Scarlet
  3. 好像还不是很懂,下面的注释是瞎写的
  4. 有时间再改进
  5. */
  6. #include<bits/stdc++.h>
  7. #define maxn 55
  8. using namespace std;
  9. typedef unsigned long long LL;
  10. #define G c=getchar()
  11. inline LL read()
  12. {
  13. LL 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;LL ans,a[maxn];
  19. void dfs(int x)//x位以前全取最高位的方案数
  20. {
  21. LL t1,t2,tt,s=0,a0=1,a1=0,a2=0;
  22. for(int i=1;i<=n;i++)
  23. {
  24. t1=a1;t2=a2;tt=(a[i]&((1<<x)-1))+1;
  25. if(a[i]>>x&1)//能取1
  26. s^=1,
  27. a1=a0+t2*(1<<x)+t1*tt,//本位为0的方案数
  28. a2=t1*(1<<x)+t2*tt;//本位为1的方案数
  29. else a1=t1*tt,a2=t2*tt;//只能取0
  30. a0=a0*tt;//方案基数
  31. }
  32. if(!s)//还没算完
  33. {
  34. ans+=a2;
  35. if(x)dfs(x-1);
  36. else ans++;
  37. }
  38. else ans+=a1;//算完了
  39. }
  40. int main()
  41. {
  42. n=read();
  43. for(int i=1;i<=n;i++)a[i]=read();
  44. dfs(31);
  45. printf("%llu",ans-1);
  46. return 0;
  47. }

Teddies (Stage III - day 2)


Palindromes (Stage III - day 2)

个回文串,问多少个使得也是回文串

先考虑这样一个事实:都是回文串,那么也是回文串。
证明十分简单,我们轻易地发现了,然后就没有然后了。

稍微加强一下可以这样:

是回文串,那么

那么问题就变得十分simple了:给定个串,问有多少

可以先对所有建Trie,然后拿所有S放到Trie上跑,跑的时候拿路上的串和当前的匹配一下就过了。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<cstdio>
  5. #include<string>
  6. #include<algorithm>
  7. #define S 131
  8. #define N 2001000
  9. using namespace std;typedef unsigned long long LL;
  10. LL hs[N],pw[N],ha,ans;
  11. int n,i,j,x,now,top,len[N],to[N],sum[N],c[N][26];
  12. string s[N];char ch[N];
  13. int main()
  14. {
  15. for(scanf("%d",&n),i=1;i<=n;i++)
  16. {
  17. scanf("%d%s",&len[i],ch+1);s[i]=ch+1;
  18. for(now=ha=0,j=1;j<=len[i];j++)
  19. {
  20. x=ch[j]-'a';
  21. ha=ha*S+x;
  22. if(!c[now][x])c[now][x]=++top;
  23. now=c[now][x];
  24. }
  25. hs[i]=ha;to[now]=i;sum[now]++;
  26. }
  27. for(pw[0]=1,i=1;i<N;i++)pw[i]=pw[i-1]*S;
  28. for(i=1;i<=n;i++)
  29. for(now=0,j=0;j<len[i];j++)
  30. {
  31. int x=s[i][j]-'a';
  32. now=c[now][x];
  33. if(sum[now]&&hs[to[now]]*pw[len[i]]+hs[i]==hs[i]*pw[j+1]+hs[to[now]])ans+=sum[now]*2;
  34. }
  35. printf("%llu",ans-n);
  36. }

Sophie (Stage III - day 2)


休息一会儿蛤

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