比赛链接：https://codeforces.com/gym/102946

官方题解：https://hackmd.io/@HNO2/HJTOKCOe_

难度：3星

A. A Water Problem

题意：给定一个数 ，求 的各位数字之和与 本身的乘积。

题解：按题意计算即可。

B. Bongcloud

题意：给定一个 01 矩阵，求上下对称的子矩阵有多少个。

题解：对于每列使用一次马拉车算法，求得以每个位置为中心，上下拓展的最长回文串长度。对于某一行，我们将以各位置为中心的最长回文串描出对应方格，得到如下的图。

如上图，以蓝色行为对称轴，且范围在黑色方格内的子矩形一定满足条件。对于每条对称轴，求出这样的子矩形有多少个即可。根据对称性，我们可只关注对称轴的一侧。

问题便可转化为，求以每个蓝色方格作为右下角的矩形有多少个。以最右侧蓝色方块为例，满足条件的矩形范围落在下图的黄色区域中，以该蓝色方块作为右下角的矩形个数实际上就是区域中的方格数。

而这样的区域一定是一个单调上升的区域，因此我们在从左向右枚举这些位置时，用一个单调栈维护这样的区域即可。时间复杂度 。

C. Chicken Nuggets

题意：给定一个树，各点有一个点权。如果一个点被去掉，则与之相连的边也会被去掉。现需要去掉一些点，使得剩下的各点与之相连的边数都为奇数，求剩下各点的点权和最大是多少。

题解：定义状态 ，表示以 为根的子树，点  去掉/保留，点 的度数为偶数/奇数，该状态下点权和的最大值。最初，，，（ 是不可能出现的状态）。然后像背包 dp 一样，将  的各个儿子放入背包中。假设将  的儿子  放入背包前， 的各个 dp 值为 。此时将 放入背包中，有：

最终答案为 ，时间复杂度 。

D. Discombobulator 3000

题意：交互题。现有两个数列 和 ，两者都为  到  的排列，且  为  循环右移  位的结果。每次询问两个值 ，可以得到 。在询问次数不超过  的条件下，求得 。

题解：询问 ，得到的结果中若只有一个 ，则 。若有两个 ，即 ，则再询问 。若 ，说明 ，否则说明 ，据此得出 。询问次数最多为 。

E. Evenly Distributed

题意：定义一个数集可以被均分，表示存在一种方案将这个数集分为两个集合，使得这两个集合中数的和相等。现要求够造一个含  个正整数的集合，这  个数的和为 ，且这个集合的任意一个子集都不能被均分。

题解：贪心，每次把能放入集合中最小的数放入集合，那么依次放入集合的数为 ，可以发现正好都是  的幂次。按照贪心的思路，先在集合中放入 ，那么最后需要放入的则是 。而最后放入的数应当大于 ，也就是说如果 ，即，那么满足条件的构造方式便是不存在的。

F. Fishy Study

题意：有一个鱼塘，以  行  列的 01 矩阵表示， 表示该位置一开始没有鱼， 表示该位置一开始有鱼。同时，鱼塘中某个位置还有一个海胆。每一天，鱼塘中依次发生如下变化：

1. 海胆会往上、下、左、右中可移动的方向移动一格。

2. 对于每个位置，如果海胆在该位置，则该位置这一天没有鱼；否则，如果该位置前一天有鱼，且周围八个格子中有  或  条鱼，则该位置这一天有鱼；否则，如果该位置前一天周围八个格子中有  条鱼，则该位置这一天有鱼；否则，该位置这一天没有鱼。

给出鱼塘的初始状态，并给出一个理想状态，问  天内该鱼塘是否可能出现理想状态。

题解：鱼塘的最终状态其实只与海胆的移动路线有关。由于  最大为 ，海胆的移动路线最多有  种，爆搜即可。我的代码中使用了 bitset 存储状态，需要注意下标的区别。

G. Group-Theoretic Machine

题意：给出三维空间里的六个点 ，其中 平行于 x 轴， 平行于 y 轴， 平行于 z 轴。问是否存在一个正方体，使得这六个点分别在正方体的六个面上。若存在，求出这个正方体的各顶点坐标。

题解：不会。

H. Halting Problem

题意：给一张连通图，要求选出一个点集，使得点集中任意选择两点，从一点到另一点的任意路径长度都为  的倍数。求点集中点数最多为多少。

题解：显然， 时答案为所有的点。由于是任意路径，因此两点间如果存在一条长度为  的路径，那么通过重复走某条边可以得到长度为  的路径。因此，当  时，答案只能为 。当  时，如果给出的图为二分图，二分图左部和右部对应的两个点集都是满足条件的，选择点数更多的即可；如果不是二分图，可以证明两个不同点之间肯定既存在长度为偶数的路径，又存在长度为奇数的路径，所以此时答案只能为 。判断是否为二分图使用染色法，时间复杂度 。

写这篇题解主要是测试b站专栏的代码高亮以及公式功能，以后或许会发更多的题解。