目录题目[WC2006]水管局长题面：题解：[FJOI2015]火星商店问题题面题解[USACO13OPEN]阴和阳Yin and Yang题面题解[51nod]1472 取余最大值题意题解CF1137C Museums Tour题面题解
题目
以下题解里面要是有不对的地方欢迎提醒/打脸。
[WC2006]水管局长
题面：
题解：
首先根据一些常识,我们可以发现，符合要求的边一定在最小生成树上，因为有删边操作，因此我们需要做的就是动态维护最小生成树。
因为删边不好处理，因此我们可以直接倒着处理，这样删边就变成加边了。
因为要维护边，因此我们考虑将每条边都视作一个带权中转点。即对于x — > y的边，连x —> now — > y,其中now为一个带权点。
同时如果已经构成一棵树，我们要再往里面塞边的话，就必须要删掉一条边，否则会构成环。
因此对于一条连接x —> y，边权为(k)的边，我们查询x — > y路径上边权的最大值(maxn)，那么会有2种情况：
(maxn > k)，那么说明插入这条边是优的，因此我们删去最大值所代表的边，加入当前边
(maxn le k),那么说明保留最大值比较优，所以我们忽略这条边，不进行修改。
然后就可以了。
[FJOI2015]火星商店问题
题面
题解
观察到，如果没有最近d天的限制，那么我们只需要将所有物品按照所属商店的顺序加入可持久化trie树。
如果我们要查询商店编号在([ll, rr])之间的最大xor值，那么我们只需要查询区间([l, r])内的xor最大值即可。
其中(l)表示第一个属于查询范围内的物品编号，(r)表示最后一个属于查询范围内的物品编号。
具体如何获取这2个编号？因为物品是按照所属商店顺序加入的，所以我们只需要在加入的物品序列中二分一下就可以了。
那么再考虑最近d天的限制。
相当于是查询商店编号属于([ll, rr]),时刻属于([l, r]) 内的最大xor值。
我们考虑线段树分治。
对于每个询问区间，我们将它的查询时刻区间分成log段，挂在线段树上。
对于每个物品，因为我们需要将物品按照所属商店的顺序加入，因此对于线段树上的每个区间，我们都需要重建整个可持久化trie树。
不过因为物品是一个单点修改，因此就算我们在每个包括了这个物品的区间都放一个这个物品，每个物品也最多放log个。
因此我们在每个包括了这个物品的区间内放一个这个物品，然后每到一个区间，就取出所有在这个区间内出现过的物品，重建整棵trie树。
然后对于每个挂在这个区间上的询问，二分我们需要查询的物品区间，在可持久化trie树上查询并更新这个询问的答案。
最后再输出即可。
复杂度是(O(nlog^2n))的
[USACO13OPEN]阴和阳Yin and Yang
题面
题解
看上去点分搞搞就可以了？
[51nod]1472 取余最大值
题意
有一个长度为n的数组a，现在要找一个长度至少为2的子段，求出这一子段的和，然后减去最大值，然后对k取余结果为0。
问这样的子段有多少个。
题解
之前做过这题的树上版本，可以直接套上来做。
我们考虑点分治，因为拼接2条路径时需要知道最大值是谁，所以不能直接做完个子树就放桶。
我们考虑容斥，先求出所有的路径，按照max从小到大排序，然后每枚举到一条线段，就减去max然后在桶里面找方案，再加入桶。
但是这样会有重复，因此我们单独求出每棵子树内部互相匹配的方案。然后用总方案减去这部分，就得到了答案。
CF1137C Museums Tour
题面
一个国家有 (n) 个城市，通过 (m) 条单向道路相连。有趣的是，在这个国家，每周有 (d) 天，并且每个城市恰好有一个博物馆。
已知每个博物馆一周的营业情况（开门或关门）和 (m) 条单向道路，由于道路的设计，每条道路都需要恰好一个晚上的时间通过。你需要设计一条旅游路线，使得从首都：(1) 号城市开始，并且当天是本周的第一天。每天白天，如果当前城市的博物馆开着门，旅行者可以进入博物馆参观展览，否则什么也做不了，这一天的晚上，旅行者要么结束行程，要么通过一条道路前往下一个城市。当然，旅行者可以多次经过一个城市。
要求让旅行者能够参观的不同博物馆数量尽量多（同一个城市的博物馆参观多次仅算一次），请你求出这个最大值。
题解
如果我们对原图缩点会怎样？
每个强联通分量的贡献会随着进入的时间而改变。
考虑到(d)不大，可以考虑将每个城市拆成(d)个单独的点，((x, i))表示点(x)在星期i的状态，再用((x, i)) —> ((x, i + 1))，然后再缩点。
那么我们会发现，一旦我们可以到达一个点，并且((x, i))是开启状态，那么我们一定可以获得这个贡献，因为我们走(k)到达的，一定是某个城市的第(k)个状态。因此我们就可以在新图上直接跑最长路了。
支付宝扫一扫
微信扫一扫
最新评论