20221005考试总结
总结
T1
挺套路的题，通过 00 11 得到 \(1,0\) 的个数，容易发现 10 01
的总个数已经被确定且容易构造。
但是有边界，考虑 00 11 个数为 \(0\)，此时可以取 \(1\) 个也可以取 \(0\) 个。然后 100->55
这种两个构成的计数问题，一定要考虑只有一个的边界情况，
注意我们通过题目信息得到新信息的过程，要看看是否为一一映射。
T2
有趣的题。
我先思考了如果一个问题我限定一个时间 \(T\)，等 \(T\) 秒过完，得到的收益，实际上我们可能有根据当前信息改变等待的这个时间，所以这样不行。
接着考虑 \(t\) 时刻到 Trie 上 \(j\) 点的最优方案，发现其实不好转移。
注意到我们能决定的只有回答还是等待，所以这样的话转移会带上一个概率，但是这个概率却是无法相加后取最值的。
正难则反，考虑到 \(j\) 点时还剩时间 \(t\)，最优能得到什么，这样的话，转移就只和我们的决定有关，成功解决这道题。
T3
等价于求最优解并构造方案。
它的修改本质上是需要决定一个最值，付出对应的代价，然后如果某个数绝对值严格小于最值，那么这个数的正负性就可以被指定，然后指定最值后最优化代价就是要求出删去的数的最小个数。
我们需要求出对于每个最值的删除数最小个数。
由于不让 \(0\) 出现，所以先判掉不修改只删除的方案，这个是简单的。
有两种思考方式，对应了两种求答案的方式。
一个数为负视为 -1，为正视为 1，可调整视为
0
Method1
考虑一段极长连续相同子段，如果不为
0，那么必须删去然后只剩下一个。
如果为
0，其左右两边的状态和自身长度决定了它应该被删去一个或者不做任何处理。
如果能够维护机场连续相同子段，就可以得到答案。
考虑最值从小到大变化的过程，每次会把一个非 0 数改为
0，经典的 set 维护线段问题。
Method2
考虑动态规划。
设 \(dp[i][0/1]\) 表示考虑到第 \(i\) 个数，末尾为 \(-1/1\) 的代价。
\[ v_i=0:dp[i][o]=\min(dp[i-1][o\oplus 1],dp[i-1][o]+1)\\ \]
\[ v_i\ne0: \begin{cases} dp[i][v_i]&=\min(dp[i-1][v_i\oplus 1],dp[i-1][v_i]+1)\\ dp[i][v_i\oplus1]&=dp[i-1][v_i\oplus 1]+1\\ \end{cases} \]
然后就是动态 DP，考虑能不能写成矩阵乘法的形式，发现是一个 \(+\min\) 矩阵乘法。
线段树维护即可。