Nanako

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)$,就不符合题意了啊。
阅读全文 »

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

阅读全文 »

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$ 条边,那么总边数应该是

不难发现,要最大化总边数其实也就是要最小化 $\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$。所谓「大胆猜想,从不求证」。证明?问就是不会。这是学了这么多年数学的数学直觉。

阅读全文 »

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/

阅读全文 »

引入

首先引入一个问题。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$,则有

注意到 $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$。即,

根据定义,显然 $P_1(n, m) = \pi(n) - m$,于是我们对上式适当变换,得

接下来,我们只需要计算 $\phi(n, m)$ 和 $P_2(n, m)$。根据定义,不难得到其计算方式如下:

复杂度分析

阅读全文 »

Problem L. Wizards Unite

Statement

给 $1$ 把金钥匙(可多次使用的钥匙),$k$ 把银钥匙(只能用一次)。给 $n$ 个箱子,每个箱子有一个打开所需时间 $t_i$(跟钥匙类型无关)。一把钥匙同时只能开一个箱子,问打开所有箱子所需的最小总时间。有 $z$ 组测试数据。

$0 \leq k < n \leq 10^5$

$0 \leq t_i \leq 10^9$

$\sum n \leq 10^6$

Solution

本场最简单的题。

不失一般性,我们认为所有箱子按 $t_i$ 排升序。显然方案只能是 $k$ 把银钥匙都用来开一个箱子,金钥匙开其他所有箱子,而答案就是以下两者中的较大值:用银钥匙的箱子中耗时最长的一个的耗时;金钥匙开其他所有箱子的耗时之和。

注意到答案无论如何也不可能小于 $t_n$,也就是说用银钥匙开 $t_n$ 箱子一定不会浪费时间。那么为了令金钥匙耗时之和尽可能小,实际上 $k$ 把银钥匙开的就是最右边的 $k$ 个箱子,于是答案就很显然了。时间复杂度 $O(n \log n)$。

阅读全文 »

Problem J. Space Gophers

Statement

有一个由边长为 $1$ 的小正方体组成的边长为 $10^6$ 的实心正方体。在其中挖 $n$ 条隧道,每条隧道用 $(-,y_i,z_i)$ 或 $(x_i,-,z_i)$ 或 $(x_i,y_i,-)$ 表示。挖隧道的含义是,指定其中两个维度的坐标,沿平行于另一个维度轴线的方向把 $10^6$ 个方块拿走。挖完 $n$ 条隧道之后,$q$ 次询问两个点 $(s_x,s_y,s_z)$ 和 $(t_x,t_y,t_z)$ 是否可以通过若干条隧道连通。保证 $s$ 和 $t$ 处于隧道中。有 $z$ 组测试数据。

$1 \leq z \leq 6$

$1 \leq n \leq 3 \times 10^5$, $1 \leq x_i,y_i,z_i \leq 10^6$

$1 \leq q \leq 5 \times 10^5$, $1 \leq s_x,s_y,s_z,t_x,t_y,t_z \leq 10^6$

Solution

clp 单切之前大致跟我讲了一下做法。实际上两条隧道连通 iff 某一个维度坐标相等或相差 1,于是我们要做的事情就是把所有这样的隧道对找出来,在并查集上 merge 起来。

这个东西说起来简单,实现起来就比较呕吐……具体还是看代码吧……似乎是这篇文章里最长的代码

Code (By clp012345)

阅读全文 »

Problem I. Sum of Palindromes

Statement

把给定的 $n$ 位数分解成不超过 $25$ 个回文数(不允许前导零)。有 $z$ 组测试数据。

$1 \leq z \leq 20000$

$1 \leq n \leq 10^5$

$\sum n \leq 3 \times 10^6$

Solution

跟国内比赛撞车了(2016 CCPC Changchun J),可能这些毛子出题人没怎么看国内比赛的题。

做法很简单,就是每次减掉小于当前数的最大的回文数。很显然每次可以减掉一半的长度,所以大概只需要 $\log n$ 次就够了。唯一的难点在于实现有点恶心,需要上高精度,不过我直接复制以前打 16 长春时候的代码了。(那个时候写得很丑不要骂我呜呜呜)

Code (By Nanako)

阅读全文 »