Codeforces Round #418 (Div. 2)

Chinese Round. 是说时间怎么这么友善...... 不是很难. 比赛的时候完成了前4道. 离比赛结束还有40s的时候交了一发D, 然而...... CE了...... 一开始以为是C++11的锅, 结果发现M_PI这个常量不是标准库里的. GG...... 比赛结束后又交了一发, A掉了......TAT 本场比赛很多题目都是多解的 (我做出的也不是最优解法 TAT), 兹磁一个......D的贪心很妙. E是个不错的DP题. 题解: 5/5 # A. An abandoned sentiment from past 两个长度分别为n,k的序列a,b, 元素两两不同. a中有k个空位. 问是否能以某种顺序把b插入a, 使得a不是单调递增序列. (2≤n≤100, 1≤k≤n)

元素两两不同告诉我们, 当k>1时直接回答 Yes (只需把b倒序插入). 当k=1时, 验证一下即可.

B. An express train to reveries

p是1到n的一个排列. 长度为n的序列a,b各恰有一个元素在对应位置与p不同. 保证a,b至少有一位不同. 求一个可能的p, 保证有解. (2≤n≤1000, 1≤ai,bi≤n)

设ai≠pi, bj≠pj, 那么除了i,j, 其余位置a,b对应元素相等, 且等于p的对应元素. 据此可以得出一或两个空位, 及备选元素. 枚举并验证.

为了得到i,j, 还可以这样判断: a,b中出现了两次的元素和一次都没出现的元素.

C. An impassioned circulation of affection

一个长度为n, 由小写字母组成的字符串, q个询问: 至多改变m个字符, 连续一串c的最大长度是多少? (1≤n≤1500, 1≤q≤2*10^5)

n的范围较小, 提示我们可以大力预处理一波.

先考虑一下怎么验证一个答案. 可以得到长度为k的字符串, 当且仅当存在区间[i,i+k), 其中不是c的字符个数≤m.

长度为k的子串中, 非c的最小个数cnt(c,k), 这个量是关于k非严格单调递增的. 每个长度为k的区间, 向右扩展一位, 非c的个数要么不变, 要么+1. 如果一个区间没有取到cnt(c,k)的最小值, 那么它扩展出来不会优于取到最小值的任一区间[i,i+k). 因此, cnt(c,k+1)=cnt(c,k)或cnt(c,k)+1.

预处理出来, 就可以二分了. 时间复杂度 .

事实上, 可以直接预处理答案: 非c的个数对应的最大长度k, 取前缀max, 得到非c的个数不超过x, 对应的最大长度.

two-pointer也是可以的. , 适合字符集很大的时候.

D. An overnight dance in discotheque

平面上有n个两两不在多于一点相交的圆(xi,yi,ri). 把它们分成两个集合A,B, 一个集合的价值等于平面上被圆面覆盖奇数次的面积之和, 求两集合价值之和的最大值. (1≤n≤1000, -10^{6≤xi,yi≤10}6, 1≤ri≤10^6)

看到几何题有点虚......然后发现和几何算法关系不大. 可以抽象出一个有根树森林的模型. 令每个点的权值为圆的面积. 则一棵树的价值=奇数层点权和-偶数层点权和 (0-indexed). 设 为子树 中, A最高一层的层数在最终形成的树中的奇偶性为 , B最高一层的层数在最终形成的树中的奇偶性为 , 最大价值. 即为答案.

一个圆可能被很多圆所包含, 哪一个才是它在树上的父亲呢? 发现只用比较面积. 面积最小的一个就是了.

另外有一个贪心算法: 对于每一棵有根树, 将它的根划分到集合B, 其余划分到集合A.

让我们来证明其正确性 (感谢仓鼠大爷的帮助 QwQ 简单起见采用了下面这个数学归纳法版本). 记一个节点集合 所形成的虚树的价值为 , . 对于本题, 任意 满足 . 把 分成 两个不相交的部分, 即 . 同时证明以下3个结论: 1. 当 时, 最大. 2. 当 时, 最大. 3. 当 时, 最小.

首先, 对于 , 这些结论是平凡的. 当 , 不妨令根节点在 集合. 对于结论 1,3, 由对称性可知合理; 对于结论2, 当 , . 去掉根节点后, 我们得到一些规模小于 的子树. 现在, 需要把子树划分为 两部分, . 每棵子树是独立的. 1. 最大. 由归纳假设, , 故 . 2. 最大, 即 最小. . 3. 最小, 即 最大. .

证毕.

如果用贪心算法, 树不用显式地建出来, 只用数一数每个点有多少个祖先.

建树可以做到 : BST (std::set) + 扫描线. 由于圆只有相离和包含关系, 所以竖直方向上的相对顺序不会变化. 把圆分为上半弧和下半弧两个部分. 插入一个上半弧, 如果上方没有弧, 则它是根; 否则, 最靠近它的是上半弧, 则找到了它的父亲; 否则, 找到了它的兄弟. 怎么在竖直方向上比较两道弧呢? 代值计算......本题有两圆相切的情况, 所以用圆的半径作排序的第二关键字.

E. An unavoidable detour for home

求满足以下条件的 个点的无向图的数目, 答案模 : - 没有重边, 自环 - 1号点到每个点的最短路 (经过边数最少的路径) 存在且唯一 - 设 为 到 号点的最短路, 则 - 已知第 个点的度数为

先来挖掘一下性质. . 称最短路为 的点为第 层, 那么第 层的每个点向上一层连1条且仅1条边, 剩下的边连向本层或下一层.

