36th Petrozavodsk Programming Camp, Winter 2019 Day 1

From EOJ Wiki
Revision as of 08:10, 23 September 2019 by Xiejiadong (talk | contribs) (→‎Problem C)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

Solved again 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.