2022牛客暑期多校训练营2 ¶

排名	当场过题数	至今过题数	总题数
29/1381	9	12	12

A¶

upsolved by JLK

题意¶

\(n\)个点的凸包，选\(k\)个点，求新凸包的最大周长。

\(3 \le k \le n \le 2000\)

题解¶

显然有一个\(O(n^3k)\)的做法：枚举起点，\(dp_{i,j}\)表示前\(i\)个点选了\(j\)个点，且第\(i\)个必须选，此时凸壳的最大周长。

然后不难发现这个是决策单调的。也就是说，如果\(y\)的最优决策是从\(x\)点转移过来，那么\(y+1\)的决策点不会小于\(x\)。使用决策单调可以优化至\(O(n^2k\log n)\)。

由于每个凸包是在原来的点里面选若干个，把其中每个点看做起点都是一样的。一种想法就是随机选一个点作为起点，多跑几次。一个起点的复杂度为\(O(nk\log n)\)。随机\(C\times \frac nk\)个点，调参就可以过了。实测\(C=10\)可过。

训练中想到了wqs二分，就是每条边减去一个权值跑一遍，跑出选任意多点的最大周长，看选的点数来调整二分。同样用决策单调来优化。正确性似乎没问题，但是由于带两个log，TLE了。

题解做法是把dp看做矩阵乘法来倍增优化，并且只考虑编号小的到编号大的点，最后枚举一条编号大的到编号小的边来计算答案。

C¶

solved by TYB

题意¶

玩传统nim游戏：\(n\)堆石子，第\(i\)堆有\(a_i\)个，每次从一堆拿走\(>0\)个，无法操作者输。必胜者想在最少的轮数内结束，必输者想在最多的轮数内结束，求进行的轮数和先手的操作方案数。

\(n\le10^5,a_i\le10^9\)

题解¶

结论：从一个必输局面开始，一定是每人轮流拿一个。因为必输者存在以下策略：选一堆lowbit最小的石子，并从中拿走一个，这样必胜者也只能从另一堆lowbit最小的石子中拿走一个才能使SG值为\(0\)（由于必输者操作之前SG值为\(0\)，所以至少有两堆lowbit最小的石子）。这样第一问就解决了。

对于先手必胜的情况，有了上面的结论，只需要尽量拿得多即可。所以方案数也很好求。

但对于先手必输的情况，虽然用上面的结论可以构造一种方案，但并不能包括全部情况。比如对于2 2 4 4四堆石子，先手从哪堆拿一个都可以。假设我们在最低位的\(1\)在第\(k\)位的石子堆拿走一个，那么对于SG值的变化是反转了\(0\sim k\)位。那么对于必胜者，想让SG又变为\(0\)，它显然只能操作在最低位的\(1\)在第\(k\)位的石子堆，其\(0\sim k-1\)位必须为\(0\)（否则就可以拿很多个石子）。

D¶

solved by TYB

题意¶

找负环。

题解¶

可以SPFA，因为其下限就是Bellman-Ford，只需要看每个点的入队次数。

Bellman-Ford代码：

// C++ Version
struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn];
const int inf = 0x3f3f3f3f;

bool bellmanford(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0;
  bool flag;  // 判断一轮循环过程中是否发生松弛操作
  for (int i = 1; i <= n; i++) {
    flag = false;
    for (int u = 1; u <= n; u++) {
      if (dis[u] == inf) continue;
      // 无穷大与常数加减仍然为无穷大
      // 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
      for (auto ed : e[u]) {
        int v = ed.v, w = ed.w;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          flag = true;
        }
      }
    }
    // 没有可以松弛的边时就停止算法
    if (!flag) break;
  }
  // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
  return flag;
}

E¶

solved by JLK

题意¶

\(F_{n,k}\)表示长度为\(n\)的小写字母构成的串中，恰好包含\(k\)个bit串的个数。

求出\(F_{n,0},\cdots,f_{n,n}\)。

\(1 \le n \le 10^6\)。

题解¶

考虑容斥。

\(f_i\)表示长度为\(n\)的串当中至少出现\(i\)次bit的个数。\(g_i\)表示恰好\(i\)次的个数。

\(f_i=26^{n-3i}\times C_{n-2k}^k\)

\(g_i=f_i-\sum\limits_{j=i+1}^n C_i^j \times g_j\)

移项，\(f_i=\sum\limits_{j=i}^n g_j\)

把所有下标都翻转一下，令\(f'_i=f_{n-i},g'_i=g_{n-i}\)

然后移项，最终可以得到\(i!(n-i)!f'_i=\sum\limits_{j=0}^i C_i^ jj!(n-j)! g'_j\)

