题解：P14408 [JOISC 2015] IOIOI 卡牌占卜 / IOIOI Cards

· · 题解

字符串给定的形式是 A,B,C,D,E，这是相当奇怪的。

区间操作转化成差分，每次操作选一条边，花费边权的代价将连接的两个点状态取反，则有些点要求被操作奇数次，有些点要求被操作偶数次。

你的操作肯定不会成环，而一条路径只会对路径的两端造成影响。所以你本质上要对奇数点求一般图最小权完美匹配，两点边权是图上最短路。

这看起来完全不可做啊，但是字符串给定的形式是 A,B,C,D,E，所以只有 O(1) 个奇数点，有点搞笑。