本文是 XXVII POI (2019/2020 年度) 的中文翻译。今年受新冠疫情影响,Stage III 被取消了,因此只有 Stage I 和 Stage II 的题目。

Stage I

Najmniejsza wspólna wielokrotność (nww)

给出一个自然数 \(M\),找到一个区间 \([a,~b]\) 使得 \(M = \text{lcm}(a, a + 1, \dots, b)\),并且 \(a < b\)

输入格式

输入数据第一行包含一个整数 \(z\),表示测试数据组数。对于每组测试数据:

第一行包含一个整数 \(M\),含义如题面所述。

输出格式

对于每组数据,如果不能找到一个合法的区间,输出 NIE。否则,输出两个正整数 \(a\)\(b\)。如果存在多组解,找一个 \(a\) 最小的。如果还有多组解,找一个 \(b\) 最小的。

样例输入

3
12
504
17

样例输出

1 4
6 9
NIE

样例解释

对于第一个数据,\(12\) 是区间 \([2,4]\) 的最小公倍数,包含 \(2\)\(3\)\(4\)。也是区间 \([1,4]\) 的最小公倍数,包含 \(1\)\(2\)\(3\)\(4\)。其中后者的 \(a\) 更小。

附加样例参见 nww/nww*.innww/nww*.out

  • 附加样例 \(1\)\(5\) 组数据,\(M\) 依次为:\(5\)\(6\)\(7\)\(8\)\(9\)
  • 附加样例 \(2\)\(1\) 组数据,\(M\)\(1\ 000\ 000\)
  • 附加样例 \(3\)\(1\) 组数据,\(M\)\(99\ 999\ 990\ 000\ 000\)
  • 附加样例 \(4\)\(z = 10000\)\(M\)\(500\ 001\ 500\ 001\ 000\ 001\)\(500\ 001\ 500\ 001\ 000\ 000\) 交替出现。

数据范围与提示

Subtask # 额外限制 分值
1 \(1 \le z \le 10, 1 \le M \le 1000\) 18
2 \(1 \le z \le 100, 1 \le M \le 10^9\) 20
3 \(1 \le z \le 100, 1 \le M \le 10^{18}\) 20
4 \(1 \le z \le 10000, 1 \le M \le 10^{18}\) 42

Pisarze

给出一行波兰语文本,已知这段文本来自于以下三本书之一:

  • Adama Mickiewicza 所著的 Pan Tadeusz
  • Henryka Sienkiewicza 所著 Quo Vadis
  • Bolesława Prusa 所著的 Lalka

请你写一个程序判断这行文本来自于哪本书。

输入格式

输入数据第一行包含一个整数 \(T\),表示测试数据组数。对于每组测试数据:

第一行包含一段波兰语文本,由 \(10\)\(2000\) 个单词组成。这一行的开头或者结尾都是一个完整的单词或者标点符号。

保证输入的所有文本长度之和不超过 \(2 \cdot 10^6\)

输出格式

对于每组数据,输出 MickiewiczPrus 或者 Sienkiewicz,表示这行文本所在书的作者。

样例输入

3
Petroniusz obudzil sie zaledwie kolo...
Litwo! Ojczyzno moja! ty jestes jak...
W poczatkach roku 1878, kiedy swiat...

注意:样例输入并不完整,被截断了一部分。

样例输出

Sienkiewicz
Mickiewicz
Prus

数据范围与提示

这题的代码长度不能超过 \(10\) KB。

这是一个数据分析题,你的程序不需要准确的识别每组数据。评分标准如下:

  • \(T\) 是测试数据组数。
  • \(P\) 是选手程序识别对的数据组数。
  • 如果 \(P \ge 0.9 \cdot T\),那么选手会获得 \(100\%\) 的分数。
  • 如果 \(P \le \frac{T}{3}\),选手会获得 \(0 \%\) 的分数。
  • 否则,选手获得的分数为 \(100 \cdot \frac{P- \frac{T}{3}}{0.9 \cdot T - \frac{T}{3}} \%\)

每个测试数据的文本来自于提供的文本,同时还附赠了一个脚本 pistestgen.py,可以从这里下载。用命令 python3 pistestgen.py subtask name directory [seed] 即可生成一组数据,其中:

  • subtask 是子任务编号,一个从 \(1\)\(4\) 的整数。
  • name 是测试数据的名字,这个脚本会生成 name.inname.out 这两个文件。
  • directory 是包含这三本书的文件夹路径。
  • seed 是可以不加的字符串,用于生成同一组数据(两次程序如果 seed 值是一样,那么生成的数据也是一样的)。

