做题历程
8:00 ~ 8:40
写A。
8:40 ~ 9:40
看B,C想B，写B。
9:40 ~ 10:40
手玩了一下C，推出了那个规律。
10:40 ~ 11:20
写C。
11:20 ~ 12:00
看了看D，尝试写dp暴力，没空，最后随便写了写。
总结
- 写代码要注意细节，不然容易挂。
题解
A
倒序做一遍双指针，没什么好说的。
不过有很多人用奇怪的数据结构，不知道怎么做的，感觉很奇怪。
B
用期望+区间dp或直接区间dp即可。
需要一点排列组合。
C
需要知道一个规律，即最终合法情况一定是每一行BRBR交替，或是每一列BRBR交替，
所以直接判断一下，是否能行交替或列交替，直接算即可。
注意可能有重复情况，需要特判。
D
根号分治+树形dp。
首先考虑暴力dp，设 \(dp_{i,1/0}\) 表示 \(i\) 的子树内所有关键点都被满足，且 \(i\) 在/不在 联通块内的最小代价。
有转移方程
\[dp_{i,0}=\sum_{v\in{Son_u}}min(dp_{v,0}, dp_{v,1}) \]\[dp_{i,1}=\sum_{v\in{Son_u}}min(dp_{v,0}, dp_{v,1}-k) \]很难看出，对于一个固定的 \(k\)，在最优情况下，选择的联通块的数量大约是 \(\frac{n}{k}\) 这个级别的。
感性理解，对于每个关键点，与它距离小于 \(k\) 的关键点，都会在同一联通块中。
所以最终答案中联通块距离一定大于 \(k\)。
所以对于 \(k \leq \sqrt{n}\) 直接暴力dp，因为卡常，所以需要加一个dfs序优化。
对于 \(k > \sqrt{n}\) 需要一个树形背包。
设 \(dp_{i，j,1/0}\) 表示 \(i\) 的子树内所有关键点都被满足，使用了 \(j\) 个联通块，且 \(i\) 在/不在 联通块内的最小代价。
转移同上。
标签：33dai,联通,暴力,40,交替,35,NOIP2023,dp,关键点 From： https://www.cnblogs.com/PeyNiKge/p/17745853.html