2022 CCPC Guangzhou Onsite

大概按题目难度顺序排序。这篇题解可能没那么口胡。

GYM104053E Elevator

相当于每个电梯在 \(-x_i\)，每次可以把最大的，编号最小的值减一，要求使得 \(i\) 是编号最小的最大值的步数。那显然是都怼到 \(-x_i\) 处然后算一算有多少编号比 \(i\) 小的即可。这个可以树状数组，复杂度 \(O(n\log n)\)。

GYM104053H GameX

最优策略肯定是每次找到一个最小的还没出现的自己会输的数值填上，所以直接搞两个指针指一指就好了， 复杂度 \(O(n)\)。

GYM104053L Station of Fate

把 \(n\) 个数分成 \(m\) 组，每组至少一个人的方案数是 \(\binom{n-1}{m-1}\)，再分配上顺序，总和就是 \(n!\binom{n-1}{m-1}\)。

GYM104053I Infection

设 \(f[i,j]\) 代表以 \(i\) 为根的子树选了 \(j\) 个节点，不定根的概率，\(g[i,j]\) 代表定根的概率，然后转移的时候就分类讨论一下根有没有定即可。根据树形背包的理论，复杂度为 \(O(n^2)\)。

GYM104053M XOR Sum

从大到小考虑每一位，枚举有多少为卡到上界，再枚举 \(0,1\) 的个数，那么就可以算出低位对高位的进位，把这个也计入状态中转移即可。复杂度是个很小的东西，所以应该咋写都能过。

GTM104053J Math Exam

显然有 \(a_i=a_{i-1}+2\) 或者 \(-a_{i-1}\)。设 \(b_i=|\frac{a_i+1}{2}|\)，

A Alice and Her Lost Cat

K Middle Point Graph