Review

开场跟榜看 L,水题不讲,10min1A,rank10(什么嘛我手速还挺快的)。跟榜看 C,字符串分类讨论一下,33min1A,rank11(什么嘛我手速还挺快的)。跟榜看 E,还是字符串分类讨论一下,但是漏情况了交了发 WA……57min2A,rank18(什么嘛我手速还挺快的)

到目前为止都还算顺利,但是接下来的 M 我们开始三人互演。首先我们发现安全的程度和到原点的距离有关,但是达到一定临界值之后就一样安全了。一开始我想当然设了个临界值 lim = R - r,WA 了之后我认真画了个图改成了 lim = max(0, R - 2 * r),又 WA 了之后 Luowaterbi 认真画了个图告诉我是 lim = max(0, 2 * r - R),又 WA 了之后我才发现其实这是小圆半径不同取值范围时的两种情况,所以改成 lim = abs(R - 2 * r) 就过了,109min6A,是的,这题交了六发才过,过的时候 rank 已经掉到 66 了。

A 很有趣,是个好题,讨论了一会之后离散化过掉了,184min2A。G 讨论了一会之后我发现是从高位到低位贪心,由于需要高精度用 Java 写了一下,不知道 BigInteger 怎么算的内存,交了好几发 MLE 才过,259min5A

过完 A 和 过完 G 的时候 rank 都是 44,但是最后又掉到 54 / 254 了。什么时候能进个 Au 线呢……

Solution(咕咕)

Review

开场 Luowaterbi 告诉我 I 是 sb 题,让输出四个数的和,然后我就直接 ull 冲了上去 WA 了一发,才发现最大值正好可以卡爆 ull……这种题意义何在啊!!!加了个特判过了,13min2A。然后看榜好像 K 也很签到,于是写了一下,22min1A,由于手速还可以所以 rank28。

接下来的 L 和 F 难度好像差不多,我们先读了 L,接着队友又去读 F 了。我对着 L 一顿口胡,最后突然想到正解才发现口胡的全是假的,于是交了一发过了,60min1A,rank 掉到 31。然后我们对着 F 一顿推,但是没啥好的结论。推着推着,Luowaterbi 突然告诉我这个 F 居然有某种奇妙深刻的递推关系。但是数据范围又要求高精度,所以我又开始展示我的垃圾 Java 水平,这么简单的代码写了好久,然后还连交了四发 WA,debug 了半天之后突然发现是因为文件创建在一个 package 里,所以 Intellij 自动在我的代码开头加了 package 我没发现……122min5A 之后 rank 又掉到 37,又是同题数垫底了……实在是我队传统艺能……

接下来 G 和 M 难度好像也差不多,我们先读了 G,接着队友又去读 M 了。我对着 G 一顿口胡,说这个就是基环内向森林啊,然后类似后缀数组一样倍增乱搞一下就能搞出来。但是后缀数组我学得实在垃圾,只会抄板子,有点写不明白,然后我爬了。但是 Luowaterbi 就不一样了,他看了很久的 M,看着看着,Luowaterbi 突然告诉我这个 M 居然只跟每个位置的后继状态数有关。于是我迅速写了一下,287min1A,rank 又掉到 46 了,我只能爬。

