康复训练（一）

P11268 买东西题

很明显的反悔贪心。

首先对物品按照原价从小到大，满减券也按照 \(w\) 从小到大，这样每个物品能使用的满减券对应一个前缀。

对于任意一件物品，要么花费 \(b_i\) 要么花费 \((a_i-v_x)\)。

如果是前者，对后面没有什么影响。

如果是后者，这件物品使用了一张满减券，有可能之后再用更优，所以需要考虑反悔。

当且仅当 \(a_i-v_x+b_j>b_i+a_j-v_x\) 时，反悔更优。

充分性显然，主要说一下必要性。

由于 \(i\) 能用的满减券 \(j\) 也能用，所以如果 \(i\) 选择换一张券而且更优那还不如让 \(j\) 用，这样不可能出现上诉情况。

所以不等式变为 \(a_j-(a_i-b_i)<b_j\)，等价于使用了一张 \((a_i-b_i)\) 的满减券。

实现方面采用大根堆，每次将使用堆顶满减券与优惠价比较，如果用了插入反悔策略即可。

1349C Orac and Game of Life

一道思维题。

任意一个 \(s\ge 2\) 的同色连通块在每一刻的颜色均相同，且每次变为另外一种颜色。

即使是 \(s=1\) 的孤立点，如果其周围有 \(s\ge 2\) 的连通块，下一刻它也会被融入连通块。

所以 \(s=1\) 的孤立点最后一定会被最近的连通块所融入。

BFS 即可。

LOJ 无聊的数对

首先考虑 \([1,n]\) 如何求无聊的数对。

对于 \(x\le y\)，假设 \(x\) 和 \(y\) 分别有 \(w_x\) 和 \(w_y\) 个 \(1\)，那么异或起来必定会少偶数个 \(1\)，所以最后有 \((w_x+w_y-2k)\) 个 \(1\)。

所以当且仅当 \(w_x\) 和 \(w_y\) 奇偶性不同时才有奇数个 \(1\)，答案也就是有奇数个 \(1\) 的个数与有偶数个 \(1\) 的个数相乘。

回到问题，这时候不能用暴力求解了，发现个数具有可加性，考虑线段树，但空间不够，需要动态开点。

接着考虑一个线段树区间如何求个数，发现有偶数个 \(1\) 的个数就是长度除以 \(2\)。

证明需要用线段树的性质，如果以 \([0,2^{32}-1]\) 建线段树，那么每个区间都类似于 \([2^a,2^b-1]\)（此时认为左端点时 \(2^0=0\)）

所以每个区间会长成这样：\(000\dots0-111\dots 1\) ，令 \(1\) 有 \(sum\) 个，且忽视开头的 \(1\)。

如果 \(sum\) 为奇数，那么任意一个有偶数个 \(1\) 的数取反后对应一个奇数个 \(1\) 的数。

如果 \(sum\) 为偶数，那么忽略第一个便变为奇数情况，加上第一个过后只不过对数变为两倍。

得证。