[关闭]
@happyforever 2018-11-06T12:06:48.000000Z 字数 7259 阅读 485

11.6日测试解题报告

清北学堂 解题报告

各题状况

期望得分：
实际得分：

T1

后悔之前没有认真练习树状数组求逆序对。。
然后考场上用半小时出来了hhhhhhhhh
天才儿童nlh
然后得意忘形把离散化数组和树状数组空间开小了
挂成分暴力
日
image.png

T2

我暴力代码常数巨大所以暴力分全挂了
的分因为的最后一次贡献没有考虑所以输出比答案少就很难受。

T3

题意读错浪费了
最后还剩分钟的时候开始写，总共用了分钟写完

题目及考场代码

T1

image.png

  1. /*
  2.  * 求逆序对？？？
  3.  * 求f(x)>g(y)同时x<y的点对(x,y)个数
  4.  *
  5.  * 60分n^2枚举
  6.  *
  7.  * 离散化+树状数组求逆序对？
  8.  * 插入的时候插入g[i]
  9.  * 查询的时候查询f[i]
  10.  *
  11.  * ....
  12.  * 天才儿童nlh
  13.  * 现场YY出来树状数组求逆序对还行。
  14.  * 可把我给牛逼坏了。
  15.  */
  16. #include <cstdio>
  17. #include <algorithm>
  19. inline int read()
  20. {
  21.     int n=0,w=1;register char c=getchar();
  22.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  23.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  24.     return n*w;
  25. }
  26. inline int lb(int x)
  27. {return x&(-x);}
  29. const int N=1e5+1;
  30. int n,k,tot,f[N],g[N],tr[N],a[N];
  31. long long ans;
  33. inline int ksm(long long x,int b)
  34. {
  35.     long long res=1;
  36.     for(;b;b>>=1,x=x*x%k)
  37.         if(b&1)
  38.             res=res*x%k;
  39.     return res;
  40. }
  42. inline void add(int x)
  43. {
  44.     for(;x<=tot;x+=lb(x))
  45.         ++tr[x];
  46. }
  47. inline int sum(int x)
  48. {
  49.     int res=0;
  50.     for(;x;x-=lb(x))
  51.         res+=tr[x];
  52.     return res;
  53. }
  55. int main()
  56. {
  57.     freopen("calc.in","r",stdin);
  58.     freopen("calc.out","w",stdout);
  60.     n=read(),k=read();
  61.     for(int x,i=1;i<=n;++i)
  62.     {
  63.         x=read();
  64.         f[i]=ksm(i,x);
  65.         g[i]=ksm(x,i);
  66.         a[++tot]=f[i];
  67.         a[++tot]=g[i];
  68.     }
  69.     std::stable_sort(a+1,a+1+tot);
  70.     for(int i=1;i<=n;++i)
  71.     {
  72.         f[i]=std::lower_bound(a+1,a+1+tot,f[i])-a;
  73.         g[i]=std::lower_bound(a+1,a+1+tot,g[i])-a;
  74.     }
  75.     for(int i=n;i;--i)
  76.     {
  77.         ans+=sum(f[i]-1);
  78.         add(g[i]);
  79.     }
  80.     printf("%I64d",ans);
  82.     fclose(stdin);fclose(stdout);
  83.     return 0;
  84. }

T2

