小白月赛77题解

A.小Why的方阵

当至少存在一组对角元素相等时，输出 。

B.小Why的循环置换

数组有序等价于消除所有循环，消除一个大小为 的循环至少需要 次操作，也就是每多一个循环就可以少操作一次。

C.小Why的商品归位

由于多个人跑一趟和一个人跑多趟是等价的，那么实际上是没有最优策略的，直接差分就可以得到答案了。

D.小Why的密码锁

考虑字符串哈希，扫一遍就可以得到结果。

E.小Why的简单加减

我们称断点为可以无限减的点，显然最优情况断点至多只有一个。

我们先假设 无限大，记 为 的前缀，找到第一个 小于 的点记为断点 ，那么在 之前的所有负数都能变为非负。容易发现，断点取在 的右边不会比取在 更优。

无论 有没有限制，当我们确定断点后，所有除了断点的负数都是可以选择的，那么我们只需要选择 中最小的负数作为断点即可。

F.小Why的数论测试

如果只考虑前两个操作，那么从 到 的逆过程就是最优的。

如果考虑至少使用一次平方操作，那么 的过程一定可以写作 。枚举 的取值可以做到 。