AtCoder Regular Contest 105
A Fourtune Cookies
按题意模拟。
B MAX-=min
题目中提到过程一定会停止，考虑 \(n=2\) 时就是更相减损至相等，即求 \(\gcd\)，扩展到 \(n\) 更大的情况似乎也类似。
事实上，由于 \(\gcd(x,y)=\gcd(x,y-x)\)，所以无论怎样操作序列的 \(\gcd\) 是不变的，而最终序列只有一个本质不同元素，则答案就是 \(\gcd\)。
C Camels and Bridge
先枚举所有的排序顺序，设 \(d_i\) 为 \((i,i+1)\) 的距离，则对于区间 \([l,r]\) 以及路段 \(k\)，如果 \(\sum_{i=l}^{r} w_i>v_k\)，则 \(\sum_{i=l}^{r-1} d_i\ge l_k\)，可以二分得到所有满足条件中 \(l_k\) 的最大值 \(b_{l,r}\)，这样就是对每个区间都有形如 \(\sum_{i=l}^{r-1} d_i\ge b_{l,r}\)，求 \(\sum d\) 的最小值。
没学过差分约束，所以我口胡了一个区间 DP，设 \(f_{l,r}\) 为区间 \([l,r]\) 距离的最小值，转移就是：
\[f_{l,r}=\max_{k=l}^{r-1} \{f_{l,k}+f_{k+1,r}\} \]本质上是 Floyd，还是差分约束。
D Let's Play Nim *
Game Theory is not for me.
本质上是要求构造出的石子堆异或和是否为零。
如果是偶数次操作，则先手每次选择最大值放到一个固定的位置，就会有一堆石子超过超过总数一半，异或和一定不为 \(0\)；同理，如果是奇数次操作，后手每次选择最大值放到先手第一次放到的位置，异或和也一定不为 \(0\)。
一种特殊情况是后手可以模仿先手操作，即每一种大小的出现次数都是偶数，这样后手每一次操作都可以使当前场面异或和为 \(0\)。
于是结论：
-
当 \(n\) 为奇数时，后手必胜。
-
当 \(n\) 为偶数时，当且仅当每种大小的出现次数都是偶数，后手必胜，否则先手必胜。
E Keep Graph Disconnected *
Game Theory is realy not for me.
容易看出终止状态是两个完全图分别包含 \(1\) 和 \(n\)，设 \(1\) 所在连通块大小 \(siz\)，则一共操作次数 \(n(n-1)/2-m-siz(n-siz)\)，为奇数时先手胜，为偶数时后手胜。
\(n(n-1)/2-m\) 的奇偶性已知，主要是对 \(siz\) 的讨论，当 \(n\) 为奇数时，\(siz(n-siz)\) 一定为偶数，可以直接判断。
\(n\) 为偶数时，将初始连通块分成 \(1\) 所在连通块，\(n\) 所在连通块，大小为奇数的块和大小为偶数的块，我们只要求最终连通块的奇偶性，于是只有奇数块的连接对答案有影响。
然后我就不会了，下面是对题解的摘抄：
一个我想到的事实：存在模仿操作来抵消影响，例如先手连奇数块，后手再连奇数块就可以抵消掉先手的操作，从而使结果不变，但需要讨论奇数块的个数。
目前讨论的前提条件是 \(n\) 为偶数，设 \(1\) 所在连通块初始大小 \(x\)，\(n\) 所在连通块初始大小 \(y\)，那么当 \(x,y\) 奇偶性不同时，剩余块的大小总和为奇数，因此奇数块的个数为奇数。此时先手可以操作一个奇数块来达到目的，如果需要成绩为奇数则与 \(x,y\) 中为奇数的相连，反之则与 \(x,y\) 中为偶数的相连。接下来奇数块个数为偶数，后手每次操作，先手可以通过模仿来抵消，因此先手必胜。
通过观察上面的分析，我们得出一个结论：奇数块个数为偶数时，\(x,y\) 最终的奇偶性都不可改变。即当希望发生改变的一方操作时，另一方都可以将其抵消，这建立在奇数块有偶数个，即改变与抵消成对出现。因此 \(x,y\) 奇偶性相同时，奇数块个数为偶数，可以直接通过 \(n(n-1)/2-m-xy\) 来判断答案。
标签：连通,奇数,乱写,siz,ARC105,奇偶性,偶数,操作,杂题 From： https://www.cnblogs.com/SoyTony/p/Problems_in_ARC_105.html