七中六队 SCCPC 游记：E 难评

· · 生活·游记

有剧透，必须看题后再看游记。

先简单地介绍一下我们队伍：名字叫【七中六队】，算是七中队伍里最菜的了。队员是三个小学生，本来是 syq,wzy 和 zzr 一队的，但不知道为什么，zzr 跳到了另一个大佬的初中队伍，我们队来了一个 why。总的来看，我们队配置是最低的，平均年龄约 12.0，劣势在我。

Day 0

热身赛，我们没去，而是在上课。晚上看了一下上届题目，最简单的题居然没过？！不管了，睡觉！

Day 1

我早早地来到了考场门口等队友，看到了来自 JX、七中、大学的参赛者。等了好久，才凑齐人，进了考场。

开始了，先开 A：不做；再开 B：不做……总之，首 A 提交之前，我们都觉得没有一眼看出十分简单的题目。直到 D 题 A 了一些，我们才做 D。syq 做了 D，又开了 G，我在看难题。做出了 G，我们开始做 H。最开始看题时，syq 提出：我们不会做最大独立集问题。我和 syq 看了好一会儿，都没有看出什么。这时 why 画了一下样例的图，结果画错了，把不该连的边连上，该连的边不连。由于我们没有做过此类问题，看到这个图，恍然大悟：

图的最大独立集等于图的所有边的补集的最大连通块！

我和 why 发现：反图中的连通块都是强连通的。于是，why 提出：

若 a \oplus b 中 1 的个数为偶数个，c \oplus b 中 1 的个数为偶数个，则 a \oplus c 中 1 的个数为偶数个。

syq 说这显然不对，反例很容易找到。我打了 a,b,c \le 100 的表，发现竟然是对的！syq 又说，这个没什么用，他带 why 去想另一道题了。刚才我发现连通块都是强连通的，我赌连通块数量不会太多，那我就可以扫点，如果跟之前的连通块的任意一点异或满足条件，则加入连通块；否则，新开联通块。就有了以下伪代码：

unordered_map<int,int> mp;
for (int i = 1;i <= n;++i){
  bool f = 1;
  for (auto c:mp)
    if (c.first ^ a[i]中一的个数 % 2 == 0){
      mp[c.first]++;
      f = 0;
      break;
    }
  if (f) ++mp[a[i]];
}

不曾想，这个时间复杂度一看就复杂度超标的代码，竟一次 AC。总结：我也不知道怎么做的，就对了。

做了 G 看 C。先证了一下贪心，本想着用图论，还是算了。根据 syq 的说法这种题目交给我好一些，模拟写得略好。我的思路大概是这样：用候选列表维护精灵，对于每个精灵，用候选列表与它害怕的精灵求交。若交为空，尽量同归。但样例太水了，吃了好多罚时才 A。

来做 E。why 写了树形 DP，很多错误，我改错误，why 说改得不对，又改回来了。在这改来改去之间，比赛已然结束。我们力竭了，赛后找到 zzr 交流，发现：我们的状态对得不少，但其他的都不好，还没有发现关键性质：操作方案与树形态成双射关系。赛后我们感慨：

意难平，E 难评啊！

统计：

syq：贡献两道 easy。
wzy：贡献一道 easy，一道 middle，5 发罚时。
why：贡献 0.9 道 middle。

遗憾与高兴

  1. 【七中六队】得到 74 名，小学生队伍第 1 名。
  2. 【七中六队】在封榜前超过了 zzr 的有大佬的队伍 1 题，但他们在封榜被带飞 2 题，我们遗憾没有超过，若做出 E，即可使用【罚时优势】暴打 zzr。
  3. 【七中六队】超过了七中的一个中学生队伍。

感谢大家观看！