Public NOIP Round
Public NOIP Round
yzxoi
2022-10-21 (Updated: 2022-10-21)
DP, 二分, 二分图, 决策单调性, 剪枝, 爆搜, 线段树, 线段树优化 DP, 背包, 贪心
A
经过一定分析可以发现合法数很少，写个爆搜+剪枝把所有答案先跑出来，查询二分即可。
O(?X+Q\log X)
B
很容易设出一个简单的 DP，设 f_{i} 表示当前子序列结尾为 a_i，且保证最终一定含 a_i，长度最大值。
设 g_{i,j} = \min { j> i \land a_j > a_i}
有转移：
其中，
其中 a_j>a_ia_i 从小到大枚举即可。
线段树辅助转移。
特别注意，初始合法的点仅为 [1,g_1]。
O(n\log n)
C
每个连通块独立，分别考虑。
根据提示，容易想到按图是否为二分图分类。
若该连通块为二分图，将该图黑白染色，两图的左黑+右白、右黑+左白数量相等，容易证明这是充要的。
若该连通块不为二分图，即其必含奇环，注意到变换之和为偶数，故黑、白点奇偶性相同，且权值集合相同，容易证明这是充要的。
D
只需要考虑 1\times x+ 5\times y 即可。
贪心地想，容易发现每次只会选一个物品。
综合上述，一个代价为 a_i 的物品价值为 5\lceil \frac {a_i}5\rceil-a_i，其新代价为 \lceil \frac {a_i} 5\rceil，而总新容量为 \lfloor \frac m5\rfloor，初始答案为 m\bmod 5。
注意到价值很小，可以将价值放到状态里，设 f_{i,j} 表示考虑所有代价 \leq i 的物品，获得价值为 j，所需要的最小代价。
显然其满足决策单调性，将所有代价为 i 的物品抽出来排序求前缀和，转移即可。
O(n\log n)
Copyright ? 2019-2022 yzxoi