Public NOIP Round
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}$。
有转移：
$$
f_j \leftarrow f_i + 1
$$
其中，$j\in [g_i,g_{g_i}) \land a_j > a_i$。
其中 $a_j>a_i$ 限制，直接按 $a_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)$