所有的测试数据保证也是通过这个程序生成的。

Subtask # 额外限制 分值
1 \(T \le 100\),每行包含 \(500\) 到 \(2000\) 个单词 20
2 \(T \le 1000\),每行都是由完整的句子组成 20
3 \(T \le 1000\),每行包含 \(30\) 到 \(80\) 个单词 30
4 \(T \le 1000\) 30

Pomniejszenie

给出两个数字串 \(A\)\(B\),保证 \(A \ge B\)。你可以修改 \(A\) 里面恰好 \(k\) 个数字,求出比 \(B\) 小的最大数字。

输入格式

输入数据第一行包含一个整数 \(t\),表示测试数据组数。对于每组测试数据:

第一行包含三个非负整数 \(A\)\(B\)\(k\)。保证 \(A\)\(B\) 的长度是一样的,并且可能有前导零。\(k\) 是一个正整数,并且不会超过 \(A\)\(B\) 的长度。

输出格式

对于每组数据,输出一个满足下面条件的整数 \(C\)

  • \(C\) 的长度必须和 \(A\) 以及 \(B\) 的一样,可以包含前导零。
  • \(C\) 是由 \(A\) 恰好修改了 \(k\) 个字符得到。
  • \(C\) 要尽可能的大,并且 \(C\) 要小于 \(B\)

如果不存在满足按上面条件的 \(C\),请输出\(-1\)

样例输入

4
555 333 1
0555 0551 3
0555 0333 4
9 9 1

样例输出

255
0499
-1
8

附加样例参见 pom/pom*.inpom/pom*.out

  • 附加样例 \(1\)\( t = 100\)\(A\) 依次是 \(20\ 000, 20\ 001, \dots\)\(B\) 一直是 \(20\ 000\)\(k=1\)
  • 附加样例 \(2\)\(t = 100\);对于每组数据 \( n = 5000\),并且 \(A\)\(B\) 里仅包含数字9\(k\) 依次是 \(4901, \dots, 5000\)
  • 附加样例 \(3\)\(t = 100\);对于每组数据 \( n = 10^5\),并且 \(A\) 里包含数字9\(B\) 里仅包含数字 2\(k\) 依次是 \(1, \dots, 100\)

数据范围与提示

\(n\) 是数字串 \(A\)\(B\) 的长度,保证对于所有数据有 \(1 \le t \le 100\)

Subtask # 限制 分值
1 \(1 \le n \le 5\) 18
2 \(1 \le n \le 5000\) 20
3 \(1 \le n \le 10^5, k=1\) 20
4 \(1 \le n \le 10^5\) 42

Przedszkole

有一个 \(n\) 个点 \(m\) 条边的无向图,每个点从 \(1\)\(n\) 编号。你有 \(k\) 种颜色,要给每个点染色,使得有边相连的两个点颜色不一样。求出染色方案数,对 \(10^9+7\) 取模。

输入格式

第一行包含 \(3\) 个整数 \(n\)\(m\)\(z\),表示图中点个数,边条数和询问个数。

接下来 \(m\) 行,每行包含两个整数 \(a_i\)\(b_i\),表示点 \(a_i\)\(b_i\) 之间有一条边相连。保证不会有重边和自环。

接下来 \(z\) 行,每行包含一个整数 \(k_i\),表示你有 \(k_i\) 种颜色。

输出格式

对于每组数据,输出你有 \(k_i\) 种颜色时的染色方案数,对 \(10^9+7\) 取模。

样例输入

4 4 1
1 2
2 3
1 3
3 4
3

样例输出

12

附加样例参见 prz/prz*.inprz/prz*.out

  • 附加样例 \(1\)\(n=5,m=10\),两个询问 \(k \in \{5, 6\}\)
  • 附加样例 \(2\)\(n=11,m=40\),一个询问 \(k=15\)
  • 附加样例 \(3\)\(n=100,m=15\)\(5\) 个询问,\(k\)\([10, 100]\) 里面随机;
  • 附加样例 \(4\)\(n=100,m=100\),所有点构成了一个环;三个询问 \(k \in \{5, 10, 15\}\)

