CodeForces 中分段 随机挑战 Part2

$$\large \bf\text{Task Clear}$$ - ## .#1 [CF1043F Make It One](https://www.luogu.com.cn/problem/CF1043F) **题意** ：给出正整数集合 $S$ ，要求选出 $T\subseteq S$ 使得 $\gcd(T)=1$ 且 $|T|$ 尽量小。 输出这个最小值，或指出无解。 $n,S\leq 3\times 10^5$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2500$ - **思维 Fineness** : $(5)$ 观察 - $\ \ \ \,\, $ **实现 Mass** : $(4)$ 制式 - $\ $ **质量 Quality** : $(6)$ ------------ 见过这题，直接给做法。 可以发现答案的上界是 $7$ 。需要构造一个集合满足任选 $k$ 个 $\gcd>1$ 。 最坏情况是 $2,3,5,7,11,17$ 的缺一项组合。 枚举答案并判定，直接用 [题解 P2714 【四元组统计】](https://www.luogu.com.cn/blog/command-block/solution-p2714) 即可。 [评测记录](http://codeforces.com/contest/1043/submission/137597460) ------------ - ## .#2 [CF484E Sign on Fence](https://www.luogu.com.cn/problem/CF484E) **题意** ：给定一个长度为 $n$ 的数列，有 $m$ 次询问。要你在区间 $[l,r]$ 内选一个长度为 $k$ 的区间，求区间最小数的最大值。 $n,m\le 10^5$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2500$ - **思维 Fineness** : $(3)$ 套路 - $\ \ \ \,\, $ **实现 Mass** : $(4.5)$ 制式 - $\ $ **质量 Quality** : $(5.5)$ ------------ - **口胡情况** ：两眼秒了。$\color{green}\bf\Delta$ 考虑二分答案 $x$ ，将 $\geq x$ 的都设为 $1$ ，需要找出极长 $1$ 段看是否 $\geq k$ 。 主席树从小到大插入即可。 复杂度 $O(n\log n+m\log^2 n)$。 不写代码。 ------------ - ## .#3 [CF555E Case of Computer Network](https://www.luogu.com.cn/problem/CF555E) **题意** ：给定一张 $n$ 个点 $m$ 条边的无向图，给定 $q$ 组有向点对 $(s, t)$。 判定是否存在使得所有 $s$ 都能到达 $t$ 的定向方案。 $n,m,q \le 2 \times 10^5$。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2800$ - **思维 Fineness** : $(4)$ 经典模型 - $\ \ \ \,\, $ **实现 Mass** : $(5.5)$ 制式 - $\ $ **质量 Quality** : $(5)$ ------------ - **口胡情况** ： 10min $\color{green}\bf\Delta$ 将原图缩边双，将每个边双连成一个环，边双内部限制可以无视。 割边的方案变成了树的情况，树上差分即可。 [评测记录](http://codeforces.com/contest/555/submission/137600246) （1A非常感动 ------------ - ## .#4 [CF442C Artem and Array](https://www.luogu.com.cn/problem/CF442C) **题意** ：给定 $A_{1\sim n}$，你需要进行 $n$ 次操作：删去某一元素 $A_i$ ，并获得 $\min\{A_{i-1}, A_{i+1}\}$ 的分数。若不存在 $A_{i-1}$ 或 $A_{i+1}$，则此次操作不得分。 计算至多能得到多少分。 $n\leq 5\times10^5,A\leq 10^6$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2500$ - **思维 Fineness** : $(6.5)$ 观察 - $\ \ \ \,\, $ **实现 Mass** : $(3)$ 轻 - $\ $ **质量 Quality** : $(7)$ ------------ - **口胡情况** ： 10min $\color{green}\bf\Delta$ - **引理零** ：两侧的元素必然最后删除。 - **引理①** ：若 $B_i\geq A_i$ ，则 $B$ 的最优得分 $\geq A$ 的。 - **引理②** ：对于 $A_{i-1}\geq A_i\leq A_{i+1}$ ，先删除 $A_i$ 是不劣的。先删除 $A_{i-1},A_{i+1}$ 得分更少，且剩余的序列更小。 这说明 $A_i$ 早于 $A_{i-1},A_{i+1}$ 删除，又因为 $A_{i-1},A_{i+1}$ 不删除时这个结构不会改变，故可以首先删除 $A_i$ 。 用单调栈可以维护删除的过程。最终剩余部分必然**严格**先升后降（单峰），记有 $t$ 个。 删除不会影响“先升后降”的性质，可以发现每个数只可能在被大于它的数删除时贡献（每个数只能匹配更小的数），最优方案是前 $t-2$ 小各贡献一次，而不断删除（除两侧的）最大值可以达到这个界。 [评测记录](http://codeforces.com/contest/442/submission/137601802) ------------ - ## .#5 [CF1521D Nastia Plays with a Tree](https://www.luogu.com.cn/problem/CF1521D) **题意** ：给出一棵 $n$ 个点的树，要切 $k$ 条边再连 $k$ 条边，将树改造为链。求 $k$ 的最小值，并给出构造。 $n\leq 2\times 10^5$ ------------ **评价** ： - $\ $ **CF Difficulty** : $2500$ - **思维 Fineness** : $(5.5)$ 经典 - $\ \ \ \,\, $ **实现 Mass** : $(4)$ 轻细节 - $\ $ **质量 Quality** : $(6)$ ------------ - **口胡情况** ： 10min $\color{green}\bf\Delta$ 问题可以转化为将树划分为尽量少的链。将这些链切出来并首尾相连即可。 首先可以想到一个经典的 DP ： $f[u][0/1]$ 表示 $u$ 子树内剖分后 $u$ 不是/是 端点 的最小链数目。 但是输出方案很麻烦。 类似树的最大匹配，这个问题也有个贪心，就是在子树内能合就合。可以证明在同等数目的情况下会得到 $u$ 是端点的方案。 正确性说明：子树内能合成不合成，链条数目 +1 ，而受益仅仅是祖先处可能的链条数 -1 ，现在合成必不亏。 [评测记录](http://codeforces.com/contest/1521/submission/137603635) ------------ - ## .#6 [CF675E Trains and Statistic](https://www.luogu.com.cn/problem/CF675E) **题意** ：有 $n$ 个车站，告诉第 $i$ 个车站可以单向直达 $[i+1,a_i]$。 记 $p(i,j)$ 为从 $i$ 到 $j$ 最小乘车次数，求 $\sum\limits_{i=1}^n\sum\limits_{j=i+1}p(i,j)$ 。 $n\leq 10^5$。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2300$ - **思维 Fineness** : $(5)$ 观察（经典） - $\ \ \ \,\, $ **实现 Mass** : $(4)$ 轻 - $\ $ **质量 Quality** : $(7)$ ------------ - **口胡情况** ：10min $\color{green}\bf\Delta$ - 单组询问的策略 若能一步走到终点，直接走过去。 否则走向 $a_{i+1\sim a_i}$ 中最大的。 记 $S_l=\sum\limits_{r=l+1}^np(l,r)$ ，考虑逐步减小 $l$ ，求出各个 $S_l$ 。 有递推式 $S_p=(n-p)+S_{t_p}-(a_p-t_p)$ 。 $(n-p)$ 是所有目的地都要先走一步，$S_{t_p}$ 是算上第一步走了 $t_p$ 的贡献和， $(a_p-t_p)$ 是算多了的部分（实际上一步可达没必要走 $t_p$） [评测记录](http://codeforces.com/contest/675/submission/137605229) ------------ - ## .#7 [CF1344F Piet's Palette](https://www.luogu.com.cn/problem/CF1344F) **题意** ：一个包含三原色 `RYB` 的序列**混合**的结果定义为： - 如果序列开头两项颜色相同，将这两项删去。 - 如果序列开头两项颜色不同，将这两项替换为与这两种颜色不同的颜色。 - 特别地，如果序列为空，则混合的结果是白色 `W`。 有一个长为 $n$ 的颜色序列 $A$ （某些位置为空），给出 $k$ 个操作: - `mix`：选择一个子序列和混合时的顺序（忽略空位置），给出其混合后的结果。 - `RY`：选择一个子序列，将所有 `R` 变为 `Y`，所有 `Y` 变为 `R`，`B` 和空位置不变。 - `RB`：选择一个子序列，将所有 `R` 变为 `B`，所有 `B` 变为 `R`，`Y` 和空位置不变。 - `YB`：选择一个子序列，将所有 `Y` 变为 `B`，所有 `B` 变为 `Y`，`R` 和空位置不变。 你需要根据 `mix` 操作的信息确定一种可能的 $A$。 $n, k \leqslant 10^3$。 ------------ - **口胡情况** ：AGC / ARC 有类似套路，一眼秒了。 将 `RYB` 分别看做 $1,2,3$ ，空位置看做 $0$ ，混合相当于异或和。 将每个位置的值记作 $a_i+2b_i$ ，这样 $a_i,b_i$ 都是 $01$ 变量。 - `mix` ： 给出一条方程。 - `RY` ： ${\rm swap}(a_i,b_i)$ - `RB`： $b_i\leftarrow a_i{\ \rm xor\ }b_i$ - `YB`： $a_i\leftarrow a_i{\ \rm xor\ }b_i$ `bitset` 高斯消元即可，复杂度为 $O(n^3/\omega)$ 。 [评测记录](http://codeforces.com/contest/1344/submission/137736290) ------------ - ## .#8 [CF1439C Greedy Shopping](https://www.luogu.com.cn/problem/CF1439C) **题意** ：给定一个大小为 $n$ 的**非升序列** $a$ 。 现在有两类操作： - 给出 $x,y$ 将 $A_{1,x}$ 对 $y$ 取 $\max$ 。 $\forall i\in[1,x],a_i=\max(a_i,y).$ - 给出 $x,y$ ，从左往右访问序列 $a_{x\sim n}$ ，如果 $a_i\le y$ ，则 $y\leftarrow y-a_i,cnt\leftarrow cnt+1$ 。 回答 $cnt$ 的值。 $n,q\leq 2\times 10^5$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2600$ - **思维 Fineness** : $(5)$ 套路 - $\ \ \ \,\, $ **实现 Mass** : $(5)$ 制式 - $\ $ **质量 Quality** : $(6.5)$ ------------ - **口胡情况** ： 5min $\color{green}\bf\Delta$ 可以发现 $cnt$ 增加的地方只会形成 $O(\log n)$ 条连续段，因为 $y$ 每过一段必然减半。 用线段树维护区间和，第一个操作可以二分后区间覆盖。 复杂度 $O(q\log n\log y)$。不写代码。 ------------ - ## .#9 [CF19D Points](https://www.luogu.com.cn/problem/CF19D) **题意** ：在一个笛卡尔坐标系中，定义三种操作: 1. 在坐标系上标记一个点 $(x,y)$，保证 $(x,y)$ 在添加前不在坐标系上。 2. 移除点 $(x,y)$，保证 $(x,y)$ 在移除前已在坐标系上。 3. 找到所有已标记并在 $(x,y)$ 右上方的点中，最左边的点，若点不唯一，选择最下面的一个点; 如果没有符合要求的点，给出 `-1`，否则给出 $(x,y)$ 。 $n\leq 2\times 10^5$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2800$ （就这？） - **思维 Fineness** : $(4.5)$ 套路 - $\ \ \ \,\, $ **实现 Mass** : $(5)$ 制式 - $\ $ **质量 Quality** : $(6.5)$ ------------ - **口胡情况** ： 10min $\color{green}\bf\Delta$ 首先考虑如何求答案的横坐标。 记 $Y_x$ 表示横坐标为 $x$ 的最大纵坐标，若不存在则为 $-\infty$ 。可以用 `std::set<int>` 维护。 询问即找 $Y_{x+1\sim +\infty}$ 中第一个 $>y$ 的，这个用线段树二分。 找到横坐标后，在对应 `set` 中二分即可得到纵坐标。 [评测记录](http://codeforces.com/contest/19/submission/137607827) ------------ - ## .#10 [CF1452E Two Editorials](https://www.luogu.com.cn/problem/CF1452E) **题意** ：给出 $1\sim n$ 中的 $m$ 个区间 $l_{1\sim m}$。 需要选定两个长为 $k$ 的区间 $A,B$ ，最大化 $\sum\limits_{i=1}^m\max\big(|l_i\cap A|,|l_i\cap B|\big)$ 。 $n,m\leq 2000$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2500$ - **思维 Fineness** : $(5.5)$ 套路 - $\ \ \ \,\, $ **实现 Mass** : $(3.5)$ 轻 - $\ $ **质量 Quality** : $(7)$ ------------ - **口胡情况** ： 以为是繁琐的二维前缀和。$\color{red}\bf\Delta$ 对于区间 $[l,r],[a,a+k-1]$ （其中只有 $a$ 是变量），交的大小和两区间的中点距离正相关。 不妨假设 $A$ 比 $B$ 靠左，可以发现，一定是 $A$ 处理一个前缀， $B$ 处理一个后缀。（ $l$ 按照中点排序） 预处理前后缀用单个区间处理的答案，直接枚举方案，逐个添加区间即可做到 $O(nm)$ 。 [评测记录](http://codeforces.com/contest/1452/submission/137613016) ------------ - ## .#11 [CF1407E Egor in the Republic of Dagestan](https://www.luogu.com.cn/problem/CF1407E) **题意** ： 给出 $n$ 个点 $m$ 条边的有向图，边有黑白两种颜色。 现在要给点染色，每个点染成黑或白色。白点只能走它连出去的白边，黑点只能走它连出去的黑边。 问是否存在一种染色方案，使得不存在 $1\rightarrow n$ 的路径。若不存在这样的染色方案，最大化 $1\rightarrow n$ 的最短路径长度。构造染色方案。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2500$ - **思维 Fineness** : $(6.5)$ 观察+建模 - $\ \ \ \,\, $ **实现 Mass** : $(3.5)$ 轻 - $\ $ **质量 Quality** : $(8)$ ------------ - **口胡情况** ： 30min 讨论 $\color{blue}\bf\Delta$ 首先看如何判定是否能使得不存在 $1\rightarrow n$ 的路径。 将图反过来，变为只能接受同色的入边。 维护一个集合 $S$ ，表示无论染色方案如何，都能从 $n$ 到达的点集。 初始时，$S=\{n\}$ ，按照任意顺序添加点。 添加点 $u$ 时，查看 $u$ 的来自 $S$ 的入边，若黑白都有，则将 $u$ 加入 $S$ 。 若将 $u$ 加入了 $S$ ，则 $u$ 的出边可能产生贡献，引发连锁反应，但总复杂度是均摊 $O(n+m)$ 的。 最终若 $1$ 不在 $S$ 内，则存在一种方案使得不存在 $1\rightarrow n$ 的路径，否则不存在。 具体地，对于不在 $S$ 内的点，从 $S$ 来的入边必然同色（若存在），染成另一种颜色即可。 进一步考虑如何最大化最短路（此时 $1$ 在 $S$ 内）。记 $dis_u$ 为最终方案中 $n$ 到 $u$ 的最短路， $dis_1$ 就是答案。 假设我们知道了 $dis$ 从小到大的顺序，按照这个顺序加入各个点，每次将 $dis$ 置为前继中黑白两色的 $\max$ 。（$\min$ 被染色干掉了） 类似 Dijkstra ，不断应用目前最小的松弛，由于边权为 $1$ 可以直接 BFS 。 [评测记录](http://codeforces.com/submissions/command_block#) ------------ - ## .#12 [CF605E Intergalaxy Trips](https://www.luogu.com.cn/problem/CF605E) **题意** ：给出 $n$ 个点的有向完全图，$i \to j$ 的边每天出现的概率均为 $w_{i,j}$ 。 每天可以选择停留，或选一条存在的出边走过去。求最优策略下从 $1$ 到 $n$ 的期望天数。 $n \le 10^3$。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2700$ - **思维 Fineness** : $(6)$ 刻画+模型 - $\ \ \ \,\, $ **实现 Mass** : $(4)$ 轻细节 - $\ $ **质量 Quality** : $(7)$ ------------ - **口胡情况** ：10min $\color{green}\bf\Delta$ 记 $f_u$ 为从 $u$ 出发到达 $n$ 需要的期望天数，有方程： 记排列 $p$ 满足 $f_{p_i}<f_{p_{i+1}}$ ，有转移 ： $$f_{p_k}=\sum\limits_{i=1}^{n}\prod_{j=1}^{i-1}(1-w_{p_k,p_j})w_{p_k,p_i}\min(f_i+1,f_{p_k}+1)$$ 这里是枚举 $i$ 表示第 $i$ 优的出边存在，更优的出边均不存在。 后面的 $\min(f_i+1,f_{p_k}+1)$ 是因为可以选择停留。 $$ \begin{aligned} f_{p_k}&=\sum\limits_{i=1}^{k-1}\prod_{j=1}^{i-1}(1-w_{p_k,p_j})w_{p_k,p_i}f_i+1+\prod_{j=1}^{k}(1-w_{p_k,p_j})(f_{p_k}+1)\\ f_{p_k}&=\bigg(1-\prod_{j=1}^{k}(1-w_{p_k,p_j})\bigg)^{-1}\bigg(\sum\limits_{i=1}^{k-1}\prod_{j=1}^{i-1}(1-w_{p_k,p_j})w_{p_k,p_i}f_i+1+\prod_{j=1}^{k}(1-w_{p_k,p_j})\bigg) \end{aligned} $$ 可以发现，$f_{p_k}$ 的值只会从 $f_{p_{1\sim k-1}}$ 转移而来。跑类 Dijstra 即可。 [评测记录](http://codeforces.com/contest/605/submission/137500839) ------------ - ## .#13 [CF1375G Tree Modification](https://www.luogu.com.cn/problem/CF1375G) **题意** ：给定一棵 $n$ 个点的树。 每次操作可以选定三个点 $a,b,c$ ，要求 $a$ 与 $b$ 相邻，$b$ 与 $c$ 相邻。 - 所有与 $a$ 相邻的节点和 $c$ 连边； - 断掉连接 $a$ 与其所有相邻节点的边； - $a$ 与 $c$ 连边。 求出将树变为菊花所需要的最小操作数。 $n\leq 2\times 10^5$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2800$ - **思维 Fineness** : $(7)$ 观察+猜想+证明 - $\ \ \ \,\, $ **实现 Mass** : $(3)$ 轻 - $\ $ **质量 Quality** : $(6.5)$ ------------ - **口胡情况** ： 麻了，完全不会。 $\color{red}\bf\Delta$ 观察操作情况可以发现，相似的结构摆在不同的深度，操作次数会大为改变，似乎和奇偶性有关。（比如长度不同的扫把） 将树黑白染色，我们的目的是将某种颜色的点减少到只剩一个。 观察操作，可以发现，有且仅有 $a$ 的颜色有改变。这指出一个显然的答案下界，记 $cnt_0,cnt_1$ 分别为初始时黑白点计数，则 ${\rm Ans}\geq \min(cnt_0,cnt_1)-1$ 。 这个下界也是可以达到的，只需证若某种颜色 $c$ 有 $\geq 2$ 个点，一定能找到 $c\leftrightarrow \neg c \leftrightarrow c$ 的结构，于是总可以通过一次操作将 $c$ 的个数减小 $1$ 。 [评测记录](http://codeforces.com/contest/1375/submission/137608927) ------------ - ## .#14 [CF1264D2 Beautiful Bracket Sequence (hard version)](https://www.luogu.com.cn/problem/CF1264D2) **题意** ： 定义一个括号序列（不必合法）的权值为：删除一些括号得到合法括号序列的最大深度。 现在有含 `()?` 的长为 $n$ 的字符串 $S$，`?` 可以替换为 `(` 或 `)` ，求所有替换方案的权值的和。 $n\leq 10^6$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2900$ - **思维 Fineness** : $(7)$ 观察+推导 - $\ \ \ \,\, $ **实现 Mass** : $(5)$ - $\ $ **质量 Quality** : $(7)$ ------------ - **口胡情况** ： 看错题直接白给。 - 注：范德蒙德卷积等价于下降幂的二项式定理： $$ \begin{aligned} &(x+y)^{\underline n}=\sum\limits_{k=0}^n\dbinom{n}{k}x^{\underline k}y^{\underline {n-k}}\\ \Rightarrow\ &\dbinom{x+y}{n}=\sum\limits_{k=0}^n\dbinom{x}{k}\dbinom{y}{n-k} \end{aligned} $$ 考虑给定串如何计算权值。若保留的括号不是 $k\times'('+k\times')'$ ，则可以删除一些多余的括号。 保留的括号一定形如 $((()))$ ，他们在原序列中顺序排列。 记 $l_i$ 为 $S_{1\sim i}$ 中的左括号个数， $r_i$ 为 $S_{i\sim n}$ 中的右括号个数，枚举中心点，权值为 $\max_p\min(l_p,r_{p+1})$ 。 而且由于 $a$ 单调不升，$b$ 单调不降，且 $i$ 增大时 $a,b$ 两者必有其一改变，故最大的 $p$ 一定是**唯一**的。 枚举 $p$ 计算贡献，记 $L_i$ 为 $S_{1\sim i}$ 中问号个数， $R_i$ 为 $S_{i\sim n}$ 中问号个数 ，则： （枚举有 $i$ 个左侧问号变成了左括号） $$ \begin{aligned} {\rm Ans}&=\sum\limits_{p=1}^n\sum\limits_{i=0}(l_p+i)\dbinom{L_p}{i}\dbinom{R_{p+1}}{l_p+i-r_{p+1}}\\ &=\sum\limits_{p=1}^n\Bigg(l_p\sum\limits_{i=0}\dbinom{L_p}{i}\dbinom{R_{p+1}}{l_p+i-r_{p+1}}+\sum\limits_{i=0}i\dbinom{L_p}{i}\dbinom{R_{p+1}}{l_p+i-r_{p+1}}\Bigg)\\ &=\sum\limits_{p=1}^n\Bigg(l_p\sum\limits_{i=0}\dbinom{L_p}{i}\dbinom{R_{p+1}}{R_{p+1}-l_p-i+r_{p+1}}+L_p\sum\limits_{i=0}\dbinom{L_p-1}{i-1}\dbinom{R_{p+1}}{R_{p+1}-l_p-i+r_{p+1}}\Bigg)\\ &=\sum\limits_{p=1}^n\Bigg(l_p\dbinom{L_p+R_{p+1}}{R_{p+1}-l_p+r_{p+1}}+L_p\dbinom{L_p+R_{p+1}-1}{R_{p+1}-l_p+r_{p+1}-1}\Bigg)\\ \end{aligned} $$ [评测记录](http://codeforces.com/contest/1264/submission/137608475) ------------ - ## .#15 [CF1209F Koala and Notebook](https://www.luogu.com.cn/problem/CF1209F) **题意** ：定义一条路径的权值为路径上所有边的编号直接相连所得到的十进制数字的大小。 求 $1$ 到每个点的最短路，答案对 $10^9+7$ 取模。 $n\leq 10^5$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2600$ - **思维 Fineness** : $(6.5)$ - $\ \ \ \,\, $ **实现 Mass** : $(4)$ 轻 - $\ $ **质量 Quality** : $(7)$ ------------ - **口胡情况** ：麻了，完全不会。 $\color{red}\bf\Delta$ 将一条边 $\xrightarrow{\overline {abc}}$ 拆点变为 $\xrightarrow{\overline {a}}\xrightarrow{\overline {b}}\xrightarrow{\overline {c}}$ 。注意正反向的边拆点不同。 然后跑 BFS ，松弛顺序以 $dis_u$ 为序，对于 $dis_u$ 相等的则按照出边排序。 队列中维护把一个个 $dis_u$ 相等的连续段，归纳可知正确性。（甚至不需要比较） 复杂度 $O(nd\log n)$ ，其中 $d=10$ 。 [评测记录](http://codeforces.com/contest/1209/submission/137559476) ------------ - ## .#16 [CF1381C Mastermind](https://www.luogu.com.cn/problem/CF1381C) **题意** ： 给出序列 $A_{1\sim n}$ ，需要构造 $B_{1\sim n}$ （或指出无解），符合下列条件： - $A_i=B_i$ 发生 $x$ 次。 - $A,B$ 看做多重集的交集大小为 $y$ 。 $A,B$ 的值域都是 $[1,n+1]$ 。 多组数据，$\sum n\leq 10^5$ 。 ------------ **评价** ： - $\ $ **CF Difficulty** : $2500$ - **思维 Fineness** : $(6.5)$ 观察 - $\ \ \ \,\, $ **实现 Mass** : $(4.5)$ 细节 - $\ $ **质量 Quality** : $(7)$ ------------ - **口胡情况** ：麻了，完全不会。 $\color{red}\bf\Delta$ 记 $A$ 中出现次数最多的数为 $t$ ，不存在的某个数为 $e$ 。 - $x=0,y=n$ 相当于需要将 $A$ 重排，且使得对应位置均不相同。 容易发现，假如 $t$ 出现次数超过一半，则无解。 否则，将其余颜色连续排列成序列 $A$ ，构造 $tA$ 对 $At$ 即可。 例 ：$333322211-222113333$ 。 - $y=n$ 假设我们选定了相同的位置集合，剩余部分就是 $x=0,y=n$ 的情况。 选相同的位置时，每次贪心地选目前出现次数最多的（为了方便需要保证 $t$ 一直是最大值之一）。可以发现 $x$ 越大越可能（使得剩余的最大值不超过一半）有解。 - $x=0$ 选与 $e$ 匹配的 $n-y$ 个位置时，贪心地选目前出现次数最多的。 记与 $e$ 匹配前 $t$ 的个数为 $a$ ，匹配后为 $b$ ，则若 $a+b>n$ 则无解。 否则，匹配前将其余颜色连续排列为 $A$ ，匹配后是 $B$ ，构造 $tA$ 对 $Bet$ 即可。 - 一般情况 先贪心用 $x$ ，再贪心用 $n-y$ 。 [评测记录](http://codeforces.com/contest/1381/submission/137733482)