[关闭]
@Scarlet 2017-01-12T12:06:34.000000Z 字数 7637 阅读 874

POI 1997

POI 1997 OI 解题报告


The Number of Symmetrical Choices (Stage I)

题意:每次选择a[i]或者b[i]的单词拼接,求成为回文串的方案数

新建源汇,根据题意可以建出一个DAG
f[x][y]为从走到的回文路径的方案数,则
边界条件:f[x][x]=1
对于一条边,若a[x]==a[y],则f[x][y]=1
转移方程为:
a[x]==a[y],则f[x][y]=sum(f[i][j])(有边,有边)
a[x]!=a[y],则f[x][y]=0
最终答案即为f[S][T],时间复杂度

From Claris

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 666
  6. #define maxm 2333
  7. using namespace std;
  8. #define AE(u,v) to[Si]=v,nxt[Si]=i1[u],i1[u]=Si++,to[Si]=u,nxt[Si]=i2[v],i2[v]=Si++
  9. int i1[maxn],i2[maxn],nxt[maxm],to[maxm],Si;
  10. int v[maxn][maxn],f[maxn][maxn];
  11. int n,m,st[2][maxn],en[2][maxn],a[maxn];char s[maxn];
  12. int F(int x,int y)
  13. {
  14. if(v[x][y])return f[x][y];
  15. v[x][y]=1;
  16. if(a[x]!=a[y])return 0;
  17. for(int i=i1[x];i+1;i=nxt[i])
  18. for(int j=i2[y];j+1;j=nxt[j])
  19. f[x][y]+=F(to[i],to[j]);
  20. return f[x][y];
  21. }
  22. int main()
  23. {
  24. memset(i1,-1,sizeof(i1));
  25. memset(i2,-1,sizeof(i2));
  26. scanf("%d",&n);m=2;
  27. for(int k=0;k<2;k++)
  28. for(int i=1;i<=n;i++)
  29. {
  30. st[k][i]=m+1;
  31. scanf("%s",s+1);
  32. int l=strlen(s+1);
  33. for(int j=1;j<l;j++)
  34. AE(m+j,m+j+1);
  35. for(int j=1;j<=l;j++)a[m+j]=s[j]-'a'+1;
  36. en[k][i]=m+=l;
  37. }
  38. for(int i=1;i<n;i++)
  39. {
  40. AE(en[0][i],st[0][i+1]);
  41. AE(en[0][i],st[1][i+1]);
  42. AE(en[1][i],st[0][i+1]);
  43. AE(en[1][i],st[1][i+1]);
  44. }
  45. AE(1,st[0][3]);
  46. AE(1,st[1][4]);
  47. AE(en[0][n],2);
  48. AE(en[1][n],2);
  49. for(int i=1;i<=m;i++)
  50. {
  51. v[i][i]=f[i][i]=1;
  52. for(int j=i1[i];j+1;j=nxt[j])
  53. {
  54. v[i][to[j]]=1;
  55. if(a[i]==a[to[j]])f[i][to[j]]=1;
  56. }
  57. }
  58. printf("%d",F(1,2));
  59. return 0;
  60. }

Jumps (Stage I) (0/100)


Cheap Travels (Stage I)

题意:给定若干酒店的坐标和价格,每走就必须开♂房♂过♂一♂晚,求最少休息时间和最少价格

似乎是普及组DP ,f[i]表示在第个酒店过♂夜的答案,单调队列 转移即可。
可以用个双关键字dp技巧:一个数位扩大后加上另一个数位,详见代码

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 1010
  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 f[maxn],p[maxn];
  17. struct poi{int d,p;}a[maxn];
  18. inline bool cmp(const poi &a,const poi &b){return a.d<b.d;}
  19. void out(int x)
  20. {
  21. if(a[x].d==0)return;
  22. out(p[x]);printf("%d ",a[x].d);
  23. }
  24. int main()
  25. {
  26. int m=read(),n=read();
  27. for(int i=1;i<=n;i++)
  28. a[i].d=read(),a[i].p=read();
  29. a[++n].d=m;
  30. sort(a+1,a+1+n,cmp);
  31. memset(f,0x7f7f7f7f,sizeof(f));f[0]=0;
  32. for(int i=1;i<=n;f[i]+=a[i].p*10000+1,i++)
  33. for(int j=0;j<i;j++)
  34. if(a[i].d-a[j].d<=800)
  35. if(f[j]<f[i])f[i]=f[j],p[i]=j;
  36. out(p[n]);puts("");
  37. memset(f,0x7f7f7f7f,sizeof(f));f[0]=0;
  38. for(int i=1;i<=n;f[i]+=a[i].p+10000,i++)
  39. for(int j=0;j<i;j++)
  40. if(a[i].d-a[j].d<=800)
  41. if(f[j]<f[i])f[i]=f[j],p[i]=j;
  42. out(p[n]);puts("");
  43. return 0;
  44. }

