2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest 题解

发布于 2020-03-02  118 次阅读



## A - [Berstagram](https://codeforces.com/contest/1250/problem/A)
### 题目大意
现在有一个序列 $1,2,...,n-1,n$,有 $m$ 次操作,每次可以把其中一个数往前挪一位(如果这个数在第一位就不动)。问每个数可能在这个序列的最左边和最右边分别是多少?
$1 \leq n \leq 10^5,1 \leq m \leq 4 \times 10^5$
### 思路简述
直接根据题意模拟就行了......
[Code by HeRaNO](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250A.cpp)
## B - [The Feast and the Bus](https://codeforces.com/contest/1250/problem/B)
### 题目大意
现在有 $n$ 个人属于不同的 $k$ 个小组。现在你只有一辆车,但你可以选择在这车上安装 $s$ 个位置。现在要把这 $n$ 个人都运走,出发一次需要的花费为 $s$,并且一个小组内的人不能被分开来运。问如何选择 $s$,使得总花费最少?输出总花费。
$1 \leq n \leq 5\times 10^5,1 \leq k \leq 8000$
### 思路简述
显然,这个题不能二分这个 $s$,因为设运的次数为 $t$,那么总花费就是 $s\times t$,而 $t$ 与 $s$ 有关,所以不具有二分性。
这个题可以考虑贪心:将每一组的人数从大到小排序后,实际上我们只需要从头和尾开始往中间逼近,设 $c_i$ 表示第 $i$ 组的人数,那么我们就需要找最大的 $c_i+c_j$,这就是我们需要找的 $s$。之后仍然是双指针那样,从头和尾开始,根据这个 $s$ 来更新答案就行。
[Code by Vingying](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250B.cpp)
## C - [Trip to Saint Petersburg](https://codeforces.com/contest/1250/problem/C)
### 题目大意
一个人想去圣彼得堡旅游,他从第 $L$ 天去并在第 $R$ 天回来,每一天花费 $k$ 块钱。现在他要在圣彼得堡兼职赚钱,现在一共有 $n$ 份兼职,第 $i$ 份兼职从第 $l_i$ 天开始,第 $r_i$ 天结束,并且获得 $p_i$ 块钱。他可以一次性做很多份兼职,但每一份兼职必须从头做到尾,否则不能得钱。问:他该如何选择 $L,R$,使得自己能够赚钱,并且赚得最多?盈利为 $0$ 或者亏损输出 $-1$。
$1 \leq n \leq 2\times 10^5,1 \leq k,p_i \leq 10^{12}, 1 \leq l_i \leq r_i \leq 2\times 10^5$
### 思路简述
这个题还要输出方案......
首先不难发现,我们要找的 $L,R$ 一定是某一份工作的 $l_i$ 和某一份工作的 $r_i$ 。我们可以将每一份工作按照 $l_i$ 排序,将每一份工作看做一条线段,这样实际上就是左端点枚举,动态删除线段,查询最大和的经典问题了。这一部分可以用前缀和+线段树区间加以及区间最大来实现。然后这个题还要输出方案,所以线段树里面存一个pair,表示最大和以及对应的右端点就行。
[Code by Vingying](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250C.cpp)
## D - [Conference Problem](https://codeforces.com/contest/1250/problem/D)
一道神仙dp好像......还没看题
## E - [The Coronation](https://codeforces.com/contest/1250/problem/E)
~~(这题真是苦了xydg了)~~
### 题目大意
有 $n$ 个人,第 $i$ 个人佩戴着第 $i$ 个宝石项链,每一个宝石项链都由 $m$ 个宝石组成。宝石一共有两种,”0“表示第一种,”1“表示另外一种。如果 $i$ 和 $j$ 佩戴的宝石项链相同位置上宝石种类相同数小于 $k$,那么这两个人就会发生冲突。现在你可以让一些人反着戴宝石项链,例如00101110反着戴为01110100。问是否可以让所有人互相都不起冲突?如果不可以,输出 $-1$;如果可以,则输出最少需要反戴的人数以及一个方案。
$2 \leq n \leq 50,1 \leq k \leq m \leq 50$
### 思路简述
我们来看第 $i$ 个人和第 $j$ 个人的情况:
1. 两个人无论是否反不反戴,都不会起冲突;
2. 两个人无论是否反不反戴,都会起冲突。这种情况便是无解,直接输出$-1$即可;
3. 两个人都不反戴会起冲突,其中一个人反戴不会起冲突。
对于每一个项链,都有两种状态:反戴与不反戴,设不反戴的状态为 $i$,反戴的状态为 $i'$,那么我们可以讨论每一种情况:
1. $i$ 和 $j$ 是不冲突的,$i'$ 和 $j'$ 也是不冲突的;
2. 输出$-1$;
3. $i$ 和 $j'$ 是不冲突的,$i'$ 和 $j$ 是冲突的。
这其实和2-SAT有些像,我们可以按照2-SAT的构图方式去建图,然后每一个连通块里面统计一个答案即可。
~~だが断る!~~
使用 2-SAT 去处理这个问题的话有一个缺点,就是 2-SAT 并不是直接得出代价最小的方案。所以我们可以寻求一个相似的替代方案。
实际上根据上面的分析,直接搞二分图,对每个连通块分别处理,dfs染色即可。
在染色完成之后,对于每个联通块统计一下两种染色方案哪一种的代价更小,然后选取更小的方案即可。由于联通块之间的选择互相之间不影响,所以可证这是最优的。
[Code by ZXyang](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250E.cpp)
## F - [Data Center](https://codeforces.com/contest/1250/problem/F)
这题就十足的签到题了(
[Code by Vingying](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250F.cpp)
## G - [Discarding Game](https://codeforces.com/contest/1250/problem/G)
### 题目大意
你和电脑做游戏。游戏一共有 $n$ 轮,第 $i$ 轮你会得到 $a_i$ 分,电脑会得到 $b_i$ 分。当有一方的分数大于等于 $k$ 时这一方输掉(你和电脑可能同时输掉)。现在你有一种操作,每次操作可以让双方减去目前双方较小的分数。问你是否能赢?不能输出$-1$,能的话输出最小需要的操作次数,并且输出一个方案。
$1\leq n \leq 2\times 10^5,2 \leq a_i,b_i < k \leq 10^9$
### 思路简述
假设现在游戏进行到了第 $i$ 轮,那么我在第 $i$ 轮进行一次操作,在第 $i+1$ 轮进行一次操作,等价于在第 $i+1$ 轮进行一次操作(当然,第 $i$ 轮时你输了除外)。于是我们可以用单调队列,或者尺取法来进行一次 $O(n)$ 的dp,设 $dp[i]$ 表示前 $i$ 轮所需要的最小操作次数,那么转移就是 $dp[i]=dp[j]+1$。
dp之后就是更新答案。 更新答案的过程也和上述dp过程异曲同工,然后这题要输出方案,dp的时候记录一下dp的前驱就行。
[Code by Vingying](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250G.cpp)
## H - [Happy Birthday](https://codeforces.com/contest/1250/problem/H)
### 题目大意
给你 $c_0$ 个 $0$,$c_1$ 个 $1$,......,$c_9$ 个 $9$,你所不能组出的最小的不含前导0的正整数是什么?
$0 \leq c_i \leq 10^5$
### 思路简述
一个简单的分类讨论。
我们只需要找出第一个出现次数 $cnt$ 最小的那个数,之后输出 $cnt+1$ 次该数就行。当然这是不考虑有 $0$ 的情况。有 $0$ 的话就看 $0$ 的出现次数 $cnt_0$ 与 $cnt$ 的大小,如果 $cnt_0+1<cnt$ 那么就输出这个数后补上 $cnt_0+1$ 个 $0$ 就行。
[Code by Vingying](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250H.cpp)
## I - [Show Must Go On](https://codeforces.com/contest/1250/problem/I)
好像也是一个神仙dp......还没看
## J - [The Parade](https://codeforces.com/contest/1250/problem/J)
### 题目大意
所有的士兵身高种数为 $n$,身高为 $i$ 的士兵有 $c_i$ 个。现在要将这些士兵排成 $k$ 排,每一排的士兵两两身高差的绝对值不能超过 $1$。现问最多可以排多少士兵?
$1 \leq n \leq 30000,1 \leq k,c_i \leq 10^{12}$
### 思路简述
显然答案是有二分性的,我们可以二分每一排有多少个士兵,然后check就行。
怎么check呢?我们不可能一排一排地放,而是从身高小的往大的排,这样可以保证是最优的排法。于是就只需要看这个身高的可以排多少排,然后依次这么处理过去即可。
[Code by Vingying](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250J.cpp)
## K - [Projectors](https://codeforces.com/contest/1250/problem/K)
貌似是一道神仙网络流......还没看(
## L - [Divide The Students](https://codeforces.com/contest/1250/problem/L)
### 题目大意
一共有 $a$ 个学生用汇编,$b$ 个学生用 Basic,$c$ 个学生用 C++,要把他们分成三组,求在所有分组方案中人数最多的组的最少人数。
$1 \leq a,b,c \leq 1000$
### 思路简述
枚举答案,现在要把会 Basic 的学生分到 $a$ 和 $c$ 里,先判断 $a$ 和 $c$ 是不是要进到 $b$ 里面,然后进多少。
[Code by ZXyang](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250L.cpp)
## M - [SmartGarden](https://codeforces.com/contest/1250/problem/M)
### 题目大意
有这么一块 $n\times n$ 的农田(图为 $n=5$ 的情况)
![](https://espresso.codeforces.com/bfd18a99e34af3940250773ba3caf59bf273b8ce.png)
主对角线以及下面那条对角线全是石块,现在你可以做最多 $50$ 次操作,每次操作可以选取一些行和列,之后在这些行和列的交叉点给农作物浇水。注意不可以选取交叉点有石块的行和列。输出一种让所有农作物都至少被浇过一次水的方案。
$1 \leq n \leq 5000$
### 思路简述
这题好神奇啊......智慧的构造。
这里翻译一下 zscoder 的题解(
For each bit $i$, let L = set of indices $x$ with bit $i=0$, R = set of indices $y$ with bit $i=1$ and $y+1$ also has bit $i=1$.
Similarly, for each bit $i$, let L = set of indices $x$ with bit $i=1$, R = set of indices $y$ with bit $i=1$ and $y+1$ also has bit $i=0$.
Now, we used 26 sets.
Observe that only pairs $(x,y)$, with $y = 01111...1$ (the string of 1s is nonempty) and $x = 1$ such that there is at least one bit 1 in the suffix, are uncovered.
Thus, it is sufficient to make $12$ more queries that cover all $y$ of the form $0111...1$ for a fixed 1-suffix length and then put all $x$ that can be matched on the left hand side.
In total, my solution uses $38$ queries.
对于每一位 $i$,让 $L$ 为所有第 $i$ 位为 $0$ 的 $x$ 坐标的集合,让 $R$ 为所有第 $i$ 位为 $1$ 并且 $y+1$ 的第 $i$ 位也为 $1$ 的 $y$ 坐标的集合;
相似地,让 $L$ 为所有第 $i$ 位为 $1$ 的 $x$ 坐标的集合,让 $R$ 为所有第 $i$ 位为 $0$ 并且 $y+1$ 的第 $i$ 位也为 $0$ 的 $y$ 坐标的集合。
现在,我们有 $26$ 个集合了。
注意到只有形如 $(x,y)$ 的点对,其中 $y=0111...1$(“1”串非空)并且 $x=1$ ,这样至少有一个“1”在后缀没有被覆盖。
因此,可以构造 $12$ 次操作覆盖所有对于一个固定“1”串长度,形如 $0111...1$ 的 $y$,之后构造所有满足条件的 $x$。
总计,操作数为 $38$ 次。
~~渣翻见谅~~
## N - [Wires](https://codeforces.com/contest/1250/problem/N)
### 题目大意
给定由 $n$ 个点组成的若干个无向边构成的连通块,希望修改最少的边使得所有的**边**是互达的(即边连通),并输出一个方案。
$1\leq n \leq 10^5$
### 思路简述
可以发现连通图要么带环,要么是一棵树。也不难发现,最少修改次数就是初始连通块数量-1.
如果一个连通块里面有度数为 $1$ 的点,就直接将与它相连的边修改就行。
而如果没有的话,就说明这个连通块肯定带环,直接改一条环边就行。
~~然而这题真的不好写~~
[ZXyang](https://acm.uestc.edu.cn/user/ZXyaang/ ): 一开始想的是暴力模拟找叶结点和环,但是这个样子写起来会非常非常麻烦。于是在wa了两发之后,我突发奇想换了一种写法,就变成代码里面既可以找叶结点又可以找环的神奇dfs了。
即:直接dfs随便走,直到走到了一个结点没有任何未访问过的节点相连接,那么这个点要不是叶节点,要不然就是在环上的节点。
[Code by ZXyang](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250N.cpp)
## 总结
~~奇怪的知识增加了!~~