总成绩是 5 - 605,rank 50/186。只能说是稳定发挥,但是什么时候能进个 Au 线呢……其实这场六题 + 手速就 Au 了,就是说其实还是有希望的吧……(?

Solution(咕咕)

Review

感觉还是好菜,该加训了……

刚开场就开始演队友。我直接读了 J,迅速大力交了两发 WA 的二分答案。一看 M 过了好多,又大力交了一发 WA。想了一会,才突然意识到 J 题的合法性并不是单调的,于是,Luowaterbi 认为答案就是一个前缀和加一个后缀 min,我照做,又交了一发 WA。

此时已经快一个小时了,而我们两个水题都 WA 着……我突然意识到 M 题需要特判 0 1,改了改过了,58min2A。owojiecao 突然发现 J 题 $0$ 必买,应该去掉 $0$ 再做。我和 Luowaterbi 纷纷感叹自己傻逼,然后我手抖写错,又交了两发才过,70min5A。此时发现 C 过题人数和 J 差不多,于是读 C,发现是个分类讨论傻逼题,然后我第一发没讨论没 $1$ 的情况,第二发交了个弱智 PE,第三发才过,84min3A

我智商完全不在线,短短不到一个半小时的时间连交了七发罚时,已经同题数垫底 rank 105,感谢队友不杀之恩。

好在中期打得还不算烂。此时大多数人都是三题, DEF 都是刚有几个人通过。我读了 D,Luowaterbi 读了 F,无果,交换题意,我发现 F 是个找规律的构造题,手玩了一会之后会了,但没认真审题又交了一发 PE,142min2A,rank 上升到 43,还是同题数垫底。我们又读了难度跟 DF 相近的 E,我说二分答案显然,于是转化成询问给定步数之内能否访问每个位置给定次数。想了一会发现大力贪心似乎可行,但没处理好交了发 WA,遂下机交给 owojiecao 写 D。跟 luowaterbi 一起读了很久 E 的代码,改了三次,终于发现我有个地方写了点很弱智的东西……228min4A,rank 掉到 55,还是同题数垫底(虽然之后有人帮我们垫底了)

接下来只有 owojiecao 的 D 比较可以期待的样子,而我和 Luowaterbi 去读剩下的题里读相对可能比较可做的 L。事实证明 L 是个我们之中并没有人会的生成函数,而 owojiecao 的 D 也没调出来……

最后 rank 80/354,什么时候能进个 Au 线呢……

Solution(咕咕)

Problem H. 最大公约数

Statement

给出两个整数 $k,n$ ($1 \leq k \leq n$),求最小的 $y$,使得对于任意 $x \in [1,n]$ 且 $x \neq k$,都满足 $\gcd(x, y) \neq \gcd(k,y)$。如果不存在这样的 $y$,输出$-1$。有 $T$ 组测试数据。

$1 \leq T \leq 50$

$1 \leq k \leq n \leq 500$

Solution

不存在这样的 $y$ 当然是骗你的,因为一定存在……

我在狂演 F 题的时候这题就有一些队伍过了,于是 Luowaterbi 和 owojiecao 就在看,但是没什么结论……我演完 F 之后看了一会样例,猜想答案就是 $k \cdot \prod_{i = 1, i \in p}^{\lfloor \frac{n}{k} \rfloor} i$,虽然不会证明但是我们三个都没想到反例,于是我就交了两发 WA,发现需要高精度,用 Java 重写,过了。

抄了一个必要性证明大概是这样的:

  • 必须保证 $k|y$。否则就有 $\gcd(k,y) \neq k$,又因为显然 $\gcd(k,y) = \gcd(\gcd(k,y),y)$,就不符合题意了啊。
  • 对于 $[1,\lfloor \frac nk \rfloor]$ 中的每一个质数 $p$,必须保证 $p|\frac yk$。否则就有 $\gcd(pk,y) = k \cdot \gcd(p,y/k) = k =\gcd(k,y)$,就不符合题意了啊。

充分性问就是不会证啊,proof by AC。

Code

这是不带高精度 WA 掉的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ll;

const int N = 1e5 + 5;
const int M = 1e3;

ll flag[N], pri[N];
void sieve () {
for (int i = 2;i < M;i++) {
if (!flag[i])
pri[++pri[0]] = i;
for (int j = 1;j <= pri[0] && pri[j] * i < M;j++) {
flag[pri[j] * i] = 1;
if (i % pri[j] == 0) break;
}
}
}

int main () {
sieve();
int T;
scanf("%d", &T);
while (T--) {
ll n, k;
scanf("%lld%lld", &n, &k);
ll p = 1, ans = k;
while (k * pri[p] <= n) {
ans *= pri[p];
p++;
}
printf("%lld\n", ans);
}
return 0;
}

这是带高精度的 Java 版本。我实在是不会 Java,勉强照着上面的 C++ 打的,如果写得很傻逼请不要 D 我呜呜呜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
public static void main (String args[]) {
final int N = 1000;
int flag[] = new int[N];
int pri[] = new int[N];
for (int i = 2;i < N;i++) {
if (flag[i] == 0) pri[++pri[0]] = i;
for (int j = 1;j <= pri[0] && i * pri[j] < N;j++) {
flag[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}

Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
for (int it = 1;it <= T;it++) {
int n = scan.nextInt();
int k = scan.nextInt();
int p = 1;
BigInteger ans = new BigInteger(k + "");
while (k * pri[p] <= n) {
ans = ans.multiply(BigInteger.valueOf(pri[p]));
p++;
}
System.out.println(ans);
}
}
}

Problem F. 乘法

Statement

给两个长度分别为 $n,m$ 的数列 $A, B$ 来表示一个 $n \times m$ 的矩阵 $C$(即 $C_{i,j} = A_i \cdot B_j$)。 给出整数 $K$,你需要求出 $C$ 中第 $K$ 大的数。

$1 \leq n,m \leq 10^5$, $1 \leq K \leq n \times m$

$-10^6 \leq A_i,B_i \leq 10^6$

Solution

$O(n \log m \log (\max C_{i,j} - \min C_{i,j}))$ 的做法显然吧……

我们预先对每一行排好序。对于一个假定的答案 $mid$,我们可以 $O(n)$ 枚举行,对于每一行都 $O(\log m)$ 二分一下计算有多少个数大于 $mid$,就能 $O(n \log m)$ 计算 $mid$ 是第几大。又因为 $mid$ 与其位次是单调的关系,那么考虑二分答案 $mid$,就可以 $O(n \log m \log (\max C_{i,j} - \min C_{i,j}))$ 求 $K$ 大了。

二分这种东西需要注意一下细节,尤其是这题还有负数和 $0$……我开场读的第一题就是这个,一眼就会了,以为有希望抢一血,结果是被 lower_boundupper_bound 演了很久,调了一个小时……太丢人了……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
ll a[N], b[N];
ll n, m, k;

ll getrank (ll cur) {
ll rank = 0;
for (int i = 1;i <= n;i++) {
ll pos;
if (a[i] == 0) pos = (cur <= 0) ? m : 0;
if (a[i] > 0) pos = m - (lower_bound(b + 1, b + m + 1, (double)cur / a[i]) - (b + 1));
if (a[i] < 0) pos = upper_bound(b + 1, b + m + 1, (double)cur / a[i]) - (b + 1);
rank += pos;
//cout << "L" << i << ':' << pos << endl;
}
return rank + 1;
}

int main () {
scanf("%lld%lld%lld", &n, &m, &k);
for (int i = 1;i <= n;i++) {
scanf("%lld", &a[i]);
}
for (int i = 1;i <= m;i++) {
scanf("%lld", &b[i]);
}
sort(b + 1, b + m + 1);

ll l = -1e12, r = 1e12;
while (l <= r) {
ll mid = (l + r) / 2;
ll rank = getrank(mid);
if (rank > k) l = mid + 1;
else r = mid - 1;
}
printf("%lld", r);
}

Problem C. 染色图

色图?哪里有色图?

Statement

在一张无向图中,如果存在一种方案,使得给每个结点染上一种颜色 $c_i \in [1,k]$ 后,任意一对相邻结点的颜色不同,则称这张无向图可以 $k$ 染色。在有 $n$ 个节点的、可以 $k$ 染色的所有简单图中,选出边数最多的一个,我们记其边数为 $g(n,k)$。

现在,给定 $n,l,r$,求 $\sum_{i=l}^{r} g(n,i)$ 对 $998244353$ 取余后的结果。有 $T$ 组测试数据。

$1 \leq T \leq 1000$

$1 \leq l \leq r \leq n \leq 10^9$

Solution

考虑一张有 $n$ 个结点染上 $k$ 种颜色,每种颜色使用了 $a_i$ 次。既然只有同色是不能连边的,那么我们把除了同色的团只玩的边全部连起来。一个大小为 $x$ 的团有 $\frac{x(x+1)}2$ 条边,那么总边数应该是
$$
\binom{n}{2} -
\sum_{i=1}^{k} \binom{a_i}{2}
$$
不难发现,要最大化总边数其实也就是要最小化 $\sum_{i=1}^k a_i^2$。为满足这一点,$a_i$ 应当均分。如果 $a_i$ 不是均分,即存在 $i,j$ 使得 $|a_i-a_j| \geq 2$,那么令 $a_i = a_j = \frac{a_i+a_j}{2}$,$\sum_{i=1}^k a_i^2$ 显然变小。所以,$a_i$ 肯定是均分,即有 $n \bmod k$ 个 $a_i$ 等于 $\lfloor \frac nk \rfloor + 1$,剩下的 $k - n \bmod k$ 个 $a_i$ 等于 $\lfloor \frac nk \rfloor$。

又考虑到 $n \bmod k$ 其实就等于 $n - k\lfloor \frac nk \rfloor$,所以,我们得出一个很长很长的式子
$$
g(n, k) = \binom {n}{2} - (n - k\lfloor \frac nk \rfloor) \cdot \binom {\lfloor \frac nk \rfloor + 1} {2} - (k - n + k\lfloor \frac nk \rfloor) \cdot \binom {\lfloor \frac nk \rfloor} {2}
$$
队友 Luowaterbi 化简了很久很久,结果好像是
$$
g(n, k) = \frac 12
(
n^2 - n -
2n \lfloor \frac nk \rfloor +
k \lfloor \frac nk \rfloor +
k \lfloor \frac nk \rfloor ^ 2
)
$$
太久远了我也不知道是不是对的建议自己化简一遍

然后大力往上套数论分块就过辣!时间复杂度 $O(T \sqrt n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
const int M = 1e3;
const int mod = 998244353;

ll qpow (ll a, ll b) {
ll ret = 1;
while (b) {
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}

ll inv (ll a) {
return qpow(a, mod - 2);
}

int main () {
int T;
scanf("%d", &T);
while (T--) {
ll n, l0, r0;
scanf("%lld%lld%lld", &n, &l0, &r0);
ll ans = 0;
for (int l = l0, r;l <= r0;l = r + 1) {
ll k = n / l;
r = min(n / k, r0);
ll len = r - l + 1;
ll cur = 0;
cur += (n * n - n) % mod * len % mod;
cur -= 2 * n * len % mod * k % mod;
cur += ((l + r) * len / 2) % mod * k % mod;
cur += ((l + r) * len / 2) % mod * k % mod * k % mod;
cur = (cur % mod + mod) % mod;
ans = (ans + cur) % mod;
}
printf("%lld\n", ans * inv(2) % mod);
}
}

Problem B. 密码学

Statement

将小写字母从 $0$ 到 $25$ 编号,将大写字母从 $26$ 到 $51$ 编号。用字符 $a$ 加密字符 $b$ 得到的字符,是 $a$ 和 $b$ 的编号相加后对 $52$ 取余后的结果对应的字符。用字符串 $key$ 加密字符串 $s$ 得到的字符串长度与 $s$ 相同,其中,第 $i$ 个字符是用 $key_i$ 加密 $s_i$ 得到的字符,如果 $key$ 的长度不够,则将 $key$ 重复多次。

有 $n$ 个字符串 $s_1,s_2,\dots,s_n$ 和 $m$ 次加密操作 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$。第 $i$ 次加密操作用 $s_{x_i}$ 加密 $s_{y_i}$,并将 $s_{y_i}$ 替换为加密结果。现在给出 $n$ 个字符串的最终结果和 $m$ 次加密操作,求 $n$ 个字符串的初始值。

$1 \leq n,m \leq 1000$, $1 \leq x_i,y_i \leq n$

$1 \leq |s_i| \leq 100$

Solution

模拟题,没啥好说的……加密是加解密就是减……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
int x[N], y[N];
char s[N][105];

int chartoint (char c) {
if (('a' <= c) && (c <= 'z')) return c - 'a';
if (('A' <= c) && (c <= 'Z')) return c - 'A' + 26;
}

char inttochar (int a) {
if ((0 <= a) && (a <= 25)) return a + 'a';
if ((26 <= a) && (a <= 51)) return a - 26 + 'A';
}

int main () {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1;i <= m;i++) {
scanf("%d%d", &x[i], &y[i]);
}
for (int i = 1;i <= n;i++) {
scanf("%s", &s[i]);
}

for (int i = m;i >= 1;i--) {
int lx = strlen(s[x[i]]);
int ly = strlen(s[y[i]]);
for (int j = 0;j < ly;j++) {
int tmp = 0;
tmp += chartoint(s[y[i]][j]);
tmp -= chartoint(s[x[i]][j % lx]);
tmp += 52;
tmp %= 52;
s[y[i]][j] = inttochar(tmp);
}
}

for (int i = 1;i <= n;i++) {
printf("%s\n", s[i]);
}
}

Problem A. 期望逆序对

Statement

给 $n$ 个随机变量 $x_1,x_2,\dots,x_n$,$x_i$ 的值是 $[l_i,r_i]$ 中随机选取的整数。你可以将这些随机变量排成任意的顺序,求逆序对数期望的最小值对 $998244353$ 取余后的结果。

$1 \leq n \leq 5 \times 10^3$, $1 \leq l_i \leq r_i \leq 10^9$

Solution

事实上,取值的期望(即 $\frac{l_i+r_i}{2}$)越小就应该排在越前面,这样得到的序列的逆序对数的期望就是最小的。

为什么呢?对于任意一个序列,我们选择相邻的两项,其他项不动,考虑这两项是否应该交换。如果前一项的期望比后一项大,那么显然交换之后逆序对数减小,所以答案的序列中相邻里两项一定是前一项的期望比较小,而要满足这个性质就只能令期望单增,于是我们确定了这个序列的顺序。

之后就只需要 $O(n^2)$ 枚举每一对变量,$O(1)$ 计算其产生的逆序对数就行了。把两个变量看成分别在 $x$ 轴和 $y$ 轴上的区间,两个变量之间能产生的逆序对数其实就等价于一个矩形在 $y=x$ 的一侧的面积吧,这个就各凭本事吧,现场写的是分类讨论。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ll;

const int N = 1e5 + 5;
const int M = 1e3;
const int mod = 998244353;

ll qpow (ll a, ll b) {
ll ret = 1;
while (b) {
if (b & 1) ret = ret * a % mod;
a = a * a % mod;
b >>= 1;
}
return ret;
}

ll inv (ll a) {
return qpow(a, mod - 2);
}

struct node {
int l, r;
} a[N];
ll invv[N];
bool operator < (const node& a, const node& b) {
return a.l + a.r < b.l + b.r;
}

ll calc (const node& a, const node& b) {
if (a.l <= b.l) {
if (a.r <= b.l) return 0;
if ((a.r > b.l) && (a.r <= b.r)) {
ll tmp = a.r - b.l + 1;
return tmp * (tmp - 1) / 2 % mod;
}
if (a.r > b.r) {
ll tmp = (b.r - b.l + 1);
ll sum = tmp * (tmp - 1) / 2 % mod;
sum += (a.r - b.r) * tmp;
return sum % mod;
}
} else {
ll tmp = (a.r - a.l + 1);
ll sum = tmp * (tmp - 1) / 2 % mod;
sum += (a.l - b.l) * tmp;
return sum % mod;
}
}

int main () {
int n;
scanf("%d", &n);
for (int i = 1;i <= n;i++) {
scanf("%d%d", &a[i].l, &a[i].r);
}
sort(a + 1, a + n + 1);
for (int i = 1;i <= n;i++) {
invv[i] = inv(a[i].r - a[i].l + 1);
}

ll q = 1;
for (int i = 1;i <= n;i++) {
q *= a[i].r - a[i].l + 1;
q %= mod;
}

ll p = 0;
for (int i = 1;i <= n;i++) {
for (int j = i + 1;j <= n;j++) {
ll tmp = calc(a[i], a[j]);
tmp = tmp * invv[i] % mod;
tmp = tmp * invv[j] % mod;
p += tmp;
if (p >= mod) p -= mod;
}
}

printf("%lld", p);
}

Review

triple_a 问我和 clp012345 要不要来玩,于是我就打了,前 World Finalist 带飞谁不爱呢

因为纯属娱乐所以可能并不是全力打,不过也并没有做到同一时刻只有一个人写……总之就是图一乐吧。

刚开场的时候因为是娱乐所以他们两个也就随便开题不跟榜了,我们各自读了一下几道题。clp012345 开始猛凹 C 凹了接近两个小时,结果是 C 最后也没过。我看到有人过 L 就大力 WA 了一发,发现把大于写成大于等于,43min2A。B 题 triple_a 说只会 TLE 的枚举子集,于是 clp012345 说 Sum over Submask DP 能做,51min1A。triple_a 又读了 I 题,说做法显然但是难写,我一看题居然是原题(2016 CCPC Changchun J),可能毛子出题人没看过国内这场,于是直接复制粘贴交了,71min1A。G 我之前就说是大力枚举,但我不会计算几何,让 triple_a 写了,105min2A。我们交流了一下 F 的题意,然后 triple_a 觉得他大概会写,然后他说反正是随便打打所以他有事要出门了(草)。我大力猜了一下 A 题有个结论,但是需要筛 $10^{11}$ 以内的质数个数,时间复杂度没法接受,clp012345 告诉我有一种叫作 Meissel-Lehmer 的神棍算法可以 $O(n^\frac 23)$ 求这个东西……找了个板子复制粘贴(?),然后我搞错边界,又贡献一发罚时,156min2A。期间 clp012345 单切了 H(我题都没读……),167min2A接下来我假装看 C 和 E,其实已经没思路了完全躺了。但他们两个还是很猛,clp012345 单切了 J,230min4A。triple_a 回来把 F 写了,257min2A。我跟 clp012345 说 E 题的圆其实就是竖线,他说用离散化线段树维护一下就行,293min4A

前 World Finalist 带飞果然牛逼,9 个题,力压 dmy,我全程躺着被带飞。

Solution(待完善)

Problem A. Bags of Candies

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-A/

Problem B. Binomial

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-B/

Problem C. Bookface

大致题意:数轴上有 $n$ 个点 $a_1,a_2,\dots,a_n$,每次你可以花费 $1$ 代价使某个点向某个方向移动 $1$(但所有点必须时刻在正半轴上)。现在,希望你求出最小总代价,使得任意两点间的距离都大于等于 $d$。有 $z$ 组测试数据。

$1 \leq z \leq 10^5$

$1 \leq n \leq 2 \times 10^5$, $1 \leq d \leq 10^6$, $0 \leq a_i \leq 3 \times 10^{11}$

$\sum n \leq 10^6$

Solution

World Finalist 凹了两个小时都没出的题,鸽。

Problem D. Clique

没读,全场最不可做的题。

Problem E. Contamination

triple_a 给我说的大致题意:平面上,给定 $n$ 个圆 $(c_x, c_y, r)$ 以及 $q$ 个询问 $(p_x,p_y,q_x,q_y,y_{min},y_{max})$,问能不能从 $(p_x,p_y) $ 走到 $(q_x,q_y)$,并满足路线不能碰到圆且任意时刻都有 $y \in [y_{min},y_{max}]$。

$1 \leq n, q \leq 10^6$

$-10^9 \leq c_x, c_y \leq 10^9$, $1 \leq r \leq 10^9$

$-10^9 \leq p_x,p_y,q_x,q_y,y_{min},y_{max} \leq 10^9$, $y_{min} \leq p_y, q_y \leq y_{max}$

一直到最后一个小时,我都是按这个题意理解的。我提出,如果圆两两不交,那么圆其实等价于其平行于 $y$ 轴的直径;但圆如果相交,就没有任何办法可做。最后一个小时 clp012345 来看 E,他自己读了一遍题,然后告诉我,题目里面说了圆是不交的……

Solution

但我没想到怎么维护这个东西,clp012345 说就是一棵离散化线段树。有空的时候再具体问他。

Code (By clp012345)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <bits/stdc++.h>

#define FOE(i, s, t) for (int i = s; i <= t; i++)
#define FOR(i, s, t) for (int i = s; i < t; i++)
#define K 2300001
#define M 1000000007
#define NINF -2002100100
#define LL long long

using namespace std;

int n, q;

struct P {
int x, y, r;
};

P p[K];

int cx[2 * K];

struct Q {
int sx, ymin, ymax, ex, id;
};

Q qu[K];

bool cmpY(P A, P B) {
return A.y < B.y;
}

bool cmpQY(Q A, Q B) {
return A.ymin < B.ymin;
}

int l[4 * K], r[4 * K];
LL a[4 * K];
int h;

int sol[K];

void build(int u, int lb, int rb) {
a[u] = NINF;
if (lb == rb) return;

build(l[u] = ++h, lb, (lb + rb) >> 1);
build(r[u] = ++h, (lb + rb) / 2 + 1, rb);
}

void insert(int u, int lb, int rb, int pos, LL val) {
if (lb == rb) {
a[u] = val; return;
}

int mid = (lb + rb) >> 1;

if (mid >= pos) {
insert(l[u], lb, mid, pos, val);
} else {
insert(r[u], mid + 1, rb, pos, val);
}

a[u] = max(a[l[u]], a[r[u]]);
}

LL query(int u, int lb, int rb, int lq, int rq) {
if (lq <= lb && rb <= rq) {
return a[u];
}

if (rb < lq || rq < lb) return NINF;

int mid = (lb + rb) >> 1;

LL a1 = query(l[u], lb, mid, lq, rq);
LL a2 = query(r[u], mid + 1, rb, lq, rq);

return max(a1, a2);
}

int tx[2 * K], head;

int findX(int val) {
int low = 1, high = head;
int res;

while (low <= high) {
int mid = (low + high) >> 1;

if (tx[mid] <= val) {
low = mid + 1;
res = mid;
} else {
high = mid - 1;
}
}

return res;
}

void solve() {
scanf("%d%d", &n, &q);

FOE(i, 1, n) {
int x, y, r;
scanf("%d%d%d", &x, &y, &r);
p[i].x = x; p[i].y = y - r; p[i].r = r;
cx[i] = x;
}

FOE(i, 1, q) {
int px, py, qx, qy, ymin, ymax;
scanf("%d%d%d%d%d%d", &px, &py, &qx, &qy, &ymin, &ymax);

cx[i + n] = px;
cx[i + n + q] = qx;

qu[i].sx = min(px, qx);
qu[i].ex = max(px, qx);
qu[i].ymin = ymin;
qu[i].id = i;
qu[i].ymax = ymax;
}

sort(p + 1, p + n + 1, cmpY);
sort(qu + 1, qu + q + 1, cmpQY);
sort(cx + 1, cx + n + 2 * q + 1);

int last;
FOE(i, 1, n + 2 * q) {
if (i == 1 || cx[i] != last) {
head++; tx[head] = cx[i];
last = cx[i];
}
}

build(0, 1, head);

int ptr = 1;

FOE(i, 1, q) {
int cmin = qu[i].ymin;

// printf("cmin is %d\n", cmin);

while (ptr <= n && p[ptr].y <= cmin) {
int qx = findX(p[ptr].x);
// printf("INSERT %d\n", ptr);
insert(0, 1, head, qx, p[ptr].y + p[ptr].r * 2);

// printf("PTR is %d\n", ptr);

ptr++;
}

int qsx = findX(qu[i].sx);
int qex = findX(qu[i].ex);

// printf("? %d %d\n", qsx, qex);

int id = qu[i].id;

sol[id] = (query(0, 1, head, qsx, qex) < qu[i].ymax);
}

FOE(i, 1, q) {
if (sol[i]) puts("YES"); else puts("NO");
}
}

int main() {
solve();
}

Problem F. The Halfwitters

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-F/

Problem G. Invited Speakers

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-G/

Problem H. Lighthouses

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-H/

Problem I. Sum of Palindromes

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-I/

Problem J. Space Gophers

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-J/

Problem K. To argue, or not to argue

大致题意:一个 $n \times m$ 的网格,某些位置是可用的(可以坐一个人),某些位置是不可用的(不能坐人)。现在有 $k$ 对共 $2k$ 个人,所有人两两不同。每个人都要坐到一个可用的位置,且每一对人坐的两个位置都不能相邻。问安排座位的方案数对 $10^9+7$ 取余后的结果。有 $z$ 组测试数据,数据保证可用的座位至少有 $2k$ 个。

$1 \leq z \leq 10$

$1 \leq n, m \leq 144$, $1 \leq k \leq \frac{nm}{2}$

Solution

我读的题,第一反应是反过来统计有相邻的情况的方案数然后做个容斥。跟 clp012345 说了下题意,他说要再上个插头 DP。

事实证明这两个思路都是对的,但具体实现实在是太过复杂,我们在有更简单的题没写完的情况下也就放弃了,没继续往下讨论。

Problem L. Wizards Unite

https://tanakarino.cn/2020/06/02/2020-Petrozavodsk-Winter-Camp-Day-5-L/

引入

首先引入一个问题。LibreOJ 6235:令 $\pi(n)$ 为 $n$ 以内的质数个数,求 $\pi(n)$ $(1 \leq n \leq 10^{11})$。

当然你可能会说你有分段打表的做法。众所周知,$1 \leq l \leq r \leq 10^{12}$ 且 $0 \leq r - l \leq 10^6$ 时,$[l, r]$ 中质数个数有一个很 trivial 的类似 Eratosthenes 筛的 $O((r - l)\log \log \sqrt r)$ 的做法。在这个基础上把 $[1, 10^{11}]$ 分成 $10^4$ 段,每段在本地预处理一下,段外的部分再单独算。这样分段打表确实可以卡过去,但是我们有不那么生草的做法:洲阁筛 min_25筛 Meissel-Lehmer 算法可以在 $O(n^{\frac23})$ 的时间复杂度内计算 $\pi(n)$。

这个算法在算法竞赛选手之间并不怎么普及(所以想写这篇文章),可能是因为实现起来确实略微有点麻烦(尤其是对不能抄板子的 OI 选手来说?)。虽然说 Miller-Rabin 素性判断和 Pollard-Rho 质因数分解也很麻烦,但也面对的场景大概也多一些,相比之下 Meissel-Lehmer 算法在算法竞赛生涯中可能遇不到几次(?)。目前见到的相关题目只有 2016 ICPC 沈阳赛区网络赛 J 和 2020 毛营 Day5 I,更生草的是可以看到后者的官方题解就是分段打表……大概进一步印证了这个算法的冷门……?

原理

令 $p_1, p_2, \dots, p_m$ 为前 $m$ 个质数。定义 $\phi(n, m)$ 为 $[1, n]$ 内所有质因子都大于 $p_m$ 的数的个数,$P_k(n, m)$ 为 $[1, n]$ 内恰有 $k$ 个大于 $p_m$ 的质因子的数的个数。 特别地,令 $P_0(n, m) = 1$,则有

$$
\phi(n, m) = P_0(n, m) + P_1(n, m) + \dots + P_k(n, m) + \dots
$$

注意到 $p_m^k > n$ 时有 $P_k(n, m) = 0$,所以,如果我们取 $x \in [n^{\frac13}, n^{\frac12}]$ 并令 $m = \pi(x)$,对于任意 $k \geq 3$,都有 $P_k(n, m) = 0$。即,
$$
\phi(n, m) = P_0(n, m) + P_1(n, m) + P_2(n, m)
$$

根据定义,显然 $P_1(n, m) = \pi(n) - m$,于是我们对上式适当变换,得
$$
\pi(n) = \phi(n, m) - P_2(n, m) + m - 1
$$
接下来,我们只需要计算 $\phi(n, m)$ 和 $P_2(n, m)$。根据定义,不难得到其计算方式如下:
$$
P_2(n, m) = \sum_{x < p \leq \sqrt n} (\pi(\frac np) - \pi(p) + 1)
$$

$$
\phi(n, m) =
\begin{cases}
[n], & m = 0 \
\phi(n, m - 1) - \phi(\frac {n}{p_m}, m - 1), & m \geq 1
\end{cases}
$$

复杂度分析

$P_2(n, m)$

对于 $x < p \leq \sqrt n$,显然有 $\frac np < \frac nx < n^{\frac 23}$,为了快速计算 $P_2(n, m)$,我们可以用线性筛 $O(n^\frac 23)$ 预处理 $[1, n^{\frac 23}]$ 内的质数,然后 $O(n^\frac 12)$ 进行累加。时间复杂度 $O(n^\frac 23)$,空间复杂度 $O(n^\frac 23)$。

如果这个空间复杂度无法接受,我们可以时间换空间,少预处理一些,对于较大的询问则令 $\pi(n)$ 和 $P_2(n, m)$ 相互调用。那么时空复杂度是多少,究竟应该预处理多少呢?下面那份网上找的板子预处理的范围是 $5 \times 10^6$,并且认为可以降到 $n^\frac 13$,我暂且没算明白……

$\phi(n, m)$

更算不明白了……这式子看上去挺慢的,然而又可以大力预处理大力剪枝(见板子),总之实际跑起来完全没问题。但很想知道时间复杂度怎么算……

代码

这是网上可以大量找到的一个 Meissel-Lehmer 的板子(看码风也知道不是我写的),想自己整一个,但是我太懒了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
const int N = 5e6 + 2;//通过知道前面的n^1/3的质数可以推断后面n^2/3的质数所以可以适当减小
bool np[N];
int prime[N], pi[N];
int getprime()
{
int cnt = 0;
np[0] = np[1] = true;
pi[0] = pi[1] = 0;
for(int i = 2; i < N; ++i)
{
if(!np[i]) prime[++cnt] = i;
pi[i] = cnt;
for(int j = 1; j <= cnt && i * prime[j] < N; ++j)
{
np[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
return cnt;
}
const int M = 7;//为了减小内存可以不过是质数
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;//为了减小内存可以不过要按质数减小如去掉17
int phi[PM + 1][M + 1], sz[M + 1];
void init()
{
getprime();
sz[0] = 1;
for(int i = 0; i <= PM; ++i) phi[i][0] = i;
for(int i = 1; i <= M; ++i)
{
sz[i] = prime[i] * sz[i - 1];
for(int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
}
}
int sqrt2(ll x)
{
ll r = (ll)sqrt(x - 0.1);
while(r * r <= x) ++r;
return int(r - 1);
}
int sqrt3(ll x)
{
ll r = (ll)cbrt(x - 0.1);
while(r * r * r <= x) ++r;
return int(r - 1);
}
ll getphi(ll x, int s)
{
if(s == 0) return x;
if(s <= M) return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
if(x <= prime[s]*prime[s]) return pi[x] - s + 1;
if(x <= prime[s]*prime[s]*prime[s] && x < N)
{
int s2x = pi[sqrt2(x)];
ll ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
for(int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]];
return ans;
}
return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}
ll getpi(ll x)
{
if(x < N) return pi[x];
ll ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1;
return ans;
}
ll lehmer_pi(ll x)
{
if(x < N) return pi[x];
int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
int b = (int)lehmer_pi(sqrt2(x));
int c = (int)lehmer_pi(sqrt3(x));
ll sum = getphi(x, a) +(ll)(b + a - 2) * (b - a + 1) / 2;
for (int i = a + 1; i <= b; i++)
{
ll w = x / prime[i];
sum -= lehmer_pi(w);
if (i > c) continue;
ll lim = lehmer_pi(sqrt2(w));
for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1);
}
return sum;
}

这个板子有一个比较有疑问的地方:有两个功能完全一样的函数 getpilehmer_pi。很显然 getpi 就是我们上面介绍的方法,但 lehmer_pi 写的内容我完全没懂……看起来是传说中(?)Deleglise 和 Rivat 提出的 $O(\frac{n^\frac 23}{\log^2 n})$ 的优化(有兴趣可以看这篇论文)。如果真的是的话,只能说这个优化的常数也太大了——测试了各种数据范围,结论是这个 lehmer_pi 跑起来比 getpi 还要慢一些……如果要抄这个板子的话,还是直接忽略最后一段吧……