20231017 NOIP#22总结
时间安排
7:50~8:25
看题，\(A\) 会最一档，\(B,D\) 不会。
8:25~8:40
写 \(A\) 最低档的暴力。
8:40~9:30
想了一会 \(A\) 感觉不太能延伸了，写 \(B\) 的 \(n^2\) 暴力。
9:30~10:00
写 \(C\) 链的特殊性质
10:00~10:40
想了个 \(D\) 的做法假了，写个爆搜结束了。
10:40~11:50
罚坐中——最后 \(C\) 斜挂了。
总结反思
- 想不出来就检查检查暴力尝试优化
题解
A.DP
这个 \(DP\) 非常厉害！
设 \(f[i]\) 表示第 \(i\) 天结束了，目前从能力为 \(0\)，未来能达到目标的概率。（一看这个状态就非常厉害
考虑将整个序列划分为几个连续段，设第 \(i\) 个段的长度为 \(l_i\)，权值和为 \(s_i\)，则整个序列的答案为：
\[\sum_{i=1}^n (\ \frac{s_i}{1000} \times (\prod_{j=1}^{i-1} (1-\frac{s_i}{1000})) \times (\prod_{j=1}^i (1-p)^{l_j})\ ) \]考虑倒着 \(DP\)，设 \(s[i]\) 为前 \(i\) 个的权值和，转移方程为
\[f[i]=\max\{f[j]\times (1-p)^{j-i}\times (1.0-(s[j-1]-s[i-1]))+(1-p)^{j-i}\times (s[j-1]-s[i-1])\} \]后面一大串化简一下其实是和答案的式子是一样的。
在考虑若 \(s[j-1]-s[i-1]\geq 1000\) 那在这个地方断开答案显然不会更差，对于所有能力为 \(0\) 的点直接忽略，所以每个 \(i\) 最多转移 \(1000\) 次，复杂度是 \(O(1000n)\) 可过。
B.主席树
按 \(a_i\) 从小到大处理，以 \(a_i\) 为阶段建主席树，对于每个 \(a_i\) 将其影响到的区间（即 \([\max(i-m+1,1),i]\)）区间加一，询问就是第 \(x\) 个版本中区间 \([l,r]\) 的最大值。
C.bitset优化+构造
D.折半搜索+高位前缀和
首先特判 \(m=0\)
以 \(0,1,2,3,4\) 分别代表“白色边”、“紫色边”、“黑色边”、“白色点”、“紫色点”。
要求 \(012\) 每个至少一个，则答案为 \(\{012\}-\{12\}-\{02\}-\{01\}+\{2\}+\{1\}+\{0\}-\{\emptyset\}\) （\({x}\) 表示出现 \(x\) 的方案数。
设 \(cnt\) 为联通块数，\(sep\) 为独立节点数。则有显然的几个答案为：
\[\{012\}=2^n\ \ \{02\}=2^{cnt}\ \ \{2\}=2^{sep}\ \ \{0\}=2^{sep}\ \ \{\emptyset\}=0 \]考虑 \(\{1\}\)，等价于将图黑白染色，如果可行则方案为 \(2^{cnt}\)，否则为 \(0\)。
考虑 \(\{01\}\) 和 \(\{12\}\) 情况一样，以 \(\{12\}\) 为例，即图中没有相邻都为 \(3\) 的点。
将 \(n\) 个点折半搜索，\(f[s]\) 状压表示后半部分中（当然那一半都行）满足条件的点集为 \(s\) 的方案。设右半部分点的全集为 \(U\)，再搜索前半部分，当搜索到合法点集 \(t\) 时，统计 \(t\) 中的点与右半部分相邻的点的点集为 \(T\)。
\[\{12\}+=\sum_{s\subset \complement_U T} f[s] \]后面这个 \(\sum\) 可以预处理高位前缀和解决。
标签：10,12,20231017,40,times,012,1000 From： https://www.cnblogs.com/programmingysx/p/17770500.html