T1：
简单贪心。
T2：
有的\(n\)间屋子被\(n-1\)条双向路径连通，构成树结构。其中第\(i\)个屋子中住着一个种族\(c_i\)的狼人。
树的一个连通子图中，若其中一个种族的狼人超过了其他种族的总和，它们可以在该连通子图中进行支配。具体而言，记\(a_i\)为种族为\(i\)的狼人在连通子图中的个数总和，则支配的条件是存在\(k\)使得\(a_k>\sum_{i\ne k} a_i\)。
那么，有多少个不同的连通子图会出现支配的情况？答案对998244353取模。
\(\dagger\) 连通子图指点集和边集分别为原图点集和边集的子集，且连通的图。子图不同，当且仅当选择的点集和边集至少有一个不完全相同。
考虑对每一种种族各自求一遍答案。对于一个种族，让是这个种族的结点权为 \(1\)，否则权为 \(-1\)，即计数有多少个连通子图的权值和为正数。
\(dp[i][j]\) 表示 \(i\) 的子树内权值为 \(j\) 的方案数。\(j\) 的范围既是当前种族总个数，又是 \(sz[i]\)。根据树上背包经典分析，复杂度为 \(O(n\cdot \sum cnt[i])=O(n^2)\)。
T3：
对一个全排列\(a_1,a_2,\cdots,a_n\)，给定\(m\)并依次做如下操作
- 对\(a_1\sim a_m\)进行从小到大排序；
- 对\(a_2\sim a_{m+1}\)进行从小到大排序：
- ……
- 对\(a_{n-m+1}\sim a_{n}\)进行从小到大排序：
注意每次排序都改变了\(a\)序列，每次的\(a_i\)指上一轮排序后处在\(i\)位置的数。
我们不知道初始的\(a\)，只知道排序的最终结果，记做\(b_1,b_2,\cdots,b_n\)。求所有可能的初始\(a\)中，字典序第\(k\)小的？保证存在\(k\)个不同的初始\(a\)。
若出现 \(b_{i-1}>b_{i}\)，说明 \(b_i\) 这个数初始位于 \(a_{i+m-1}\)，然后可以把 \(b_i\) 这个位置删掉。
由此得到一个单调上升的序列 \(b'\)，即求对应 \(b'\) 的字典序第 \(k\) 小的 \(a'\)，把 \(a'\) 按顺序填回 \(a\) 里还没有被确定的位置即可。
一般字典序都是试填法，看填最小的行不行 …… 逐渐增大，每次减去对应方案数。
考虑怎么求方案数。发现 \(b'_1\) 必然是在 \(1\sim m\) 的位置里随便填一个，\(m\) 种；\(b'_2\) 在 \(1\sim m+1-pos[b'_1]\) 的剩下 \(m\) 个位置里选一个，也是 \(m\) 种 …… 直到后面的位置不够了，变成 \(m-1,m-2,\dots,1\)。
然后不太清楚了 …… 总之是试填法。
T4：很少见到这么纯种的人类智慧。
给定正整数\(K\)，请构造两个01串\(S,T\)，使得他们恰好有\(K\)个本质不同的最长公共子序列。
额外给定参数\(L\)，构造的串必须满足\(\max(\vert S\vert,\vert T\vert)\le L\)。
考虑对于两个 01 串，记 \(g(x,y)\) 为有多少种不同的 LCS，使得尽量取字典序最小的结束位置时，落点恰好是 \((x,y)\)。
这是对所有 LCS 不重不漏的分类。
构造初始串 \(S=1,T=11\)，此时 \(g(1,1)=1,g(1,2)=0\)。设当前 \(\sum g(x,y)=k\)，我们希望通过在 \(S,T\) 后面增加常数个字符，达到让 \(k+1\) 或 \(k\times 2\) 量级的效果。这样可以在 \(2\log n\) 长度构造出来。
事实上这是可行的，我们增强结论，让所有 \(g\) 在 \(g(|S|,|T|)=k,g(|S|,|T|-1)=1\)，其余位置 \(0\)。
如果要 \(k+1\)，可以 \(S+0100,T+000\)；如果要 \(k\rightarrow 2k+1\)，\(S+101000,T+011000\) 即可。
标签：11,连通,vert,NOIP,种族,子图,2024,排序,sim From： https://www.cnblogs.com/FLY-lai/p/18574297