0716

A?

先考虑已知选取的线段如何算出答案：维护一个 \(pos\) 表示当前处理到的最右端的右端点，每次在 \(pos < l\) 的线段中选出 \(r\) 最小的一个，感性地理解这是最优的。

再考虑原问题：使用 DP，令 \(f_{i,j}\) 表示 \(pos = i\)，已经选取了 \(j\) 条合法线段的方案数，枚举下一条选取的线段的右端点 \(k\) 进行转移。

• \(i < l \le r = k\) 的线段（目标线段）有 \(k - i\) 条，可选或不选，但必须有一个；

• \(i < l < r < k\) 的线段已经在其他情况下被提前统计，不能选；

• \(i < l \le k < r\) 的线段有 \((n - k) \times (k - i)\) 条，可选或不选。

暴力进行 DP，\(O(n^3)\)，足以通过。

B

有一个巨蠢的容斥做法，但由于枚举子集时间无法接受。

考虑 DP，令 \(f_{i,j}\) 表示 \([1,i]\) 中至少被 \(a_{1 \dots j}\) 中一个整除的数有多少，则答案为 \(n - f_{n,k}\)。

则有转移：\(f_{i,j} = \left\lfloor \frac{n}{a_i} \right\rfloor + f_{i,j-1} - f_{\left\lfloor \frac{n}{a_i} \right\rfloor, j-1}\)，时间复杂度 \(O(nk)\)

注意到 \(\left\lfloor \frac{n}{a_i} \right\rfloor\) 的取值很少，下面说明：

• 在 \(x\) 从 1 到 \(\sqrt{n}\) 的区间内，有 \(O(\sqrt{n})\) 个不同的值。
• 在 \(x\) 从 \(\sqrt{n}\) 到 \(n\) 的区间内，虽然 \(x\) 的个数是 \(O(n - \sqrt{n})\)，但是这些 \(x\) 所对应的取整值总数最多也只有 \(O(\sqrt{n})\) 个，原因是当 \(x = \sqrt{n}\) 的时候，原式取值已经下降到 \(\sqrt{n}\)。

因此有效的状态数仅有 \(O(\sqrt{n}k)\) 种，考虑用记忆化来优化过程。

然而发现数组开不下，那我们只对有效状态分布密集的小段进行记忆化，即预先设定 \(lim\)，对 \(i < lim\) 记忆化。

一个技巧是先将 \(a\) 排降序，这样可以使得 \(i\) 这一维度下降更快，更有利于记忆化的命中。

C

CF1371F

巨大分讨题，跳过。

D

至今没会。

0717

A

首先，最大的伪光滑数所有质因数相同。如果一个合法的伪光滑数有不相同的质因数，我们把小的质因数全部换成最大的，需要满足的式子 \(a_k^k \le n\) 中，\(k\) 没有变化，所以这个数仍旧合法，却比原来的数大。

那只需要一个堆维护，每次取出其中的最大值，若其最大质因数的次数大于 \(1\)，就减 \(1\) 然后丢回去，重复 \(k\) 次即为答案。

一个细节是堆里的元素应维护一个 \(lim\)，记录上次替换成的质因子，否则可能会出现重复（例：\(X / 2 / 3\) 和 \(x / 3 / 2\)）。

while (k--)
{
	node now = q.top(); q.pop();
	if (!k)
	{
		cout << now.v << endl;
		return 0;
	}
	if (now.k > 1)
		for (int i = 1; i <= now.nxt; i++)
			q.push(node{now.v / now.p * pr[i], now.p, now.k - 1, i});
}

D

\(n \le 22\)，考虑状压。

首先可以一个数组 \(a\) 把每个人的朋友压进去。

令 \(f_s\) 表示达到状态为 \(s\) 的最小花费，转移直接把 \(a\) 数组或进去就行，细节很少。

E

注意到把所有数字按二进制字符串拼起来长度增长很快，但总长小于 \(75\)，可以得到结论 \(num \le 20\)（选取了 \(1 \dots num\)）。

这提示我们进行状压，令 \(f_{i,k}\) 表示第 \(i\) 位前有最后一次切割且得到数字 \(1 \dots 20\) 的状态为 \(k\)，转移可表示为：

f[k + 1][j | (1 << (sum[i][k] - 1))] += f[i][j];

复杂度 \(O(n^3)\)，足以通过此题。

0718

A

考虑一个合法的拼接，必须满足：

• 各个拼接前的串内部 \(\texttt{1}\) 间隔为 \(m\)；

• 接口处的 \(\texttt{1}\) 间隔为 \(m\)。

