题解

题意概述

给定偶数 n 和一个 n * n 的 01 网格，将其平分为上下左右四个象限，每次操作可以翻转一个网格的元素。求最少需要多少次操作使得四个象限镜像对称（每两个相邻的象限中的 01 网格关于它们相邻的那条轴对称）. 此外还会有 m 次询问，每次询问翻转一个坐标，求翻转后的最少操作次数。

解题思路

我们找到成对的镜像对称格子，每对是 4 个格子（例如整个网格左上角，左下角，右上角，右下角就是一对），我们的目标是将每对格子变为全 0 或全 1。可以统计每对格子当前有多少个 0 和 1，然后取最小值即可。对于询问，我们可以直接更新对应的网格对，然后重新计算即可。复杂度 O(n^2)。

题意概述

给定 N 个数（N 不超过 200000，每个数范围 0 ~ N），每次操作可以将其中一个数修改为任意非负整数。对 0 ~ N 中的每一个 i，求最少操作几次可以使整个数列的 mex 为 i。一个数列的 mex 指的是最小的未出现过的非负整数.

解题思路

如果数列 mex 为 i，则 0 ~ i - 1 的每一个数都出现过，且 i 没有出现过. 对于每个 i，我们统计 0 ~ i - 1 中有几个数没有出现过（表示有几个空位需要填），再统计 i 出现了几次（这几个 i 都必须修改为其他数）。由于可以拿 i 来填充前面空位，所以两者的较大值就是答案.

题意概述

一种编程语言有 REP 和 PRINT 两种语句，其中 PRINT X 可以输出 X，REP 可以重复执行一系列语句，也可以嵌套，类似于 C++ 和 Python 的 for 循环。给定 N <= 100, K <= 3，以及 N 个 1 ~ K 的整数，求是否可以使用 K 个以内的 PRINT X 语句 (1 <= X <= K) 和任意多个 REP 语句组成程序来输出这 N 个数。共有 T 组询问 (T <= 100)。

解题思路

如果 K = 1，必可以输出。否则我们可以先判断整个序列是否有循环节，找到其中最短的循环节 S，则 S 中不含任何循环节。接下来如果循环节内部有 3 种数字，则 1,2,3 中必然有一个数只存在于 S 前面连续的一段或者后缀连续的一段。我们将连续的一段排除，递归判断剩下的部分（剩下部分只有两个数）。

如果循环节内部有 2 种数字，则需要分类讨论。如果 K = 2，则 S 必然是 111222... 或者 222111.. 这种形式。如果 K = 3，则可能有 1212222 这种形式（即包含两个循环节 12 和额外输出的 222，这也满足 3 个 PRINT）。我们可以暴力删除连续 1 或 2 的前缀或后缀，再递归判断剩下部分即可。