数据范围与提示

对于 \(100\%\) 的数据,\(1 \le n \le 10^5, 0 \le m \le \min(10^5, n(n-1)/2), 1 \le z \le 1000, 1 \le a_i, b_i \le n, 1 \le k_i \le 10^9\)

Subtask # 额外限制 分值
1 \(n \le 8, k \le 8, z \le 50\) \(8\)
2 \(n \le 15\) \(26\)
3 \(m \le 24\) \(33 \)
4 每个点恰好有两条边和它相连 \(33\)

Układ scalony

有一个 \(n \cdot m\) 个点排成 \(n\)\(m\) 列,其中第 \(i\) 行第 \(j\) 列的坐标为 \((i, j)\)。对于两个点 \((x_1,y_1)\)\((x_2,y_2)\),如果 \(|x_1-x_2| + |y_1-y_2|=1\),那么它们之间有一条边相连。

给定一个整数 \(k\),你需要找到这个图的一个生成树,使得它的直径上恰好有 \(k\) 条边。

输入格式

输入仅一行包含三个整数 \(n\)\(m\)\(k\)

输出格式

如果不存在这样的生成树,输出 NIE。否则,在第一行输出 TAK。接下来 \(nm-1\) 行,每行包含 \(4\) 个整数 \(i_1,j_1,i_2,j_2\) (\(1 \le i_1, i_2 \le n, 1 \le j_1, j_2 \le m\)),表示点 \((i_1,j_1)\) 和点 \((i_2,j_2)\) 之间有边相连。如果有多组解,输出任意一组即可。

样例输入 1

2 3 4

样例输出 1

TAK
1 1 1 2
1 1 2 1
1 2 2 2
2 3 2 2
1 2 1 3

样例解释 1

样例输入 2

2 3 1

样例输出 2

NIE

附加样例参见 ukl/ukl*.inukl/ukl*.out

  • 附加样例 \(1\)\(n=2,m=3,k=3\)
  • 附加样例 \(2\)\(n=1,m=10,k=10\)
  • 附加样例 \(3\)\(n=1000,m=1000,k=999\ 999\)

数据范围与提示

对于 \(100\%\) 的数据,\(1 \le n, m \le 1000, 0 \le k \le 10^6\)

Subtask # 限制 分值
1 \(n,m\le 6\) 20
2 \(n \le 3, m \le 1000\) 20
3 \(n,m \le 1000\)\(n \cdot m\) 是奇数 30
4 \(n,m \le 1000\)\(n \cdot m\) 是偶数 30

Stage II

Day 0

Wakacje Bajtazara (wak)

给出一棵 \(n\) 个点的树,第 \(i\) 个点有个权值 \(w_i\)。现在你需要一条长度为 \(2k-1\) 的路径 \(p_1,p_2,\dots,p_{2k-1}\),使得:

  • \(p_i\)\(p_{i+1}\) 在树上相邻
  • \(p_1,p_3,p_5,\dots,p_{2k-1}\) 互不相同
  • \(w_{p_1}+w_{p_3} + \dots + w_{p_{2k-1}}\) 最大
输入格式

第一行一个整数 \(n\) (\(1 \le n \le 10^6\)),表示树上节点个数。

第二行 \(n\) 个整数 \(w_1,w_2,\dots,w_n\) (\(1 \le w_i \le 10^6\)),表示每个点的权值

接下来 \(n-1\) 行,每行两个整数 \(a_i\)\(b_i\) (\(1 \le a_i, b_i \le n\)),表示树上一条边。

输出格式

第一行输出一个整数表示最大权值。第二行输出一个整数表示 \(k\) 的大小。第三行输出 \(p_1,p_2,\dots,p_{2k-1}\)。如果有多个方案,输出任意一个即可。

样例输入
8
3 8 5 4 1 2 1 1
1 2
2 3
2 4
5 4
4 6
7 6
8 7
样例输出
13
4
3 2 1 2 4 6 7

Day 1

Drzewo czwórkowe (czw)

有一个 \(2^m \times 2^m\) 的黑白格子,现在用一个递归定义的字符串来描述这个格子。

  • 如果整个格子都是白色的,用一个 0 来标记
  • 如果整个格子都是黑色的,用一个 1 来标记
  • 否则,先用 4 来标记,接下来对应 \(4\)\(2^{m-1} \times 2^{m-1}\) 的格子描述,依次为左上角,右上角,左下角,右下角的格子。

