模拟赛 29 题解

思维+模拟+计数+子树贡献+决策单调性

A.数上的数

每个数管辖一定的范围，随便做就好了。

B.矩阵游戏

计数好题。

首先考虑一行或一列异或两次就会变回来，所以直接考虑奇偶性就可以。

我们可以分行列考虑，计算有 $i$ 行染黑和有 $j$ 列染黑的方案数。

注意这里的 $i$ 和 $j$ 都要和 $k$ 的奇偶性相同，因为染两次相当于没染。

但是这样会算重，如果把行列的状态取反，那么原来被染了一次的还是染了一次，原来染了两次还是相当于没染。

如果一个取反后的状态仍被统计，那么它的贡献就要乘 $\frac 1 2$。

之前的条件是 $i,j\leqslant k,i,j\equiv k\pmod 2$，取反后若仍满足条件，则为 $n-i,m-j\leqslant k,n-i,m-j\equiv k\pmod 2$。

C.隐藏食物

二进制枚举每一位后，变成统计树上两个组两两间路径的和。

考虑每条边的贡献就好了。

D.魔法商店

这里是小体积多物品01背包的通法——决策单调性。

先按体积分组，每组内必定是从大到小取。

仿照多重背包的单调队列解法，当考虑到体积为 $w$ 的物品时，按 $\mod w$ 的剩余系分类。

枚举余数为 $r$，我们集中考虑体积为 $kw+r$ 这一类状态，其中 $k$ 是上界。

那么我们当前的决策区间就是 $[0,k]$，可以证明这是有决策单调性的。

因为相同体积，取得越多，肯定价值越劣。所以关于 $f$ 有决策单调性。

jzp 给出了一种证明：把背包的容量看成自变量，价值看作函数。

在固定体积的情况下，这个函数是上凸。

由于容量 $d$ 增大，肯定拿的价值变多，所以函数向上向右移动。

又因为是凸函数，所以具有决策单调性。