image.png

  1. /*
  2.  * 20分枚举每次给哪个系统升级
  3.  * 另外20分r=0考虑有n个不同长度的线段，从下往上扫描，每次将所有等于当前高度的线段增高一单位，总共有k单位额外线段
  4.  *
  5.  * 其他情况：
  6.  * 首先把所有的防御塔变成同样的级别
  7.  * 而后如果能将所有的都升级就全都升级
  8.  * 否则考虑升级第r+1,3r+2,5r+3,...最后如果((2(x+1)-1)r+x+1)>n>((2x-1)r+x)，那么也就是说最后会有一部分位置无法被覆盖，此时我们再从后面往前升级防御塔。。。
  9.  * 不对。
  10.  * 好像最后几个很难讨论的样子。
  11.  * 细节好多啊我操。。。
  12.  *
  13.  * 写完暴力。
  14.  * 滚了滚了。
  15.  */
  16. #include <cstdio>
  17. #include <algorithm>
  19. inline int read()
  20. {
  21.     int n=0,w=1;register char c=getchar();
  22.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  23.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  24.     return n*w;
  25. }
  27. const int N=1e5+1;
  28. int n,r,a[N],vis[11],emp[11];
  29. long long k,ans;
  30. inline int min(int x,int y)
  31. {return x<y?x:y;}
  32. inline int max(int x,int y)
  33. {return x>y?x:y;}
  35. void dfs(int now)
  36. {
  37.     if(now>k)
  38.     {
  39.         for(int i=1;i<=n;++i)emp[i]=0;
  40.         long long minn=1e18+1;
  41.         for(int i=1;i<=n;++i)
  42.             for(int j=max(1,i-r);j<=min(n,i+r);++j)
  43.                 emp[j]+=a[i];
  44.         for(int i=1;i<=n;++i)
  45.             if(minn>emp[i])
  46.                 minn=emp[i];
  47.         if(minn>ans)
  48.             ans=minn;
  49.         return ;
  50.     }
  51.     for(int i=1;i<=n;++i)
  52.     {
  53.         ++a[i];
  54.         dfs(now+1);
  55.         --a[i];
  56.     }
  57. }
  59. int main()
  60. {
  61.     freopen("game.in","r",stdin);
  62.     freopen("game.out","w",stdout);
  64.     n=read(),r=read();
  65.     scanf("%I64d",&k);
  66.     for(int i=1;i<=n;++i)
  67.         a[i]=read();
  68.     if(n<=10)
  69.         dfs(1);
  70.     else
  71.     {
  72.         std::sort(a+1,a+1+n);
  73.         int tmp,cnt=1,emp=a[1],i=2;
  74.         for(;i<=n && a[i]==a[i-1];++i)++cnt;
  75.         for(;i<=n;++i)
  76.         {
  77.             tmp=cnt*(a[i]-emp);
  78.             if(k>tmp)
  79.                 k-=tmp;
  80.             else    break;
  81.             for(;i<n && a[i+1]==a[i];++i)++cnt;
  82.             emp=a[i],++cnt;
  83.         }
  84.         ans=emp,k/=cnt;
  85.         if(k)ans+=k-1;
  86.     }
  87.     printf("%I64d",ans);
  89.     fclose(stdin);fclose(stdout);
  90.     return 0;
  91. }

T3

image.png

image.png

  1. /*
  2.  * 对每个联通块维护有哪些边，把这些边存起来然后sort一发，之后记录前缀和
  3.  * 每次询问的时候考虑对每个联通块分别求出最大能到哪个w，答案就是这个位置的前缀和
  4.  *
  5.  *
  6.  * 。。。
  7.  * woc理解错题意了
  8.  * 完犊子
  9.  * 赶紧上暴力算了。
  10.  * 
  11.  * 应该能拿个30分？
  12.  */
  13. #include <cstdio>
  14. #include <cstring>
  15. #include <algorithm>
  17. inline int read()
  18. {
  19.     int n=0,w=1;register char c=getchar();
  20.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  21.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  22.     return n*w;
  23. }
  25. const int N=1e5+1;
  26. int n,m,k,q,tot,head[N];
  27. long long ans,emp;
  28. bool vis[N];
  29. struct Edge{
  30.     int v,w,nxt;
  31. }edge[N<<1];
  33. inline void add(int w,int v,int u)
  34. {
  35.     edge[++tot]=(Edge){v,w,head[u]};head[u]=tot;
  36.     edge[++tot]=(Edge){u,w,head[v]};head[v]=tot;
  37. }
  39. void dfs(int now)
  40. {
  41.     vis[now]=true;
  42.     for(int v,i=head[now];i;i=edge[i].nxt)
  43.         if(edge[i].w<=q)
  44.         {
  45.             emp+=edge[i].w;
  46.             if(!vis[v=edge[i].v])
  47.                 dfs(v);
  48.         }
  49. }
  51. int main()
  52. {
  53.     freopen("graph.in","r",stdin);
  54.     freopen("graph.out","w",stdout);
  56.     n=read(),m=read(),k=read();
  57.     for(int i=1;i<=m;++i)
  58.         add(read(),read(),read());
  59.     while(k--)
  60.     {
  61.         q=read(),ans=0;
  62.         memset(vis,false,sizeof vis);
  63.         for(int i=1;i<=n;++i)
  64.             if(!vis[i])
  65.             {
  66.                 emp=0,dfs(i);
  67.                 emp>>=1;
  68.                 if(emp>ans)ans=emp;
  69.             }
  70.         printf("%I64d\n",ans);
  71.     }
  73.     fclose(stdin);fclose(stdout);
  74.     return 0;
  75. }

