T1
一眼秒了，15min 写过。
思路比较简单，设 \(f_{i,j}\) 表示长度为 \(i\)，第 \(i\) 位填 \(j\) 的序列的个数，那么转移从比 \(j\) 小的数和 \(j\) 的倍数转移就好了。
复杂度调和级数。
T2
非常抽象。看错了两遍题，变成了三个不同的题。写了三份不同的代码。
最后时间紧迫，最后一份代码没调对。非常搞笑。
我的做法比 std 麻烦一点，其实差不多。
首先容易发现这是一个子序列 dp。数据范围很小，那么可以大胆设状态。
设 \(f_{i,k,0/1}\) 表示前 \(i\) 座城池，一共选了 \(k\) 个城池，第 \(i\) 个选/不选的答案。
枚举上一个选的城池 \(j\)，考虑 \(j \sim i\) 之间的士兵的贡献。\(j+1 \sim \lfloor \frac{i+j}{2} \rfloor\) 的士兵会选 j，其余的会选 \(i\)。预处理一个前缀、后缀和，就可以快速算出一段区间到 \(i\) 的贡献。
转移就非常简单了。
T3
考场上没看题，考后思路一眼出，估计场上 20min 就可以写完。
T4
巧妙的转化。没见过还真不一定能做出来。