2019年11月

[Summary]

11月搞颓记录

11-2

Process

现在是下午16:15 今天三道题都不难

T1

[贪心]

直接贪心，每次看当前最小的 + 最大的是否 $\le k$ ，如果是则放两个最小的，否则就放最小的和最大的。正确性显然

T2

[kruskal重构树]

建kruskal重构树，在树上找到子树中最小的 $b$ 去更新答案即可

T3

[动态规划] [背包]

直接dp，设 $dp[i][j]$ 在 $i$ 子树选了 $j$ 个的答案，树上背包转移即可

11-3

搞不动

11-4

Process

状态不好，什么都想不清

T1

[子集和DP]

T2

题意写得*一样

直接算两边的总方案减去不合法方案，再乘起来即可

T3

[动态规划]

简单 DP ，设 $dp[i]$ 表示冻住前 $i$ 长度的最小代价。可以用线段树维护区间最小值做到 $O(n \log n)$

显然这个 DP 数组是单调不降的，于是只要找到最靠前的，能转移到它的位置往它转移就行了，随便搞下就能 $O(n)$ 了

11-5

Process

随便写了个T3，T1T2都不会做

T1

[动态规划] [DP优化]

状态形如若干个段，每个段都满足 $sum(l, r) = r - l + 1$

射击的顺序与答案没有关系，那么可以从左往右考虑，设 $f[i]$ 表示最右边的段以 $i$ 为右端点时的方案数，有转移：

$f[i] = \sum_{j, sum(i, j) = i - j} \sum_{sum (j - k, j) = 0} f[j - k - 1]$

后面那个 $\sum$ 是因为 $j$ 前面那些空的位置实际上都能作为合法的左端点

因为 $sum(i, j) = i - j$ 可以拆成 $sum (1, i) - i = sum (1, j) - j$ ，所以用桶记录就能做到 $O(1)$ 转移

T2

[概率和期望] [方差]

容易发现实际上每一个结点只会在最后一次涉及到它的操作中被影响到，考虑把每一次染色的操作看做是把 x 与它相邻的结点从原所属块中拎出来放在同一个块内，那么最后只要对每一个块分别去考虑即可，并且注意到，块与块之间是不会互相影响的。

用 $c_{i}$ 表示第 i 个块的大小，w 表示白色结点个数，那么推式子得到：

$\begin{aligned} D(w) &= E(w^{2}) - E^{2}(w) \\ &= E( \sum c_{i}^{2} + \sum_{i!=j} c_{i} c_{j} ) - (\sum pc_{i})^{2} \\ \end{aligned}$

注意 $E(\sum c_{i}^{2}) = \sum p c_{i}^{2}$ 而不是 $\sum (pc_{i})^{2}$ ，继续推式子得到

$D(w) = \sum c_{i}^{2} (p - p^{2})$

那么只需要维护 $\sum c_{i}^{2}$ 即可。这个时候就可以 $O(n^{2})$ 做了，即每次暴力把与 x 及与其相邻的结点从所属块中拎出来。

考虑优化，动态维护 $\sum c_{i}^{2}$。 把一次操作看成给它周围的边定向，即一开始每条边全都无向，对 $x$ 操作就是将与 $x$ 相邻的点都指向它

对每个点维护一个 vector, 记录所有它相邻，且未指向它 (包括未定向或指出去) 的点的集合。每次只需要动态更新这些点的 $c^2$ 即可

复杂度是均摊 $O(n\log n)$ 的

inline void update (int x, int d)
{
	ADD (ans, MOD - (LL) size[x] * size[x] % MOD);
	size[x] += d;
	ADD (ans, (LL) size[x] * size[x] % MOD);
}

inline void Solve ()
{
	P = (P - (LL) P * P % MOD + MOD) % MOD;

	while (Q--)
	{
		int op = read<int>();
		if (op == 1)
		{
			int x = read<int>();

			for (int i = 0; i < G[x].size(); ++i)
			{
				int y = G[x][i];
				if (col[y]) update (col[y], -1), G[col[y]].pb (y);
				col[y] = x, update (col[y], 1);
			}

			G[x].clear ();
		}
		else printf("%lld\n", (LL) P * ans % MOD);
	}
}

expr

直接模拟即可

11-7

Process

又是搞一上午T1，太菜了

T1

[数学]

因为所有可以被表示出来的数 num ，总满足 。所以对于模 a 等于 x 的所有数而言，不能被表示出来的数一定是一段前缀。

于是可以对 $x \in [0, a-1]$ 找到最小的 $p$ 满足对于当 且 $num \ge pa$ 时，num 都能够被表示，然后差分标记，每次计算一个长为 a 的段内，不能表示出来的数的数量即可 $O(a+b)$ 计算答案。

考虑优化，发现贡献不同的段实际上最多只有 a 个，所以可以一次性把它们全部计算，就能 $O(a)$ 做了。

T2

[概率和期望] [构造] [贪心]

看到这个题可能直觉会想到一个做法：选一个 x ，把 $< x$ 的全部修改为 x。除此之外，还存在一种方案：保持原来的最小值最小，其它的至少都比最小值大 1 ，这样转只可能转出这些最小值，获得更大的收益。

