[关闭]
@happyforever 2018-10-29T14:27:16.000000Z 字数 8528 阅读 520

10.23晚上解题报告

解题报告 清北学堂

图片.png

各题状况

期望得分：
实际得分：

T1

写了半小时的KMP
调了一个半小时的AC自动机
发现不会改就放过了
hash有想过但是实在怕被卡就没有写
然后号上午写了一份unsigned long long自然溢出的代码过了。。。

T2

因为输入数据比较大，有的人没写快读就很亏，然后老师开了的时限
。。。。
开我也过不了。。。
小数据范围没写，只写了特殊性质，然后了。

数据锅了hhhh
部分分的数据范围与题目给的范围不一样

T3

分Floyd
分每次暴搜

题目及考场代码

T1

图片.png
图片.png
图片.png

  1. /*
  2.  * 有人说是AC自动机。。
  3.  * 吔
  4.  * 我只会KMP是不是凉了2333
  5.  * O(Ln)，最坏情况O(1e9)
  6.  */
  7. #include <cstdio>
  8. #include <cstring>
  10. const int N=1e5+1;
  11. int L,n,m,next[21];
  12. char s[N],ss[N/10+1][21];
  13. bool flag=true;
  15. void getNext(char *ss)
  16. {
  17.     for(int j=0,i=1;i<m;++i)
  18.     {
  19.         while(j && ss[i]!=ss[j])
  20.             j=next[j];
  21.         if(ss[i]==ss[j])
  22.             next[i+1]=++j;
  23.         else    next[i+1]=0;
  24.     }
  25. }
  27. void KMP(char *ss)
  28. {
  29.     for(int j=0,i=0;i<L;++i)
  30.     {
  31.         while(j && s[i]!=ss[j])
  32.             j=next[j];
  33.         if(s[i]==ss[j])
  34.             ++j;
  35.         if(j==m)
  36.         {
  37.             flag=false;
  38.             printf("%d\n",i-m+2);
  39.             return ;
  40.         }
  41.     }
  42. }
  44. int main()
  45. {
  46.     freopen("monitor.in","r",stdin);
  47.     freopen("monitor.out","w",stdout);
  49.     scanf("%d%d%d",&L,&n,&m);
  50.     for(int i=1;i<=n;++i)
  51.         scanf("%s",ss[i]);
  52.     scanf("%s",s);
  53.     for(int i=1;i<=n;++i)
  54.     {
  55.         getNext(ss[i]);
  56.         KMP(ss[i]);
  57.         if(!flag)goto E;
  58.     }
  59.     if(flag)puts("no");
  61. E:  fclose(stdin),fclose(stdout);
  62.     return 0;
  63. }

T2

图片.png
图片.png
图片.png

  1. /*
  2.  * 多加了边就会形成环
  3.  * 不存在k=0考虑LCA求解
  4.  * 有一个环的话
  5.  */
  6. #include <cstdio>
  7. #include <iostream>
  9. inline int read()
  10. {
  11.     int n=0,w=1;register char c=getchar();
  12.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  13.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  14.     return n*w;
  15. }
  17. const int N=1e5+1;
  18. int n,q,tot,head[N];
  19. int val[N],deep[N],fa[N],son[N],size[N],top[N],idx[N];
  20. struct Edge{
  21.     int v,w,nxt;
  22. }edge[N];
  23. inline void add(int w,int v,int u)
  24. {
  25.     edge[++tot]=(Edge){v, w,head[u]};head[u]=tot;
  26.     edge[++tot]=(Edge){u,-w,head[v]};head[v]=tot;
  27. }
  29. void dfs1(int now)
  30. {
  31.     size[now]=1;
  32.     for(int v,i=head[now];i;i=edge[i].nxt)
  33.         if((v=edge[i].v)!=fa[now])
  34.         {
  35.             deep[v]=deep[now]+1;
  36.             val[v]=edge[i].w;
  37.             fa[v]=now;
  38.             dfs1(v);
  39.             size[now]+=size[v];
  40.             if(size[son[now]]<size[v])
  41.                 son[now]=v;
  42.         }
  43. }
  45. void dfs2(int now,int tp)
  46. {
  47.     top[now]=tp;
  48.     if(!son[now])return ;
  49.     dfs2(son[now],tp);
  50.     for(int i=head[now];i;i=edge[i].nxt)
  51.         if(edge[i].v!=fa[now])
  52.             dfs2(edge[i].v,edge[i].v);
  53. }
  55. inline int Lca(int x,int y)
  56. {
  57.     while(top[x]!=top[y])
  58.     {
  59.         if(deep[top[x]]<deep[top[y]])
  60.             std::swap(x,y);
  61.         x=fa[top[x]];
  62.     }
  63.     return deep[x]>deep[y]?y:x;
  64. }
  66. inline int query(int x,int y)
  67. {
  68.     int lca=Lca(x,y);
  69.     long long ans=0;
  70.     while(x!=lca)
  71.     {
  72.         ans-=val[x];
  73.         x=fa[x];
  74.     }
  75.     while(y!=lca)
  76.     {
  77.         ans+=val[y];
  78.         y=fa[y];
  79.     }
  80. //  printf("%d",ans);
  81.     return ans;
  82. }
  84. int main()
  85. {
  86.     freopen("lab.in","r",stdin);
  87.     freopen("lab.out","w",stdout);
  89.     n=read(),q=read();
  90.     for(int i=1;i<n;++i)
  91.         add(read(),read(),read());
  92.     dfs1(1);
  93.     dfs2(1,1);
  94.     int k,x,y,z;
  95.     while(q--)
  96.     {
  97.         k=read(),x=read(),y=read(),z=read();
  98.         puts(query(x,y)==z?"yes":"no");
  99.     }
  101.     fclose(stdin),fclose(stdout);
  102.     return 0;
  103. }

