JSOISC2022模拟2
update 2022-07-17
前言
暴力出奇寄（
不会写正解就算了，暴力还出了那么多 sb 问题。T2 手残打错，void dfs 写成 int dfs，T3题目看错 ，T4 \(2 \times 10^{5}\) 但数组开的是 \(10^{5}\)。（关键样例和自己造数据都没查出来？）
wssb。
T1
按位考虑，记录第 \(i\) 位初始时是 \(0/1\) ,最终会变成什么。
（考试时怎么就没想到（wssb
例题 P2114 起床困难综合症
T2
可以把不能在一组的星星之间连边，可以发现是一堆长度 \(\leq 5\) 的链和长度为 \(6\) 的环。
可以先处理出所有链和环的大小，然后计算出从链（或环）中选出 \(k\) 个星星的方案数。
设链（或环）的大小为 \(m\);
链的问题就是从 \(m\) 个元素中选出 \(k\) 个不相邻元素的方案数，即 \(C_{m-k+1}^{k}\)。
环的问题可以用链的方案数减去两端都选的方案数，即 \(C_{m-k+1}^{k} - C_{m-k-1}^{k-2}\)。
最后的答案用背包处理， \(dp[i][k]\) 表示选择 \(k\) 个星星的方案数，为了节省空间，第一维可以用滚动数组。
T3
前置知识：
\(O(1)\) 查询 LCA
根号分治例题 P3396 哈希冲突
树的直径例题 P1099 树网的核
T4
线段树骗部分分（
咕咕咕