题解

A Qfish的魔方

记录每个数的个数，判断每个数的个数是否恰好为3个。

B 寻找最大值

题目意思是求可以交换交换两个位置能够得到的最大值。因为我们只能进行一次交换操作，为了使得交

换后的值最大，我们需要把尽可能大的数字从后面交换到前面来，所以只需要从第一位往后找到不是最

大值的第 x 位，再往后找到值最大的第 y 位 (1 ≤ x < y ≤ n)，交换 x, y 位置的数字，得到的值即

是最大值。

C 找数字

找数字：记录一下数字出现的次数，输出只出现一次的数字。

D 找更多数字

从高位往低位找到第一个不为0的位置，分成两堆数字，两堆数字的异或和就是两个只出现一次的数

字，记录一下前缀异或和，就可以快速回答询问。

E 井字棋

判断有没有一行全为'X'，有没有一列全为'X'，有没有一个对角线全为'X'，满足其中一个条件，则是先手

赢，否则后手赢。

F 不匹配子串

两个字符串长度均小于等于500。考虑一个字符串的子串数量只有n(n 2 +1)个。所以可以暴力存下字符串

s的所有子串，然后将这些子串和字符串r进行匹配，若匹配的两个字符串长度相等且有k个位置的字符

不同，则满足条件的子串数量加一。时间复杂度O(n 2m)，n代表字符串s长度，m代表字符串r长度。当然也可以不存子串，直接在字符串s上匹配，这样的时间复杂度O(nm)。1 ≤ n ≤ 500 1 ≤

m ≤ 500上述两种写法均可通过。

G 猫猫的天空城

使用并查集，虽然有n张图，但nm总点数不超过1e6，可以对这nm个点重新编号。

对于删边操作，如果直接按照给定的顺序删边，难以更新合并连通块。这里可以用倒序的思想，将所有

询问保存下来，从后往前处理。

合并时，删除的边不参与。然后从后往前将操作中删除的边加入进去，并更新合并的连通块，然后进行

对应的查询操作。

H 猫猫魔法

按照题意模拟即可，主要考查了字符串

I 发糖果

首先，对于函数F(S ′ , m),可以抽象成一张二分图，对于每个人而言，对能给他发糖果的天都连上一条

边，那么函数F(S ′ , m)即为子图的最大匹配数。而对于S的每一个子集S ′ ,都需要做一遍二分图匹配是

做不到的，需要做2 n次二分图匹配。

根据拓展hall定理：

Hall 定理：

对一个二分图 G=(V1,V2,E)，对 S ⊆ V1 设 f(S) 为 S 连到 V2 的点集大小，则存在 V1 的完美匹配（即

大小等于 |V1| 的匹配）当且仅当对任意 S ⊆ V1 都有 |S| ≤ |f(S)|。（要求右部的话，交换 V1,V2 即可）

扩展 Hall 定理：

令 M = max_{S ⊂ V1} {|S| - |f(S)|}，则 G 的最大匹配为 |V1| - M。（对左右部件用这个定理都可以得到

最大匹配）

我们可以得知，一个集合最大匹配数与它的子集的点数与连接的点数是相关的，这部分可以通过sosdp

进行转移。那么我们只需要知道该集合的点数与连接的点数，就可以得到每个子集的最大匹配数。

但是并不好获得子集的点数与连接的点数，这里需要用到一点容斥，将总的天数减去与该子集完全有无

连边的天数即是与该子集有连接的天数。这里同样用到一次sosdp。通过两次sosdp,对于该2 n个子图，我们都可以得到最大匹配数，将所有的最大匹配数相加即可。

欧拉筛预处理质数，通过一个二分check即可得到最小的m，或者不可能。当k在n*2 n以内时，可以有

解。

J 黑白黑

假设白布中有黑色污渍，那么矩阵中一定有一行从左到右出现了1之后会出现0然后又出现1，以此判断

即可。

或者可以用DFS+计数的方法，遍历矩阵数一下黑色0的个数cnt，再从边界开始DFS数一下白布外0的个

数x，比较一下，若cnt=x，输出No；若cnt>x，输出Yes。