TCO 2013 Record

由于觉得TC的题目非常好玩！我就把13年的1000pts的题目也做掉了。
vfk每场刷三题比我每场刷一题的速度还快……简直跪傻。

1A DirectionBoard

Description

一个 $n*m$ 的棋盘，每个格子上有一个方向，改变最少的方向使得每一个点顺着箭头出发走都能走回来。

Difficulty

$\bigstar \bigstar$

MainAlgorithm

最小权匹配

Complexity

$O(n^6)$

Solution

即改变最少的边使得整个图被环覆盖。
注意到一个点在环中，只会有一个出点与一个入点。很容易转成匹配模型。
将原有边权值标为0，新增边标为1。
跑KM就好。

1B EllysReversals

Description

给出 $N$ 个串，我们有一个操作：翻转一个长度为偶数的串前缀。定义两串等价为将这个操作进行任意多次后两串相等。
每次我们可以把两个等价的串消掉，问最后剩几个串。

Difficulty

$\bigstar$

MainAlgorithm

连通块
串翻转

Complexity

$O(n^2 * len \log len)$

Solution

显然假如我们能解决判断两个串等价的问题的话，只需要跑一跑联通块，求个大小就好。
我们先看看操作。我们可以通过将三次操作组合起来完成将从奇数位开始，到偶数位结束的串翻转的操作。
假如我们没有偶数这个限制，我们就可以进行任意翻转。包括交换相邻两个。
那么只需要他们的组成元素完全相同就为等价。
加上偶数这个限制之后，我们把相邻两数打个包，一起判等价就好。

1C TheKnights

Description

一个 $N*N$ 的棋盘，上面随机放两个 $(a,b)$ 的马，问被控制的格子的期望个数。

Difficulty

$\bigstar \bigstar$

MainAlgorithm

数学期望

Complexity

$O(1)$

Solution

显然每个格子都是独立的。
对每个格子考虑被控制的概率。只需要知道有几个格子可以控制它就好。设为 $x$，那么它被控制的概率就是 $\frac{2*x}{n^2}-\frac{k*(k-1)}{n^2*(n^2-1)}$.
然后就是艰苦卓绝地讨论。显然不可能人工讨论出来= =。
注意到整个棋盘被划分成了 $5*5$ 块，每个块我们暴力统计一下有多少格子能控制，然后就行了。

2A ThePowers

Description

对于 $X \in [1,A], Y \in [1,B]$，问 $X^Y$ 的不同结果数。

Difficulty

$\bigstar \bigstar \bigstar$

MainAlgorithm

容斥原理

Complexity

$O(\log^4 A + \log^2 A * 2^{15} + A^{3/4})$

Solution

考虑两个数的次幂得到了相同结果，$X_1^{Y_1} = X_2^{Y_2}$.
则 $X_1 = X_2^{\frac{Y_2}{Y_1}}$. 故 $X_2^{\frac{1}{Y_1}}$ 是一个整数。同理可证 $X_1^{\frac{1}{Y_2}}$ 是一个整数。
那么 $X_1^{Y_1} = X_2^{Y_2} = r^{k*Y_1*Y_2}. X_1 = r^{k_1}, X_2 = r^{k_2}.$
我们发现，只有有着共同的 $r$ 的数才会产生冲突。而且冲突的数量与 $r$ 无关。只与最大的 $r$ 的次数有关。我们预处理出来拥有 $k$ 次的 $r$ 能产生的贡献。
即 $(r^x)^y$ 的不同答案数。其中 $x \in [1,\log_r A], y \in [1,B]$.
那么就变为 $x*y$ 的不同答案数。
由于不同的 x 能达到的数不同，为了方便处理，我们分别处理 $(i-1)*B \sim i*B$ 中的数个数。这部分需要考虑的是 $i \sim \log_r A$ 对这段区间的覆盖。
注意到假如 $a$ 是 $b$ 的约数，$b$ 能覆盖到的点 $a$ 全能覆盖到，故 $i \sim \log_r A$ 中(通过搜索发现)去重后最多只有 15 个元素。
那么通过容斥暴力把这部分算出来。
再从 $1$ 枚举到 $\sqrt{A}$，把答案统计出来就好。

2B LitPanels

Description

一个 $n*m$ 的棋盘，选择两个 $x*y$ 的矩形（可以相交），在矩形内任意染黑格子，问最后棋盘状态的方案数。

Difficulty

$\bigstar \bigstar \bigstar$

MainAlgorithm

状压DP

Complexity

$O(n^4+n^2*2^{12})$

Solution

不妨先把结果分类。对答案的状态用一个 $(a,b)$ 的包围盒包裹住，分别讨论 $(a,b)$ 包围盒的方案数。
考虑我们需要满足什么条件。
1、包围盒的每一条边都必须有至少一个染色点。
2、能用两个 $x*y$ 的矩形包裹所有染色点。
将第二个条件转化一下，考虑到矩形的两种摆放方式，变为：有两种区域，至少有一种内部没有染色点。
那么，我们总共就有6个需要考虑的条件。
枚举每一个点，统计出它在那几个条件上。
这样，我们能得到 $2^6$ 个不同的满足情况的条件的点数。
考虑用DP统计合法方案。$f_{i,j}$ 表示考虑到了 $i$ 种点，当前满足情况为 $j$ 的方案数。
转移：$f_{i,j}=f_{i-1,j}+sum_{k ~ or ~ i=j}f_{i-1,k}*(2^{cnt_j}-1)$.

