Nanako

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

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$ 应当均分。如果 $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$。

阅读全文 »

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)$。根据定义,不难得到其计算方式如下:

复杂度分析

阅读全文 »