XOR Gates (Stage I)

题意:给定若干个引脚和异或门的连接情况,求给定区间内有多少能使异或门输出1的情况。

因为是亦或,所以最终答案一定是若干引脚的亦或值。
因为是个DAG,所以可以用dfs求出最终结果是有哪些引脚亦或所得。这里是的,用手写平衡树启发式合并不知道会不会快。
然后题目就变成,在一定区间内,若干位亦或值为的数有多少个。
题目中前后给出区间范围小于,但是为了出题坑害青少年锻炼dp技巧,就写了个数位dp。
因为给的是闭区间,所以还要验证一下第一个数的合法性。这里是

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 110
  6. #define maxm 3210
  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) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  18. int idx[maxm],nxt[maxm*2],to[maxm*2],Si,n,m,k;
  19. bitset<101>w[maxm],fin;
  20. int vis[maxm];
  21. void dfs(int x)
  22. {
  23. vis[x]=1;
  24. for(int i=idx[x];i+1;i=nxt[i])
  25. {
  26. if(!vis[to[i]])dfs(to[i]);
  27. w[x]^=w[to[i]];
  28. }
  29. }
  30. int f[maxn][2],g[maxn],ans;
  31. int dfs(int N,bool top,bool s)
  32. {
  33. if(N>=n)return s;
  34. if(!top&&f[N][s]+1)return f[N][s];
  35. int ans=0,t=top?g[N]:1;
  36. for(int i=0;i<=t;i++)
  37. ans+=dfs(N+1,top&(i==t),s^(fin[N]&i));
  38. if(!top)f[N][s]=ans;
  39. return ans;
  40. }
  41. void add(int x)
  42. {
  43. int a=read();
  44. if(a<0)w[x][-a-1]=w[x][-a-1]^1;
  45. else AE(x,a-1);
  46. }
  47. int main()
  48. {
  49. memset(idx,-1,sizeof(idx));
  50. n=read(),m=read(),k=read()-1;
  51. for(int i=0;i<m;i++)add(i),add(i);
  52. dfs(k);ans=0;fin=w[k];
  53. for(int i=0;i<n;i++)scanf("%1d",&g[i]),ans^=fin[i]&g[i];
  54. memset(f,-1,sizeof(f));
  55. ans-=dfs(0,1,0);
  56. for(int i=0;i<n;i++)scanf("%1d",&g[i]);
  57. memset(f,-1,sizeof(f));
  58. ans+=dfs(0,1,0);
  59. printf("%d\n",ans);
  60. return 0;
  61. }

Airports (Stage II - day 0)

题意:给定无向图的每个点度数,构造一个没有重边、自环的图。

清新小构造。考虑每次找到最大度数的点,直接将他连向剩余最大的deg[i]个。可以看出这样的构造是正确的。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 505
  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 n;
  17. struct poi{int i,d;}a[maxn];
  18. inline bool cmp(const poi &a,const poi &b){return a.d<b.d;}
  19. int main()
  20. {
  21. n=read();
  22. for(int i=1;i<=n;i++)
  23. a[i]=(poi){i,read()};
  24. for(int i=n,j;i>=1;i--)
  25. for(sort(a+1,a+1+i,cmp),j=i-1;j>=i-a[i].d;j--)
  26. printf("%d %d\n",a[i].i,a[j].i),a[j].d--;
  27. return 0;
  28. }

Addon (Stage II - day 1)

题意:在给定集合内选出一个数和一个子集,并使得中小于等于的所有数都能有中数的和表示,能用中的数之和表示且不大于的数都在中。最大化并最小化

枚举了大半天题意,你妈嗨.jpg。
考虑模拟:最小的数字是一定要加入的。然后对加入的数字做一波完全背包,再加入下一个数,直到存在一个能用已知数表示但不在集合的数。
看代码吧= =
加了bitset特技加速完全背包。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 20010
  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],x,n,aa;
  17. bitset<maxn>f,b;
  18. vector<int>ans;
  19. int main()
  20. {
  21. n=read();
  22. for(int i=1;i<=n;i++)b[read()]=1;
  23. for(int i=1,j;i<=10000;i++)
  24. if(b[i])
  25. {
  26. if(aa=i,!f[i])
  27. for(ans.push_back(i),f[i]=1,j=0;(1<<j)<=10000/i;j++)
  28. f|=(f<<(i<<j));
  29. }
  30. else
  31. if(f[i])
  32. {
  33. for(printf("%d\n",aa),j=0;j<ans.size();j++)
  34. printf("%d\n",ans[j]);
  35. return 0;
  36. }
  37. return 0;
  38. }