T3

图片.png
图片.png
图片.png

  1. /*
  2.  * 40分可以floyd
  3.  * 考虑对每个点，维护其到其子树内各点的奇、偶路径长度和
  4.  */
  5. #include <cstdio>
  6. #include <cstring>
  8. const int N=1e5+1;
  9. int n,q,tot,head[N];
  10. struct Edge{
  11.     int v,w,nxt;
  12. }edge[N<<1];
  13. long long ans[2];
  15. inline void add(int w,int v,int u)
  16. {
  17.     edge[++tot]=(Edge){v,w,head[u]};head[u]=tot;
  18.     edge[++tot]=(Edge){u,w,head[v]};head[v]=tot;
  19. }
  20. inline int read()
  21. {
  22.     int n=0,w=1;register char c=getchar();
  23.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  24.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  25.     return n*w;
  26. }
  27. void dfs(int now,int fa,long long w)
  28. {
  29.     ans[w&1]+=w;
  30.     for(int v,i=head[now];i;i=edge[i].nxt)
  31.         if((v=edge[i].v)!=fa)
  32.             dfs(v,now,edge[i].w+w);
  33. }
  35. int main()
  36. {
  37.     freopen("civilization.in","r",stdin);
  38.     freopen("civilization.out","w",stdout);
  40.     n=read(),q=read();
  41.     for(int i=1;i<n;++i)
  42.         add(read(),read(),read());
  43.     int x;
  44.     while(q--)
  45.     {
  46.         x=read();ans[1]=ans[0]=0;
  47.         dfs(x,x,0);
  48.         printf("%I64d %I64d\n",ans[1],ans[0]);
  49.     }
  51.     fclose(stdin),fclose(stdout);
  52.     return 0;
  53. }

正解及代码

T1

遍KMP，最坏复杂度可以得

用std::string里面的find函数，因为每次find是最坏复杂度的，所以最坏，也能分

hash。。。某同学：“老师，会卡hash吗”。老师：“我有一晚上的时间”。

没有卡，都卡掉了

其他比较随意的也没有卡

std::map因为时间问题会一个点

  1. #include <set>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. int L,n,m;
  6. typedef unsigned long long LLU;
  8. const LLU mod=1000000000+7;
  9. const LLU mod2=1000000000+9;
  10. const LLU base = 131;
  11. LLU h[10005];
  12. LLU h2[10005];
  13. char s[100005];
  15. LLU gethash(char *s)
  16. {
  17.     LLU ret = 0;
  18.     for(int i=0;s[i];++i)
  19.         ret=(ret*base+s[i])%mod;
  20.     return ret;
  21. }
  22. LLU gethash2(char *s)
  23. {
  24.     LLU ret=0;
  25.     for(int i=0;s[i];++i)
  26.         ret=(ret*base+s[i]) % mod2;
  27.     return ret;
  28. }
  29. std::set<std::pair<LLU,LLU> > mingan;
  31. int main()
  32. {
  33.     freopen("monitor.in", "r", stdin);
  34.     freopen("monitor.out", "w", stdout); 
  35.     scanf("%d%d%d",&L,&n,&m);
  36.     for(int i=1;i<=n;++i)
  37.     {
  38.         scanf("%s",s+1);
  39.         h[i]=gethash(s+1);
  40.         h2[i]=gethash2(s+1);
  41.         mingan.insert(make_pair(h[i],h2[i]));
  42.     }
  43.     scanf("%s",s+1);
  44.     LLU now=0,now2=0,basem=1,basem2=1;
  45.     bool flag=0;
  46.     for(int i=1;i<=m;++i)
  47.         basem=basem*base%mod,basem2=basem2*base%mod2;
  48.     for(int i=1;i<=L;++i)
  49.     {
  50.         now=(now*base+s[i])%mod;
  51.         now2=(now2*base+s[i])%mod2;
  52.         if(i>m)
  53.         {
  54.             now=((now-s[i-m]*basem%mod)+mod)%mod;
  55.             now2=((now2-s[i-m]*basem2%mod2)+mod2)%mod2;
  56.         }
  57.         if(mingan.count(make_pair(now,now2))!=0)
  58.         {
  59.             printf("%d\n",i-m+1);
  60.             flag=1;
  61.             break;
  62.         }
  63.     }
  64.     if(!flag)puts("no");
  66.     return 0;
  67. }

