CSUST ACMore Evening training 2024.3.19

Problem1

我们可以推一下这个式子就可以发现题目要我们求啥，目要去掉俩个数后算术平均数相等，那我们就选俩个去掉假设为 $a_x, a_y$ $\frac{Sum}{n} = \frac{Sum - a_x-a_y}{n - 2}$ $得到： 2 \times Sum = (a_x + a_y) \times n $ 我们会发现如果 $2 \times Sum \equiv 0 (\bmod n)$ 才可能存在有解，然后就是需要存在 $(a_x+a_y) = \frac{2\times Sum}{n}$ ，令 $w = \frac{2\times Sum}{n}$，假设 $x < y$ 要求的就是对于每一个 $y$ 有多少个 $x$ 满足 $x < y 且 a_x = w - a_y$ 我们发现只要从前往后按顺序遍历，再求一下之前有多少个 $w - a_y$ 即可，可以用个 $map$ 记录，直接遍历就好

Problem2

给定一个字符串 $s$ 以及一个字符 $c$ 需要进行一些操作，将这个字符串所有位置变成这个字符，每一次操作是选择一个值 $x$ 把所有不是 $x$ 倍数的位置修改成 $c$ ，我们可以分类讨论一下

首先是 $0$ 次，如果 $s$ 每一位都是 $c$ 那么修改次数显然是 $0$ 次

然后是 $1$ 次，我们可以枚举 $1 \sim n$ 每个数 $i$ 的倍数，然后如果对于 $i$ 的倍数位置，不存在与 $c$ 不相同的位置，那么我们就可以选择这个数，然后一次修改完毕，复杂度参考 埃氏筛 ，大致为 $O(nloglogn)$ 时间是够的

然后就是剩下的全部可以 $2$ 次操作完，细想一下，我们怎么构造，其实只需要 $n$ 和 $n - 1$ 这俩个数即可，因为 $n$ 的倍数是它自己，其他位置都可以修改，然后 $2 * (n-1) > n$ 是显然的（题目保证 $n \ge 3$ ）那么就做完了

Problem3

模拟删点的过程即可，每个点最多被删一次，每次删的点是度为 $1$ 的点，然后我们做类似与拓扑排序的一个过程，每次删掉一层，把这些删掉的点，连接的另外一些点的度减掉，如果度变成一了就放入，不过需要暂时存下来，因为每次是删一层，然后注意一下边界情况的特判就行了

Problem4

按照题意模拟即可，首先能删除的是 $1$ 个节点，接下来是 $2, 4, 8, 16$ ，对于每一步是 $2^{i-1}$，直到达到 $2^{i-1} \ge q$ ，对于$2^{i-1} < q$ 只需要每次加上$1$ 即可，到 $2^{i-1}\ge q$ 时我们发现，只要一层一层删，我们每次都能删掉 $q$ 个节点，剩下的节点个数为 $x$，那么还需要操作 $\lceil \frac{x}{q} \rceil$ 次，这样就欧拉