先对整个字符串集合判一遍条件 \(1\)，条件二可以把每个字符串抽象成两个接口，然后寻找一条合法的拼接顺序。这让人想起欧拉路径。

于是问题转化为求字典序最小的欧拉路径，对邻接表排序后上板子即可。

BCD

都没补。

0719

A

考虑一个子问题：如果已经知道了这个数列的 \(\gcd\) 为 \(d\)，那么应该怎么找到最小值呢？

首先，设一个数列 \(d_i\) 表示只进行操作 2，\(a_i\) 满足条件所需要的花费，显然若 \(a_i\) 为 \(d\) 的倍数则为 \(0\)，若 \(a_i \pm 1\) 为 \(d\) 的倍数则为 \(b\)，否则就是 inf。

然后分两种情况讨论：

• 没有 inf：

  此时需要找到一段区间 \([l,r]\) 直接删掉，让 \(d_{l \dots r} = a\) 且 \(\displaystyle \sum_{i = 1}^n d_i\) 最小。

  考虑选取了点 \(i\)，那么会对答案产生 \(a - d_i\) 的贡献。相当于找到序列 \(a - d_i\) 的最小子段和，在 \(\displaystyle \sum_{i = 1}^n d_i\) 的基础上加上这个最小值就可以了。

  具体操作可以把所有数取相反数，然后求最大字段和。

• 存在 inf：

  设最左边的 inf 的位置为 \(l\)，最右边的 inf 的位置为 \(r\)，那么 \([l,r]\) 这段区间必须要被删除，然后对于区间 \([1,l-1]\) 和 \([r+1,n]\) ，需要各自找到一个分界点使花费最少。

  设 \(d_i\) 的前缀和为 \(sum_i\)，那么显然前一个区间的最小花费就是 \(\min \left\{ sum_{i-1} + (l-i) \times a \right\}\)，可以 \(O(n)\) 解决。后面同理。

于是我们就解决了这个子问题。

再回到原题，因为不能全部删除，所以 \(a_1\) 和 \(a_n\) 中必有一个数不会被删除，既然不被删除，那么这个 \(d\) 就必然是 \(a_1,a_1-1,a_1+1,a_n,a_n-1,a_n+1\) 这六个数中任意一个数的约数。

此外，显然当 \(d\) 是质数的时候是更优的，那么可行的 \(d\) 就很小了（一个数最多由 \(9\) 个不同的质数组成），对于每个 \(d\) 做一遍子问题，原问题得解。

B

先考虑第一个限制：

• 若 \(1\) 结点的度数小于 \(k\)，显然无法满足条件，直接输出 impossible；

再处理第二个限制：

把除了 \(1\) 结点之外的所有点都进行连边，则原图就变为了一个个连通块，接下来的任务是从 \(1\) 号节点向其他连通块连边。

若连通块个数大于 \(k\)，\(1\) 号点的度数不够把图连成连通，输出 impossible。

若存在一个连通块不能到达 \(1\) 号结点（即该连通块中每一个点都不能连向 \(1\)），也无法使原图连通，输出 impossible。

其余所有情况都是可能的，输出 possible。

实现上，我们肯定不能暴力连边然后求连通块，这样干复杂度爆炸，所以我们使用 set/unordered_set 来维护未访问过的元素，使用 BFS 来找连通块即可。

C

套路是看到前缀的字眼就把字典树建出来，建完后每个字符串对应字典树上的一个节点。

题目要求每个字符串都不相同，考虑一个贪心：每次把子树中最深的字符串提升到根节点，感性理解这种贪心是正确的。

这样我们可以在每个节点建一个大根堆，每次操作把最大的数变成 \(0\) 然后把子节点的信息合并到父节点。

看起来这需要一个可并堆，但仔细思考会发现所有堆中元素的个数是 \(O(\Sigma |S|)\) 的，操作的复杂度则是 \(O(\Sigma |S| \log \Sigma S)\) 的，足以通过本题。

DE

没补

F

贪心地，可以让实力强的人打败比朋友强的选手，比朋友弱的无需考虑。

考虑如何贪心最贪心：让 \(n\) 号选手干掉后一半的选手，如果朋友干不掉前一半就让一个人再干掉前一半的一半。

实现只需要维护一个小根堆，记录路径上便宜的人，每到 \(2\) 的次幂就贿赂一个最便宜的，代码非常短。

signed main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int ans = 0;
	priority_queue<int, vector<int>, greater<int>> q;
	for (int i = n; a[i] != -1; i--)
	{
		q.push(a[i]);
		if ((1 << (int)log2(i)) == i)
			ans += q.top(), q.pop();
	}
	cout << ans << endl;
	return 0;
}

0720

失败了，一个没补出来。

0721

休息日。