「CF103E」Buying Sets
题目链接题目大意有一个大小为 $n$ 的全集，每个元素是一个数，有$n$个子集，题目保证任意$k$个子集的并的大小$\geq k$。你需要选出一些子集使得这些子集的并大小等于子集个数，且其并中元素和最小，可以为空集。$n \leq 300$题解这个题有两种做法。做法 1如果不考虑限制条件 权值取反之后就是一个最大权闭合子图模型（选了集合就要选对应的元素）考虑条件 “任意$k$个子集的并的大小...
题目链接题目大意有一个大小为 $n$ 的全集，每个元素是一个数，有$n$个子集，题目保证任意$k$个子集的并的大小$\geq k$。你需要选出一些子集使得这些子集的并大小等于子集个数，且其并中元素和最小，可以为空集。$n \leq 300$题解这个题有两种做法。做法 1如果不考虑限制条件 权值取反之后就是一个最大权闭合子图模型（选了集合就要选对应的元素）考虑条件 “任意$k$个子集的并的大小...
链接题目大意一个欧拉图，从 $1$ 出发的欧拉路径个数。 $n \leq 100$题解这种结论题可能只有知道结论才能做。首先我们求出一个 $1$ 点为根的内向生成树：我们考虑从两个方向来证明：生成树 $\to$ 欧拉回路我们对于每个点 如果存在未走过的非树边就走过去 否则走树边 这样构造显然是一个欧拉回路 且满足引理 1。欧拉回路 $\to$ 生成树把每一个点最后走的边作为树边 这样构造显然...
题意有两个有根树 每个树的点都用 $1 \ldots n$ 编号。现在你要给每一个点指定一个权值 满足所有子树的和的绝对值是 1（两棵树上相同编号的点的权值相同）$n \leq 10^5$题解首先我们考虑转化一下题意：由于只有两种状态，考虑给边定向。如果这个子树=1我们就把这个点到父亲的点往下连 否则往上连（上，下都是表示深度）。发现根没有被考虑到 新建一个虚点 向两个根连边。我们记这个点的...
题目大意题目链接 你有一个无向连通图，边的总数为偶数。设图中有 $k$ 个奇点（度数为奇数的点），你需要把它们配成 $\frac{k}{2}$ 个点对（显然 k 被 $2$ 整除）。对于每个点对 $(u,v)$，你需要用一条长度为偶数（假设每条边长度为 $1$ ）的路径将 $u$ 和 $v$ 连接。每条路径允许经过重复的点，但不允许经过重复的边。这 $\frac{k}{2}$ 条路径之间也不...
题目大意题目链接给一个无向图 边有黑白两种颜色。你每次可以指定一个回路上的所有的边颜色都反色。问至少多少次操作可以都变成白色。支持边颜色的修改。$n \leq 10^6$题解这种题目就比较神仙，代码好写 但是思维难度不低（至少我这种菜鸡想不出来）我们首先考虑如果有了一个方案 它有哪些性质。我们把所有的回路上每一次经过的边都连上去建一个新图。发现这个新图有如下性质：白边都经过偶数次黑边都经过奇...