现在给出 \(m\) 和用于描述这个格子的字符串。求出这个格子里面黑色连通块的个数和面积最大的黑色连通块。面积对 \(10^9 + 7\) 取模。

输入格式

第一行包含一个整数 \(m\) (\(1 \le m \le 10^9\)),表示格子的大小。

第二行包含一个仅包含 014 的字符串,对应了这个格子的描述,长度不超过 \(10^6\)

输出格式

第一行输出黑色连通块的数目。第二行输出面积最大的黑色连通块,对 \(10^9+7\) 取模。

样例输入
3
404004111014001410011
样例输出
2
24

Wielki Upadek (wie)

\(n\) 个多米诺骨牌,第 \(i\) 个立在了位置 \(x_i\) 处,高度为 \(h_i\)。现在又给出 \(N_1\) 个高度为 \(H_1\)\(N_2\) 个高度为 \(H_2\) 个多米诺骨牌。保证要么 \(H_1\)\(H_2\) 的约数,要么 \(H_2\)\(H_1\) 的约数。并且 \(H_1\)\(H_2\) 都小于之前的多米诺骨牌高度,也就是说 \(\max(H_1,H_2) < \min(h_1,h_2,\dots,h_n)\)

你可以任意放置这 \(N_1+N_2\) 个多米诺骨牌,然后最后选个多米诺骨牌往左或者往右推。求出最多能够推倒多少多米诺骨牌。

如果位置 \(x\)\(y\) (\(x < y\)) 有个骨牌,高度分别为 \(h_1\)\(h_2\)。如果在 \(x\) 往右推并且 \(x+h_1 \ge y\),那么在 \(y\) 的骨牌也会被推倒;如果在 \(y\) 往左推并且 \(y-h_2 \le x\),那么在 \(x\) 的骨牌也会被推倒。

输入格式

第一行包含一个整数 \(n\) (\(1 \le n \le 200000\)),表示一开始放置好的多米诺骨牌个数。

接下来 \(n\) 行,每行包含一个整数 \(x_i\)\(h_i\) (\(0 \le x_i \le 10^{18}, 1 \le h_i \le 2000000\)),表示第 \(i\) 个多米诺骨牌放在了位置 \(x_i\) 处,高度为 \(h_i\)

接下来一行包含四个整数 \(N_1\)\(H_1\)\(N_2\)\(H_2\) (\(0 \le N_1, N_2 \le 10^{18}, 1 \le H_1, H_2 \le 10^6\)),含义如题所述。

输出格式

输出一行表示最多能推倒的多米诺骨牌数目。

样例输入
3
1 5
10 6
20 7
1 4 2 1
样例输出
5

Day 2

Trudny dylemat przedszkolanina (tru)

给出一个正整数 \(n\),求出两个不超过 \(n\) 的正整数 \(x\)\(y\),使得集合 \(\{d: d \mid x \text{ or } d \mid y \}\) 的大小最大。

输入格式

第一行包含一个整数 \(n\) (\(1 \le n \le 10^{16}\))

输出格式

第一行输出集合的大小。第二行输出两个整数 \(x\)\(y\),表示一个解。如果有多组解,输出任意一个即可。

样例输入
15
样例输出
8
12 10

Marudny Bajtazar (mar)

有一个长度为 \(n\)01 串。有 \(m\) 个操作,每次翻转位置 \(a_i\) 的字符,把 0 变成 1 或者把 1 变成 0。每次操作后,找出最短的不作为子串出现的 01 串的长度。

\(1 \le n \le 10^5, 0 \le m \le 10^4\)

输入格式

第一行包含两个整数 \(n\)\(m\) (\(1 \le n \le 10^5, 0 \le m \le 10^4\)),表示字符串长度和操作个数。

第二行包含一个长度为 \(n\)01 串。

接下来 \(m\) 行,每行包含一个整数 \(a_i\) (\(1 \le a_i \le n\)),表示需要翻转的位置。

输出格式

输出 \(m+1\) 行,第 \(i\) 行表示第 \(i-1\) 次操作后的答案。第一行表示没有任何操作时的答案。

样例输入
6 2
001010
6
2
样例输出
2
3
2