2020-2021 ICPC, NERC, Northern Eurasia Onsite

发挥更加糟糕，更需继续努力。

需要补的题越欠越多，希望能在国庆补回来。

（某些题代码不给是因为考场代码不忍直视，然后我又不想写了

[A ASCII Automata Art]

solution

题面：

做法：大模拟？

[B Button Lock]

solution

题面：开局一个长度为的串，每次你可以翻转一个位或者重置为串。要求最少步数走完所有给出的串。

做法：容易建出图，那么剩下的就是找出最少的权值和的路径，使得每个点被覆盖。似乎不好玩，但注意到这些权都是必须要有的，而从大到小贪心匹配路径后，权值就一定是最优的了，所以又改成了路径数最少问题。这直接上个匈牙利即可。注意到边数是子集大小，于是总复杂度就是了。

[C Cactus Not Enough]

solution

题面：给出仙人掌图，问最少连多少条边会使得这张图再连一条边就会变成非仙人掌。

做法：考虑最终图是什么样，再考虑将最终图的环上边全删去会怎么样。发现问题等价于一棵树，删去若干条路径，使得剩余的连通块边数都不超过，这无论还是都可以做，就是感觉不太好写。时间复杂度。

[D Digits]

solution

题面：给出个数，选出若干个数，使得它们的乘积的最后一位数为，且乘积最大。

做法：直接即可，记一下最大乘积和当前长度，输出方案只要倒回来做一遍即可。时间复杂度。

其实这里直接取了对数，感谢出题人不卡之恩。

[E Equilibrium Point /\textbackslash/\textbackslash]

solution

题面：

做法：

[F Fiber Shape]

solution

题面：

做法：

[G Guide]

solution

题面：一棵树，至少要遍历不同的个点，问最少遍历长度。

做法：注意到遍历一遍再回到跟的路径长度只与遍历的节点数有关，于是贪心地想只用找最长路，尽量遍历最长路上最深的点，遍历不了才遍历浅的即可。时间复杂度。

坑：这个数据范围确实让人一直在想，第一时间让我就否定了贪心，确实是我的问题。

[H Hard Optimization]

solution

题面：

做法：

[I Is It Rated?]

solution

题面：交互题。有个人参加次竞赛，其中有一个人是你。每次竞赛会先给出个人的本轮竞赛结果，你根据他们给出的再给出自己的。然后系统会公布本次竞赛的正确结果。要求你错误的次数不超过，其中表示猜错次数最少的那个人的猜错次数。

做法：可以在这里找到做法。就是每次给猜错的人乘一个权值，每次我要给出的猜测按这个权值随机。

[J Japanese Game]

solution

题面：给出一个和长度为的数组，要求对长度为的序列染色，其中黑色极长连续段的长度分别按序等于中每一个数。此时会有很多种染色方案，但有一些位置是必须染色的。现给出和这些必须染色的位置，问。

做法：好强的构造捏。

考虑这些必须染色的位置是怎么出现的。我们若让染色最靠左，则有了一种染色方案。若最靠右，则又有了一种染色方案。而这两种染色方案的交集显然就是这些必须出现的染色位置，证明显然。

更进一步，我们只考虑最靠左，然后对每个连续段删去（不够就删完）此时最右边的最后一段白连续段长度。剩下的位置就是必须染色位置。

重新考虑这道题。我们枚举最右边的最后一段白连续段长度，于是对于每一个黑色头子要在它们前面加上的黑色长度，而其余位置由于可以被删光，所以是要加上小于等于的黑色长度。要求最开头要顶到，末尾要剩，中间黑色段之间都隔了仅有一个的白色格子。我们发现，除了一些非常小的长度，其余都可以用长度的黑色段拼凑起来，也可以说明时，成功与否等价于时成功与否。于是只用枚举，然后讨论一下即可。具体讨论这里就不给出了，不算太难。