11/10

Link。

考虑次小生成树的大小，显然如果加了一条边后再删一条边，删的边权值一定要严格小于加的边，所以就求出所有加的边和删的边权值相同可以加的边数。

为何不考虑加的边权值小于删的边？如果存在这种边，显然最小生成树不优。
Link。
答案显然能取到下限，因为有 \(t_j<a_{s_j}\)。
Link
设 \(f_{i,j}\) 表示前 \(i\) 个数，后缀极长同色串起点为 \(j\) 的方案数。

考虑题目给的限制，对于区间 \([l,r]\)，如果 \(x=2\) 那么以 \(r\) 结尾的串中，极长同色串起点必定 \(>l\)；如果 \(x=1\)，那么 \([l+1,r]\) 的所有点不能新开一个极长同色串。

于是就做完了
Link。
典题。

显然二分图匹配后，选择一侧作为 \(2\) 的集合，考虑到有多个连通分量，显然 DP。

注意二分图匹配失败的话一定无解。

Link。
数学题。

考虑最大的数是 \(x\)。

如果只选一个数，显然为 \(x\)。

如果选两个数，设为 \(a,b\)，若 \(a,b\) 都不为 \(x\) 因子，那么把较小的替换为 \(x\) 一定不劣，其他情况同理，可以证明一定要选择 \(x\)，然后再选择非 \(x\) 因子的最大数。

如果选三个数，同选两个的，但是注意 \(\dfrac{a}{2}+\dfrac{a}{3}+\dfrac{a}{5}>a\)，这是唯一的例外，直接特判即可。