| 题目名称 | 异或 | 游戏 | 连通块 | 公交路线 |
|---|---|---|---|---|
| 题目类型 | 传统型 | 传统型 | 传统型 | 传统型 |
| 目录 | xor \text{xor} xor | game \text{game} game | connect \text{connect} connect | route \text{route} route |
| 可执行文件名 | xor \text{xor} xor | game \text{game} game | connect \text{connect} connect | route \text{route} route |
| 输入文件名 | xor.in \text{xor.in} xor.in | game.in \text{game.in} game.in | connect.in \text{connect.in} connect.in | route.in \text{route.in} route.in |
| 输出文件名 | xor.out \text{xor.out} xor.out | game.out \text{game.out} game.out | connect.out \text{connect.out} connect.out | route \text{route} route |
| 每个测试点时限 | $ 1.0$秒 | $ 1.0$秒 | 2.0 2.0 2.0秒 | 1.0 1.0 1.0秒 |
| 内存限制 | 512 MB \text{512 MB} 512 MB | 512 MB \text{512 MB} 512 MB | 512 MB \text{512 MB} 512 MB | 512MB \text{512MB} 512MB |
| 子任务数目 | 10 \text{10} 10 | 20 \text{20} 20 | 25 \text{25} 25 | 20 \text{20} 20 |
| 测试点是否等分 | 是 | 是 | 是 | 是 |
| 对于C++语言 | xor.cpp \text{xor.cpp} xor.cpp | game.cpp \text{game.cpp} game.cpp | connect.cpp \text{connect.cpp} connect.cpp | route.cpp \text{route.cpp} route.cpp |
|---|
| 对于C++语言 | -lm -std=c++14 -O2 \text{-lm -std=c++14 -O2} -lm -std=c++14 -O2 |
|---|
1
1
1. 选手提交的源程序必须存放在已建立好的，且带有样例文件和下发文件的文件夹中，文件夹名称与对应试题英文名一致。
2
2
2. 文件名（包括程序名和输入输出文件名）必须使用英文小写。
3.
3.
3.
C++
\text{C++}
C++ 中函数
main()
\text{main()}
main() 的返回值类型必须是
int
\text{int}
int, 值必须为
0
0
0。
4
4
4. 对于因未遵守以上规则对成绩造成的影响，相关申诉不予受理。
5
5
5. 若无特殊说明，结果比较方式为忽略行末空格、文末回车后的全文比较。
6
6
6. 程序可使用的栈空间大小与该题内存空间限制一致。
7
7
7. 在终端中执行命令
ulimit -s unlimited
\text{ulimit\ -s\ unlimited}
ulimit -s unlimited 可将当前终端下的栈空间限制放大，但你使用的栈空间大小不应超过题目限制。
8
8
8. 每道题目所提交的代码文件大小限制为
100KB
\text{100KB}
100KB。
9
9
9. 若无特殊说明，输入文件与输出文件中同一行的相邻整数均使用一个空格分隔。
10
10
10. 输入文件中可能存在行末空格，请选手使用更完善的读入方式（例如
scanf
\text{scanf}
scanf 函数）避免出错。
11
11
11. 直接复制
PDF
\text{PDF}
PDF 题面中的多行样例，数据将带有行号，建议选手直接使用对应目录下的样例文件进行测试。
12
12
12. 使用
std:deque
\text{std:deque}
std:deque 等
STL
\text{STL}
STL 容器时，请注意其内存空间消耗。
13
13
13. 请务必使用题面中规定的的编译参数，保证你的程序在本机能够通过编译。此外不允许在程序中手动开启其他编译选项，一经发现， 本题成绩以
0
0
0 分处理。
考虑一个 n ∗ n n*n n∗n 的矩阵 A A A，初始所有元素均为 0 0 0。
执行 q q q 次如下形式的操作：给定 4 4 4 个整数 r , c , l , s r,c,l,s r,c,l,s ，对于每个满足 x ∈ [ r , r + l ) , x \in[r,r+l), x∈[r,r+l), $ y\in[c,x-r+c]$ 的元素 ( x , y ) (x,y) (x,y) ，将权值增加 s s s 。也就是，给一个左上顶点为 ( r , c ) (r,c) (r,c) 、直角边长为 l l l 的下三角区域加上 s s s。
输出最终矩阵的元素异或和。
第一行两个整数 n , q n,q n,q。
接下来 q q q 行，每行四个整数 r , c , l , s r,c,l,s r,c,l,s，代表一次操作。
输出一行，一个整数，代表答案。
10 4
1 1 10 1
5 5 4 4
1 9 4 3
3 3 5 2
0
1 0 0 0 0 0 0 0 3 0
1 1 0 0 0 0 0 0 3 3
1 1 3 0 0 0 0 0 3 3
1 1 3 3 0 0 0 0 3 3
1 1 3 3 7 0 0 0 0 0
1 1 3 3 7 7 0 0 0 0
1 1 3 3 7 7 7 0 0 0
1 1 1 1 5 5 5 5 0 0
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
见下发文件中。
保证 n ∈ [ 1 , 1 0 3 ] ， q ∈ [ 0 , 3 ∗ 1 0 5 ] ， r , c , l ∈ [ 1 , n ] , s ∈ [ 1 , 1 0 9 ] 。 n\in[1,10^3]，q\in[0,3*10^5]，r,c,l\in[1,n],s\in[1,10^9]。 n∈[1,103]，q∈[0,3∗105]，r,c,l∈[1,n],s∈[1,109]。
| 子任务编号 | n ≤ n\le n≤ | q ≤ q\le q≤ | 其他限制 | 分值 |
|---|---|---|---|---|
| 1 1 1 | 1 0 3 10^3 103 | 0 0 0 | 无 | 5 5 5 |
| 2 2 2 | 3 ∗ 1 0 2 3*10^2 3∗102 | 4 ∗ 1 0 2 4*10^2 4∗102 | 无 | 20 20 20 |
| 3 3 3 | 1 0 3 10^3 103 | 2 ∗ 1 0 3 2*10^3 2∗103 | 无 | 25 25 25 |
| 4 4 4 | 1 0 3 10^3 103 | 3 ∗ 1 0 5 3*10^5 3∗105 | 保证 r + l = n + 1 且 c = 1 保证r+l=n+1且c=1 保证r+l=n+1且c=1 | 15 15 15 |
| 5 5 5 | 1 0 3 10^3 103 | 3 ∗ 1 0 5 3*10^5 3∗105 | 保证 r + l = n + 1 保证r+l=n+1 保证r+l=n+1 | 15 15 15 |
| 6 6 6 | 1 0 3 10^3 103 | 3 ∗ 1 0 5 3*10^5 3∗105 | 无 | 20 20 20 |
Alice \text{Alice} Alice 和 Bob \text{Bob} Bob 又在一起在玩游戏，这次游戏的规则是：
1
1
1.
Alice
\text{Alice}
Alice 先手，
Bob
\text{Bob}
Bob 后手，轮流进行操作，共有
m
m
m 轮操作，有一个集合初始为
S
=
{
a
1
,
a
2
,
.
.
.
,
a
n
}
S=\{a_1,a_2,...,a_n\}
S={a1,a2,...,an}。
2
2
2. 第
i
i
i 轮操作有一个参数
b
i
b_i
bi，当前轮的操作者有以下两个选择：保留
S
S
S 中所有是
b
i
b_i
bi 倍数的数字，或者保留
S
S
S 中所有不是
b
i
b_i
bi 倍数的数字。
3
3
3. 进行了
m
m
m 轮操作后两人获得的权值是
S
S
S 中的数字之和，
S
S
S 可以为空。
Alice \text{Alice} Alice 希望权值最小， Bob \text{Bob} Bob 希望权值最大，假设他们都足够聪明，那么游戏最终的权值是多少。
第一行两个整数 n , m n,m n,m，表示集合大小和操作轮数。
第二行 n n n 个整数 a i a_i ai，表示初始集合。
第三行 m m m 个整数 b i b_i bi，为第 i i i 轮的参数。
输出一个数表示博弈的结果。
10 3
13 -6 -9 -8 11 5 -4 -9 -4 -7
2 3 3
-6
见选手目录下的下发文件中。
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 2 × 1 0 4 , 1 ≤ m ≤ 2 × 1 0 5 , − 4 × 1 0 14 ≤ a i ≤ 4 × 1 0 14 , 1≤n≤2×10^4, 1≤m≤2×10^5, -4×10^{14}≤a_i≤4×10 ^{14}, 1≤n≤2×104,1≤m≤2×105,−4×1014≤ai≤4×1014, 1 ≤ b i ≤ 4 × 1 0 14 1≤b_i≤4×10^{14} 1≤bi≤4×1014。
| 子任务编号 | m ≤ m\le m≤ | 特殊性质 | 分值 |
|---|---|---|---|
| 1 1 1 | 1 1 1 | 10 10 10 | |
| 2 2 2 | 2 × 1 0 5 2\times 10^5 2×105 |
∀
i
<
m
,
b
i
=
b
i
+
1
\forall i | 10 10 10 |
| 3 3 3 | 2 × 1 0 5 2\times 10^5 2×105 |
∀
i
<
m
,
b
i
+
1
m
o
d
b
i
=
0
\forall i | 15 15 15 |
| 4 4 4 | 7 7 7 | 10 10 10 | |
| 5 5 5 | 20 20 20 | 15 15 15 | |
| 6 6 6 | 100 100 100 | 15 15 15 | |
| 7 7 7 | 2 × 1 0 5 2\times 10^5 2×105 | m m o d 2 = 0 , ∀ i ≤ m 2 , b 2 i − 1 = b 2 i m\ mod\ 2=0,\forall i\le \frac{m}{2},b_{2i-1}=b_{2i} m mod 2=0,∀i≤2m,b2i−1=b2i | 15 15 15 |
| 8 8 8 | 2 × 1 0 5 2\times 10^5 2×105 | 10 10 10 |
小 X \text{X} X 有一张 n n n 个节点的图，每个节点有一个点权。但让 小 X \text{X} X 感到生气的是，这张图上并没有任何的边，于是他决定钦点一些边。
小 X \text{X} X 喜欢 g c d gcd gcd 和合数，所以 小 X \text{X} X 的钦点规则与 g c d gcd gcd（最大公约数）和合数有关。具体来说，对于 2 2 2 个点，如果它们点权的 g c d gcd gcd 为合数，那么 小 X \text{X} X 就会钦点它们之间连一条边。
小 Y \text{Y} Y 看到了 小 X \text{X} X 稚的行为，决定把他批判一番。他知道 小 X \text{X} X 热衷于连通块，因此他会删掉图中的一个点来使得剩余图中最大的连通块最小。
即将参加 NOIP2023 \text{NOIP2023} NOIP2023 的你对这个问题很感兴趣，于是你想知道，在 小 Y \text{Y} Y 操作之后，图中剩余的最大连通块的大小是多少。
本题有多组数据。
第一行一个整数 T T T 表示数据组数。接下来依次描述各组数据，对于每组数据：
第一行 1 1 1 个正整数 n n n，表示节点的个数。
第二行 n n n 个用空格隔开的正整数，依次描述了 1 1 1 号节点到 n n n 号节点的点权 a 1 . . . a n a_1 . . . a_n a1...an。
对于每组数据，输出一行一个整数，表示答案。
3
5
8 4 12 18 9
5
36 20 84 45 231
7
100 200 300 400 500 600 700
2
3
6
见下发文件中。
对于 16 % 16\% 16% 的数据，保证 n ≤ 300 n \le 300 n≤300，其中 8 % 8\% 8% 的数据保证 a i ≤ 2 , 000 a_i \le 2, 000 ai≤2,000；
对于 40 % 40\% 40% 的数据，保证 n ≤ 5 , 000 n \le 5, 000 n≤5,000，其中 20 % 20\% 20% 的数据保证 a i ≤ 30 , 000 a_i \le 30, 000 ai≤30,000；
对于 100 % 100\% 100% 的数据，保证 n ≤ 1 0 5 ， a i ≤ 1 0 7 n \le 10^5，a_i \le 10^7 n≤105，ai≤107，其中 52 % 52\% 52% 的数据保证 a i ≤ 1 0 5 a_i \le 10^5 ai≤105；
对于 100 % 100\% 100% 的数据，保证 T ≤ 10 ， n ≥ 2 ， a i ≥ 2 T \le 10，n \ge 2，a_i \ge 2 T≤10，n≥2，ai≥2。
A 城是一座新兴城市，城里开设了 n n n 座工厂，分属 k k k 家单位（有的单位可能没有工厂），其中第 i i i 座工厂属于第 c i c_i ci 家单位。
目前，A城的城内有 n − 1 n-1 n−1 条道路，每条道路的两端是不同的工厂。如果将工厂视作图的点，道路视作图的边，那么这张图是树。
现在A城决定开通该城的前两条公交线路。目前已经决定了：
∙ \bullet ∙ 每条公交线路将连接两座不同的工厂，且两座工厂属于同一单位。
∙ \bullet ∙ 每条公交线路在现有道路上行驶，且往返的路线是一致的。
∙ \bullet ∙ 一条公交线路不会重复经过同一座工厂，两条线路也不会经过同一座工厂。
我们认为：仅仅将某条公交线路的上行、下行方向互换，得到的是本质相同的线路；将两条公交线路互换，得到的也是本质相同的一组方案。
在公交线路的运行过程中，有可能某座工厂由于临时施工，不适合作为公交线路的首末站。不过两座工厂不会同时临时施工。
现在，A城学生算法竞赛协会悬赏 100 100 100 分，请你对于平时和 m m m 次工厂临时施工的情况，分别求出开通公交线路的方案数。
第一行三个正整数 n , m , k n, m, k n,m,k。
第二行 n n n 个数 c i c_i ci 表示工厂所属的单位。
接下来 n − 1 n - 1 n−1 行每行两个数 a i , b i a_i, b_i ai,bi, 表示有一条道路连接第 a i , b i a_i, b_i ai,bi 座工厂。
接下来 m m m 行每行一个数 k i k_i ki，表示第 i i i 次是第 q i q_i qi 座工厂临时施工。
第一行表示平时情况的方案数。
接下来 m m m 行分别表示各次询问情况下的方案数。
6 6 2
2 1 2 1 2 2
1 2
1 3
2 4
2 5
2 6
1
2
3
4
5
6
2
0
1
0
1
1
1
见下发文件中。
对于所有数据， m ≤ n ≤ 1 0 5 , c i ≤ k ≤ n m ≤ n ≤ 10^5, c_i ≤ k ≤ n m≤n≤105,ci≤k≤n。
| 测试点编号 | n ≤ n\le n≤ | 数据性质 |
|---|---|---|
| 1 , 2 1,2 1,2 | 50 50 50 | 无 |
| 3 3 3 | 1 0 3 10^3 103 | k = 1 k=1 k=1 |
| 4 4 4 | 1 0 4 10^4 104 | k = 1 k=1 k=1 |
| 5 5 5 | 1 0 4 10^4 104 | k = 1 , m ≤ 10 k=1,m\le 10 k=1,m≤10 |
| 6 6 6 | 1 0 3 10^3 103 | m = 1 m=1 m=1 |
| 7 , 8 7,8 7,8 | 1 0 4 10^4 104 | m = 1 m=1 m=1 |
| 9 , 10 9,10 9,10 | 1 0 4 10^4 104 | k = 2 , m ≤ 10 k=2,m\le 10 k=2,m≤10 |
| 11 , 12 11,12 11,12 | 1 0 5 10^5 105 | k = 2 k=2 k=2 |
| 13 , 14 13,14 13,14 | 1 0 4 10^4 104 | c q i c_{q_i} cqi 互不相同 |
| 15 , 16 15,16 15,16 | 1 0 5 10^5 105 | c q i c_{q_i} cqi 互不相同 |
| 17 , 18 , 19 , 20 17,18,19,20 17,18,19,20 | 1 0 5 10^5 105 | 无 |