因为有 37 个盘而倍数为 36 ，所以按下注金大小轮流考虑，在不超过下一个大小的值时下注金一定越多越好。

详见代码。

T3

[二分答案] [最短路] [贪心]

二分答案，问题转化为判断一个前缀是否可以是最短路。

首先这个前缀的边肯定是最小值，而其它边可能是最大值。

考虑两个人同时从起点到终点，第一个人一定走这个前缀，通过控制边权使得第一个人不比第 二个人慢。很容易想到第一个人跑一条边就设为最小值，第二个人跑就设为最大值，但是这样可能会两个人同时经过一条边的情况。

注意到如果其中一个人先走一条边，另一个人后走，那么后走的人肯定追不上先走的了。于是可以把边权按照先到的是第一个人还是第二个人来决定。由于第一个人只要不比第二个人晚到就可以，可以给第一个人的最短路长度 −0.5 来避免同时到。

具体而言，把边权翻倍并初始化 dis(1)=1 ，确定当前前缀的边权最小，然后初始化前缀末尾的 dis ，然后做 dijkstra ，这样就可以通过当前 dis 是奇还是偶来判断是谁先到达的了。注意理解除去前缀末尾，其余的点都不能初始化 dis ，否则可能会错误地用其更新到 dis(2) ，达不到强制第一个人走前缀的效果。

11-8

Process

T1总共花了50分钟，T2想 $O(n*k^2)$ 做法想了很久，T3写完暴力后想到了答案序列一定形如 $2^x3^y$ 但是来不及写了

T1

[树状数组] [计数]

发现就是要对每条连接$x$和儿子$y$的边$(x, y)$，求出$y$子树内有多少个点的编号大小比$y$大

把子树转化成祖先，树状数组统计答案即可

T2

[概率和期望] [组合数学] [树形DP] [背包]

统计方案数，考虑每个联通块的贡献，一个大小为 $x$ 的联通块对第$k$次询问的贡献就是 $x^k$

我考场上的$O(nk^2)$的做法就是直接维护这个答案，设$f[x][i]$表示$x$子树内，所有包含$x$的联通块的$x^i$之和

树上背包，考虑一个大小为$a$的联通块和一个大小为$b$的联通块如何合并，显然合并之后对答案的贡献就是 $(a + b) ^ i$

暴力直接二项式展开，即 $\sum_{j = 0} ^ i a^jb^{i - j}$，于是可以利用已经计算好的$f[][j]$和$f[][i-j]$相乘来计算答案了

---

下面是$O(nk)$的正解

考虑用经典组合式子把$x^k$拆开

看成球盒问题，枚举空盒个数，具体见此

那么我们只需要对于每个$i\in[0, k]$快速计算 $\displaystyle \Big(\sum \binom{x}{i}\Big)$ 即可。注意到此时我们已经将限制变得更加严格，现在选出来的$i$个关键点必须是互不相同的，可以直接通过树上背包DP计算得到。这样做 DP 的话第二维就能对$size$取min了，复杂度是$O(nk)$的

T3

显然第一个数一定形如$2^x$或$2^x3$，那么就很好 DP 了。

设 $f[i][x][y]$ 表示填到第 $i$ 个数，前$i$个数的$gcd$ 为$2^x3^y$的方案数（$x\in[0, \log n], y\in [0, 1]$）转移很简单，见代码

11-9

Process

40分钟把T1T3写完了，然后T2一开始写了一个假做法，因为时间比较充裕，所以有足够时间重新想做法，最后还是过了

题解不想写了

11-10

两道期望一道概率

11-11

Process

三道计数，T2T3都很简单，T1其实也很简单，但是考场上没想到，写了一个复杂度和$k$相关的暴力，居然过了（考后自己卡T了）

T1

[动态规划]

发现就是要优化一个这样的四方DP：

for (int i = 1; i <= N; ++i)
	for (int j = 1; j <= M; ++j) if (A[i] == B[j])
	{
		for (int a = 0; a < i; ++a) for (int b = 0; b < j; ++b) if (A[a] == B[b] && Map[A[a]][A[i]])
			ADD (Dp[i][j], Dp[a][b]);
		ADD (ans, Dp[i][j]);
	}

首先可以把 $a$ 这一维用前缀和优化掉，这样是 $O(n^3)$ 的，因为还是需要枚举 $b$

但是显然，对于不同的 $j$, 在枚举 $b$ 时有很大一部分是重复枚举的。再记一个前缀和即可

讲不太清，不如看代码

Dp[0][0] = 1; prefix[0] = 1;
int ans = 0;
for (int i = 1; i <= N; ++i)
{
	int res = 0;
	for (int j = 0; j <= M; ++j) 
	{
		if (A[i] == B[j]) Dp[i][j] = res, ADD (ans, Dp[i][j]);
		if (Map[B[j]][A[i]]) ADD (res, prefix[j]);
	}

	for (int j = 0; j <= M; ++j) if (A[i] == B[j]) ADD (prefix[j], Dp[i][j]);
}

cout << ans << endl;