20231014 NOIP#20总结
时间安排
7:40~8:15
看题，\(A\) 一眼切了，\(B\) 有点感觉不知道能过多少，\(C,D\) 都不太会。
8:15~8:25
写 \(A\)。
8:25~9:25
\(B\) 拼个包，左右拼了 \(70\)。
9:25~10:00
发现 \(C\) 部分分是个区间 \(DP\)，快写。
写完后输出一下方案找到了结论，哦这道题会了。
10:00~10:10
写 \(D\) 的两个特判有 \(20\)
10:10~10:30
猜出来了 \(B\) 的结论写了。
总结反思
- 别乱压行小心系统导致错误
题解
A.并查集
只用判断奇偶性直接并查集模拟即可。
B.结论题
对于每一条边，把他连接的两个点中权值较小的那个的权值加起来就行了。
换言之，将其按点权从大到小排序依次选择模拟即可。
C.结论题
如果某个数在两边都不是 \(1\)，等到它两边至少有一个是 \(1\) 时删，答案肯定不会变差，所以就按照序列里的每个 \(1\) 划分连续段。
对于每个连续段，最后一个数（设为 \(x\)）的左右肯定都是 \(1\)，这一段的代价是 \(x + \sum a[i]\times a[i+1]\) 那么取最小值作为 \(x\) 便是最优方案。
D.转化题目
\(1.\) 这个题目里，对于满足 \(x_i<x_j\) 且 \(y_i>y_j\) 的点对 \((i,j)\)，若 \(i\) 向右走，则 \(j\) 必须向右走。
\(2.\) 上升子序列中，对于满足 \(i<j\) 且 \(y_i>y_j\) 的点对 \((i,j)\)，若 \(i\) 选，\(j\) 必须不选。
在这种对应关系下，\(1\) 中合法的方案，\(2\) 中也一定合法，另个情况的方案是一一对应的，则按照 \(x_i<x_j\) 和 \(y_i>y_j\) 排序后的上升子序列数就是答案。
标签：iy,10,结论,20231014,向右走,25 From： https://www.cnblogs.com/programmingysx/p/17764501.html