丁香

紫丁香 题解 前言 来自一场 \(\text{noip}\) 提高模拟赛的题目。 题目描述 有 \(n\) 点 \(m\) 边的 简单无向连通图，点编号为 \(0\sim n-1\)，要求删掉若干条边，最大化奇数度点的个数。 求：能得到最大答案的构造，用 \(m\) 长的 \(01\) 串表示，\( ......

首先有两个前置技巧：1) 两点间的最短距离就是直接连接两点的边的长度；2) 遍历一个子图的最小花费是最小生成树的边权之和乘二。原问题让我们找出一条最短且必经过钦定边的 \(( s, i )\) 路径，那么我们先将 \(\lang s , i \rang\) 连上，问题就变成了找出一条最短且必经过钦定 ......

膜拜 yxcat 考虑二分答案，将问题转换成验证 $A$ 是否由 $S$ 通过若干次操作生成 将操作效果反向，即存在一个操作 $x$，满足 $A_i=1$ 且 $x_i=1$，那么将 $A_i$ 处的 $1$ 消掉, 也就是对于一个串 $A$，如果 $A$ 尽量消 $1$ 之后剩下的消不掉的 $1$ ......

证明了自己思维不行。记一记自己的垃圾做法。 首先是场上做法：考虑按位枚举钦定一个前缀，这样从最优化问题转化成判定性问题，更好处理。 称钦定的前缀 01 状态为 $mask$，询问串和 $mask$ 匹配的下标集合为 $goal$。考虑按操作顺序从后往前添加操作，设当前前缀还没有跟 $mask$ 匹配 ......

1.找到script标签下的id： 2.获取指定标签下的内容： 3.总结： ......