省选-构造

我们发现这道题两种颜色相邻的不能重复连边就相当于我们的第一个模型，完全图两条边直接只有一条边。

于是发扬一下人类智慧。

先考虑偶数：我们把最后一行拼到第一行，倒数第二行拼到第二行...然后就成为了 $\frac{n}{2}$ 个链条，直接当成哈密顿路径做。每个链条长度 $n+1$，中间那个点重复用。

对于奇数：我们需要转化成偶数，于是就加一个 $0$ 号节点，我们发现 $0$ 号节会在第 $1,2,\cdots \frac{n+1}{2}$ 个位置出现，然后每一个链条就割掉这个 $0$ 号节点就行了。

细节挺多的。

• 对于 $n$ 是偶数，平均数的分母一定是 $2$，但是如果一个颜色出现了奇数次就不可能了，所以只需要判断每个颜色出现次数是否是偶数次。

• 对于 $n$ 是奇数，我们先把颜色数量是偶数的排除掉，然后数量是奇数的个数如果是奇数，就先放一个到中间，剩下的进行“配对”。怎么让其恰好配对？

我们进行尝试，先划分区间，划分成四段，每段长 $len=mid\times\frac{1}{2}$，然后中间点记为 $mid$，划分方法就是一个颜色 $[mid+i,mid+len+i,mid-len-i*2]$，$[mid-i,mid-len-i,mid+len+i*2]$。

发现这样刚刚好。难写！换成题解的写法就过了？因为我的写法。。。

如果当前 $n$ 为奇数，就需要从 $+1$ 转移，否则就是从 $*2$ 转移。

我们先把所有的弄成 $+1$。

我们发现有 $n$ 维，于是每一个数初始有一个维度为 $+\infty=inf$。

现在两个数的距离就是 $\sqrt {2} inf$。

我们想调整两个数的距离但是保证其余数的大小关系不变。

我们调整一个数在另一个数的坐标，调整 $w$，于是：$inf^2+(inf-w)^2 = 2inf^2+2infw-w^2 \to 2inf^2-2infw$（忽略 $w^2$ 这种小量），对于其他数：$w^2$ 直接忽略。

于是我们只需要枚举限制然后减少 $w$。

设一个点出边的颜色点集为 $s_i$，我们发现如果 $i\to j$，那么如果 $s_j$ 不能包含 $s_i$。

为了保证这个限制，我们可以让每一个点的点集都不同，结合 $C_{14}^7\ge 3000$ 刚刚好。

P3561 [POI 2017] Turysta

P3561 [POI 2017] Turysta。

当时做图论的时候做过，人类智慧。

大概是寻找竞赛图的性质，发现 dfs 序倒序遍历一定存在边。

这个奇偶性有什么规律？画图我们只能发现 $1$ 的个数是 __builtin_popcount(n-1)。

问一下 DPSK。

我们先把杨辉三角转成组合数，然后我们需要尝试去求组合数 $\binom{n}{k}$ 的奇偶性。

$\binom{n}{k} = \frac{n!}{k!\times (n-k)!}$

我们想到了 Lucas 定理，当 $p$ 是质数时：

$C_{n}^{m}\equiv C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}\cdot C_{n \bmod p}^{m \bmod p} \pmod p$

我们现在 $p=2$，递归进行求解（按照二进制拆分），然后就变成了：

$

\binom{n}{m} \equiv \prod_{i=0} \binom{n_i}{m_i} \pmod{2} $

再加上 $\binom{0}{0}=1,\ \binom{1}{0}=1,\ \binom{1}{1}=1,\ \binom{0}{1}=0$。

因此： $\binom{n}{k} \text{ 是奇数} \iff \text{对于每一位 } i,\ k_i \le n_i \ (\text{即 } k \& (\sim n) = 0)$

其实至此就可以乱搞过题了。

我们先进行二分答案，判断这个 $mid$ 能不能被构造。我们计算每一个 $a_{i,j}$ 可以的范围 $l_{i,j}\to r_{i,j}$。

观察到 $n$ 和 $m$ 很小，所以我们尝试循环构造，进行调整。

我们先假设 $x_n\le y_m$（分情况讨论，之后再反过来），这样能保证小的那一个在根号级别。

• 从前往后调整 $x_i$，如果比 $\le x_{i-1}$ 就变成 $x_{i-1}+1$，然后和每一个 $\lceil \frac{l_{i,j}}{y_j} \rceil$ 取 $\max$。

• 从后往前调整 $y_i$，如果比 $\ge y_{i+1}$ 就变成 $y_{i+1}-1$，然后和每一个 $\lceil \frac{r_{i,j}}{x_j} \rceil$ 取 $\min$。

合法或无解就可以结束了。怎么证明正确性？

首先 $x_i\le \sqrt{inf}$，所以 $x_i$ 增加的次数 $\le \sqrt{inf}$，$y$ 减少的次数 $\le \sqrt{inf}$。

代码中由于 $n,m$ 不同，所以需要交换 $x,y$ 在做一次。

注意二分过程中最后一次调用的 check 可能失败，必须用最终答案 l 再调用一次 check 来获取正确的构造。

注意细节，特别是复制代码的时候忘改的地方。

合法的序列需要是每一个前缀和都大于等于 $0$ 的。

翻转一个区间之后最低的点一定是原来最高的点，所以我们只需要让原来最高的点翻转过后不小于 $0$。

然后充分发扬人类智慧，对于最高的点 $x$，翻转 $[1,x],[x+1,2n]$ 一定合法，所以最多需要两次。那还有没有一次的情况呢？

设需要翻转 $l,r$。我们考虑 $L,R$ 表示最左边和最右边的负数，然后我们从 $[1,L]$ 和 $[R,2n]$ 选 $l,r$。我们需要保证对于每一个 $i$，$s_{l-1}+s_r-s_i \ge 0$，于是可以贪心，分别选择 $[1,L-1]$ 和 $[R,2n]$ 中最大的两个端点作为 $l,r$，然后判断这样选合不合法。

让子图度数最小的点度数最大，这个好做，从原图每次删掉一个度数最小的点就行了，保留中间的最大答案就可以了。

最大独立集怎么办？我们好像没法求。于是我们需要利用这道题的限制，我们考虑用上一个问题的求法来求（好人类智慧啊）。

我们每一次找到度数最小的点，放进独立集，然后把与之相连的点删掉。怎么证明这样是对的？

我们发现每次选择的点的删掉的点数一定不超过 $p$（不然剩下的那个东西就比第一个问题的答案优了），所以 $q\ge\left\lfloor \frac{n}{p+1} \right\rfloor\!$。

我们先要证明答案很小。考虑进行构造。

我们发现答案一定 $\le 3$，感觉跟CF1685C Bring Balance有点像。$3$ 次中一次翻转，一次前缀，一次后缀。

0

直接判断非负。

1

• 判断全负。

• 暴力前缀/后缀。

首先需要对其做前缀和的一定是那种前缀和之后全 $\ge 0$ 的那种。