AtCoder Grand Contest #016 - Click Here
Problem A
Solutions
考虑枚举最后变成的字符，此时每次操作等价于字符串中所有枚举字符向前扩展一位，顺序统计答案即可。
时间复杂度$O(|s||\Sigma|)$
CODE
CODE - Click Here
Problem B
Solutions
假设所有颜色数为$T$，显然有$T-1 \leq a_i \leq T$。
若$a_i=T-1$表明该颜色只出现一次，若$a_i=T$表明该颜色至少出现两次。
因此通过寻找$a_i$的最小最大值，即可确定$T$的取值；再利用上诉限制判断是否合法即可。
时间复杂度$O(N)$
CODE
CODE - Click Here
Problem C
Solutions
考虑最小化每个$h \times w$矩形的和，最大化整个矩形的和。
显然有仅在$(ph,qw), \quad p,q \in N^+$处放负数，其余处放正数答案不会劣。
假设所放置的正数为$c_{x,y}$，则负数应为$-max\{1+\sum c_{x,y}\}$。为保证总和最大，$max$内每项应该相等，即$c_{x,y}$为定值。因此可令放置的正数均为$c$，则负数为$(1-hw)c-1$。
另一方面，注意到该矩形被划分成若干个$h \times w$的小矩形和一些零散的板块，且每个小矩形的和均为$-1$。因此矩形的总和与$c$正相关。
考虑最大化$c$，由给定的范围知$-10^9 \leq (1-hw)c-1, \quad c \leq 10^9$，解该不等式即可。
时间复杂度$O(HW)$
CODE
CODE - Click Here
Problem D
Solutions
易知题目给定的操作等价于一次交换操作，因此现在题目变成给定一个$a_i$数列，且有一个临时位置，初始时该位置保存的是所有数字异或和。现允许将$a_i$数列中任意一个数字与临时位置交换，求最少操作次数使得$a_i$变为$b_i$。
显然，有解当且仅当以上$n+1$个数字包含$b_i$。
现在考虑构建如下图，$(V,E), \quad E=\{(b_i,a_i) | 1 \leq i \leq n\}$，表明可以通过失去$b_i$得到$a_i$。则该题的答案相当于给定起点，要求用最短的路径去覆盖所有点，且路径之间会产生额外一点代价。
因此现在的问题变为如何在一个连通图内寻找到一个最小代价的路径覆盖解。注意到这样一个事实，如果答案有解，则必定存在一条路径能够覆盖连通图所有点。这是因为有解的条件为$n+1$个数包含$b_i$，若连通图无法由一条路径覆盖，则表明$n+1$个数中，至少有两个数不属于$b_i$，这与有解条件冲突。
基于以上事实，只需要利用并查集统计连通块个数以及大小即可计算答案。
时间复杂度$O(N\alpha(N))$
CODE
CODE - Click Here
Problem E
Solutions
不妨先考虑一个弱化问题，如何保证$i$号turkey能够存活。
考虑一对关系$(x,y)$，如果强制$x$存活，则表明在此之前$y$亦能够存活。因此可考虑自底向上进行维护一个集合$S_i$，表明为了维护$i$存活，需要保证存活的turkey集合。
一个很显然的点是，经历以上所有关系后，$S_i$集合内的所有turkey都是死亡状态，而仅有$i$号turkey存活。因此如果$S_i \cap S_j \neq \emptyset$，则表明存在一个turkey需要死亡两次，这显然是不可能的；反之，如果$S_i \cap S_j = \emptyset$，那表明两者的存活关系是完全独立的，$i$和$j$能够独立存活。
基于该点，求出每个turkey的存活集合$S_i$，然后判断任意两只turkey是否有交即可。
时间复杂度$O(N^3 + N^2M)$
CODE
CODE - Click Here
Problem F
Solutions
首先思考如何判断一个有向图是否为必胜态。
注意到两个pieces完全独立，因此可以求出每个点的SG函数。则一个有向图为必胜态当且仅当$\text{SG}_i \, \, \text{xor} \, \, \text{SG}_j \neq 0$
因此题目等价于求满足$\text{SG}_i \, \, \text{xor} \, \, \text{SG}_j \neq 0$的生成图数量；两者不等的状态不好判断，考虑求其补集，即$\text{SG}_i \, \, \text{xor} \, \, \text{SG}_j = 0$的方案
考虑将一个有向图划分为$G=U \oplus V$，其中$V=\{i|\text{SG}_i=0\}$；则该有向图的边可划分为四类，$V \to V$、$V \to U$、$U \to V$、$U \to U$
根据$\text{mex}$的定义可知，
对于$V \to V$，该部分没有边；
对于$V \to U$，因为缺少$0$，这部分可以任意连接；
对于$U \to V$，因为每个点都包含$0$，因此$U$都每个点都和$V$中至少一个点相连接；
对于$U \to U$，考虑将$V$集合删除；此时$U$中$\text{SG}_i=1$的点与当前定义的$V$集合等价，相当于原问题的子问题。
因此可以设$f(S)$表示点集为$S$的划分方案数，则可以枚举子集合进行转移。需要注意的是，为了保证$1$与$2$号点$\text{SG}$函数相等，在计算过程中，需要将两个点进行捆绑。
时间复杂度$O(N^2 \cdot 2^N + N \cdot 3^N)$
CODE
CODE - Click Here