Untitled

Untitled

展开思考过程

Hinted 3/5 似乎没有性质，因此考虑做一步转化。 考虑一个点若被同种边通过大于 2 次，那么 必然有一次没有用，考虑每条边可以是区间 +1 或者是区间 -k（k 足够大），要求最终每个点 <0 并且绝对值不是 k 的倍数 让我想到同余最短路，但是我们可以考虑最长路， Hint：你知道吗，对于 b>=a，所以第一个 区间是必须选择的，然后有一种贪心策略…… 但是之后就不行了，因为不知道哪个区间是必须选择的。 称完全包含一个区间的区间叫这个被包含区间的祖先 一个区间如有一个以上祖先，那么就是没有用的， 称没有祖先的区间为顶级区间，有一个祖先的区间为次级区间 所以只保留顶层的区间和有一个祖先的区间， 有一个祖先的区间， 它一定与祖先选择的颜色是不同的。 我们还可发现一个性质，一个顶级区间里面，如果有次级区间， 他们一定是连在一起的，否则无解，因为不能有非次级区间的外部 区间前来补位，否则就一定有被覆盖 2 次的 次级区间 补丁：被两顶级区间覆盖的次级区间有用吗？应该也是 没有用，只要有解，通过调整方案应该总是可以完成。 那么我们可以把连在一起的次级区间（必须属于同一个顶级区间）合成一个 合并之后的次级区间也不可能有包含的情况 由于没有不能染色的地方， 所以顶级区间一定覆盖了整个轨道。 现在的情况就是一个大的带一个小的，然后 大的和小的一定分属两个轨道，我们令 F(i,0) 表示从 i 出发， 选择配色方案的哪一种，最远到哪里，然后执行记忆化搜索， 总之我们就是要找个环，现在每两个都不是完全覆盖的，我们 每个点拆成两个，然后连有向边，最后就是找环的问题。 我们 topo 排序解决即可，我们最终还需要解决 如何找到顶层区间的问题，考虑按左端点排序， 在 set 等设施内记录当前已经扫过的顶层区间右端点 唉唉还是不太靠谱，分开考虑，一个 set 存跨越了 n 的那些，一个 set 存遍历过的那些，然后走的时候记得把 这个好像可以倍长断环做，先不管，先 N^2 验证一下 注意我们认为如果两个区间一模一样的话，小标号的覆盖 大标号的。 好像不是很对。。。。。。。