Genotypes (Stage II - day 1)

题意:给定一些字符生长姿势(一个变两个),每次询问给定字符串最少能由多少“S”生长成。

暴力在main上被卡了TAT。

只要让f[i][j][c]表示i-j能否变成c,大家就都会打暴力了。
然后发现main上过不去。
学习lbn位运算加速技巧,见Code

  1. /*
  2. Author:Scarlet
  3. */
  4. #pragma GCC optimize ("O2")
  5. #include<bits/stdc++.h>
  6. #define maxn 102
  7. using namespace std;
  8. int f[maxn][maxn],e[maxn][maxn],g[maxn],T,m,n;
  9. char S[maxn];
  10. inline void dp(const int &i,const int &j,int const &c)
  11. {
  12. for(int k=i;k<j;k++)
  13. for(int q=f[i][k];q;q^=q&-q)
  14. if(f[k+1][j]&e[c][__builtin_ctz(q&-q)]){f[i][j]|=1<<c;return;}
  15. }
  16. int main()
  17. {
  18. scanf("%d",&m);
  19. for(int i=1;i<=m;i++)
  20. scanf("%s",S),e[S[0]-'A'][S[1]-'A']|=1<<S[2]-'A';
  21. scanf("%d",&T);
  22. for(;T--;)
  23. {
  24. scanf("%s",S+1);int n=strlen(S+1);
  25. memset(f,0,sizeof(f));memset(g,0x7f7f7f,sizeof(g));g[0]=0;
  26. for(int i=1;i<=n;i++)f[i][i]|=1<<S[i]-'A';
  27. for(int L=1;L<n;L++)
  28. for(int i=1;i+L<=n;i++)
  29. for(int c=0;c<26;c++)
  30. dp(i,i+L,c);
  31. for(int i=1;i<=n;i++)
  32. for(int j=1;j<=i;j++)
  33. if(f[j][i]&(1<<18))g[i]=min(g[i],g[j-1]+1);
  34. if(g[n]<=n)printf("%d\n",g[n]);else puts("NIE");
  35. }
  36. return 0;
  37. }

Petrol (Stage II - day 2) (0/100)


Recursive Ant (Stage II - day 2) (0/100)


Credibility of Witnesses (Stage III - day 0) (0/100)


Canoes (Stage III - day 1) (0/100)


The Number of N-k-special Sets (Stage III - day 1) (0/100)


Monochromatic Triangles (Stage III - day 1)

题意:个点的完全图中给定某些红色边,其余全为蓝色,求同色三角形个数。

同色三角形很难统计,但是异色三角形统计较简单。考虑到每个异色三角形必有两个点连接异色边,就能统计了。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. int n,m,ans,i,d[1001];
  6. int main()
  7. {
  8. scanf("%d%d",&n,&m);
  9. for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),d[x]++,d[y]++;
  10. for(int i=1;i<=n;i++)ans+=(d[i]*(n-1-d[i]));
  11. printf("%d\n",n*(n-1)*(n-2)/6-ans/2);
  12. }

Ali Baba (Stage III - day 2)

像是爆搜题


Lecture Halls Reservation (Stage III - day 2)

题意:若干讲座从某天下午持续到另一天上午(即讲座结束后可以当天另起一个讲座),但学校只有一个讲座,问最多能有几天在开讲座。

傻鸡DP,f[i]表示前天的答案,显然可以从前一天f[i-1]转移过来,或是从某个以为结尾的讲座前转移过来。XJ8DP即可。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 30010
  6. #define maxm 10010
  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) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  18. int idx[maxn],nxt[maxm],to[maxm],Si=1,f[maxn],mx;
  19. int main()
  20. {
  21. int n=read();
  22. for(int i=1,x,y;i<=n;i++)
  23. x=read(),y=read(),AE(y,x),mx=max(mx,y);
  24. for(int i=1;f[i]=f[i-1],i<=mx;i++)
  25. for(int j=idx[i];j;j=nxt[j])
  26. f[i]=max(f[i],f[to[j]]+i-to[j]);
  27. printf("%d",f[mx]);
  28. return 0;
  29. }

Next:POI 2003

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