T2

当没有的操作时，就是在树上求两点之间的路径长度是否等于某个值

通常的想法是

换个想法，假设现在有一棵树如下

图片.png

现在求的路径长度

设表示从点到根节点的距离，那么就是蓝色线，是紫色线

图片.png

再考虑所代表的含义

即图片.png

橙色的线段代表的路径，从指向

也就是到的路径长度

由此，对于的数据，可以预处理，而后每次输出答案

对于，即只有一个环的数据，考虑环对答案的贡献

图片.png

考虑如上的一张图，询问到是否有某长度的路径，的权值与是相反数

所以从走到再走回去只会增加（或减少）环的大小的时间

虽然没有给有两个（有两个环）的情况，但我们应该用它来考虑向正解的靠近

不妨先考虑两个环互不影响的情况

图片.png

假设第一个环的大小是，第二个环的大小是，

那么就是要求同余方程是否有解

根据裴蜀定理，同余方程有解当且仅当

所以我们要求的就是上述方程是否有解

再考虑更一般的情况：可能有很多环

那么先求一遍每个点到根的路径，再在操作过程中对所有产生的环求其大小（假定有个环，大小分别为），询问时，一个数不能被拼出来当且仅当 

  1. #include <cmath>
  2. #include <cstdio>
  3. #include <cstring>
  5. const int N=100001;
  6. int n,q,head[N],tot;
  7. struct Edge{
  8.     int v,w,nxt;
  9. }edge[N<<1];
  10. inline void add(int w,int v,int u)
  11. {
  12.     edge[++tot]=(Edge){v, w,head[u]};head[u]=tot;
  13.     edge[++tot]=(Edge){u,-w,head[v]};head[v]=tot;
  14. }
  15. inline int read()
  16. {
  17.     int n=0,w=1;register char c=getchar();
  18.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  19.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  20.     return n*w;
  21. }
  22. typedef long long LL;
  23. LL sum[100005];
  25. void dfs(int x,int fa)
  26. {
  27.     for(int v,i=head[x];i;i=edge[i].nxt)
  28.         if((v=edge[i].v)!=fa)
  29.         {
  30.             sum[edge[i].v]=sum[x]+edge[i].w;
  31.             dfs(v,x);
  32.         }
  33. }
  34. LL gcd(LL a, LL b)
  35. {return b==0?a:gcd(b,a%b);}
  37. int main()
  38. {
  39.     freopen("lab.in","r",stdin);
  40.     freopen("lab.out","w",stdout); 
  41.     n=read(),q=read();
  42.     for(int i=1;i<n;++i)
  43.         add(read(),read(),read());
  44.     dfs(1,0);
  45.     LL g=0;
  46.     for(int i=0,k,x,y,t;i<q;++i)
  47.     {
  48.         k=read(),x=read(),y=read(),t=read();
  49.         if(k==0)
  50.         {
  51.             if(!g)
  52.                 g=abs(sum[x]-sum[y]+t);
  53.             else
  54.                 if(abs(sum[x]-sum[y]+t)%g!=0)
  55.                     g=gcd(g,abs(sum[x]-sum[y]+t));
  56.         }
  57.         else
  58.             if(k==1)
  59.             {
  60.                 if(sum[y]-sum[x]==t)//不需要环
  61.                     puts("yes");
  62.                 else
  63.                     if(g==0)//没有环
  64.                         puts("no");
  65.                     else
  66.                         if((t-(sum[y]-sum[x]))%g==0)
  67.                             puts("yes");
  68.                         else    puts("no");
  69.             }
  70.     }
  71.     fclose(stdin);fclose(stdout);
  72.     return 0;
  73. }

T3

考虑求一个点的子树中所有点到这个点的权值和 

  1. void dfs1(int x,int fa)
  2. {
  3.     size[x]=1;
  4.     for(int v,i=head[x];i;i=edge[i].nxt)
  5.         if((v=edge[i].v)!=fa)
  6.         {
  7.             dfs1(v,x);
  8.             size[x]+=size[v];
  9.             f[x]+=f[v]+edge[i].w*size[v];
  10.         }
  11. }

