VP赛时三题。被AB题卡炸了，C题反倒发挥正常，D题可惜只想到了一半

A

没发现数据范围很小可以暴力 + 题干减号看成了加号，导致创造了二十多分钟才过A题的新纪录（

code

B

贪心 or 找规律，也是牢了一会儿。

显然要贪心地创造出能用上第二个操作的情景。所以从\(1\)位置出发，每次在右侧找一个 可用第二次操作的最远的右端点 使用第一次操作。若最后一个不是\(n\)位置，则需要额外在\(n\)位置补充第一个操作。

code

C

究极打表 + 找规律题，略带点数学计算。

首先打表发现，\(S(p)\)最大的排列一定满足这个性质：将\(1到n\)按顺序放，每一次放在最左端或最右端空出来的位置。

除了最后一个数位置固定，其他每个数都可任选两个位置来放，故总排列数为\(2^{n-1}\)。所以当\(2^{n-1} <= k\)时有解，\(>k\)时无解。

之后考虑依次放\(1到n\)，放\(1\)时，可以发现：\(1\)放在第一个位置对应前\(2^{n-2}\)种方案；而放在最后一个位置对应后\(2^{n-2}\)种方案。

依此类推，当放\(i\)时，\(i\)放在靠前的位置对应前\(2^{n-i-1}\)种方案；而放在靠后的位置对应后\(2^{n-i-1}\)种方案。

每一次可根据\(2^{n-i-1}与k\)的大小关系来决定第\(i\)个数放在前面还是放在后面，所以直接模拟放的过程即可。注意每次当\(i\)放在后面时要更新\(k\)的值

code

D

一道不是很难的构造题，但赛时没做出来，有点失落qwq...

想到了可以只放奇数或者偶数，这样出现的质数只可能是\(2\)，其他的数均为\(>2\)的偶数。这里选择偶数\(2,4,6...2n\)。

但没有想到构造方式。根本原因是完全把层序遍历抛到脑后了，一直在想深搜的构造而未果。

可以发现要想避免出现质数\(2\)，则任意一条边连接的两个数的差不能为\(2\)，即任意一条边的两个端点不能是一对相邻的偶数。

考虑将相邻的偶数分隔开：可以想到分层：按照\(bfs\)序，在奇数层正序放\(2,4,6...\)，在偶数层倒序放\(2n,2n-2...\)，这样就能尽可能地避免相邻偶数之间共边的情况，但不能完全避免，因为还需要考虑最后放的两个数 ——— 它们之间的差一定为\(2\)，且可能存在边。

还需要知道不是非得放偶数，也可以将某个偶数改为奇数。所以考虑将这两个数中的某一个改为奇数，使得它们的差值为\(1\)，这样所有边就都满足要求了。

但这两个点不是都可以改的，而是必须要选择一个叶节点才行，否则改变非叶节点的话还会影响该数与其他数的关系，从而不能保证修改的正确性。

由于这两个点是\(bfs\)过程中最后遍历的，因此二者中最后遍历的那个一定是叶节点。记录下来最后一个遍历的结点，并改为合适的奇数即可。

code

E

期望递推 + 推公式

首先要观察出无后效性：设以\(1\)为根，则从某个点往\(1\)走就相当于往上走。当从某个点向上移动后，就永远不会再向下移动了，因为第奇数次操作一定向上走，即使第偶数次操作往下走，下一步也会恢复过来。因此可以想到通过上方结点的期望步数来递推出下方结点的期望步数。

设\(f[u][p]\)：从 \(u\) 出发，有 \(p\) 个硬币，且设定先执行的是偶数步的操作，走到结点\(1\)的最小期望步数。

则\(ans_u,_p =\) :

0                   u == 1
1 + f[fa[u]][p]     u != 1(先执行奇数次的操作，一定向上走一步，再在u的父亲处执行偶数步的操作)

考虑计算\(f[u][p]\)，递推过程如下（\(d_v\)表示度数）：

code