前言
开始口胡
T1
题目大意
序列 $s$ 中的 $x$ 满足
- $x$ 不包含数码 $\texttt{7}$。
- $x$ 的所有因数的数码不包含 $\texttt{7}$。
有 $T$ 次询问，每次询问给定 $a$，询问 $a$ 在 $s$ 中的后继或返回 $a\in s$。
$1\le a\le 10^7$。
题解
CCF 两年之内最水的签到题，可以类似埃筛的做法直接预处理范围内不满足的数，用二分或预处理每一个数的后继即可。
时间复杂度 $O(n\log n- O(T\log n)$ 或 $O(n\log n)- O(T)$。
T2
题目大意
构造一个长度为 $n$，权值范围为 $[0,m]$ 的序列 $a$，设 $S=\sum_i 2^{a_i}$，$S$ 需满足 $\text{popcount}(S)\le k$。
定义一个序列的权值和 $w_a=\prod_i v_{a_i}$。求 $\sum_a w_a$。
$1\le k\le n\le 30$，$1\le m\le 100$。
题解
首先考虑暴搜，时间复杂度 $O(m^n)$。期望得分 $20$。
可以剪枝，倒序枚举，若当前状态的 $\text{popcount}(S) > k$ 退出，同时保证序列递减，统计答案时用组合数算一下即可。这里期望得分 $30$。
正解是 DP。考虑到每次加一个数时会对 $\text{popcount}$ 产生多少贡献，可以记一个累计进位，多设 $2$ 维状态。
钦定 $a_i$ 单调不降，设 $f(i, j, k, l)$ 表示当前数为 $i$，剩下 $j$ 个数，有 $k$ 个进位，$\text{popcount}$ 为 $l$。 则有
$$
f(i + 1, j - x, \dfrac{k + x}2, l + (x + y) \bmod 2)=\sum_{x=1}^j f(i, j, k, l) \times \dbinom{j}{x}\times v_i^x
$$
时间复杂度 $O(n^4m)$。
T3
题目大意
给定序列 $a$，一次操作可以选取 $i\in(1,n)$，将 $a_i\gets a_{i - 1} + a_{i + 1} - a_i$。问经过若干次操作后，$a$ 方差的最小值。
题解
首先考虑乱搞，由于只有单组数据，可以用模拟退火求最优值。期望得分 ？。
首先要知道这个操作的意义，考虑将 $a$ 映射到数轴上，一次操作相当于将 $a_i$ 对 $(a_{i-1},a_{i+1})$ 的中点做一次对称操作，即两端距离仍未改变。则问题转化为所有线段经过一系列交换之后，使得端点的方差最小。
那么显然，方差最小指所有数离平均数的距离更近，则自然可得这些线段的长度构成一个单谷，即先降后升。
至此，我们可以将所有线段的长度降序排序，考虑每个线段放在左端或右端，时间复杂度 $O(2^n\times n)$。
再次考虑 DP，设 $f(i, \sum_i a_i)=\min\{\sum_i a_i^2\}$。表示当前枚举到第 $i$ 条线段的状态。则有
$$
f(i + 1, \sum_i a_i+x)=f(i,\sum_i a_i)+x^2
$$
$$
f(i + 1, \sum_i a_i + i \times x)=f(i, \sum_i a_i)+2\sum_i a_i \times x+x^2i
$$
分别表示当前线段放在左边或右边的贡献。
时间复杂度 $O(nm\min\{n,m\})$。
T4
题目大意
$x^n+y^n=z^n$
题解
首先依题意模拟有 $24$ 分。
先考虑走空格的贡献，注意到 $1$ 道路可以特判，$2$ 道路可以直接维护一个点所能走到的范围，$3$ 道路可以用并查集维护一个联通块。但是加上一个点相当于将一个联通块分裂，不易维护。可以倒序处理每一个点，每次将几个连通块合并即可。
其次考虑重复的贡献，需要用一个数据结构维护一段线段在联通块之内的贡献。
再次考虑棋子的贡献，可以维护每一个联通块能达到的点集，与上种贡献类似。
至此，我们需要一个数据结构支持合并和查询一段区间信息，可以用线段树合并实现。
时间复杂度 $O(nm\log nm)$。
后记
口胡结束