AtCoder Grand Contest 002

A - Range Product

题目大意：

判断\(\displaystyle\prod\limits_{i=a}^{b}i\)的正负号或者是\(0\)，\(-10^9\le a\le b\le10^9\).

题解：

先判断是否为\(0\)，然后根据负数因子的个数回答即可。

B - Box and Ball

题目大意：

有\(n\le10^5\)个盒子，一开始\(1\)号盒子中有一个红球，其它每个盒子中有一个白球。

接下来\(m\)次操作，每次操作从\(x\)号盒子中随机取出一个球放入\(y\)号盒子，保证\(x\not=y\)，且\(x\)号盒子此时至少有一个球。

问最后有多少个盒子中可能存在红球。

题解：

令\(f_i\)表示\(i\)号盒子中可能有红球，\(siz_i\)为\(i\)号盒子中球的数量。

则一开始\(f_1=1,siz_i=1\)，每次操作，\(f^{'}_y=f_x\lor f_y\)，如果操作后\(siz_x=0\)，则令\(f_x=0\)，否则不变。

最后扫一遍\(f_i=1\)的盒子数量即可，时间复杂度\(O(n)\).

C - Knot Puzzle

题目大意：

有\(n\le10^5\)段绳子，第\(i\)段绳子的长度为\(a_i\)，第\(i\)段和第\(i+1\)段绳子被第\(i\)个结系在一起。

如果一段绳子的总长度不小于\(L\)，那么就可以解开这段绳子中的任意一个结，问是否存在一种方案将\(n-1\)个结都解开。

题解：

考虑最后一个结，它能被解开的充要条件是连接的相邻两段绳子的长度和不小于\(L\)，如果不存在这样的结，显然无解。

如果存在，那么按离这个结的从远到近的顺序解开两边的结最后再解开这个结即可。

D - Stamp Rally

题目大意：

给出一张无向连通图，点数和边数分别为\(1\le n,m\le10^5\)。

有\(q\le10^5\)次询问，每次询问至少需要用到编号不大于多少的边，才能使得与\(x\)和\(y\)两个点至少一个点连通的点数不少于\(z\).

题解：

方法一：

考虑对边分块，取块大小\(K=\sqrt{m}\)，用并查集维护连通块大小，先找到每组询问答案所在块编号，再枚举答案判断。

时间复杂度\(O(q\sqrt{m}+n+m)\)，空间复杂度\(O(n+m+q)\).

方法二：

单独考虑每组询问，显然可以二分答案，并查集判断。

于是我们使用整体二分，但是每次重建并查集代价太高，可以考虑按bfs的顺序访问整体二分的树结构。

这样每层的区间中点是有序的，按顺序加边即可，而进入新的一层的时候则需要重置并查集。

因为二分的树结构只有\(O(\log{m})\)层，因此时间复杂度为\(O((n+m+q)\log{m})\).

E - Candy Piles

题目大意：

有\(n\le10^5\)堆糖果，第\(i\)堆糖果的数量为\(1\le a_i\le10^9\)，两个小朋友玩游戏，轮流操作，每次操作必须选择以下两种操作之一：

• 吃掉当前最多的那堆糖果

• 从当前剩下的每堆糖果中吃掉一个

吃掉最后一个糖果的人输。如果都采取最优策略，问先手胜还是后手胜。

题解：

将\(a\)从大到小排序，然后按\(a_1,\cdots,a_n\)像统计的柱形图一样画出方格图，则问题转化为从\((0,0)\)出发轮流向上或向右走一步，走到轮廓边界的人输。

可以将轮廓上的点看做必胜态，则可以证明，不在轮廓上的点，同一对角线上的点的状态是相同的，证明如下。

若\((x,y),(x+1,y+1),(x+2,x+2)\)都存在，\((x+2,y+2)\)可能在轮廓上，则\((x,y)\)和\((x+1,y+1)\)一定相同。

用反证法分两种情况讨论：

• 如果\((x,y)\)为必胜态，\((x+1,y+1)\)为必败态，因为\((x,y)\)为必胜态，因此\((x+1,y)\)和\((x,y+1)\)至少有一个为必败态，而必败态不能到达任何一个必败态，与\((x+1,y+1)\)为必败态矛盾；

• 如果\((x,y)\)为必败态，\((x+1,y+1)\)为必胜态，因为\((x,y)\)为必败态，则\((x+1,y)\)和\((x,y+1)\)都是必胜态，而必胜态至少要能到达一个必败态，因此\((x+2,y)\)和\((x,y+2)\)都是必败态，又因此\((x+2,y+1)\)和\((x+1,y+2)\)都是必胜态，与\((x+1,y+1)\)为必胜态矛盾；

因此不在轮廓上的点，同一对角线上的点的状态是相同的。

因此问题转化为求同一对角线上最接近轮廓线的点的状态，这个状态和它向上和向右两个方向到轮廓线的距离的奇偶性有关。

如果两个距离都为偶数，则为必败态，否则为必胜态，证明如下。

其中一个距离为零，这种情况，同一行或者同一列的状态是交替分布的，满足条件。

两个距离都不为零，这种情况，考虑向右一个位置和向上一个位置的两个位置，当且仅当它们都是必胜态的时候，当前位置为必败。

而这两个位置的状态和上一条证明的规律相符，因此该规律对当前情况也成立。

因此整个算法的时间复杂度为排序所需的复杂度\(O(n\log{n})\)。

F - Leftmost Ball

题目大意：

有\(n\le2000\)种颜色的球，每种颜色都有\(k\le2000\)个，现在将它们放在一行任意排列，然后将每种颜色最左边的球染色成\(0\)号颜色（与\(n\)种颜色都不同），问最终有多少种不同的局面。

题解：

考虑如何一个最终局面是否合法。最终局面合法，当且仅当，将出现的颜色按除了\(0\)号颜色之外的每种颜色最左边的球的顺序重新编号，第\(i\)种颜色的球左边至少有\(i\)个白球。

因此可以用\(f[i][j]\)表示仅考虑有\(i\)个\(0\)号球，\(j\)种不同颜色的球的不同局面数量，则答案为\(f[n][n]\times n!\)。

显然\(f[0][0]=1\)，\(f[i][j]\)则需要考虑当前最左边的球放\(0\)号球还是放\(j\)种颜色中编号最小的颜色的球。

• 如果放\(0\)号球（要求\(i>0\)），则有\(f[i-1][j]\)种方案；

• 如果不放\(0\)号球（要求\(j>i\)），则需要先将该种颜色的其余\(k-2\)个球的位置决定好，然后转化为子问题\(f[i][j-1]\)，共\(\displaystyle\binom{i+j(k-1)-1}{k-2}\times f[i][j-1]\)种方案；

时空复杂度\(O(n(n+k))\)，注意要特判\(k=1\)，此时显然只有一种方案。