Public NOIP Round

Public NOIP Round

A

经过一定分析可以发现合法数很少，写个爆搜+剪枝把所有答案先跑出来，查询二分即可。

O(?X+Q\log X)

56740

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)

56884

C

每个连通块独立，分别考虑。

根据提示，容易想到按图是否为二分图分类。

若该连通块为二分图，将该图黑白染色，两图的左黑+右白、右黑+左白数量相等，容易证明这是充要的。

若该连通块不为二分图，即其必含奇环，注意到变换之和为偶数，故黑、白点奇偶性相同，且权值集合相同，容易证明这是充要的。

56887

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)