▶INFO 题意简述 给定一个 个点 条边的图，每个边分为黑边和白边，构造一组黑边个数等于白边个数的生成树或报告无解。 容易发现如果 是偶数，那么 就是奇数不可能平均分，此时应该报告无解。 我们给黑色边定价 白色边定价 。 我们希望求一颗

又是计数，吓哭了。 计数题太困难。 考虑加入之后的双端队列里有什么性质。由于你是按照从小到大的顺序加入的，因此呈现一个两边大中间小的 V 字形。 由于题目要求第 个数是 ，那么肯定 的左侧和右侧至少有一侧取空了。由于我们是对最终序列计数，因此我们不妨钦定取空的是左边的。因此这个问题其实等价于将序列的前 个元素分成两个递减的子序列，我们将两个子序列分别称作左侧子序列和右侧的子序列，代表其中的元

这里本来应该有另外一个 DP 题的题解的。但是牛客这些题目题解更好写。 A 赛时提示说只看灰字会更容易通过。那我们分析一下灰色字体。 之前分析了给出的 galgame 链接的代码，发现之和最后一个选项有用，但是赛时感觉没啥用。 “你应该多和我聊天”和“偶尔给我送送礼物”说明前面 的个数应该大于 的个数。“然后在那个特殊节日里跟我有特殊互动”猜测是倒数第二天，因此倒数第二天进行 ，“最后在我内心

怎么都在写根号做法？ 莫队做法有点过于无脑了。 另外突然发现我之前因为和别人朝 inline 有没有用的时候交了一发这题的代码测了一下，结论是 inline 似乎确实有用。然后我以为自己做过这个题目直接交了。 讲下我的 做法。 首先判断是否有解是容易的，直接扫描线即可。但是我们要输出一个数！怎么办？ 考虑一个数的可行区间。显然满足以下两个条件。 其中 表示当前这个数上一次出现的时候， 表示下

和上一篇一起的。 怎么置换群还在追我。 根据排序不等式，显然答案最大是就是排列 对应位置的数完全相同的时候。我们其实并不在乎下标，只在乎对应的值。因此我们不妨固定 ，先将 排序，对应调整 序列的位置，将对 的操作转化到对 的操作上。 显然这个游戏就变成了两个人分别选择一对 中的元素并交换。由于你需要点积增加，因此逆序对必须减少，所以游戏不可能永远进行。不妨把 看作一个置换，恒同变换是

感觉最近有点颓废啊。水几篇题解。 简而言之，就是你希望把 个元素分成 组，使得每组中 。 对于这种限制我们通常先按照某一个维度排序，这样通常可以方便处理一点。 我们先考虑按照 从大到小进行排序，按照 排序似乎不太好做（或许只是因为我太菜了）。排序之后，我们就只需要考虑最后一个元素的限制了。 我们拿到一个元素有两种选择，一种只先留着，之后再配对。或者可以选择现在配对，限制就是当前这个元素的限

前置知识 抽象向量空间 线性代数研究的“向量”究竟是什么？实际上向量的内涵要远大于一个高维空间的点，一个 的元素。 简单来说，一个向量就是“可以让我们进行各种基本代数运算的东西（“the laws of algebra work!”）”。 具体的，线性代数研究的“向量”是一个集合中的元素，其有良好定义的加法和数乘运算，具体的标准如下（线性空间的定义）： 是交换群。 是域。 存在一个 和

属于是看上去是模板，实际上有点小巧思的题目。 考虑我们如何比较两个方案大小。可以先比位数然后比字典序。因此我们只需要先求出最小位数然后再构造最小字典序方案即可。 和数位以及倍数相关容易想到同余最短路（和这题很像）。我们拆成 个点，记作 ，表示用若干个数拼成摸 余 ，最后一位数为 ，到这个点的最短路就是拼成摸 余 ，最后一位数为 的最小位数。 考虑每次往后拼一位。对于每个 ，连边 ，权值为

学网络流学的。文章末尾附带了一个精神正常的简略版本。 对于这种简单题，我们显然是可以用网络流的，对于 的数据范围我并不知道能不能过，所以我觉得应该要写预流推进。我不会。 所以我觉得这题不应该是网络流，但是我觉得就是网络流。 于是我开始尝试手搓网络流。但是一想到数据范围是 我就觉得要写预流推进，而我并不会预流推进，所以我认为这就是一个非常困难的题目。因为我不会写。 所以我决定开始想更快的网络流做

很神奇的题目。 首先你考虑我们如何把那个异或转化掉。直接异或显然是不好做的。 异或考虑拆位。考虑我们如何比较两个二进制数的大小？我们从高到低考虑，如果一个是 而另一个是 那么前一个就小于后一个了。 我们忽略 的限制，将所有的 都插入到一颗 trie 树上。考虑此时插入 。我们用 表示 二进制从高到低的第 位，第 位是代表 的那位。假设插入到第 位，假设 ，那么我们反转 ，那么之