正解及代码

T1

考虑树状数组求逆序对的原理：从后往前插入元素，每次询问统计有多少小于当前查询位置的位置有元素
需要离散化

  1. #include <cstdio>
  2. #include <algorithm>
  4. inline int read()
  5. {
  6.     int n=0,w=1;register char c=getchar();
  7.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  8.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  9.     return n*w;
  10. }
  11. inline int lb(int x)
  12. {return x&(-x);}
  14. const int N=1e5+1;
  15. int n,k,tot,f[N],g[N],tr[N<<1],a[N<<1];
  16. long long ans;
  18. inline int ksm(long long x,int b)
  19. {
  20.     long long res=1;
  21.     for(;b;b>>=1,x=x*x%k)
  22.         if(b&1)
  23.             res=res*x%k;
  24.     return res;
  25. }
  27. inline void add(int x)
  28. {
  29.     for(;x<=tot;x+=lb(x))
  30.         ++tr[x];
  31. }
  32. inline int sum(int x)
  33. {
  34.     int res=0;
  35.     for(;x;x-=lb(x))
  36.         res+=tr[x];
  37.     return res;
  38. }
  40. int main()
  41. {
  42.     freopen("calc.in","r",stdin);
  43.     freopen("calc.out","w",stdout);
  45.     n=read(),k=read();
  46.     for(int x,i=1;i<=n;++i)
  47.     {
  48.         x=read();
  49.         f[i]=ksm(i,x);
  50.         g[i]=ksm(x,i);
  51.         a[++tot]=f[i];
  52.         a[++tot]=g[i];
  53.     }
  54.     std::stable_sort(a+1,a+1+tot);
  55.     for(int i=1;i<=n;++i)
  56.     {
  57.         f[i]=std::lower_bound(a+1,a+1+tot,f[i])-a;
  58.         g[i]=std::lower_bound(a+1,a+1+tot,g[i])-a;
  59.     }
  60.     for(int i=n;i;--i)
  61.     {
  62.         ans+=sum(f[i]-1);
  63.         add(g[i]);
  64.     }
  65.     printf("%I64d",ans);
  67.     fclose(stdin);fclose(stdout);
  68.     return 0;
  69. }

T2

二分答案+贪心
每次的时候从前往后枚举所有位置，贪心策略：如果有某个位置的防御级别小于当前的答案那么就将位置的防御塔都升级一次，此时的所有位置都会增加的防御级别，虽然前面的也会影响到，但是由于我们只是在判断一个答案是否可行，而前面的已经判断过可行所以再加上一些防御等级依然是可行的，就不需要管了
对于上面的"所有位置都增加的防御级别"，如果暴力维护的话最坏是的，那么总体复杂度就是，有点太看不起的数据了
所以考虑每次时维护一个差分数列，那么"所有位置都增加的防御级别"也就是在的位置差分数组标记为就行了
这样就可以优化成每次的
总复杂度

  1. #include <cstdio>
  2. #include <algorithm>
  4. inline long long read()
  5. {
  6.     long long n=0;register char c=getchar();
  7.     while(c<'0' || c>'9')c=getchar();
  8.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  9.     return n;
  10. }
  12. typedef long long LL;
  13. const int N=5e5+5;
  14. LL n,R,k,ans,sum[N],Sum[N],a[N],b[N];
  15. inline LL min(LL x,LL y)
  16. {return x<y?x:y;}
  17. inline LL max(LL x,LL y)
  18. {return x>y?x:y;}
  20. inline bool judge(LL x)
  21. {
  22.     LL tot=0,delta,r;
  23.     for(int i=0;i<=n;++i)Sum[i]=sum[i],b[i]=0;
  24.     for(int i=1;i<=n;++i)
  25.     {
  26.         b[i]+=b[i-1],Sum[i]+=b[i];
  27.         if(Sum[i]<x)
  28.         {
  29.             delta=x-Sum[i];
  30.             b[i]+=delta;
  31.             tot+=delta;
  32.             if(tot>k)return false;
  33.             r=min(n,i+R+R);
  34.             b[r+1]-=delta;
  35.         }
  36.     }
  37.     return true;
  38. }
  40. int main()
  41. {
  42.     freopen("game.in","r",stdin);
  43.     freopen("game.out","w",stdout);
  45.     n=read(),R=read(),k=read();
  46.     for(int i=1;i<=n;++i)a[i]=read();
  47.     LL l,r;
  48.     for(int i=1;i<=n;++i)
  49.     {
  50.         l=max(1ll,i-R),r=min((LL)n,i+R);
  51.         sum[l]+=a[i],sum[r+1]-=a[i];
  52.     }
  53.     for(int i=1;i<=n;++i)sum[i]+=sum[i-1];
  54.     l=0,r=1e18+5e14;LL mid;
  55.     while(l<=r)
  56.     {
  57.         mid=l+r>>1;
  58.         if(judge(mid))
  59.             l=mid+1;
  60.         else    r=mid-1;
  61.     }
  62.     printf("%I64d",l-1);
  64.     fclose(stdin);fclose(stdout);
  65.     return 0;
  66. }

