Public NOIP Round
A
经过一定分析可以发现合法数很少，写个爆搜 剪枝把所有答案先跑出来，查询二分即可。
O(?X Qlog 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(nlog n)
56884
C
每个连通块独立，分别考虑。
根据提示，容易想到按图是否为二分图分类。
若该连通块为二分图，将该图黑白染色，两图的左黑 右白、右黑 左白数量相等，容易证明这是充要的。
若该连通块不为二分图，即其必含奇环，注意到变换之和为偶数，故黑、白点奇偶性相同，且权值集合相同，容易证明这是充要的。
56887
D
只需要考虑 1times x 5times y 即可。
贪心地想，容易发现每次只会选一个物品。
综合上述，一个代价为 a_i 的物品价值为 5lceil frac {a_i}5rceil-a_i，其新代价为 lceil frac {a_i} 5rceil，而总新容量为 lfloor frac m5rfloor，初始答案为 mbmod 5。
注意到价值很小，可以将价值放到状态里，设 f_{i,j} 表示考虑所有代价 leq i 的物品，获得价值为 j，所需要的最小代价。
显然其满足决策单调性，将所有代价为 i 的物品抽出来排序求前缀和，转移即可。
O(nlog n)