二项式反演得到\(j!(n-j)! g'_j=\sum\limits_{i=0}^j (-1)^{j-i} C_j^i i!(n-i)!f'_i\)

直接NTT即可，答案\(F_{n,i}=g_i=g'_{n-i}\)。

\(O(n\log n)\)

F¶

upsolved by TYB

题意¶

给定一个字符串 \(s\) 和 \(n\) 个匹配串 \(t_i\) ，\(Q\) 次操作，有以下四种：操作 1：在一个匹配串 \(t_i\) 的，末尾加上一个字符 \(c\) 操作 2：删除 \(s\) 的末尾 \(p\) 个字符操作 3：在 \(s\) 的末尾增加 \(k\) 个字符 \(c\) 操作 4：询问有多少个匹配串的字典序严格小于 \(s\) \(n, Q \le 2 \times 10^5\)，仅包含小写字母

题解¶

建trie，若按照字典序dfs，那么对于一个节点表示的串，比其字典序小的串就是所有dfs序比它小的节点表示的串。所以如果操作\(2、3\)只改动一个字符，就可以暴力搞了。考虑优化。

对于操作\(3\)，维护一个\(trans_{x,c}\)表示从\(x\)节点开始一直加\(c\)这个字符最后回走到哪个节点。如果走过头，可以倍增跳回来；如果走到尽头还不够，那么可以维护一个栈，表示当前的串后面还有哪些字符。

对于操作\(2\)，如果栈非空就暴力删栈中的元素，均摊一下复杂度没问题；删完后就倍增跳回去。

注意操作\(2\)的\(p\)可能爆\(\rm{int}\)。

G¶

solved by YZW

题意¶

签到。

题解¶

利用众所周知不言自明的结论稍加构造即可，略。

H¶

solved by JLK

题意¶

\(n\)个人坐电梯，电梯最多装\(m\)个人，共\(k\)层。

电梯只有在底层可以从向下变成向上，而在任意位置都可以向上变成向下。

走一楼花费1单位时间，进出不消耗时间。

求运完所有人最小时间。

\(1 \le n,m \le 2\times 10^5,1 \le k \le 10^9\)

题解¶

一眼贪心。

首先肯定是把向上和向下分开考虑，每上下一趟分别运向上和向下的两批人。

只考虑向上，一种策略是第一次送到达层数最高的\(m\)个人，第二次送剩下的人中到达层数最高的\(m\)个人……

至于为什么这样是最优的，考虑到达最高的那一个人，肯定总有一次要运他，而且时间取决于到达层数。那么不妨同时把其他到达层数比较高的人一起运了，否则这些人还要再花一趟来运，花费时间很多。

然后还需要考虑一个事情，就是可能在一次向上的过程中先运了A，A下去后B上来，接着运B。这样我们把AB看做是合体的一个人来运。而合体的策略就是按到达层数从高到低扫，每次判断有没有出发层数大于等于当前到达层数的人，如果有就合体。和上面想法差不多，肯定是到达层数高的人优先合体，否则不优。用set或者堆维护即可。

合体之后分批，可以求出来向上的一批批人，每批人的到达层数max。同理求出向下的每批人的出发层数max。考虑到一趟要送上去和下来的两批人，把两边的层数取max就是一趟的层数。两边一定都是从高到低来跑。

\(O(n\log n)\)

I¶

solved by YZW

题意¶

无聊的签到题。

题解¶

真无聊啊，略。

J¶

solved by YZW

题意¶

签到。

题解¶

略。

K¶

solved by YZW

题意¶

签到。

题解¶

略。

L¶

solved by YZW

题意¶

签到。

题解¶

略。

记录¶

13min：YZW AC K

17min：YZW AC G

开搞二项式反演 E，jgg 开写

🐍打断 jgg 两次，在 jgg 重新推式子的间隙开搞

52min：YZW AC J

68min：YZW AC L

76min：JLK WA E

93min：YZW AC I

97min：JLK AC E

114min：TYB AC D

134min：JLK AC H

开始搞 C，中途各种分析

155min：TYB WA C

171min：TYB WA C

187min：TYB AC C

感觉 A 最可做，开始搞 A，不会，猜做法 WA 3 次

总结¶

YZW：BIT = Boring ICPC Training，后面的 GIJKL 是真的无聊。= =

Dirt¶

C(-2)：结论不对

E(-1)：看起来式子有问题

2022牛客暑期多校训练营2¶

A¶

题意¶

题解¶

B¶

题意¶

题解¶

C¶

题意¶

题解¶

D¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

H¶

题意¶

题解¶

I¶

题意¶

题解¶

J¶

题意¶

题解¶

K¶

题意¶

题解¶

L¶

题意¶

题解¶

记录¶

总结¶

Dirt¶

2022牛客暑期多校训练营2 ¶