那么如果能够从父亲节点推到儿子节点就可以了

对每个点，把当前点的子树的贡献刨掉

  1. f2[1]=f[1];
  2. void dfs2(int x)
  3. {
  4.     for(int v,i=head[x];i;i=edge[i].nxt)
  5.         if((v=edge[i].v)!=fa)
  6.         {
  7.             f2[v] =f[v];
  8.             f2[v]+=f2[x]-f[v]-edge[i].w*size[v]+edge[i].w*(size[1]-size[x]);
  9.             dfs2(v,x);
  10.         }
  11. }

另外注意在经过一条奇边之后，奇数路径和与偶数路径和要对换；经过一条偶边之后奇数路径和与偶数路径和仅仅数值变化不会对换

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. // 70%给开了int没开longlong
  5. const int N=100001;
  6. int n,q,head[N],tot;
  7. struct Edge{
  8.     int v,w,nxt;
  9. }edge[N<<1];
  10. inline void add(int w,int v,int u)
  11. {
  12.     edge[++tot]=(Edge){v, w,head[u]};head[u]=tot;
  13.     edge[++tot]=(Edge){u,-w,head[v]};head[v]=tot;
  14. }
  15. inline int read()
  16. {
  17.     int n=0,w=1;register char c=getchar();
  18.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  19.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  20.     return n*w;
  21. }
  22. typedef long long LL;
  23. LL f[2][N];
  24. LL ans[2][N];
  25. int siz[2][N];
  26. int siz2[2][N];
  28. void dfs1(int x,int fa)
  29. {
  30.     siz[0][x]=1;
  31.     for(int v,i=head[x];i;i=edge[i].nxt)
  32.     {
  33.         if((v=edge[i].v)==fa) continue;
  34.         dfs1(v,x);
  35.         if(edge[i].w&1)
  36.         {
  37.             siz[0][x]+=siz[1][v];
  38.             siz[1][x]+=siz[0][v];
  39.             f[0][x]+=f[1][v]+edge[i].w*siz[1][v];
  40.             f[1][x]+=f[0][v]+edge[i].w*siz[0][v];
  41.         }
  42.         else
  43.         {
  44.             siz[0][x]+=siz[0][v];
  45.             siz[1][x]+=siz[1][v];
  46.             f[0][x]+=f[0][v]+edge[i].w*siz[0][v];
  47.             f[1][x]+=f[1][v]+edge[i].w*siz[1][v];
  48.         }
  49.     }
  50. }
  52. void dfs2(int x,int fa)
  53. {
  54.     for(int v,i=head[x];i;i=edge[i].nxt)
  55.     {
  56.         if((v=edge[i].v)==fa)continue;
  57.         if(edge[i].w&1)
  58.         {
  59.             siz2[0][v]=siz2[1][x];
  60.             siz2[1][v]=siz2[0][x];
  61.             ans[0][v]=f[0][v]+ans[1][x]-(f[0][v]+edge[i].w*siz[0][v])+edge[i].w*(siz2[1][x]-siz[0][v]);
  62.             ans[1][v]=f[1][v]+ans[0][x]-(f[1][v]+edge[i].w*siz[1][v])+edge[i].w*(siz2[0][x]-siz[1][v]);
  63.         }
  64.         else
  65.         {
  66.             siz2[0][v]=siz2[0][x];
  67.             siz2[1][v]=siz2[1][x];
  68.             ans[0][v]=f[0][v]+ans[0][x]-(f[0][v]+edge[i].w*siz[0][v])+edge[i].w*(siz2[0][x]-siz[0][v]);
  69.             ans[1][v]=f[1][v]+ans[1][x]-(f[1][v]+edge[i].w*siz[1][v])+edge[i].w*(siz2[1][x]-siz[1][v]);
  70.         }
  71.         dfs2(v,x);
  72.     }
  73. }
  75. int main()
  76. {
  77.     freopen("civilization.in","r",stdin);
  78.     freopen("civilization.out","w",stdout); 
  80.     n=read(),q=read();
  81.     for(int i=1;i<n;++i)
  82.         add(read(),read(),read());
  83.     dfs1(1,0);
  84.     ans[0][1]=f[0][1];
  85.     ans[1][1]=f[1][1];
  86.     siz2[0][1]=siz[0][1];
  87.     siz2[1][1]=siz[1][1];
  88.     dfs2(1,0);
  90.     int x;
  91.     while(q--)
  92.     {
  93.         x=read();
  94.         printf("%lld %lld\n",ans[1][x],ans[0][x]);
  95.         // printf("f %lld %lld\n",f[1][x],f[0][x]);
  96.         // printf("siz %d %d\n",siz[1][x],siz[0][x]);
  97.     }
  98.     fclose(stdin);fclose(stdout);
  99.     return 0;
  100. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注