暑假集训CSP提高模拟7

组题人： @KafuuChinocpp | @Chen_jr

\(T1\) P122. Permutations & Primes \(20pts\)

• 原题： CF1844B Permutations & Primes

• 假的构造策略，拿到了 \(20pts\) 。

  • 若 \(n\) 为奇数，则将 \(1\) 放在 \(\left\lceil \frac{n}{2} \right\rceil\) 的位置上，前一半质数降序放置，如果数量不够则合数降序放置，后一半降序放置。
  • 若 \(n\) 为偶数，则将 \(1\) 放在 \(\frac{n}{2}\) 的位置上，前一半质数降序放置，如果数量不够则合数降序放置，后一半降序放置。

• 正解

  • 观察到 \(1\) 对整个 \(\operatorname{mex}\) 的影响较大，故让包含 \(1\) 的区间尽量多，由 普及模拟1 T1 Past 的结论当取 \(i=n-i+1\) 时取到最大值，把 \(1\) 放在 \(\left\lceil \frac{n}{2} \right\rceil\) 的位置，然后将 \(2,3\) 分别放在首尾，剩下的随便填即可。
  点击查看代码

  int main()
  {
      ll t,n,i,j,k;
      cin>>t;
      for(j=1;j<=t;j++)
      {
          cin>>n;
          if(n==1)
          {
              cout<<"1"<<endl;
          }
          else
          {
              if(n==2)
              {
                  cout<<"2 1"<<endl;
              }
              else
              {
                  cout<<"2 ";
                  for(i=2,k=4;i<=n/2;i++,k++)
                  {
                      cout<<k<<" ";
                  }
                  cout<<"1 ";
                  for(i=n/2+2;i<=n-1;i++,k++)
                  {
                      cout<<k  <<" ";
                  }
                  cout<<"3"<<endl;
              }
          }
      }
      return 0;
  }
  

\(T2\) P135. 树上游戏 \(29pts\)

• 原题： [ARC116E] Spread of Information | luogu P3523 [POI2011] DYN-Dynamite

  • 多倍经验： luogu P3942 将军令 | luogu P2279 [HNOI2003] 消防局的设立 | luogu P2899 [USACO08JAN] Cell Phone Network G | UVA1218 完美的服务 Perfect Service

• 部分分

  • \(10pts\) ：当 \(k=n-1\) 时输出 \(1\) 。
  • \(10pts\) ：当 \(k=1\) 时求出树的直径除以 \(2\) 并向上取整即可。
  • 随机 \(pts\) ： rand() 大法好。

• 正解

  • 答案显然具有单调性，考虑二分答案。
  • 设当前二分出的答案为 \(mid\) ，则等价于覆盖距离为 \(mid\) 的情况下进行选点。
  • 做法同 luogu P3942 将军令 ，考虑进行贪心，对于深度最深的叶节点将选择的点放在边界时，即取 \(mid\) 级祖先时，覆盖的范围一定最大。
  • 设 \(f_{x}\) 表示 \(x\) 到以 \(x\) 为根的子树内最远的没被覆盖的点的距离， \(g_{x}\) 表示 \(x\) 到以 \(x\) 为根的子树内最近被选的点的距离，状态转移方程为 \(\begin{cases} f_{x}=\max\limits_{y \in Son(x)}\{ f_{y}+1 \} \\ g_{x}=\min\limits_{y \in Son(x)}\{ g_{y}+1 \}\end{cases}\) ，
  • 当 \(g_{x}>mid\) 时以 \(x\) 为根的子树内所选的点覆盖不到自己，需要祖先节点进行覆盖，此时需要统计自己的贡献，即 \(f_{x}=\max(f_{x},0)\) ；当 \(f_{x}+g_{x} \le mid\) 时以 \(x\) 为根的子树内所选的点就能覆盖整棵子树，令 \(f_{x}=- \infty\) ；当 \(f_{x}=mid\) 说明 \(x\) 必须被选，令 \(f_{x}=- \infty,g_{x}=0\) ，选择点数加一。
  • 特判下根节点没有被覆盖的情况。
  点击查看代码

  struct node
  {
      int nxt,to;
  }e[400010];
  int head[400010],f[400010],g[400010],cnt=0,sum=0;
  void add(int u,int v)
  {
      cnt++;
      e[cnt].nxt=head[u];
      e[cnt].to=v;
      head[u]=cnt;
  }
  void dfs(int x,int fa,int k)
  {
      f[x]=-0x3f3f3f3f;
      g[x]=0x3f3f3f3f;
      for(int i=head[x];i!=0;i=e[i].nxt)
      {
          if(e[i].to!=fa)
          {
              dfs(e[i].to,x,k);
              f[x]=max(f[x],f[e[i].to]+1);
              g[x]=min(g[x],g[e[i].to]+1);
          }
      }
      if(g[x]>k)
      {
          f[x]=max(f[x],0);//等待祖先的覆盖
      }
      if(f[x]+g[x]<=k)//已被覆盖
      {
          f[x]=-0x3f3f3f3f;
      }
      if(f[x]==k)//强制覆盖
      {
          f[x]=-0x3f3f3f3f;
          g[x]=0;
          sum++;
      }
  }
  bool check(int mid,int k)
  {
      sum=0;
      dfs(1,0,mid);
      sum+=(f[1]>=0);//自己到自己也得算
      return sum<=k;	
  }
  int main()
  {
      int n,k,u,v,l=0,r,mid,ans=0,i;
      cin>>n>>k;
      r=n;
      for(i=1;i<=n-1;i++)
      {
          cin>>u>>v;
          add(u,v);
          add(v,u);
      }
      while(l<=r)
      {
          mid=(l+r)/2;
          if(check(mid,k)==true)
          {
              ans=mid;
              r=mid-1;
          }
          else
          {
              l=mid+1;
          }
      }
      cout<<ans<<endl;
      return 0;
  }
  

\(T3\) P127. Ball Collector \(0pts\)

• 原题： [ABC302Ex] Ball Collector
• 弱化版：
• 部分分
  • \(20pts\) ：将选 \(a_{i}/b_{i}\) 进行状态压缩判断。

\(T4\) P159. 满穗 \(20pts\)

• 原题： luogu P7028 [NWRRC2017] Joker
• 部分分
  • \(20pts\) ：暴力修改。

总结

• \(T1\) 赛时一直在想小区间怎么合并到大区间，猜结论时不会合理分析样例和性质导致结论猜假了。
• \(T2\) 赛时和赛后转化题面转化得有点绕，很玄乎，没写完。

后记

• 特殊奖励

  

• \(T2\) 因为昨天 \(huge\) 看题后，体活来找学长时说了需要 \(CDQ\) 分治所以就临时换了这道题，正常的话应该和 暑假集训CSP提高模拟6 是一套题，还能和 \(T3\) 题面背景连上。

  

  

• \(T4\) 夹带私货，剧透了《明末千里行》的部分情节。