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

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)

休息一会儿蛤

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