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

## A – [Berstagram](https://codeforces.com/contest/1250/problem/A)

### 题目大意

$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)

### 题目大意

$1 \leq n \leq 5\times 10^5,1 \leq k \leq 8000$

### 思路简述

[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)

### 题目大意

$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$

### 思路简述

[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)

## E – [The Coronation](https://codeforces.com/contest/1250/problem/E)

~~（这题真是苦了xydg了）~~

### 题目大意

$2 \leq n \leq 50,1 \leq k \leq m \leq 50$

### 思路简述

1. 两个人无论是否反不反戴，都不会起冲突；

2. 两个人无论是否反不反戴，都会起冲突。这种情况便是无解，直接输出$-1$即可；

3. 两个人都不反戴会起冲突，其中一个人反戴不会起冲突。

1. $i$ 和 $j$ 是不冲突的，$i’$ 和 $j’$ 也是不冲突的；

2. 输出$-1$；

3. $i$ 和 $j’$ 是不冲突的，$i’$ 和 $j$ 是冲突的。

~~だが断る！~~

[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)

### 题目大意

$1\leq n \leq 2\times 10^5,2 \leq a_i,b_i < k \leq 10^9$

### 思路简述

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)

### 题目大意

$0 \leq c_i \leq 10^5$

### 思路简述

[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)

### 题目大意

$1 \leq n \leq 30000,1 \leq k,c_i \leq 10^{12}$

### 思路简述

[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)

### 题目大意

$1 \leq a,b,c \leq 1000$

### 思路简述

[Code by ZXyang](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250L.cpp)

## M – [SmartGarden](https://codeforces.com/contest/1250/problem/M)

### 题目大意

![](https://espresso.codeforces.com/bfd18a99e34af3940250773ba3caf59bf273b8ce.png)

$1 \leq n \leq 5000$

### 思路简述

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.

~~渣翻见谅~~

## N – [Wires](https://codeforces.com/contest/1250/problem/N)

### 题目大意

$1\leq n \leq 10^5$

### 思路简述

~~然而这题真的不好写~~

[ZXyang](https://acm.uestc.edu.cn/user/ZXyaang/ ): 一开始想的是暴力模拟找叶结点和环，但是这个样子写起来会非常非常麻烦。于是在wa了两发之后，我突发奇想换了一种写法，就变成代码里面既可以找叶结点又可以找环的神奇dfs了。

[Code by ZXyang](https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/Codeforces/1250N.cpp)

## 总结

~~奇怪的知识增加了！~~