2C WellTimedSearch

Description

A在 $0 \sim n-1$ 中选择了一个数。每一轮，B来猜一个数(不能有无效猜测)，A告诉他是大于、小于还是等于。等于时游戏结束。问游戏在 $l$ 到 $r$ 轮中结束的最大概率。

Difficulty

$\bigstar \bigstar$

MainAlgorithm

数学

Complexity

$O(n \log n)$

Solution

不妨把猜测过程视作一个查找过程，实际上我们就是要找到一个二叉树使得深度在 $[l,r]$ 中的结点数最多。
考虑枚举第 $l$ 层的节点个数。我们就能知道 $1 \sim l-1$ 层的最少结点数。$[l,r]$ 层中的点尽量都满。统计一下就好。

3A TrichyInequality

Description

求出满足 $\sum_{i=1}^m x_i \leq s, \forall i \leq m, x_i > 0, \forall i \leq n, x_i \leq t$ . 的向量 $X$ 的解数。

Difficulty

$\bigstar \bigstar \bigstar$

MainAlgorithm

矩乘加速

Complexity

$O((m-n)^3 log n)$

Solution

标解给的 $O((m-n)^2)$ 太科幻了……不管了，写了个矩乘。
首先我们枚举前 $n$ 个 $x$ 的取值。
则根据简单的组合数学原理我们知道答案是 $\sum_{\sum_{i=1}^n x_i = k, \forall i, 1 \leq x_i \leq t} \binom{s-k}{m-n}$.
注意到那个组合数对于 $k$ 是一个 $m-n$ 次多项式，我们可以比较方便地展开并求出每一项的系数。
将系数提前，就变成了 $\sum_{i=1}^{m-n} a_i * \sum_{\sum_{i=1}^n x_i = k, \forall i, 1 \leq x_i \leq t} k^i$.
如何求 $k^i$ ？
不妨设 $f_{n,m} = \sum_{\sum_{i=1}^n x_i = k, \forall i, 1 \leq x_i \leq t} k^m$.
可以很容易地将 $k$ 写成 $k'+x_n$，然后二项式展开得到递推式。
矩乘加速将 $f_{n,0} \sim f_{n,m-n}$ 求出来即可。

3B ToastJumping

Description

选择尽量少的模长不超过 $\sqrt{D}$ 的整向量，使得他们的和为 $(x,y)$.

Difficulty

$\bigstar \bigstar \bigstar$

MainAlgorithm

凸包
Minkowski 和

Complexity

$O(\sqrt{D})$

Solution

首先，跳跃一步能跳跃到的点是一个凸包内的整点。
然后，由于每一步是相同的，可以证明第 $i$ 次跳跃产生的图形是第 $i-1$ 次跳跃产生的图形与第 $1$ 次跳跃产生的图形的 Minkowski 和。
由于是同一个凸包产生的 Minkowski 和，可以很容易地证明第 $k$ 次跳跃产生的凸包与第一次跳跃产生的凸包相似。
那么，对于在第一个凸包上出现的点 $(x_0,y_0)$ ，其在第 $k$ 次跳跃的凸包中为 $(k * x_0,k * y_0)$.
故我们只需要一开始用 $O(\sqrt{D})$ 的时间把凸包求出来，然后在凸包上找到 $(x,y)$ 对应的覆盖边，把 $k$ 求出来即可。

Semifinal 1 GameWithTree

Description

给出一棵树，每个点有黑白两色。每次操作可以选择一个白色节点染黑，并该节点子树内的节点(除了它本身)任意染色。不能操作者负。问是否先手必胜。

Difficulty

$\bigstar \bigstar \bigstar$

MainAlgorithm

博弈论

Complexity

$O(n)$

Solution

结论：每个白点的SG值，若它的子树最大深度为 $d$，为 $2^{d-1}$.
证明：
1、先证明所有结点是独立的。
首先，一个节点时肯定是独立的。
我们不妨先假设一个状态的后继状态的子局面有着独立性。
我们将一个白色节点翻转之后，白色节点的子树可以任意翻转一些结点。
由于子树有着独立性，所以可以视作新建立了同样结构的子树，需要翻转的部分是白点，现在翻转了根节点的游戏与新建立的子树游戏的合并与原游戏是等价的。
从而，这个翻转的白节点是独立的。
2、再证明每个白节点的SG值为 $2^{d-1}$。
首先，一个独立的白色节点SG值=1.
不妨假设结论成立.
根据SG值的定义，我们只需要使拥有最长链的子树全白，则该点 $SG=2^{d-1}$.
同样，别的子树的SG值没有办法比 $2^{d-1}-1$ 更高。
故定理得证。

