chx吃瘪了, 打完感觉彻底燃尽了.
I
签到题,按照题意模拟即可.不过有个铸币把 continue 的位置写错了,导致输入还没读完程序就开始运行,平白吃了一大堆罚时.
M
同样是模拟题.枚举完种子后,只需要利用全概率公式计算第 $i$ 个种子选手在某一轮胜出的概率即可.
B
有趣的贪心题.首先注意到,一定存在一种最优方案,使得同一种颜色的格子全部通过同一种方式得到：要么为它建立一个纯色图层,再依靠上层覆盖或用橡皮扣掉不需要的位置；要么从透明图层开始,把这种颜色逐个画上去.前者记为第一类,后者记为第二类.所有第二类颜色显然可以共用一个位于最顶端的透明图层,因此若颜色 $c$ 出现了 $cnt_c$ 次,那么把它归入第二类的代价就是 $cnt_ca$.
假定第一类颜色从上到下依次为 $c_1,c_2,\ldots,c_k$,那么为了显露颜色 $c_i$,需要在它的每个格子上擦除上方的 $i-1$ 个纯色图层,其贡献为 $cnt_{c_i}(i-1)b$；而对于原图中的透明格子,则需要将全部 $k$ 个纯色图层擦除,贡献为 $cnt_0kb$.在固定了第一类颜色集合后,做一个简单的相邻交换就能发现,出现次数更多的颜色一定不劣于放在上面,所以第一类内部应当按照出现次数降序排列.
进一步地,如果某个出现次数较少的颜色属于第一类,而另一个出现次数更多的颜色却属于第二类,那么把二者交换也不会使答案变差.这是因为一个有用的、上方已有 $i-1$ 个纯色图层的颜色必然满足 $(i-1)b\le a$,否则直接在透明图层上逐个画出更优.因此将所有非零颜色按照出现次数 $cnt_1\ge cnt_2\ge\cdots\ge cnt_s$ 排序后,一定存在一个最优方案,使得第一类构成一个前缀,第二类构成剩余的后缀.
于是只需要枚举这个前后缀的分界点 $k$,对应的总代价为
$$a\sum_{i=k+1}^{s}cnt_i+b\sum_{i=1}^{k}(i-1)cnt_i+kb\cdot cnt_0.$$排序后维护前缀和并枚举 $k$ 即可,时间复杂度为 $\mathcal O(nm+s\log s)$,其中 $s$ 是出现过的非零颜色数.
K
有趣的找不变量题.二维的情况不太容易直接看出来,所以首先考虑所有青蛙都在一条直线上的弱化版本.假定受到刺激的青蛙依次为 $t_1,t_2,\ldots,t_\ell$,其中 $t_1=s,t_\ell=t$.当青蛙 $t_i$ 以青蛙 $t_{i+1}$ 为中心完成跳跃时,它的新坐标为 $2x_{t_{i+1}}-x_{t_i}$,因此这一步产生的位移为
$$2x_{t_{i+1}}-2x_{t_i}.$$这里的坐标都是这次跳跃发生前的当前位置.关键在于第 $i$ 次跳跃只移动了 $t_i$,作为对称中心的 $t_{i+1}$ 并没有移动,所以这一项中的 $2x_{t_{i+1}}$ 恰好能与下一项中的 $-2x_{t_{i+1}}$ 抵消.于是把整个接力过程中的位移全部加起来,中间项会望远镜消去,最终只剩下
$$2Q_t-2P_s.$$另一方面,每次只会有一只青蛙移动,所以全部跳跃的位移之和也就是所有青蛙从初始状态到最终状态的总位移,即
$$\sum_{i=1}^{n}(Q_i-P_i)=2Q_t-2P_s.$$这个等式对横纵坐标分别成立,因此可以直接推广回二维.计算
$$2P_s+\sum_{i=1}^{n}(Q_i-P_i),$$之后在所有最终位置中找到唯一满足 $2Q_t$ 等于这个向量的青蛙即可.时间复杂度为 $\mathcal O(n)$,坐标求和需要使用 long long.
F
很有意思的构造题.首先考虑 $x,y$ 不相邻的情况,直接把所有与 $x$ 相连的边都朝向 $x$,所有与 $y$ 相连的边都朝向 $y$,其余边随意定向即可.这样两个人从一开始就分别被钉死在两个不同的汇点上,显然不可能相遇.
真正需要处理的是 $x,y$ 相邻的情况.首先可以确定,如果整张图是一棵树,那么一定无解.任意给树上的边定向,不妨设起点边的方向为 $x\to y$,再从这条边出发任取一条极大的有向路径
$$x=v_0\to v_1=y\to v_2\to\cdots\to v_k.$$树上不可能出现有向环,所以这条路径一定会终止在一个没有出边的点 $v_k$.此时可以让 Bob 沿着这条路径向前走,而 Alice 始终在他身后一步沿原路尾随；当 Bob 到达 $v_k$ 后只能停住,下一轮 Alice 便会走到同一个点.因此至少存在一种走法使两人相遇,也就不可能满足题目中“无论如何选择”的要求.
接下来只需要考虑图中含环的情况.若删去 $(x,y)$ 后二者仍然连通,就取删边后的一条最短 $x\to y$ 路径,再把 $(x,y)$ 接回去,得到的必然是一个无弦环.将它定向成有向环,并把所有连接环内外的边都朝环内定向,其余边随意.这样环上每个点都只有唯一一条出边,两个人只能以相同速度沿环前进；由于初始时恰好相差一步,这个距离之后也会一直保持下去.
最后假设 $(x,y)$ 是桥.删去它以后图会分成两个连通块,而原图含环,所以其中至少一块不是树.假设含环的是 $x$ 所在的一侧：在这一侧选择一个离 $x$ 最近的环 $C$,若有多个则取其中最短的一个,再取 $x$ 到 $C$ 的最短路 $P$.这样的选择保证了 $C$ 没有弦、$P$ 没有弦,并且 $P$ 的内部点不会与 $C$ 产生额外连边,否则便可以找到一个距离 $x$ 更近的环.因此 $P\cup C$ 恰好是一条路径接上一个环的套索结构.
令桥的方向为 $y\to x$,把 $P$ 朝 $C$ 定向,再把 $C$ 定向成有向环；$y$ 的其他邻边全部朝向 $y$,所有从 $P\cup C$ 外部连向这个结构的边也都朝结构内部定向,其余边随意.此时 $y$ 以及套索上的每个点都恰好只有一条出边,于是 Alice 会沿着 $P$ 进入 $C$,Bob 则始终在她身后一步沿着同一条路线前进.进入环后两人仍然保持一个位置的距离,所以不可能相遇.若含环的是 $y$ 所在的一侧,交换二人的角色即可.
因此这道题唯一无解的情况就是 $x,y$ 相邻并且整张图是一棵树.其余情况按照上面的分类构造即可；寻找最短路和所需的环可以用 BFS 完成,在 $n\le 300$ 的限制下绰绰有余.