【题解】长安大学19年ACM校赛

## A. Seek Spy
判断出不同的那个数直接输出。

##B. Trial of Devil
初始时的序列为：1~n.
+ 第一次操作时，将 $\lceil$ $\frac{n+1}{2}$ $\rceil$ ~ n 范围内的数同时减去 $\lceil$ $\frac{n+1}{2}$ $\rceil$ 。这时序列变成：1~ $n_1$ ( $n_1$ = $\lfloor$ $\frac{n}{2}$ $\rfloor$ )
+ 第二次操作时，将 $\lceil$ $\frac{n_1+1}{2}$ $\rceil$ ~ $n_1$ 范围内的数同时减去 $\lceil$ $\frac{n_1+1}{2}$ $\rceil$ 。这时序列变成：1~ $n_2$ ( $n_2$ = $\lfloor$ $\frac{n_1}{2}$ $\rfloor$ )

......

最终可以推出，答案为： $\lceil$ $log_2^{n+1}$ $\rceil$ .

##C. LaTale
比较经典的树上DP问题。
+ 每个节点要维护3个信息，跟它距离为：3k，3k+1，3k+2的节点数。
+ 第一次DFS维护每个节点跟它子树中节点的信息。
+ 第二次DFS再维护每个节点跟剩余节点的信息。

##D. Bamboo Rat
二分答案+黑白染色+最小割
二分答案以保证k个数中权值最小的最大。假设当前二分出的值为x，通过建图来判断x的可行性。
建图时不用考虑权值小于x的点，对于剩余的点进行黑白染色，假设剩余的点有 $n_1$ 个。
然后开始连边：S -> 黑点连流量为1的边，黑点 -> 相邻的白点连流量为inf的边，白点 -> T 连流量为1的边。
最后跑一个最小割，如果 $n_1-min\_cut$ (S，T) $\geq k$ 则x可行，反之不可行。

## E. Game
阶梯博弈变型
如果有奇数堆石子，就在最前面添加一个空堆使其变成偶数堆。所以只需讨论偶数堆的情况。然后再将每相邻的两堆合并成一组。对于合并后的每一组，假设分别有 $x_1,x_2$ 个，那这一组的sg值为 $(x_2-x_1)\%(k+1)$ 。最后把每一组的sg值异或起来，不为0则Bob获胜，否则Alice获胜。
假设必败者移除的是奇数项的堆，那么必胜者只需移除该项后面一项同样数目即可。假设必败者移除的是偶数项的堆，那么问题就转变成了多堆石子博弈问题。

## F. Re: Trial of Devil
线段树上二分+单点修改
线段树只需维护区间最小值。初始时将A序列中的无关点（没有出现在C序列中的点）修改成inf。
然后开始按 $C_1$ ~ $C_m$ 的顺序判断A序列中的点。对于第i个点 $A_{C_i}$ ，在线段树上二分出左面和右面第一个不大于它的点的位置 $l_i$ 和 $r_i$ 。若 $r_i-l_i-1\geq k$ 则第i个点可行，反之不可行。每个点在判断结束后需要把值修改为inf。
最后如果m个点都可行，则总体可行，反之不可行。

## G. Gift
组合数+容斥
不考虑至多k个的情况的话，相当于用隔板法从n-1个间隔中选择m-1个，即 $C_{n-1}^{m-1}$ 。然后再考虑可能多于k个的情况，即使用容斥“奇减偶加”的原理，减去重复的情况。由于输入数据过大，需要用逆元乘法代替除法。

答案可以总结为： $\sum_{i = 0}^{min(m, (n-m)/k)} C_{m}^{i}\cdot C_{n-i\times k-1}^{m-1}\cdot (-1)^i$ .

## H. Matrix
矩阵乘法+DP
矩阵一共有8种，每两个相乘总共有64种情况。用一个数S代表DP时可行矩阵的状态，通过预处理的64种情况来转移S。最后如果S中包含矩阵m则可行，反之不可行。
这道题还有一个结论：若A序列中存在两个0，那么答案肯定是“YES”。

## I. Flag
先假设序列A可以分割为2个等差数列。
在序列A中，假设前k-1个数构成等差数列，前k个数不构成。将k的值分3种情况讨论：
1、k=3
2、k=4
3、k > 4
对于上面3种情况中的每一种，可以枚举2个等差数列中的首项，和至少1个等差数列的公差。
然后对于已知2个等差数列中的首项，和1个等差数列的公差的情况。通过序列后面的数，可以继续枚举另一个等差数列的公差。
最后就变成了已知2个等差数列中的首项，和2个等差数列的公差的情况。根据序列后面的数判断是否可行即可。

## J. Binary Number
先判断高位的1的位置，用组合数计算每个位置的情况数。

## K. Idol

贪心
对于S串和T串中对应位置相同的字符是没必要操作的。那么根据那些已经相同的字符，把串分割成几部分，每部分单独考虑。很容易知道被分割后的串对应位置都不相同，开始考虑被分割出的每一部分。
交换操作比修改操作更优时需要满足类似下面的条件：
$abcde\ \ \ \ \ \ abcde \\ bcdea\ \ \ \ \ \ eabcd$
假设把这种结构称作“环”，那么每个环都比直接修改少了1次操作。所以每个环的“贡献”是等价的，而且每一个位置最多只能属于一个环。所以对于被分割后的每一部分，从左向右遍历，贪心的构成环即可。

经qls hack 解法错了..............

## L. XOR
$x\oplus 4x \oplus 5x = 0 \\ x\oplus 4x \oplus (x+4x) = 0 \\ x\oplus 4x = x+4x \\ x\ \&\ 4x = 0 \\ x\ \&\ (x<<2)=0$
之后数位DP，dp[i][j] 表示第i位，状态为j时的答案。其中j有0,1,2,3四种取值，代表当前最后2位的状态。

## M. LCM
$LCM(a,b) = a\times b/***(a,b) = c \\ a\times b = c\times ***(a,b)$

c是定值，所以***(a,b)越大时， $a\times b$ 越大。***(a,b)是a和b的约数，所以***(a,b)也是 $a\times b/***(a,b)$ 即c的约数。然后通过从大到小枚举c的约数作为***(a,b)判断可行性。
对于可行性的判断，假设当前枚举的约数为d。将c/d中的因子通过枚举分成2部分，判断每部分是否都不大于n/d即可。