本文同时发表于个人洛谷博客。
部分收录于构造题部分。
2023.11.3
Luogu P2467
上一次CF就是被这个trick坑了！/ng
用 \(dp_{i,j,k}\) 表示第 \(i\) 个在前 \(i\) 个中的位置为 \(j\) 时的方案数，\(k=0\)表示是山谷，\(k=1\) 表示是山峰，显然可以写出转移方程：
\[dp_{i,j,0}=\sum_{k=1}^{j-1} dp_{i-1,k,1}
\]
\[dp_{i,j,1}=\sum_{k=j}^{i} dp_{i-1,j,0}
\]
前缀和加滚动数组即可。
CF1761D 2100
小清新题。
考虑连续进位串。发现除了第一位必须要选择 (1,1)，其他都可以任选(0,1)，(1,0)，(1,1)。
中间必须用（0,0）隔开。讨论连续段个数即可。时间复杂度 \(O(k\log n)\)，可以做到 \(O(k)\)。
2023.11.6
abc302h 空心橙
先考虑单个问题。每次操作在两点之间连边，发现对于每个联通块，如果是一颗树则是树的大小-1，否则为联通块大小。
用可撤销并查集维护即可，时间复杂度 \(O(n\log n)\)。