依次考虑每个点向之前的点如何连边, 很容易设计出这样的状态: 为前 个点, 倒数第二层有 个 1-plug, 个 2-plug, 最后一层有 个 1-plug, 个 2-plug, 的方案数. k-plug (插头) 指还有 k 个度数没有分配的点. 转移的话, 按照第 个点的度数, 所在的层数, 分类讨论; 只有 时才能新建一层.

这样做是 的, 由于常数可以很小, 足够通过本题.

可不可以直接记录还有多少个有待分配的度数 (插头的总数) 呢? 之所以记录点, 是为了防止重边. 由于每个点最多向倒数第二层连一条边, 所以倒数第二层可以直接记录度数; 最后一层还是记录点数. 这样带来了一个变化: 某点连向倒数第二层某 2-plug 的第1条边和第2条边, 算做两种不同的方案了. 那么, 顺其自然, 令每个点的三条边可区分, 最后除以 .

这样做是 的, 同样可以AC, 代码见后面.

在Editorial里看到, 有 的做法.

我们不再一个一个添加点, 而是一层一层考虑. 假设已经完成了 的连边, 距离为1的点为 . 现在往前添加一层 . 中的 个点, 每个恰向 连一条边; 中的点, 每个预留一个插头供拼接到上一层使用, 其余在内部连接, 或者连向下一层. 和 连接的方案数只和 的度数以及 有关, 不妨先DP出来. 设 为一层有 个 1-plug, 个 2-plug, 拼接有 个点的新一层的方案数; 这里, 考虑原来一层内部的连边, 但不考虑新一层内部的连边. 借助 数组, 我们就可以DP出 了: 考虑 , 最短路为1的一层为 , 每个点预留一个接向上一层的插头, 方案数. 最终的答案是 (1-indexed). 1号点肯定向 连边.

出于某种原因, 把上面这段翻译了一下.

We can conclude that . So the vertices are divided into some layers according to their distance to the vertex 1. Except the vertex 1, each vertex has exactly one edge connected to the previous layer, and the others connected to the succeed layer or a vertex in the same layer.

Let's add the vertices from left to right one by one. We call an edge with one endpoint that hasn't been decided a plug. Then, what we need to know is the number of the plugs. That's not enough. To avoid multiple edges, we need to record whether two plugs are from the same vertex. So our state is dp[number of vertices][number of 1-plug vertices in the previous layer][number of 2-plug vertices in the previous layer][number of 1-plug vertices in the current layer][number of 2-plug vertices in the current layer]. Only when number of 1-plug vertices in the previous layer = number of 2-plug vertices int the previous layer = 0, can we open a new layer. This algorithm is , but it runs fast in practice.

Since there are at most 1 edge connected to the previous layer for a vertex, we can simplify the state into dp[number of vertices][number of plugs in the previous layer][number of 1-plug vertices in the current layer][number of 2-plug vertices int the current layer]. Now, the plugs from the same vertex become distinguishable, so we need to do some division to avoid repetition. This algorithm is .

Let's add a layer in one time instead of a vertex. Assume that we've finished . To add , we enumerate the first layer in ; let it be . Since links between vertices in have already been arranged, all we concern is and the number of 1-plug and 2-plug vertices in . Let's do dp with state dp[number of 1-plug vertices in the first layer][number of 2-plug vertices in the first layer][number of vertices in the second layer]. Then, use array dp to collect our final answer. This algorithm is .

Sorry for poor English...

#define LLFORMAT "I64"

typedef long long ll;

const int MOD = 1e9 + 7, N = 51;

int d[N];
ll f[N][2*N][N][N];

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 0, n) scanf("%d", d+i);
	if (d[1] == 2)
		f[1][d[0]-1][1][0] = d[0] * d[1];
	else
		f[1][d[0]-1][0][1] = d[0] * d[1];
	rep (i, 1, n-1) rep (j, 0, 2*n+1) rep (k, 0, n+1) rep (l, 0, n+1)
	{
		ll now = f[i][j][k][l];
		if (now == 0) continue;
		
		if (j > 0)
		{
			if (d[i+1] == 2)
			{
				ll tmp = j*2*now;
				(f[i+1][j-1][k+1][l] += tmp) %= MOD;
				if (k > 0)
					(f[i+1][j-1][k-1][l] += tmp * k) %= MOD;
				if (l > 0)
					(f[i+1][j-1][k+1][l-1] += tmp * l * 2) %= MOD;
			}
			else
			{
				ll tmp = j*3*now;
				(f[i+1][j-1][k][l+1] += tmp) %= MOD;
				if (k > 0)
				{
					(f[i+1][j-1][k][l] += 2 * tmp * k) %= MOD;
					if (k > 1)
						(f[i+1][j-1][k-2][l] += tmp * k * (k-1)) %= MOD;
				}
				if (l > 0)
				{
					(f[i+1][j-1][k+2][l-1] += tmp * l * 4) %= MOD;
					if (k > 0)
						(f[i+1][j-1][k][l-1] += tmp * l * 4 * k) %= MOD;
					if (l > 1)
						(f[i+1][j-1][k+2][l-2] += tmp * l * (l-1) * 4) %= MOD;
				}
			}
		}
		else
		{
			int p = k + 2*l;
			if (d[i+1] == 2)
			{
				ll tmp = p*2*now;
				(f[i+1][p-1][1][0] += tmp) %= MOD;
			}
			else
			{
				ll tmp = p*3*now;
				(f[i+1][p-1][0][1] += tmp) %= MOD;
			}
		}
	}
	ll ans = f[n-1][0][0][0];
	rep (i, 0, n)
		(ans *= (d[i] == 2 ? 500000004 : 166666668)) %= MOD;
	printf("%" LLFORMAT "d\n", ans);
	return 0;
}