Note

我发现我对博弈论理解好浅……= =这个证明搞了两天才大概知道在干嘛……还有细节没理清……

Semifinal 2 OneBlack

Description

一个 $n*m$ 的网格图，一些格子有障碍。一条合法路径的定义是从 $(0,0)$ 到 $(n-1,m-1)$ 的，一共走 $n+m-2$ 步的路径。
你要把一些格子染黑，使得每一条合法路径上恰好有一个黑点。问合法方案数。

Difficulty

$\bigstar \bigstar$

MainAlgorithm

对偶图
DP

Complexity

$O(n^2)$

Solution

首先我们把能从 $(0,0)$ 到的、能到 $(n-1,m-1)$ 的点抠出来。其余的点都是自由的，给答案乘 $2^k$ 即可。
我们观察这些点，他们构成了一个平面图DAG。
考虑一下染色的意义，即一个极小点割。即这个割集中的每一个点都有用而不可删除。
那么，我们把原图转对偶图，在左下角建立S，在右上角建立T，一个合法的方案即为从S到T的一条路径。
DP统计一下就好。

WildCard SemiMultiple

Description

定义一个非负数 $x < 2^n$ 是 $n$ 长度下的 $m$ 的半倍数，为 $x$ 不是 $m$ 的倍数，且 $\exists k < n, x ~ xor ~ 2^k$ 是 $m$ 的倍数。
问有多少个 $n$ 长度下的 $m$ 的半倍数。

Difficulty

$\bigstar \bigstar \bigstar \bigstar$

MainAlgorithm

容斥
DP

Complexity

$O(nm)$

Solution

比较难……
我们肯定是要对每个余数分别讨论的，可以用 $O(nm)$ 的DP很轻松地把 $2^n$ 以下的所有模 $m$ 为 $r$的数搞出来。
这样就能发现只有余数 $r \equiv 2^i ~ (\bmod{~m})$ 或 $r \equiv -2^i ~ (\bmod{~m})$ 时才有可能是半倍数的。
但是也有不合法的，当且仅当应该减去 $2^i$ 的位都是0，应该加上 $2^i$ 的位都是1。
对于每个模数都去DP这个不合法的是 $O(n*m^2)$ 的，显然不行。我们要继续挖掘性质。
我们发现，当 $m=1$ 时，所有数都不合法。
当 $m$是个偶数时，我们讨论第一位的取值。当第一位取 $1$ ，只要剩下的 $n-1$ 位是 $\frac{m}{2}$ 的倍数即可。当第一位取 $0$ ，只要剩下的 $n-1$ 位是 $\frac{m}{2}$ 的半倍数即可。
那么我们只需要解决 $m$ 是个奇数的情况了。而且我们发现 $2^i$ 在模奇数意义下在一个小环内！即实际上 $2^i$ 存在循环节。
我们先将 $r \equiv 2^1 ~ (\bmod{~m})$ 的情况DP出来，我们可以直接利用这个DP的结果得到 $r \equiv 2^k ~ (\bmod{~m})$ 的结果。需要做的只有将整个DP的答案左移即可。
实际上，当 $r \equiv 2^k ~ (\bmod{~m})$ 时，只需要取出在 $n-k$ 位处的DP值，并补上前 $k$ 位的部分即可。
然后一个非常混乱的 $O(nm)$ 的DP就能解决这个问题了。

Note

搞了好久好久……vfk用的循环逆卷积随手虐你敢信……

Finals TBlocks

Description

一个 $n*m$的棋盘，有一些地方摆了o，有一些地方摆了@。
你要在里面放上T形的块，T形块不能有叠加，且T形块的中间那块一定要放在o或@上，且每个o上都要放一个T形块的中心。
@ 不超过12个。
问总共有多少种合法方案。

Difficulty

$\bigstar \bigstar \bigstar$

MainAlgorithm

分类讨论

Complexity

$O(nm*2^k)$

Solution

由于 @ 很少，我们可以枚举它存不存在，就变成一堆 o ，问合法方案数。
两个 o 会互相影响，当且仅当他们的曼哈顿距离不超过2.
这样的话，可能的情况只有三种：相邻的o，对角相邻的o，隔一个空的o。
不妨先考虑隔一个空的o。我们就能得到一张图。开始对于每个连通块分类讨论。
假如只有一个环，就有两种方法摆放。
假如有多个环，则无解。
假如是一棵树，则有 $3N+1$种摆放方法，其中 $N$ 是结点个数。
而相邻的o怎么办呢？我们发现相邻的o只有在两侧都是隔一个空的o形成树的时候才有一个解，否则无解。
对于对角相邻的o，类似也有隔一个空的o形成树的时候才有2个解，否则无解。
还要判断下棋盘边界，边界上的o的摆放也是只能延伸出一棵树的。
故可以先处理所有相邻的o、对角相邻的o、边界上的o，然后再处理内部的o，写起来会方便一些。
将所有部分的方案数乘起来即可。