36th Petrozavodsk Programming Camp, Winter 2019 Day 1

Problem A

Unsolved.

Problem B

Solved again by Kilo_5723. 02:01 (+)

题意：求 $i_1,i_2\cdots i_k$ 满足 $1\le i_1<i_2<\cdots <i_k\le n$，且使得 $max\{(w_{i_1}+w_{i_2}),(w_{i_2}+w_{i_3}),\cdots ,(w_{i_k}+w_{i_1})\}$ 最小。

题解：首先考虑二分答案。

验证的时候，我们肯定按照原来的位置，从小到大插入，满足现有的相邻和$\le mid$的插入，否则，直接扔掉。

扔掉的数，我们可以保证插入他是不优的，因为插入他，就相当于用一个比较大的数替换了一个小的数，显然不可行。

这样的时间复杂度是 $O(nlog^2n)$，TLE了。

我们观察二分答案，其实我们就是在查找插入的时候，两面出现相邻和的 max 的第 $k$ 大。

于是，我们直接动态维护插入即可。

不过动态维护似乎有点难写，在观察一下就能发现，其实就是查询每一个数的两边小于他的数里面离他最近的数是多少，直接 RMQ 维护就行了。

对于相等的数，我们可以采用左边可以取到相等的，右边必须严格小于的来区分。

这样 RMQ 问题用 ST 表解决，时间复杂度就就降到了 $O(nlogn)$。

Problem C

Resolved by Kilo_5723. 01:08 (+1)

题意：给定排列 $\{ p_n \}$，$\{ q_n \}$，构造两个长度为 $n$，取值在 $[-n,n]$ 的整数序列 $\{ a_n\} ,\{ b_n\}$，使 $a_{p_1} \le a_{p_2} \le \dots \le a_{p_n}, b_{q_1} \le b_{q_2} \le \dots \le b_{q_n}$，且对于所有的 $i<j$，满足 $a_i+b_j<0$ 的数对数量为 $k$。

题解：令 $b_{q_i}=i-1$，剩余未匹配数对为 $k$，对于每一个 $a_{p_i}$，设为 $-n$ 可以最多贡献 $n-p_i$ 组数对，设为 $n$ 可以一组都不贡献，因此在 $k>=n-p_i$ 和 $k=0$ 时都可以 $O(1)$ 得出答案，因此只考虑 $0<k<n-p_i$ 的情况。

在这种情况下，$a_{p_i}$ 可以和所有 $\{ b_n \}$ 中所有下标大于 $p_i$ 的数产生数对，由于 $\{ b_n \}$ 中的数是各不相同的，因此只要对 $\{ b_n \}$ 中下标大于 $p_i$ 的数排序，取出第 $k$ 个，取反后 $-1$ 就能贡献 $k$ 对数对。

Problem D

Solved by Weaver_zhu. 03:53 (+3)

Problem E

Unsolved.

Problem F

Solved by Xiejiadong. 00:28 (+1)

题意：初始图为白，如果一个点的所有边中仅有一条是白的，会自动变成黑的，求最少让多少条边变黑，就可以让全图变黑。

题解：稍微画一画分析一下就能发现，对于每一个联通块可以独立考虑。

而每一个联通块的答案能很明显的发现是 $边-点+1$ 。

对于每一个联通块求和即可。

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.