T3

套路题
每次询问，大的可以通过小的再加一些边之后推出，所以考虑离线做法：先把所有的询问读入，按照从小到大排序之后再处理
那么同样由于大的询问可以通过小的询问推出，考虑把所有边按照边权从小到大排序
考虑用并查集维护答案，对每个并查集维护其边权和数组：
对于每条合法的边，如果这条边的两个端点原本不联通，那么可以将加到里，并且将的父亲指向
当然不要忘了将这两个点之间的这条边的权值加到里面
一定要路径压缩！（小明没有路径压缩挂成50分其他全TLE了）

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  5. inline int read()
  6. {
  7.     int n=0,w=1;register char c=getchar();
  8.     while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
  9.     while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
  10.     return n*w;
  11. }
  13. const int N=1e5+1;
  14. int n,m,k,q,fa[N],ans[N],size[N];
  15. bool vis[N];
  16. struct Edge{
  17.     int u,v,w;
  18.     bool operator<(const Edge &gg)const
  19.     {return w<gg.w;}
  20. }edge[N];
  21. struct Query{
  22.     int w,id;
  23.     bool operator<(const Query &gg)const
  24.     {return w<gg.w;}
  25. }que[N];
  27. int find(int x)
  28. {
  29.     if(fa[x]!=x)
  30.         fa[x]=find(fa[x]);
  31.     return fa[x];
  32. }
  34. int main()
  35. {
  36.     freopen("graph.in","r",stdin);
  37.     freopen("graph.out","w",stdout);
  39.     n=read(),m=read(),k=read();
  40.     for(int i=1;i<=n;++i)fa[i]=i;
  41.     for(int i=1;i<=m;++i)
  42.         edge[i]=(Edge){read(),read(),read()};
  43.     for(int i=1;i<=k;++i)
  44.         que[i]=(Query){read(),i};
  46.     std::sort(que+1,que+1+k);
  47.     std::sort(edge+1,edge+1+m);
  49.     long long maxn=0;
  50.     int id=1,fu,fv;
  51.     for(int i=1;i<=k;++i)
  52.     {
  53.         if(que[i].w!=que[i-1].w)
  54.             for(;id<=m && edge[id].w<=que[i].w;++id)
  55.             {
  56.                 fu=find(edge[id].u),fv=find(edge[id].v);
  57.                 if(fu!=fv)
  58.                     fa[fu]=fv,size[fv]+=size[fu];
  59.                 size[fv]+=edge[id].w;
  60.                 if(size[fv]>maxn)maxn=size[fv];
  61.             }
  62.         ans[que[i].id]=maxn;
  63.     }
  64.     for(int i=1;i<=k;++i)
  65.         printf("%d\n",ans[i]);
  67.     fclose(stdin);fclose(stdout);
  68.     return 0;
  69. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注