传送门

题目
更好的阅读体验

题目大意

读入一个字符串， 匹配括号字符串所表示的树，求根节点到所有叶节点的距离之和。

分析题目

• 括号字符串中，每一个叶节点都是对应一个 ()；
• 字符串中的深度比实际深度大 $1$，需要减去 $1$ 再进行计算；
• 扫描字符串，遇到 ( 深度 $+1$，否则深度 $-1$；
• 当遇到 () 时，当前的深度 $-1$ 就是根节点到此处的距离；
• 时间复杂度为 $O(n)$ 可以通过此题。

算法步骤

1. 扫描字符串，记为 $s_i$；
2. 对 $s_i$ 作判断，( 和 ) 需要分情况讨论；
3. 如果遇到 (，深度 $+1$，并且，如果下一个字符是 ) 说明找到了叶节点，将 深度-1 记录到答案，需要注意下个字符是否为合法边界；
4. 如果遇到 )，深度 $-1$；
5. 输出答案。

代码

#include <bits/stdc++.h>  
#define int long long // 将所有的 int 替换成 long long，否则会爆 int  
using namespace std;  
string s;  
int ans,depth,i;  
signed main(){ // 因为 int 会被替换成 long long，但是返回值不允许 long long，所以使用 signed  
    cin>>s; // 对应步骤 1  
    for(i=0;i<s.length();i++) // 对应步骤 2  
        if(s[i]==\'(\'){ // 对应步骤 3 及下面两行  
            depth++;  
            if(i+1<s.length()&&s[i+1]==\')\') ans+=depth-1; // 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算  注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算 
        }else depth--; // 对应步骤 4  
    cout<<ans; // 对应步骤 5  
}

abc437

题面

A - 英尺

分值：100 分

题目描述

1 英尺等于 12 英寸。
请问 A 英尺 B 英寸换算成英寸是多少英寸？

约束条件

1. $1 \leq A \leq 8$
2. $0 \leq B \leq 11$
3. 所有输入值均为整数

输入格式

输入通过标准输入按以下格式给出：

A B

输出格式

将答案输出在一行中。省略单位（英寸）进行输出。

输入样例 1

6 7

输出样例 1

79

6 英尺 7 英寸换算成英寸为 $6 \times 12 + 7 = 79$ 英寸。

输入样例 2

4 11

输出样例 2

59

4 英尺 11 英寸换算成英寸为 $4 \times 12 + 11 = 59$ 英寸。

输入样例 3

8 0

输出样例 3

96

8 英尺 0 英寸换算成英寸为 $8 \times 12 + 0 = 96$ 英寸。

B - 幸运抽奖

题目描述

有一个 $H$ 行 $W$ 列的网格。每个格子中写着一个整数，所有整数互不相同。从上到下第 $i$ 行、从左到右第 $j$ 列的格子中写有整数 $A_{i,j}$。

现在，主持人喊出了 $N$ 个互不相同的整数 $B_1, \dots, B_N$。

对于每一行，计算出主持人喊出的整数中，有多少个出现在该行中。这些数量的最大值是多少？

约束条件

$1 \leq H \leq 3$
$1 \leq W \leq 5$
$1 \leq N \leq 90$
$1 \leq A_{i,j} \leq 90$
$A_{i,j}$ 互不相同
$1 \leq B_i \leq 90$
$B_i$ 互不相同
所有输入值均为整数

输入格式

输入通过标准输入给出，格式如下：

H W N
A_{1,1} ... A_{1,W}
...
A_{H,1} ... A_{H,W}
B_1
...
B_N

输出格式

输出一行，包含答案。

输入样例 1

3 4 5
12 3 5 7
6 10 11 9
1 2 4 8
2
4
9
6
11

输出样例 1

3

输入样例 2

3 5 2
81 63 31 16 15
30 3 6 54 24
26 41 48 64 66
44
79

输出样例 2

0

输入样例 3

3 5 12
78 19 70 58 83
12 30 80 20 27
48 71 8 43 82
82
30
43
8
80
70
20
78
12
71
19
48

输出样例 3

5

C - 驯鹿与雪橇 2

题目描述

有 $N$ 头驯鹿和 1 架雪橇。第 $i$ 头驯鹿的体重为 $W_i$，力量为 $P_i$。

对于每头驯鹿，需要选择是让它“拉雪橇”还是“乘坐雪橇”。
但是，拉雪橇的驯鹿的力量总和必须大于等于乘坐雪橇的驯鹿的体重总和。
最多可以让多少头驯鹿乘坐雪橇？

给定 $T$ 个测试用例。请分别回答每个用例。

约束条件

$1 \leq T \leq 10^5$
$1 \leq N \leq 3 \times 10^5$
$1 \leq W_i, P_i \leq 10^9$
所有输入值均为整数。
单个输入文件中所有 $N$ 的总和不超过 $3 \times 10^5$。

输入格式

输入通过标准输入给出，格式如下：

T
case_1
case_2
⋮
case_T

每个测试用例的格式如下：

N
W_1 P_1
W_2 P_2
⋮
W_N P_N

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。

输入样例 1

3
3
3 1
4 1
5 9
5
1000000000 1
1000000000 1
1000000000 1
1000000000 1
1000000000 1
10
133180711 458704923
531424946 225863856
141986070 637075158
500770732 289806469
502866767 408857335
559714289 569084545
287444582 992432993
559747907 753133304
432846188 949871298
727072164 756020367

输出样例 1

2
0
6

D - 差之和

题目描述

给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$ 和一个长度为 $M$ 的正整数序列 $B = (B_1, B_2, \dots, B_M)$。

求 $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j|$ 的值，并对 $998244353$ 取模。

约束条件

$1 \leq N, M \leq 3 \times 10^5$
$1 \leq A_i, B_j < 998244353$
所有输入值均为整数。

输入格式

输入通过标准输入给出，格式如下：

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_M

输出格式

输出一行，包含答案。

输入样例 1

4 2
1 6 9 2
3 1

输出样例 1

26

输入样例 2

8 8
185991676 311812083 311812083 84357963 185991676 185991676 724020528 369175631
455049197 387671868 4361724 724020528 724020528 455049197 455049197 724020528

输出样例 2

529117255

E - 对数组排序

题目描述

有 $N+1$ 个序列 $A_0, A_1, \dots, A_N$。$A_i$ 定义如下：
. $A_0$ 是一个空序列。
. $A_i$ $(1 \le i \le N)$ 是在序列 $A_{x_i}$ $(0 \le x_i < i)$ 的末尾添加整数 $y_i$ 后得到的序列。

找出满足以下条件的排列 $P = (P_1, P_2, \dots, P_N)$（即 $(1, 2, \dots, N)$ 的一个排列）：
. 对于 $i = 1, 2, \dots, N-1$，满足以下条件之一：
. $A_{P_i}$ 在字典序上小于 $A_{P_{i+1}}$。
. $A_{P_i} = A_{P_{i+1}}$ 且 $P_i < P_{i+1}$。
换句话说，当将 $A_1, A_2, \dots, A_N$ 按字典序排列（当有多个相同的序列时，索引较小的在前）时，$P$ 就是该排列中出现的索引序列。

约束条件

$1 \leq N \leq 3 \times 10^5$
$0 \leq x_i < i$
$1 \leq y_i \leq 10^9$
所有输入值均为整数。

输入格式

输入通过标准输入给出，格式如下：

N
x_1 y_1
x_2 y_2
⋮
x_N y_N

输出格式

在一行中输出 $P_1, P_2, \dots, P_N$，用空格分隔。

输入样例 1

4
0 2
0 1
2 2
0 1

输出样例 1

2 4 3 1

解释：
$A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1)$，所以 $P = (2, 4, 3, 1)$。

输入样例 2

5
0 1
0 1
0 1
0 1
0 1

输出样例 2

1 2 3 4 5

输入样例 3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

输出样例 3

3 8 10 5 9 6 7 1 4 2

F - 曼哈顿圣诞树 2

题目描述

在二维平面上有 $N$ 棵圣诞树。第 $i$ 棵（$1 \leq i \leq N$）圣诞树位于坐标 $(X_i, Y_i)$。

给你 $Q$ 个查询。请按顺序处理这些查询。每个查询是以下两种类型之一：

类型 1：以 1 i x y 的形式给出。将第 $i$ 棵圣诞树的坐标改为 $(x, y)$。
类型 2：以 2 L R x y 的形式给出。输出从坐标 $(x, y)$ 到第 $L, L+1, \dots, R$ 棵圣诞树中最远的圣诞树的曼哈顿距离。

这里，坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。

约束条件

$1 \leq N, Q \leq 2 \times 10^5$
$-10^9 \leq X_i, Y_i \leq 10^9$
$1 \leq i \leq N$
$1 \leq L \leq R \leq N$
$-10^9 \leq x, y \leq 10^9$
所有输入值均为整数。

输入格式

输入通过标准输入给出，格式如下：

N Q
X_1 Y_1
X_2 Y_2
⋮
X_N Y_N
query_1
query_2
⋮
query_Q

其中，第 $i$ 个查询 query_i 以下列两种格式之一给出：

1 i x y
2 L R x y

输出格式

根据问题描述中的说明，输出查询的答案，每个答案占一行。

输入样例 1

3 4
-1 -1
1 2
-2 1
2 1 2 0 0
2 1 3 -1 2
1 1 0 1
2 1 3 -1 2

输出样例 1

3
3
2

解释：
最初，第 1、2、3 棵圣诞树分别位于坐标 $(-1, -1)$、$(1, 2)$、$(-2, 1)$。
处理每个查询：

1. 从第 1、2 棵圣诞树到坐标 $(0, 0)$ 的曼哈顿距离分别为 $2$ 和 $3$。因此输出 $3$，即 $2, 3$ 中的最大值。
2. 从第 1、2、3 棵圣诞树到坐标 $(-1, 2)$ 的曼哈顿距离分别为 $3$、$2$、$2$。因此输出 $3$，即 $3, 2, 2$ 中的最大值。
3. 将第 1 棵圣诞树的坐标改为 $(0, 1)$。第 1、2、3 棵圣诞树的坐标变为 $(0, 1)$、$(1, 2)$、$(-2, 1)$。
4. 从第 1、2、3 棵圣诞树到坐标 $(-1, 2)$ 的曼哈顿距离分别为 $2$、$2$、$2$。因此输出 $2$，即 $2, 2, 2$ 中的最大值。

输入样例 2

5 7
-9 5
-2 -9
10 -6
9 8
2 9
1 3 -9 -6
2 3 4 2 7
1 4 -2 -10
2 1 2 0 -10
2 3 4 10 -9
2 3 4 8 7
2 5 5 0 2

输出样例 2

24
24
22
30
9

G - 彩色圣诞树

题目描述

今年的圣诞节季节已经结束，终于到了新年的时刻。高桥正在忙着进行大扫除，要收起圣诞树。

有一棵用三种颜色（红色、蓝色、绿色）装饰的灯泡装饰的圣诞树。圣诞树上有 $N$ 个灯泡，它们由 $N-1$ 条丝带连接。将灯泡视为顶点，丝带视为边，这个图是一棵树。

灯泡编号从 $1$ 到 $N$，丝带编号从 $1$ 到 $N-1$。丝带 $i$ 连接灯泡 $u_i$ 和 $v_i$。灯泡 $i$ 初始亮着红色（如果 $c_i$ 是 R），绿色（如果 $c_i$ 是 G），或蓝色（如果 $c_i$ 是 B）。

高桥正在考虑执行以下操作 $N-1$ 次来移除所有丝带：

1. 从尚未移除的丝带中选择一条，其两端的灯泡颜色不同，然后移除该丝带。

2. 设 $u$ 和 $v$ 是被移除丝带两端的灯泡。对于每个灯泡 $u$ 和 $v$，根据以下规则改变它们亮的颜色：

   • 如果之前亮红色，则改为亮绿色。
   • 如果之前亮绿色，则改为亮蓝色。
   • 如果之前亮蓝色，则改为亮红色。

确定高桥是否可以通过重复此操作来移除所有丝带。如果可能，输出一种方法。

给定 $T$ 个测试用例。请解决每个测试用例。

约束条件

$1 \leq T \leq 20000$
$2 \leq N \leq 2000$
$c_i$ 是 R、G 或 B。
$1 \leq u_i, v_i \leq N$
将灯泡视为顶点，丝带视为边，给定的图是一棵树。
$T, N, u_i, v_i$ 是整数。
单个输入文件中所有 $N^2$ 的总和不超过 $2000^2$。

输入格式

输入通过标准输入给出，格式如下：

T
case_1
case_2
⋮
case_T

每个测试用例的格式如下：

N
c_1 c_2 ... c_N
u_1 v_1
u_2 v_2
⋮
u_{N-1} v_{N-1}

输出格式

按顺序输出 case_1, case_2, ..., case_T 的答案，格式如下：

如果无法移除所有丝带，输出 No。

如果可能，设 $e_i$ 为第 $i$ 次操作移除的丝带编号，输出：

Yes
e_1 e_2 ... e_{N-1}

其中 $(e_1, e_2, \dots, e_{N-1})$ 必须是 $(1, 2, \dots, N-1)$ 的一个排列。

如果有多个解，任意一个都将被视为正确。

输入样例 1

3
4
GBBR
1 2
1 3
1 4
3
RRR
1 2
2 3
5
RGBRG
1 2
2 3
3 4
3 5

输出样例 1

Yes
1 3 2
No
Yes
1 4 2 3

解释：
对于第一个测试用例，例如，可以通过以下操作移除所有丝带：

1. 初始时，灯泡颜色依次（从灯泡 1 开始）为绿色、蓝色、蓝色、红色。
2. 移除丝带 1。移除后，灯泡颜色依次为蓝色、红色、蓝色、红色。
3. 移除丝带 3。移除后，灯泡颜色依次为红色、红色、蓝色、绿色。
4. 移除丝带 2。移除后，灯泡颜色依次为绿色、红色、红色、绿色。
   满足条件的 $(e_1, e_2, e_3)$ 是 $(1, 3, 2)$ 和 $(2, 3, 1)$，任意一个都将被视为正确。

对于第二个测试用例，无论你如何操作，都无法移除所有丝带。

反思

A

本题是一道签到题
根据题意可知：

$$ \text{总英寸数} = A \times 12 + B $$

由于题目的数据范围过小，可直接使用顺序结构求解
以下是我赛场时的代码

#include <bits/stdc++.h>
using namespace std;
int a,b;
int main(){
    cin>>a>>b;
    cout<<a*12+b;
}

B

题目的意思就是：题目要求计算每一行中主持人喊出的整数出现的个数，并输出这些个数的最大值
由于数据范围过小，可直接使用数组存储，不需要使用任何数据优化方案
思路：

1. 读入 $H,W,N$
2. 用二维数组 $A$ 存储矩阵
3. 用一个大小为 $91$ （∵ $1 \leq B_i \leq 90$）的布尔数组 isB 标记 $B$ 中的数
4. 对每一行遍历，统计这一行中有多少个数在 isB 中被标记为 true
5. 记录这些统计数的最大值并输出
   以下是我赛时的代码：

#include <bits/stdc++.h>
using namespace std;
int H,W,N,i,j,b,cnt,ma,a[5][6],fl[91];
int main(){
    cin>>H>>W>>N;
    for(i=0;i<H;i++) for(j=0;j<W;j++) cin>>a[i][j];
    for(i=0;i<N;i++){
        cin>>b;fl[b]=1;
    }
    for(i=0;i<H;i++){
        cnt=0;
        for(j=0;j<W;j++) if(fl[a[i][j]]) cnt++;
        if(cnt>ma) ma=cnt;
    }
    cout<<ma;
}

根据题目思路就可以得出代码，非常 Easy

C

这题我在赛时并没有得出正确程序
赛后，我邀请 deepseek 完成此题，我将对 deepseek 的内容进行阐述

算法：贪心
题目阐述：有 (N) 头驯鹿，每头驯鹿有体重 (W_i) 和力量 (P_i)。选择一部分驯鹿“乘坐雪橇”，剩下的“拉雪橇”。要求“拉雪橇”的驯鹿的力量总和 ≥ “乘坐雪橇”的驯鹿的体重总和。问最多可以让多少头驯鹿乘坐雪橇
问题转化为：在不超过总力量 (S) 的前提下，最多能选择多少头驯鹿，使得它们的 (W_i + P_i) 之和不超过 (S)。这是一个典型的贪心问题：按 (W_i + P_i) 从小到大选择，直到总和超过 (S)
对每个测试用例：

1. 读入 (N) 和每头驯鹿的 (W_i, P_i)
2. 计算总力量 (S = \sum P_i)
3. 计算每头驯鹿的 (a_i = W_i + P_i)，并排序
4. 从小到大累加 (a_i)，直到总和超过 (S)，累加的个数即为答案
   时间复杂度：$O(N \operatorname{log} N)$

这是 deepseek 给出的代码：

#include<iostream>
#include<algorithm>
using namespace std;
int T,N,i,cnt;
long long totalP,sum,W,P;
long long a[100005];

int main(){
    cin>>T;
    while(T--){
        cin>>N;
        totalP=0;
        for(i=0;i<N;i++){
            cin>>W>>P;
            a[i]=W+P;
            totalP+=P;
        }
        sort(a,a+N);
        sum=0;
        cnt=0;
        for(i=0;i<N;i++){
            if(sum+a[i]<=totalP){
                sum+=a[i];
                cnt++;
            }else{
                break;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

abc436 反思

题面

A - o 判定

问题描述

给定一个整数 $ N $ 和一个由小写英文字母组成的字符串 $ S $，其长度小于 $ N $。

请输出通过持续在字符串 $ S $ 的开头添加小写英文字母 o 直到其长度变为 $ N $ 所得到的字符串。

约束条件

• $ 2 \leq N \leq 100 $
• $ N $ 为整数
• $ S $ 是由小写英文字母组成的字符串，长度介于 $ 1 $ 到 $ N-1 $ 之间（包含边界）。

输入格式

输入通过标准输入以如下格式给出：

$$ N $$

$$ S $$

输出格式

输出答案字符串。

样例输入 1

5
abc

样例输出 1

ooabc

解释：$ N=5 $，$ S $ 的长度为 $ 3 $，因此需要在 $ S $ 的开头添加 $ 5 - 3 = 2 $ 个 o。

样例输入 2

2
o

样例输出 2

oo

样例输入 3

12
vgxgpuam

样例输出 3

oooovgxgpuam

B - 幻方阵

问题描述

给定一个大于等于 $ 3 $ 的奇数 $ N $。

有一个 $ N $ 行 $ N $ 列的方格，初始时所有格子均为空白。现在，按照以下步骤在方格中的每个格子上写入整数。
记格子 $ (i, j) $ 表示从上到下第 $ i+1 $ 行、从左到右第 $ j+1 $ 列的格子（$ 0 \leq i < N, 0 \leq j < N $）。

1. 在格子 $ \left(0, \frac{N-1}{2}\right) $ 中写入 $ 1 $。

2. 重复以下操作 $ N^2 - 1 $ 次：

   • 设上一次写入整数的格子为 $ (r, c) $，写入的整数为 $ k $。如果格子 $ ((r-1) \bmod N, (c+1) \bmod N) $ 是空白的，则在该格子写入 $ k+1 $；否则，在格子 $ ((r+1) \bmod N, c) $ 中写入 $ k+1 $。
   • 这里，$ x \bmod N $ 表示 $ x $ 除以 $ N $ 的余数。

请找出按照此过程在每个格子中写入的整数。
可以证明，每个格子恰好会被写入一个整数。

约束条件

• $ 3 \leq N \leq 99 $
• $N$ 是奇数

输入格式

输入通过标准输入以如下格式给出：

$$ N $$

输出格式

设格子 $ (i, j) $ 中写入的整数为 $ a_{i, j} $，并按如下格式输出：

$$ a_{0, 0} \ a_{0, 1} \ \dots \ a_{0, N-1} \\ \vdots \\ a_{N-1, 0} \ a_{N-1, 1} \ \dots \ a_{N-1, N-1} $$

样例输入 1

3

样例输出 1

8 1 6
3 5 7
4 9 2

解释：

1. 在格子 $ (0, \frac{3-1}{2}) = (0, 1) $ 中写入 $ 1 $。
2. 格子 $ ((0-1) \bmod 3, (1+1) \bmod 3) = (2, 2) $ 是空白的，因此写入 $ 2 $。
3. 格子 $ ((2-1) \bmod 3, (2+1) \bmod 3) = (1, 0) $ 是空白的，因此写入 $ 3 $。
4. 格子 $ ((1-1) \bmod 3, (0+1) \bmod 3) = (0, 1) $ 非空白，因此在格子 $ ((1+1) \bmod 3, 0) = (2, 0) $ 中写入 $ 4 $。
5. 依此类推……

样例输入 2

5

样例输出 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

C - 放置 2×2 方块

问题描述

有一个 $ N $ 行 $ N $ 列的方格。记格子 $ (i, j) $ 表示从上到下第 $ i $ 行、从左到右第 $ j $ 列的格子。初始时，方格上没有任何方块。

现在将进行 $ M $ 次操作。第 $ i $ 次操作（$ 1 \leq i \leq M $）如下：

• 将以格子 $ (R_i, C_i) $ 为左上角的 $ 2 \times 2 $ 区域的方块放置到方格上，当且仅当该区域与已放置的其他方块不重叠。
  更精确地说，对于单元格集合 $ S = \{ (R_i, C_i), (R_i+1, C_i), (R_i, C_i+1), (R_i+1, C_i+1) \} $，如果方格上已存在的方块占据了 $ S $ 中的任意一个格子，则什么也不做；否则，放置一个占据 $ S $ 中全部 4 个格子的方块。

请计算所有操作结束后，方格上共有多少个方块。

约束条件

• $ 2 \leq N \leq 10^9 $
• $ 1 \leq M \leq 2 \times 10^5 $
• $ 1 \leq R_i, C_i \leq N-1 $
• 输入均为整数

输入格式

输入通过标准输入按以下格式给出：

$$ N \ M $$

$$ R_1 \ C_1 $$

$$ R_2 \ C_2 $$

$$ \vdots $$

$$ R_M \ C_M $$

输出格式

输出答案。

样例输入 1

4 3
1 1
2 2
2 3

样例输出 1

2

解释：
下图展示了操作过程，黑色填充区域表示方块，红色边框区域表示下一个要放置方块的位置。

1. 操作 1：以格子 $ (1, 1) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。
2. 操作 2：以格子 $ (2, 2) $ 为左上角的 $ 2 \times 2 $ 区域中，格子 $ (2, 2) $ 已被占据，因此什么也不做。
3. 操作 3：以格子 $ (2, 3) $ 为左上角的 $ 2 \times 2 $ 区域为空，因此放置方块。

因此，所有操作结束后，方格上有 2 个方块。

样例输入 2

1000000000 4
1 1
1 101
101 1
101 101

样例输出 2

4

所有操作都可以放置方块。

样例输入 3

8 10
6 5
7 3
6 7
3 4
4 2
3 7
1 3
7 4
6 1
6 1

样例输出 3

8

可能存在满足 $ (R_i, C_i) = (R_j, C_j) $ 的 $ i, j $（$ i \neq j $）。

D - 传送迷宫

问题描述

有一个迷宫，由 $ H $ 行 $ W $ 列的网格构成。记格子 $ (i, j) $ 表示从上到下第 $ i $ 行、从左到右第 $ j $ 列的格子。格子 $ (i, j) $ 的类型由字符 $ S_{i, j} $ 给出，每个字符的含义如下：

• .：空单元格
• #：障碍单元格
• 小写英文字母（a - z）：传送单元格

在迷宫中，你可以按任意顺序执行以下两种类型的操作任意多次：

1. 步行：从当前单元格移动到上下左右四个方向相邻的单元格。但是，不能移动到障碍单元格或网格外。
2. 传送：当你处于一个传送单元格时，可以移动到写有相同字母的任意传送单元格。

判断是否可以从单元格 $ (1, 1) $ 移动到单元格 $ (H, W) $，如果可能，求出所需的最小总操作次数。

约束条件

• $ 1 \leq H, W \leq 1000 $
• $ H \times W \geq 2 $
• $ H $ 和 $ W $ 为整数
• $ S_{i, j} $ 是 .、# 或小写英文字母
• $ S_{1, 1} \neq \# $
• $ S_{H, W} \neq \# $

输入格式

输入通过标准输入按以下格式给出：

$$ H \ W $$

$$ S_{1, 1} \ S_{1, 2} \ \dots \ S_{1, W} $$

$$ \vdots $$

$$ S_{H, 1} \ S_{H, 2} \ \dots \ S_{H, W} $$

输出格式

如果可以从单元格 $ (1, 1) $ 移动到单元格 $ (H, W) $，输出所需的最小总操作次数；否则输出 -1。

样例输入 1

3 4
..a.
####
ba#b

样例输出 1

5

解释：
可以通过以下操作从单元格 $ (1, 1) $ 移动到单元格 $ (3, 4) $：

1. 从 $ (1, 1) $ 步行到 $ (1, 2) $
2. 从 $ (1, 2) $ 步行到 $ (1, 3) $
3. 从 $ (1, 3) $ 传送到 $ (3, 2) $
4. 从 $ (3, 2) $ 步行到 $ (3, 1) $
5. 从 $ (3, 1) $ 传送到 $ (3, 4) $

总操作次数为 $ 5 $，这是最小值。

样例输入 2

3 4
..a.
####
b.#b

样例输出 2

-1

无法从单元格 $ (1, 1) $ 移动到单元格 $ (3, 4) $。

样例输入 3

4 4
xxxx
xxxx
xxxx
xxxx

样例输出 3

1

样例输入 4

7 11
u..#y..#...
k..#.z.#.k.
iju#...#x..
###########
..x#.t.#..n
abc#y..#...
..z#..t#.y.

样例输出 4

12

E - 最小交换次数

问题描述

给定一个整数序列 $ P = (P_1, P_2, \dots, P_N) $，它是 $ (1, 2, \dots, N) $ 的一个排列。这里保证 $ P $ 不等于 $ (1, 2, \dots, N) $。

你想要执行零次或多次以下操作，使 $ P $ 匹配序列 $ (1, 2, \dots, N) $：

• 选择一对整数 $ (i, j) $ 满足 $ 1 \leq i < j \leq N $。交换 $ P_i $ 和 $ P_j $ 的值。

设 $ K $ 为使 $ P $ 匹配序列 $ (1, 2, \dots, N) $ 所需的最少操作次数。

找出可以作为第一次操作的操作数量，使得存在一个操作序列能在 $ K $ 次操作内使 $ P $ 匹配序列 $ (1, 2, \dots, N) $。当且仅当选择的整数对 $ (i, j) $ 不同时，两个操作被视为不同。

约束条件

• $ 2 \leq N \leq 3 \times 10^5 $
• $ 1 \leq P_i \leq N $（$ 1 \leq i \leq N $）
• $ P_i \neq P_j $（$ 1 \leq i < j \leq N $）
• 存在 $ 1 \leq i \leq N $ 使得 $ i \neq P_i $
• 所有输入值均为整数

输入格式

输入通过标准输入按以下格式给出：

$$ N $$

$$ P_1 \ P_2 \ \dots \ P_N $$

输出格式

输出答案。

样例输入 1

5
3 1 4 2 5

样例输出 1

6

例如，可以通过以下三次操作达成目标：

1. 选择 $ (i, j) = (1, 2) $。$ P $ 变为 $ (1, 3, 4, 2, 5) $
2. 选择 $ (i, j) = (2, 4) $。$ P $ 变为 $ (1, 2, 4, 3, 5) $
3. 选择 $ (i, j) = (3, 4) $。$ P $ 变为 $ (1, 2, 3, 4, 5) $

无法在两次或更少操作内达成目标，因此 $ K = 3 $。

如上所述，第一次操作选择 $ (1, 2) $ 可以在三次操作内达成目标。此外，如果第一次操作选择 $ (1, 3) $、$ (1, 4) $、$ (2, 3) $、$ (2, 4) $、$ (3, 4) $ 中的任意一个，那么通过适当执行接下来的两次操作，也可以使 $ P $ 变为 $ (1, 2, 3, 4, 5) $。

因此，输出 6。

样例输入 2

2
2 1

样例输出 2

1

样例输入 3

20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1

样例输出 3

77

F - 星空风景照

问题描述

在从 AtCoder 星球看到的夜空中，有 $ N $ 颗星星，这些星星自东向西排成一条直线。从东数第 $ i $ 颗星星（$ 1 \leq i \leq N $）是这些星星中第 $ B_i $ 亮的。

Takahashi 决定用以下步骤拍摄夜空：

1. 选择一对整数 $ (l, r) $ 满足 $ 1 \leq l \leq r \leq N $，并调整相机，使得从东数第 $ l $ 颗、第 $ (l+1) $ 颗、…、第 $ r $ 颗星星全部进入取景框，且没有其他星星进入取景框。
2. 选择一个整数 $ b $ 满足 $ 1 \leq b \leq N $，并打开快门，使得所有 $ N $ 颗星星中亮度排名在第 1 到第 $ b $ 位（且在取景框内）的星星被拍摄到，其他星星不被拍摄。
   但是，他不能拍摄没有星星被捕捉到的照片。

求用这种方式拍摄的照片中，可以捕捉到的星星的不同集合的数量。

约束条件

• $ 1 \leq N \leq 5 \times 10^5 $
• $ 1 \leq B_i \leq N $（$ 1 \leq i \leq N $）
• $ B_i \neq B_j $（$ 1 \leq i < j \leq N $）
• 所有输入值均为整数

输入格式

输入通过标准输入按以下格式给出：

$$ N $$

$$ B_1 \ B_2 \ \dots \ B_N $$

输出格式

输出答案。

样例输入 1

4
3 1 4 2

样例输出 1

12

例如，当 $ (l, r) = (2, 4) $，$ b = 3 $ 时，你可以拍摄包含两颗星星的照片：从东数第 2 颗星星和第 4 颗星星。

包括这个在内，你可以拍摄以下 12 种不同的星星集合。每张照片中，较东的星星排在较左边，第 $i$ 亮的星星用整数 $i$ 标记。

没有其他集合可以被捕捉，因此输出 12。

样例输入 2

7
1 2 3 4 5 6 7

样例输出 2

28

样例输入 3

20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1

样例输出 3

627

G - 线性不等式

问题描述

给定一个长度为 $ N $ 的正整数序列 $ A = (A_1, A_2, \dots, A_N) $ 和一个正整数 $ M $。

求满足以下条件的非负整数序列 $ x = (x_1, x_2, \dots, x_N) $ 的数量：

$$ \sum_{i=1}^{N} A_i x_i \leq M $$

由于该数量可能非常大，请输出其对 $ 998244353 $ 取模的结果。

约束条件

• $ 1 \leq N \leq 100 $
• $ 1 \leq A_i \leq 100 $（$ 1 \leq i \leq N $）
• $ 1 \leq M \leq 10^{18} $
• 所有输入值均为整数

输入格式

输入通过标准输入按以下格式给出：

$$ N \ M $$

$$ A_1 \ A_2 \ \dots \ A_N $$

输出格式

输出满足条件的非负整数序列的数量（对 $ 998244353 $ 取模）。

样例输入 1

4 6
5 4 3 2

样例输出 1

10

满足条件的序列 $ x $ 有以下 10 个：
$ (0,0,0,0) $, $ (0,0,0,1) $, $ (0,0,0,2) $, $ (0,0,0,3) $, $ (0,0,1,0) $, $ (0,0,1,1) $, $ (0,0,2,0) $, $ (0,1,0,0) $, $ (0,1,0,1) $, $ (1,0,0,0) $。

因此，输出 10。

样例输入 2

6 89
4 7 5 10 7 6

样例输出 2

38469

样例输入 3

1 1000000007
1

样例输出 3

1755655

满足条件的序列 $ x $ 有 $ 1000000008 $ 个。

输出其对 $ 998244353 $ 取模的结果，即 $ 1755655 $。

样例输入 4

20 738894495848985641
40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37

样例输出 4

31156940

反思

A - o 判定

这是一道水题，但我只会做水题
整理一下题意，意思就是说给出 $N$ 和 $S$，输出 $N-S_{size}$ 个 o 用于补全，然后再输出原来的字符串 $S$
时间复杂度：$O(N)$，可以通过！
然后就没什么东西了
可能需要注意一下 for 循环的三个语句，到底在做什么：

令 $k$ 为 $N-S_{size}$
若 $N=5 ,\space S=\text{fuck}$
则 $k=N-S_{size}=5-4=1$
所以应该输出 $1$ 个 o
然后再输出完整的 S

#include <bits/stdc++.h>
using namespace std;
int x,i;
string s;
int main(){
    cin>>x>>s;
    for(i=1;i<=x-s.length();i++) cout<<'o';
    cout<<s;
}

就是这样，so easy

B - 幻方阵

这题需要一定的耐心来阅读题面文本。
这题可以直接根据 题目描述 的题进行暴力编写程序，不需要一些复杂的抽象概念思考建模。
我直接贴代码了，毫无技术含量。

#include <bits/stdc++.h>
using namespace std;
int a[100][100],n,r,c,k,nr,nc,i,j;
int main(){
    cin>>n;c=(n-1)/2;
    for(k=1;k<=n*n;k++){
        a[r][c]=k;
        nr=(r-1+n)%n;
        nc=(c+1)%n;
        if(a[nr][nc]!=0) nr=(r+1)%n,nc=c;
        r=nr;
        c=nc;
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            cout<<a[i][j];
            if(j<n-1) cout<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

[collapse status="false" title="Typora 渲染后的 PDF"]https://www.tropical-fish.cn/usr/uploads/2025/12/4031836290.pdf
[/collapse]

abc435

A - Triangular Number 三角数

题面翻译

时间限制：2 秒 / 内存限制：1024 MiB
分数：100 分

题目描述

给定一个正整数 $N$。
输出从 1 到 $N$ 的所有整数的和，即 $1+2+\dots+N$。

约束条件

• $1 \le N \le 100$
• $N$ 是整数

输入格式

输入从标准输入按以下格式给出：

N

输出格式

输出从 1 到 $N$ 的所有整数的和。

样例输入 1

5

样例输出 1

15

样例解释 1

因为 $1+2+3+4+5=15$，所以输出 15。

样例输入 2

1

样例输出 2

1

样例输入 3

29

样例输出 3

435

思考

很简单，方法在题面中已经给出了，即 $\sum_{i=1}^{n} i$ ，这个算法的时间复杂度是 $O(n)$ 的。
也可以使用高斯求和的方法， $\frac{n(1+n)}{2}$。
我太懒了，使用高斯求和的方法。

代码

#include <bits/stdc++.h>
using namespace std;
int n,x,i,s;
int main(){
    cin>>n;
    for(i=1;i<=n;i++) s+=i;
    cout<<s;
}

B - No-Divisible Range 无因数区间

题目翻译

时间限制：2 秒 / 内存限制：1024 MiB
分数：200 分

题目描述

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。
请找出满足 $1 \le l \le r \le N$ 的整数对 $(l,r)$ 的数量，要求这些整数对满足如下条件：
对于所有满足 $l \le i \le r$ 的整数 $i$，$A_i$ 不是区间 $[l,r]$ 内所有元素的和的约数。

约束条件

• $1 \le N \le 50$
• $1 \le A_i \le 1000$
• 所有输入值均为整数

输入格式

输入数据通过标准输入给出，格式如下：

N
A_1 A_2 … A_N

输出格式

输出满足条件的整数对 $(l,r)$ 的数量。

样例输入 1

5
8 6 10 5 7

样例输出 1

6

样例解释 1

序列 $A=(8,6,10,5,7)$。
例如，整数对 $(l,r)=(1,2)$ 满足条件：区间和为 $A_1+A_2=14$，$A_1=8$ 和 $A_2=6$ 都不是 14 的约数。
而整数对 $(l,r)=(1,3)$ 不满足条件：区间和为 $A_1+A_2+A_3=24$，$A_1=8$ 是 24 的约数。
满足条件的整数对为 $(1,2),(1,4),(2,3),(2,4),(3,5),(4,5)$，共 6 个，因此输出 6。

样例输入 2

3
1 1 1

样例输出 2

0

思考

就不打炮打蚊子了。
直接暴力枚举 $l$ 到 $r$，求和为 $S$ ，公式为 $S=\sum_{i=l}^{r} a_i$，然后判断从 $l$ 到 $r$ 如果能被 $S$ 整除，那这个就不是一个无因数区间，不应该计入到答案，否则就计入到答案，最后输出即可。
警告：暴力枚举 $l$ 到 $r$ 的时候，需要排除 $l > r$ 的状态，即 if(l>r) continue;。
时间复杂度为 $O(n^3)$，题目规定 $N \leq 50$，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
int n,i,a[60],fl,s,t,w,ans;
int main(){
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    for(t=1;t<=n;t++) for(w=1;w<=n;w++){
        if(t>w) continue;
        fl=1;s=0;
        for(i=t;i<=w;i++) s+=a[i];
        for(i=t;i<=w;i++) if(s%a[i]==0) fl=0;
        ans+=fl;
    }
    cout<<ans;
}

C - Domino 多米诺

题面翻译

时间限制：2 秒 / 内存限制：1024 MiB
分数：300 分

题目描述

有 $N$ 张多米诺骨牌排成一行，放置在数轴上。第 $i$ 张骨牌位于坐标 $i$ 处，高度为 $A_i$。
当第 $i$ 张骨牌向右倒下时，坐标在 $i$ 到 $i+A_i-1$（包含两端）范围内的所有骨牌都会向右倒下。
当第一张骨牌向右倒下时，总共会有多少张骨牌倒下？

约束条件

• $1 \le N \le 5 \times 10^5$
• $1 \le A_i \le N$
• 所有输入值均为整数

输入格式

输入数据通过标准输入给出，格式如下：

N
A_1 A_2 … A_N

输出格式

输出当第一张骨牌向右倒下时，倒下的骨牌总数。

样例输入 1

4
3 1 4 1

样例输出 1

4

样例解释 1

当第一张骨牌向右倒下时，第二张和第三张骨牌也会向右倒下。当第三张骨牌向右倒下时，第四张骨牌也会倒下。

样例输入 2

9
1 4 1 4 2 1 3 5 6

样例输出 2

1

样例解释 2

当第一张骨牌向右倒下时，没有其他骨牌会倒下。

样例输入 3

10
5 4 3 2 1 1 2 3 4 5

样例输出 3

5

思考

数据范围 $N \le 5\times10^5$，暴力模拟每张骨牌的连锁倒下会超时，不能用 $O(N^2)$ 的暴力枚举了，必须用 $O(N)$ 贪心策略。
核心是维护当前最远覆盖位置和遍历边界：

1. 第一张骨牌倒下的初始覆盖范围是 $1+A[1]-1$，记为 ma，用 tmp 记录当前需要遍历的右边界；
2. 从第 2 张骨牌开始，在 tmp 范围内遍历，不断更新 ma 为所有骨牌能覆盖的最远位置；
3. 遍历到 tmp 时，将 tmp 更新为新的 ma，扩展遍历范围；
4. 最终答案取 ma 和 $N$ 的较小值，避免覆盖范围超出骨牌总数。

小声：我看到时间限制为 2s 的时候以为不用贪心，就用暴力枚举，结果 TLE 了我操，∵数据范围是指数级的，是 $2.5 \times {10}^{11}$，但实际上计算机每秒大约只能做 $10^9$ 次，∴会超时。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int a[N],n,i,ma,tmp;
int main(){
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    if(n==0) return cout<<0,0;
    ma=1+a[1]-1;
    tmp=ma;
    i=2;
    while(i<=tmp&&i<=n){
        if(i+a[i]-1>ma) ma=i+a[i]-1;
        if(i==tmp) tmp=ma;
        i++;
    }
    if(ma>n) cout<<n;
    else cout<<ma;
}

D - Reachability Query 2 可达性查询 2

题面翻译

时间限制：3 秒 / 内存限制：1024 MiB
分数：425 分

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的有向图。顶点编号为 $1$ 到 $N$，第 $i$ 条边是从顶点 $X_i$ 指向顶点 $Y_i$ 的有向边。初始时，所有顶点均为白色。
按顺序处理 $Q$ 个查询，每个查询为以下两种类型之一：

1. 1 v：将顶点 $v$ 染成黑色。
2. 2 v：判断从顶点 $v$ 出发，沿着边遍历是否能够到达某个黑色顶点。

约束条件

• $1 \le N \le 3 \times 10^5$
• $0 \le M \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• $1 \le X_i, Y_i \le N$
• 图中无自环（即 $X_i \neq Y_i$）。
• 图中无重边（即所有 $(X_i, Y_i)$ 互不相同）。
• 查询中，$1 \le v \le N$。
• 所有输入值均为整数。

输入格式

输入数据通过标准输入给出，格式如下：

N M
X_1 Y_1
⋮
X_M Y_M
Q
query_1
⋮
query_Q

其中 query_i 表示第 $i$ 个查询，格式为以下两者之一：

1 v
2 v

输出格式

设第二类查询的数量为 $q$，输出 $q$ 行结果：

• 对于第 $i$ 个第二类查询，若从顶点 $v$ 能到达黑色顶点，输出 Yes；否则输出 No。

样例输入 1

5 6
1 2
2 3
3 1
4 5
1 4
2 5
5
1 3
2 1
2 4
1 5
2 4

样例输出 1

Yes
No
Yes

样例解释

初始时，给定的图如最左侧的图所示。
第一个查询将顶点 3 染成黑色（如中间的图所示）。
第二个查询中，从顶点 1 可以到达黑色顶点 3，故输出 Yes
第三个查询中，从顶点 4 无法到达任何黑色顶点，故输出 No。
第四个查询将顶点 5 染成黑色（如最右侧的图所示）。
第五个查询中，从顶点 4 可以到达黑色顶点 5，故输出 Yes。

思考

很明显，这是一道图论题，其实我个人做的图论题也不多，我首先感觉是 P3916 图的遍历 - 洛谷 的升级版，多了染色和一些杂七杂八的东西，抽象。
小声：我刚看到每个查询的时候我还以为他考的是并查集。
一个经典的解决动态图可达性问题的方法是使用 bitset 或 分块，但 $N=3 \times 10^5$，bitset 太大（$N=3 \times 10^5 \space \text{bits}$ 约 $37.5 \space \text{KB}$ 每个顶点，总共 $N=3 \times 10^5$ 个顶点就是 $10^{10} \space \text{bits} \approx 1.25 \text{GB}$，太特么大了）。
我草比赛怎么结束了？

E - Cover query 覆盖查询

题面翻译

时间限制：2 秒 / 内存限制：1024 MiB
分数：450 分

题目描述

有 $N$ 个单元格从左到右排成一行。
从左数第 $i$ 个单元格（$1 \le i \le N$）被称为单元格 $i$。
初始时，所有单元格均为白色。

按顺序处理 $Q$ 个查询。
第 $i$ 个查询（$1 \le i \le Q$）的内容如下：

给定两个整数 $L_i$ 和 $R_i$（$1 \le L_i \le R_i \le N$）。
将单元格 $L_i, L_i+1, \dots, R_i$ 全部染成黑色。
在此操作中，原本白色的单元格会被染成黑色，原本黑色的单元格保持黑色不变。

操作完成后，求出 $N$ 个单元格中仍为白色的单元格数量。

约束条件

• $1 \le N \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• $1 \le L_i \le R_i \le N$
• 所有输入值均为整数

输入格式

输入数据通过标准输入按以下格式给出：

N Q
L_1 R_1
L_2 R_2
⋮
L_Q R_Q

输出格式

输出 $Q$ 行。
第 $i$ 行（$1 \le i \le Q$）输出第 $i$ 个查询的答案。

样例输入 1

10 5
3 5
8 9
5 8
2 9
6 6

样例输出 1

7
5
3
2
2

样例解释

初始时，10 个单元格从左到右排成一行。

第一个查询将单元格 3、4、5 染成黑色。操作后，白色单元格为 1、2、6、7、8、9、10，共 7 个。
第二个查询将单元格 8、9 染成黑色。操作后，白色单元格为 1、2、6、7、10，共 5 个。
第三个查询将单元格 5、6、7、8 染成黑色。操作后，白色单元格为 1、2、10，共 3 个。
第四个查询将单元格 2 到 9 染成黑色。操作后，白色单元格为 1、10，共 2 个。
第五个查询将单元格 6 染成黑色。操作后，白色单元格仍为 1、10，共 2 个。

因此，按顺序输出 7、5、3、2、2。

样例输入 2

1000000000 1
1 500000000

样例输出 2

500000000

思考

[待补]

F - Cat exercise 猫咪的锻炼

题面翻译

时间限制：2 秒 / 内存限制：1024 MiB
分数：550 分

题目描述

有 $N$ 座猫塔从左到右排成一行，从左数第 $i$ 座猫塔（$1 \le i \le N$）的高度为 $P_i$。
其中，序列 $(P_1,P_2,\dots,P_N)$ 是 $(1,2,\dots,N)$ 的一个排列。

从左数第 $i$ 座猫塔和第 $j$ 座猫塔之间的距离定义为 $|i-j|$。

初始时，有一只猫位于高度为 $N$ 的猫塔顶端。
高桥想要锻炼这只猫，方式是重复选择并移除猫塔。

当高桥移除一座猫塔时，猫的移动规则如下：

1. 若猫不在被移除的猫塔顶端，则猫保持不动。

2. 若猫在被移除的猫塔顶端，且该猫塔的左侧或右侧至少有一座猫塔存在，则猫会移动到以下目标猫塔：

   • 目标猫塔的范围是：从被移除的猫塔出发，通过重复移动到相邻猫塔能够到达的所有猫塔（不包含被移除的猫塔）。
   • 目标猫塔是上述范围内高度最高的猫塔。
   • 此时，猫的移动距离计入总距离，该距离等于移动前所在猫塔和移动后所在猫塔之间的距离（与移动过程中经过的猫塔高度、数量无关）。
3. 若猫在被移除的猫塔顶端，且该猫塔的左右两侧都没有猫塔存在，则猫会跳进高桥的怀里，锻炼就此结束。这种情况下，不计入任何移动距离。

注意：被移除的猫塔留下的空位不会被填补。也就是说，初始时从左数第 $i$ 座猫塔的相邻猫塔仅为第 $i-1$ 和第 $i+1$ 座猫塔（若存在），后续不会因为其他猫塔被移除而与非原本相邻的猫塔变成相邻关系。

请你求出，锻炼结束前猫能够移动的最大可能总距离。

约束条件

• $1 \le N \le 2 \times 10^5$
• $(P_1,P_2,\dots,P_N)$ 是 $(1,2,\dots,N)$ 的一个排列
• 所有输入值均为整数

输入格式

输入数据通过标准输入按以下格式给出：

N
P_1 P_2 … P_N

输出格式

输出锻炼结束前猫能够移动的最大可能总距离。

样例输入 1

5
5 3 4 1 2

样例输出 1

5

样例解释 1

初始时，猫塔的高度从左到右依次为 5、3、4、1、2。
下文将从左数第 $i$ 座猫塔（$1 \le i \le 5$）简称为猫塔 $i$。
初始时，猫位于猫塔 1 的顶端（高度为 5）。

若高桥按照 1 → 2 → 3 → 5 → 4 的顺序移除猫塔，猫的移动过程如下：

1. 移除猫塔 1：从猫塔 1 出发，通过重复移动到相邻猫塔可到达的猫塔为 2、3、4、5（不含猫塔 1）。其中高度最高的是猫塔 3（高度为 4），猫移动到该猫塔。
2. 移除猫塔 2：猫不在该猫塔顶端，保持不动。
3. 移除猫塔 3：从猫塔 3 出发，可到达的猫塔为 4、5（不含猫塔 3）。其中高度最高的是猫塔 5（高度为 2），猫移动到该猫塔。
4. 移除猫塔 5：从猫塔 5 出发，可到达的猫塔仅有 4（不含猫塔 5），猫移动到该猫塔。
5. 移除猫塔 4：猫的左右两侧都没有猫塔，跳进高桥怀里，锻炼结束。

此时，猫的总移动距离为 $|1-3| + |3-5| + |5-4| = 5$。不存在任何一种猫塔移除顺序，能让猫的总移动距离达到 6 或以上，因此输出 5。

样例输入 2

3
1 3 2

样例输出 2

1

样例解释 2

初始时，猫塔的高度从左到右依次为 1、3、2。
下文将从左数第 $i$ 座猫塔（$1 \le i \le 3$）简称为猫塔 $i$。
初始时，猫位于猫塔 2 的顶端（高度为 3）。

若高桥按照 2 → 3 的顺序移除猫塔，猫的移动过程如下：

1. 移除猫塔 2：从猫塔 2 出发，可到达的猫塔为 1、3（不含猫塔 2）。其中高度最高的是猫塔 3（高度为 2），猫移动到该猫塔。
2. 移除猫塔 3：猫的左右两侧都没有猫塔，跳进高桥怀里，锻炼结束。

此时，猫的总移动距离为 $|2-3|=1$，这是最大可能的总距离。

注意：移除猫塔 2 后，猫塔 1 和猫塔 3 不会被视为相邻。

思考

[待补]

G - Domino Arrangement 多米诺序列

题面翻译

时间限制：2 秒 / 内存限制：1024 MiB
分数：600 分

题目描述

有 $N$ 个单元格从左到右依次编号为 $1$ 到 $N$。初始时，所有单元格均未被涂上任何颜色。

共有 $M$ 种颜色，对于第 $i$ 种颜色，你可以选择单元格区间 $[L_i, R_i]$（即 $L_i, L_i+1, \dots, R_i$）内任意数量的单元格，将其涂为该颜色（可选择涂 0 个、1 个或多个）。

请计算满足以下条件的涂色方案数，并将结果对 $998244353$ 取模：

• 对于每一个单元格 $i$：

  • 若该单元格被涂上了某一种颜色，则其左侧相邻单元格 $i-1$ 和右侧相邻单元格 $i+1$ 中，恰好有一个 单元格被涂成了与 $i$ 相同的颜色；
  • 特别说明：单元格 $0$ 和 $N+1$ 被视为未被任何颜色涂色（即不存在的单元格）。

约束条件

• $1 \le N,M \le 5 \times 10^5$
• $1 \le L_i \le R_i \le N$
• 所有输入值均为整数

输入格式

输入数据从标准输入按以下格式给出：

N M
L_1 R_1
L_2 R_2
⋮
L_M R_M

输出格式

输出满足条件的涂色方案数（对 $998244353$ 取模）。

样例输入 1

5 2
1 3
1 5

样例输出 1

11

样例解释 1

第 1 种颜色可涂色的单元格范围是 $1,2,3$，第 2 种颜色可涂色的单元格范围是 $1,2,3,4,5$。
满足条件的涂色方案共有 11 种。

样例输入 2

3 3
1 1
2 2
3 3

样例输出 2

1

样例解释 2

唯一满足条件的方案是：不涂任何单元格（若给任意单元格涂色，都无法满足“恰好一个相邻单元格同色”的条件）。

样例输入 3

500000 10
1 499999
2 499998
3 499997
4 499996
5 499995
6 499994
7 499993
8 499992
9 499991
10 499990

样例输出 3

775503999

补充说明

答案需对 $998244353$ 取模后输出。

思考

[待补]

感受

我也不是打 noip 的货，也很菜

题解

梦熊 NOIP 2025 模拟赛 3 题解

T1 战争游戏

题目描述

游戏在一行 $n$ 个城市上进行，城市 $i$ 初始有士兵 $a_i$ 人。前 $m$ 个城市属于小L，其余属于小K，两人交替操作，小L先手。操作包含三种：

1. 转移：选择己方地盘上相邻（$|x-y|=1$）的两个城市 $x$、$y$，将 $x$ 的所有士兵转移到 $y$，$a_x$ 变为 0。
2. 攻占：选择己方城市 $x$ 和对方相邻城市 $y$，小L操作需满足 $a_x > a_y$，小K操作需满足 $a_x \geq a_y$，攻占后 $y$ 归己方，士兵转移方式同转移操作。
3. 不进行任何操作。
   当一方占据所有城市时获胜，需对 $m=1,2,...,n-1$ 分别输出获胜方。

关键思路

1. 特殊性质B：若先手第一步无法攻占，双方会优先集中兵力，最终比较分界线两侧总兵力。
2. 特殊性质C：若先手第一步可攻占对方城市且后手无法反制，比较攻占后两侧总兵力。
3. 正解：先手攻占后需判断对手是否能反制，若能则选择转移兵力，否则执行攻占，核心是比较关键状态下的兵力总和。

T2 加减乘除

题目描述

给定一棵以 1 为根的树，每个节点 $u$ 有运算符号 $op_u$（加或减）和数值 $a_u$。$q$ 次询问，每次给定 $x$，从根节点出发，需满足边的范围条件 $[l_v, r_v]$（即经过节点 $u$ 运算后的 $x'$ 需在子节点 $v$ 的边范围内）才能走向子节点，求能到达的节点个数。

正解

1. 区间预处理：每个节点 $u$ 对应可到达的 $x$ 区间 $[L_u, R_u]$，初始根节点区间为 $[-\infty, +\infty]$。
2. 区间更新：向下遍历树时，运算操作会平移区间，边的范围条件会取区间交集，以此递推得到所有节点的 $[L_u, R_u]$。
3. 高效查询：对所有区间端点离散化，用差分法给每个区间 $[L_u, R_u]$ 加 1，查询时二分找到 $x$ 对应的区间，即可得到答案。
4. 时间复杂度：$O((n+q) \log n)$。

T3 空之碎物

题目描述

定义二进制不退位减法 $\ominus$，给定序列 $a$，对于区间 $[l, r]$，$f(l, r)$ 表示将该区间元素作为多重集，经若干次合并操作（选两个数合并为其不退位减法结果）后剩余的最大值。求 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} f(i, j)$ 对 998244353 取模的值。

核心性质

1. 性质1：最终操作结果可表示为 $x \ominus(y \ominus a_1 \ominus a_2 \ominus ... \ominus a_{n-2})$（$a_1~a_{n-2}$ 为除 $x,y$ 外的元素）。某二进制位无1时无影响，恰好一个1时贡献由 $y$ 选择决定，至少两个1时贡献为0。
2. 性质2：若区间长度超过 $\log_2 V + 2$（$V$ 为元素最大值，此处 $V < 2^{25}$），则 $f(l, r)$ 等于区间最大值。

正解

1. 处理长区间：直接累加所有长度超过 $\log_2 V + 2$ 的区间的最大值。
2. 处理短区间：枚举每个二进制位，对该位有两个1的元素建立连边，通过枚举连边计算贡献，时间复杂度 $O(n \log_2^2 V)$。

T4 Ice Drop

题目描述

一个正整数序列是“好的”，当且仅当对任意正整数 $k$，序列中所有 $k$ 的倍数位置连续。给定序列 $a$，$f(b)$ 表示满足以下条件的“好的”序列 $b'$ 的数量：

1. $|b'| = |b|$；
2. 若 $b_i > 1$，则 $b_i' = b_i$；
3. $LCM(b_1,...,b_m) = LCM(b_1',...,b_m')$（$m$ 为 $b$ 的长度）。
   $q$ 次询问，每次给定 $l, r$，求 $\sum_{x=l}^{r} \sum_{y=x}^{r} f(a[x,y])$ 对 $10^9+7$ 取模的值。

关键思路

1. 核心等价：序列是“好的”等价于每个质因子的指数序列是单峰的。
2. 特殊性质A（$q=1$）：不能新增质因子，也不能超过原质因子最大指数，通过组合数计算合法填充方式，答案为各质因子贡献乘积。
3. 特殊性质B：若只有一个质因子，合法区间是若干不交区间的子集，答案非0即1。
4. 正解：用扫描线结合线段树，维护全局乘、单点修、查历史和，对每个不交区间单独处理，时间复杂度 $O(n \log n)$。

个人代码

T1

主要思路：骗分

#include <bits/stdc++.h>
using namespace std;
int T,n,i,m,ma,t,a[100010];
string ans;
int main(){
    cin>>T;
    while(T--){
        cin>>n;t=ma=0;ans="";
        for(i=1;i<=n;i++)
            cin>>a[i],ma+=a[i];
        for(m=1;m<n;m++){
            t+=a[m];
            if(2*t>ma) ans+='1';
            else ans+='0';
        }
        cout<<ans<<"\n";
    }
}

太好力，又水了一篇 blog
MX-S11

P1304 哥德巴赫猜想 - 洛谷

第一代代码

#include <bits/stdc++.h>
using namespace std;
int i,n,a,b,fl,t;
int prime[] = {
    0,  
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
    127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
    179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
    233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
    283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
    353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
    419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
    467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
    547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
    607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
    661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
    739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
    811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
    877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
    947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
    1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
    1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
    1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
    1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
    1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
    1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
    1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
    1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
    1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
    1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
    1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
    1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
    1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
    1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
    2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
    2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
    2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
    2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
    2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
    2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
    2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
    2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
    2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
    2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,
    2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
    2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
    3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
    3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,
    3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
    3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
    3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
    3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,
    3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571,
    3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
    3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
    3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,
    3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
    3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
    4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
    4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139,
    4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,
    4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
    4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
    4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493,
    4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583,
    4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
    4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
    4759, 4783, 4787, 4789, 4793, 4801, 4813, 4817, 4831, 4861,
    4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943,
    4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009,
    5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099,
    5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189,
    5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281,
    5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393,
    5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449,
    5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527,
    5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641,
    5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701,
    5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801,
    5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861,
    5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953,
    5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067,
    6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143,
    6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229,
    6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311,
    6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373,
    6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481,
    6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577,
    6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679,
    6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763,
    6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841,
    6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947,
    6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001,
    7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109,
    7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211,
    7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307,
    7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417,
    7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507,
    7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573,
    7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649,
    7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727,
    7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841,
    7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927,
    7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039,
    8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117,
    8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221,
    8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293,
    8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389,
    8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513,
    8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599,
    8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681,
    8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747,
    8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837,
    8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933,
    8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013,
    9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127,
    9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203,
    9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293,
    9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391,
    9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461,
    9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539,
    9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643,
    9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739,
    9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817,
    9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901,
    9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973
};
int main(){
    cin>>n;
    for(i=1;i<=(n-2)/2;i++){
        t=2*i+2;fl=0;
        cout<<t<<"=";
        for(a=1;a<=1300;a++){
            if(fl==1) break;
            for(b=1;b<=1300;b++){
                if(fl==1) break;
                if(prime[a]+prime[b]==t) cout<<prime[a]<<"+"<<prime[b]<<"\n",fl=1;
            }
        }
    }
}

第二代代码

发现数组越界，只有 $1299$个数，却循环到 $1300$

#include <bits/stdc++.h>
using namespace std;
int i,n,a,b,fl,t;
int prime[] = {
    0,  
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
    127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
    179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
    233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
    283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
    353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
    419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
    467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
    547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
    607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
    661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
    739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
    811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
    877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
    947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
    1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
    1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
    1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
    1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
    1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
    1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
    1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
    1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
    1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,
    1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
    1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
    1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
    1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,
    1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
    2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
    2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,
    2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
    2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
    2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
    2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,
    2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,
    2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
    2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
    2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,
    2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
    2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
    3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
    3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,
    3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,
    3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
    3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
    3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,
    3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571,
    3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
    3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
    3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,
    3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,
    3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
    4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
    4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139,
    4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,
    4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
    4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
    4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493,
    4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583,
    4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
    4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
    4759, 4783, 4787, 4789, 4793, 4801, 4813, 4817, 4831, 4861,
    4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943,
    4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009,
    5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099,
    5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189,
    5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281,
    5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393,
    5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449,
    5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527,
    5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641,
    5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701,
    5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801,
    5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861,
    5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953,
    5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067,
    6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143,
    6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229,
    6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311,
    6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373,
    6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481,
    6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577,
    6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679,
    6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763,
    6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841,
    6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947,
    6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001,
    7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109,
    7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211,
    7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307,
    7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417,
    7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507,
    7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573,
    7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649,
    7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727,
    7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841,
    7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927,
    7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039,
    8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117,
    8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221,
    8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293,
    8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389,
    8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513,
    8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599,
    8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681,
    8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747,
    8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837,
    8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933,
    8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013,
    9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127,
    9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203,
    9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293,
    9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391,
    9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461,
    9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539,
    9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643,
    9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739,
    9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817,
    9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901,
    9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973
};
int main(){
    cin>>n;
    for(i=1;i<=(n-2)/2;i++){
        t=2*i+2;fl=0;
        cout<<t<<"=";
        for(a=1;a<=1229;a++){
            if(fl==1) break;
            for(b=1;b<=1229;b++){
                if(fl==1) break;
                if(prime[a]+prime[b]==t) cout<<prime[a]<<"+"<<prime[b],fl=1;
            }
        }
        cout<<"\n";
    }
}

第三代代码

少了一个质数，所以炸了，现在 AC 了

【知识要点】栈、队列、堆、优先队列

1. 栈(Stack)和队列(Queue)基础

1.1 基本概念对比

1.2 队列的详细定义

• 队列是C++标准库中的重要数据结构
• 允许删除的一端称为队头(Front)
• 允许插入的一端称为队尾(Rear)
• 空队列：队列中没有元素的状态
• 操作原则：先进先出(FIFO)

1.3 C++队列基本操作示例

#include<bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q; // 定义一个空队列
  
    for(int i=0; i<5; i++) {
        q.push(i); // 将i插入到队尾
    }
  
    q.emplace(32); // 将32放置到队尾，作用和push一样
  
    cout << q.size() << endl; // 输出队列中元素的个数
  
    while(!q.empty()) { // 当队列不为空时，继续循环
        cout << q.front() << endl; // 输出队列中的首元素
        q.pop(); // 将元素从队头删除
    }
  
    return 0;
}

1.4 队列queue的完整函数列表

• q.pop() - 删除queue的队头元素
• q.front() - 返回队列的队头元素，但不删除
• q.back() - 返回队列的队尾元素，但不删除
• q.push(arg) - 将元素arg插入到队列的队尾
• q.emplace(arg) - 将元素arg放置到队列的尾部(效果同push)
• q.size() - 返回队列中元素的个数
• q.empty() - 队列为空时返回true，否则false
• q.swap(q1) - 交换q和q1中的元素(交换底层数据结构)
• swap(q,q1) - 非成员函数，效果同成员函数swap

1.5 队列的应用场景

• BFS(广度优先搜索)算法
• 单调队列
• 缓冲区管理
• 任务调度

2. 堆(Heap)与优先队列(Priority Queue)

2.1 堆的基本概念

• 堆是一类特殊的数据结构，常用的是二叉堆
• 形式上是一个数组，本质上是一棵完全二叉树

• 分为大根堆和小根堆：

  • 大根堆：除根节点外，每个节点的值都大于等于其子节点的值

    • 公式表示：A[parent(i)] >= A[i]

  • 小根堆：除根节点外，每个节点的值都小于等于其子节点的值

    • 公式表示：A[parent(i)] <= A[i]
• 堆中的任一子树也还是堆

2.2 堆的基本操作

• push操作(插入)：往堆尾加入元素，并通过从下往上调整保持堆性质
• get操作(删除)：取出堆顶元素，用堆尾元素覆盖堆顶，再从上往下调整

2.3 优先队列的实现

C++中用 priority_queue实现堆的功能：

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 默认大根堆
    priority_queue<int> max_heap;
  
    // 小根堆定义方式
    priority_queue<int, vector<int>, greater<int>> min_heap;
  
    // 自定义结构体的优先队列
    struct Node {
        int u, len;
        bool operator < (const Node &x) const {
            return x.len < len; // 注意这里是反向定义，实现小根堆效果
        }
    };
  
    priority_queue<Node> custom_heap;
  
    return 0;
}

2.4 优先队列的操作函数

• push(Elem e) - 插入元素，时间复杂度O(log n)
• pop() - 删除顶部元素，O(log n)
• top() - 返回顶部元素，O(1)
• size() - 返回元素数量
• empty() - 判断是否为空

2.5 优先队列的特殊注意事项

1. 不支持除顶部外其他元素的访问和操作
2. 没有内置的clear()操作，需要手动实现：

void clear(priority_queue<int> &q) {
    while (!q.empty()) q.pop();
}

3. 访问top()前必须检查队列是否为空

3. 经典问题与解决方案

3.1 合并果子问题

问题描述：有n堆果子，每次合并两堆消耗体力值为两堆果子数之和，求最小总消耗。

解决方案：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
  
    for(int i = 0; i < n; i++) {
        int x; cin >> x;
        q.push(x);
    }
  
    while(q.size() > 1) {
        int x = q.top(); q.pop();
        int y = q.top(); q.pop();
        ans += x + y;
        q.push(x + y);
    }
  
    cout << ans;
    return 0;
}

时间复杂度分析：O(n log n)

3.2 互数问题

问题描述：给定素数集合S，生成由S中素数乘积构成的"互数集合"，求第n小的互数。

解决方案：

typedef long long ll;

int main() {
    ll k, n;
    cin >> k >> n;
    vector<ll> primes(k);
    priority_queue<ll, vector<ll>, greater<ll>> heap;
    set<ll> seen;
  
    for(int i = 0; i < k; i++) {
        cin >> primes[i];
        heap.push(primes[i]);
        seen.insert(primes[i]);
    }
  
    ll humble = 1;
    for(int i = 0; i < n; i++) {
        humble = heap.top(); heap.pop();
        for(auto p : primes) {
            ll num = humble * p;
            if(seen.find(num) == seen.end()) {
                seen.insert(num);
                heap.push(num);
            }
        }
    }
  
    cout << humble;
    return 0;
}

时间复杂度分析：O(nk log n)

3.3 两个序列的最小N个和

问题描述：有两个长度为N的有序序列A和B，求A和B中各取一个数相加得到的N²个和中最小的N个。

解决方案：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

struct HeapNode {
    int x, val;
    bool operator < (const HeapNode &other) const {
        return val > other.val; // 小根堆
    }
};

int main() {
    int n, a[maxn], b[maxn], pos[maxn] = {0};
    priority_queue<HeapNode> q;
  
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++) cin >> b[i];
  
    // 初始时每个a[i]配b[0]
    for(int i = 0; i < n; i++) {
        q.push({i, a[i] + b[0]});
    }
  
    for(int i = 0; i < n; i++) {
        HeapNode tmp = q.top(); q.pop();
        cout << tmp.val << " ";
        int x = tmp.x;
        if(++pos[x] < n) {
            q.push({x, a[x] + b[pos[x]]});
        }
    }
  
    return 0;
}

时间复杂度分析：O(n log n)

4. 高级应用提示

1. Dijkstra算法优化：堆/优先队列可用于优化Dijkstra最短路径算法，将时间复杂度从O(V²)降低到O(E + V log V)
2. 单调队列：一种特殊的队列，可以高效解决滑动窗口最值问题
3. 多路归并：优先队列可以高效解决多路归并问题，如上面的最小N个和问题
4. Huffman编码：优先队列可用于构建最优前缀编码树

5. 总结

掌握这些基础数据结构及其应用场景，对于算法学习和编程竞赛至关重要。优先队列作为堆的高级抽象，在实际应用中更为方便，但理解其底层堆的原理同样重要。

【熟能生巧】

P9588 「MXOI Round 2」队列

题目描述

小 C 有一个队列，他要对这个队列进行 $q$ 次操作。操作共四种，参数分别如下：

$1\ x$：这是第一种操作，表示从队尾依次插入 $1,2,3,\cdots,x$；

$2\ y$：这是第二种操作，表示弹出队头的前 $y$ 个元素；

$3\ z$：这是第三种操作，表示查询队列中的第 $z$ 个元素；

$4$：这是第四种操作，表示查询队列中所有元素的最大值。

你需要帮助他维护这个队列，并对于每个第三种操作和第四种操作，输出查询的答案。

输入格式

第一行两个整数 $c,q$，其中 $c$ 表示测试点编号。$c=0$ 表示该测试点为样例。

接下来 $q$ 行，每行 $1 \sim 2$ 个整数，表示一个操作，格式见【题目描述】。

输出格式

对于每个第三种操作和第四种操作，输出一行一个整数，表示查询的答案。

输入输出样例 #1

输入 #1

0 9
1 5
1 3
2 2
1 4
3 6
3 8
2 4
4
3 3

输出 #1

3
2
4
1

说明/提示

【样例解释 #1】

在进行第四次操作后，队列中的元素依次为 $3,4,5,1,2,3,1,2,3,4$。

在进行第七次操作后，队列中的元素依次为 $2,3,1,2,3,4$。

【数据范围】

设 $\sum x$ 表示单个测试点内 $x$ 之和。

对于 $100\%$ 的数据，$1 \le q \le 2\times 10^5$，$1 \le x,y,z \le 10^9$，$0 \le \sum x \le 2\times10^{14}$，保证在进行第二种操作前队列内元素个数不小于 $y$，在进行第三种操作前队列内元素个数不小于 $z$，在进行第四种操作前队列内元素个数大于 $0$。

特殊性质 A：没有第二种操作。

特殊性质 B：没有第三种操作。

特殊性质 C：没有第四种操作。

P2723 [USACO3.1] 丑数 Humble Numbers

题目描述

对于一给定的素数集合 $S = \{ p_1, p_2, ..., p_k \}$, 考虑一个正整数集合，该集合中任一元素的质因数全部属于 $S$。这个正整数集合包括，$p_1$、$p_1 \times p_2$、$p_1 \times p_1$、$p_1 \times p_2 \times p_3$ ...(还有其它)。该集合被称为 $S$ 集合的“丑数集合”。注意：我们认为 $1$不是一个丑数。

你的工作是对于输入的集合 $S$ 去寻找“丑数集合”中的第 $n$ 个“丑数”。保证答案可以用 32 位有符号整数表示。

补充：丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积，第 $n$ 个“丑数”就是在能由素数集合中的数相乘得来的（包括它本身）第 $n$ 小的数。

输入格式

输入的第一行是两个的整数，分别代表集合 $S$ 的大小 $k$ 和给定的参数 $n$。

输入的第二行有 $k$ 互不相同的整数，第 $i$ 个整数代表 $p_i$。

输出格式

输出一行一个整数，代表答案。

输入输出样例 #1

输入 #1

4 19
2 3 5 7

输出 #1

27

说明/提示

数据规模与约定

对于 $100\%$ 的数据，保证：

• $1 \leq k \leq 100$。
• $1 \leq n \leq 10^5$。
• $2 \leq p_i < 2^{31}$，且 $p_i$ 一定为质数。

说明

题目翻译来自 NOCOW。

USACO Training Section 3.1

P1323 删数问题

题目描述

一个集合有如下元素：$1$ 是集合元素；若 $P$ 是集合的元素，则 $2\times P+1$，$4\times P+5$ 也是集合的元素。

取出此集合中最小的 $k$ 个元素，按从小到大的顺序组合成一个多位数，现要求从中删除 $m$ 个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。

注：不存在所有数被删除的情况。

输入格式

只有一行两个整数，分别代表 $k$ 和 $m$。

输出格式

输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。

输入输出样例 #1

输入 #1

5  4

输出 #1

137915
95

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $1\le k,m\le300$。
• 对于 $100\%$ 的数据，保证 $1\le k,m\le3\times10^4$。

P2085 最小函数值

题目描述

有 $n$ 个函数，分别为 $F_1,F_2,\dots,F_n$。定义 $F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)$。给定这些 $A_i$、$B_i$ 和 $C_i$，请求出所有函数的所有函数值中最小的 $m$ 个（如有重复的要输出多个）。

输入格式

第一行输入两个正整数 $n$ 和 $m$。

以下 $n$ 行每行三个正整数，其中第 $i$ 行的三个数分别为 $A_i$、$B_i$ 和 $C_i$。

输出格式

输出将这 $n$ 个函数所有可以生成的函数值排序后的前 $m$ 个元素。这 $m$ 个数应该输出到一行，用空格隔开。

输入输出样例 #1

输入 #1

3 10
4 5 3
3 4 5
1 7 1

输出 #1

9 12 12 19 25 29 31 44 45 54

说明/提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n,m\le10000$，$1 \leq A_i\le10$,
$0 \leq B_i\le100$,
$0 \leq C_i\le10^4$。

【答案校对】

队列

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=800010;
int c,T,t,i,cnt,op,x,del,qwq,f[N],l[N],r[N],a[N*2],h=1,n=400005;
int read(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){ 
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return f*x;
}
void update(int x,int l,int r,int ql,int qr,int k){
    int mid=(l+r)>>1;
    if(ql<=l&&r<=qr){
        a[x]=k;return;
    }
    if(ql<=mid) update(x*2,l,mid,ql,qr,k);
    if(qr>mid) update(x*2+1,mid+1,r,ql,qr,k);
    a[x]=max(a[x*2],a[x*2+1]);
}
int query(int x,int l,int r,int ql,int qr){
    int mid=(l+r)>>1,sum=0;
    if(ql<=l&&r<=qr){
        return a[x];
    }
    if(ql<=mid) sum=max(sum,query(x*2,l,mid,ql,qr));
    if(qr>mid) sum=max(sum,query(x*2+1,mid+1,r,ql,qr));
    return sum;
}
signed main(){
    cin>>c>>T;
    while(T--){
        op=read();
        if(op==1)
            x=read(),l[++t]=1,r[t]=x,update(1,1,n,t,t,x),f[t]=f[t-1]+x;
        else if(op==2){
            x=read();cnt=0;
            for(i=h;i<=t;++i){
                cnt+=r[i]-l[i]+1;
                if(cnt>=x){
                    cnt-=r[i]-l[i]+1;
                    l[i]+=x-cnt;del+=x-cnt;
                    if(l[i]>r[i])update(1,1,n,i,i,0),++h;
                    break;
                }
                del+=r[i]-l[i]+1;r[i]=l[i]=0;++h;
                update(1,1,n,i,i,0);
            }
        }
        else if(op==3){
            x=read();
            qwq=lower_bound(f+h,f+t+1,del+x)-f;
            printf("%lld\n",del+x-f[qwq-1]);
        }
        else printf("%lld\n",query(1,1,n,h,t));
    }
}

丑数

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,i,j,a[105],b[105],s[100005],zx;
signed main(){
    cin>>n>>m;
    for(i=1;i<=n;i++)
        cin>>a[i];
    s[0]=1;
    for(i=1;i<=m;i++){
        zx=pow(2,31)-1;
        for(j=1;j<=n;j++){
            while(a[j]*s[b[j]]<=s[i-1])
                b[j]++;
            if(a[j]*s[b[j]]<zx)
                zx=a[j]*s[b[j]];
        }
        s[i]=zx;
    }
    cout<<s[m];
}

删数问题

#include <bits/stdc++.h>
#define int long long
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
string p;
int k,m,s;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>k>>m;
    q.push(1);
    while(k){
        int s=q.top();
        p=p+to_string(s);
        q.pop();
        q.push(s*2+1);
        q.push(s*4+5);
        k--;
    }
    cout<<p<<"\n";
    while(true){
        for(int i=0;i<p.size();i++){
            if(p[i+1]>p[i]){
                s++;
                p.erase(i,1);
                if(s>=m){
                    cout<<p;
                    exit(0);
                }
                break;
            }
        }
    }
}

最小函数值

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[10001],b[10001],c[10001],n,m,s[10000001],i,j,t;
signed main(){
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
    for(i=1;i<=n;i++) for(j=1;j<=100;j++) s[++t]=a[i]*j*j+b[i]*j+c[i];
    sort(s+1,s+1+t);
    for(i=1;i<=m;i++) cout<<s[i]<<" ";
}

T1

【题面】T678583 A美丽数 (beauty)

题目描述

小 B 对数字有着独到的见解，他认为一个数是美丽数当且仅当这个数的相邻两位都不相同。

例如12345、12121是美丽数，而123321、11不是美丽数。
现在小B想知道，对于所有满足以下条件的数中，最小的那个数是什么?如果不存在这样的美丽数，则输出-1。

· 对 于i(0≤i≤9), 这个数中是i 的位数一共有ai 个。

· 这个数不能有前导0,即012是不合法的。
有多组测试点，每组测试点现在给你a0～a9, 请你回答小B 的问题。

输入格式

第一行包含一个整数T。

接下来T 行，每行10个整数， a0～a9, 含义如题。

输出格式

输出T, 每行一个整数，表示答案。

输入输出样例 #1

输入 #1

12
6 0 0 0 0 0 0 0 0 5
0 1 0 2 0 0 0 0 0 0
3 0 0 0 2 0 0 1 0 0
0 1 2 3 4 5 6 7 8 9
1 2 0 1 5 0 1 0 0 0
2 1 1 0 1 5 0 0 0 0
6 0 1 0 2 0 0 0 1 0
8 1 0 0 1 0 0 0 0 0
5 2 0 0 2 0 1 0 0 0
3 0 0 0 0 3 0 2 1 1
3 1 0 5 0 0 1 0 0 0
0 1 2 0 0 1 0 1 0 5

输出 #1

-1
313
404070
123234345454565656767676787897979898989898989
1404143464
1505052545
-1
-1
1010404060
5050507879
1303030363
1929295979

说明/提示

对于100%的数据，保证：T≤10,1≤n,ai≤ 10⁵, 其中$n=∑ai（0≤i≤9）$

A: 保证最多只有2个ai>0。

B: 保证最多只有3个ai>0。

【代码】T678583 A美丽数 (beauty)

#include <bits/stdc++.h>
using namespace std;
int t,i,d,p,m,c,w,l,g,a[11],cnt[11],f;
string s;
bool j(int t,int b=-1){
    int mx=0;
    for(i=1;i<=10;i++){
        if(i-1==b) continue;
        if(cnt[i]>mx) mx=cnt[i];
    }
    return mx\*2<=t+1;
}
int main(){
    cin>>t;
    while(t--){
        for(i=1;i<=10;i++) cin>>a[i];
        m=c=0;l=-1;s="";
        for(i=1;i<=10;i++) m+=a[i];
        if(m==0){cout<<-1<<"\\n";continue;}
        for(i=1;i<=10;i++) if(a[i]>c) c=a[i];
        if(c>(m+1)/2){cout<<-1<<"\\n";continue;}
        for(i=1;i<=10;i++) cnt[i]=a[i];
        for(p=0;p<m;p++){
            f=0;
            for(d=1;d<=10;d++){
                g=d-1;
                if(cnt[d]==0) continue;
                if(g==l) continue;
                if(p==0&&g==0) continue;
                cnt[d]--;
                if(j(m-p-1,g)){
                    s+=char('0'+g);
                    l=g;
                    f=1;
                    break;
                }
                cnt[d]++;
            }
            if(!f){cout<<-1<<"\\n";break;}
        }
        if(f) cout<<s<<"\\n";
    }
}

URL

【MX-X23】梦熊 X 组 · 月亮赛（同步赛） - 洛谷 | 计算机科学教育新生态

【MX-J26】梦熊 J 组 · 月亮赛（同步赛） - 洛谷 | 计算机科学教育新生态

我的分数

X组：10分

J组：210分

MX-J26/X23 月亮赛 官方题解

A. 丢手绢

小朋友的编号为 $1 \sim n$，直接处理不够便捷，因此将所有编号减去 1，转换为 $0 \sim n-1$。这样调整后，便能通过取模运算轻松计算出每个被放手绢的小朋友编号。

具体规则如下：设编号为 $x$ 的小朋友被记录的数字为 $a_{x}$，则被放手绢的小朋友编号为 $(x + a_{x}) \mod n$。需特别注意，此处涉及负数取模的情况，计算时需遵循相应的取模规则。

后续操作流程为：统计每个小朋友被投放手绢的次数，找出其中的最大值，再依次输出所有出现最大值的小朋友的位置（此处位置需根据最初编号规则还原，若最终结果需对应 $1 \sim n$ 的编号，需将计算得到的 $0 \sim n-1$ 编号加 1）。

该算法的时间复杂度为 $O(n)$，其中 $n$ 为小朋友的总数，仅需遍历一次所有小朋友的记录即可完成统计与计算。

B. 括号序列

首先进行初步判断：若括号序列中左括号和右括号的数量不相等，则该括号序列一定无法构成合法序列，直接判定为无解。接下来仅针对左右括号数量相等的情况展开分析。

判断括号序列是否合法可通过前缀和的方法实现，具体定义前缀和数组 $a_i$ 如下：

$$ a_{i}= \begin{cases} 0, & i=0 \\ a_{i-1}+1, & s_{i}='(' \\ a_{i-1}-1, & s_{i}=')' \end{cases} $$

当遇到相邻的 “)(” 时，将其修改为 “()”，这一操作的本质是将初始时 “)” 对应位置的前缀和加 1，而其他位置的前缀和保持不变。括号序列合法的核心条件是：所有位置的前缀和 $a_i \geq 0$。

基于此条件，判断流程如下：找到第一个满足 $a_i < 0$ 的位置，若该位置附近存在可修改的 “)(” 结构（即能通过修改使该位置及后续位置的前缀和均非负），则进行修改操作，随后再次检查修改后的括号序列是否满足所有前缀和 $a_i \geq 0$，以此确定序列是否合法。

该算法的时间复杂度为 $O(n)$，$n$ 为括号序列的长度，仅需遍历一次序列即可完成前缀和计算与合法性判断。

C. 猜拳游戏

首先定义 $g = \gcd(n, m)$（即 $n$ 和 $m$ 的最大公约数），并令 $n' = \frac{n}{g}$，$m' = \frac{m}{g}$。

在猜拳游戏中，$10100$ 是一个足够大的数字（其值超过 $\text{lcm}(n, m)$，即 $n$ 和 $m$ 的最小公倍数），因此只需考虑游戏不断进行过程中可能出现的所有状态。

将字符串 $a$（长度为 $n$）和字符串 $b$（长度为 $m$）分别按照下标对 $g$ 取模的余数进行分组，共可分为 $g$ 组。以第 $k$ 组（$0 \leq k < g$）为例，字符串 $a$ 中属于该组的有 $n'$ 个招式，字符串 $b$ 中属于该组的有 $m'$ 个招式，这两组招式两两组合形成的 $n' \times m'$ 种情况，一定会在同一局游戏中全部出现。

若要避免平局，必须保证字符串 $a$ 中该组的 $n'$ 个招式组成的集合与字符串 $b$ 中该组的 $m'$ 个招式组成的集合没有交集（即两组招式完全不同）。

接下来需讨论 “石头（R）、剪刀（P）、布（S）” 这三种招式在字符串 $a$ 和 $b$ 中的可选情况，在所有合法的情况中选择操作次数最少的方案，最后将 $g$ 组的最少操作次数相加，得到最终的答案。

该算法的时间复杂度为 $O(n + m)$，其中 $n$ 和 $m$ 分别为字符串 $a$ 和 $b$ 的长度，需分别遍历两个字符串完成分组与招式集合的判断。

D. 卡常数

首先分析单个数列的情况：对于某一数列，选择其中一个位置 $j$，会使该数列的代价乘以系数 $\frac{a_{i,j} - b_{i,j}}{a_{i,j}}$（其中 $a_{i,j}$ 和 $b_{i,j}$ 为该数列第 $j$ 个元素的相关参数）。由于该系数为真分数，将数列中所有这样的真分数按照从小到大的顺序排列后，从左到右选择这些真分数（即优先选择较小的真分数），能使数列代价的减少量最大，是最优的选择策略。

进一步计算每个数列中，按照上述顺序选择每个元素时，该元素能让数列代价比选择上一个元素后再减少的量，将这个减少量定义为该元素的“价值”。通过分析可发现，在同一个数列中，元素的价值是单调递减的（即越靠后选择的元素，其减少代价的能力越弱）。

基于单个数列的价值特性，将所有数列中所有元素的价值整合到一个集合中，对该集合按照从大到小的顺序排序，然后依次选择价值最大的元素，即可实现整体代价的最小化。

贪心策略正确性证明：由于单个数列内部元素的价值单调递减，后续元素的价值必然小于前面元素的价值，因此在选择时，后续元素不可能先于前面元素被选中，这就保证了将所有元素价值排序后从大到小选择的贪心策略是正确的。

设 $m = \sum l_i$（其中 $l_i$ 为第 $i$ 个数列的长度），则该算法的时间复杂度为 $O(m \log m)$，主要耗时在于对所有元素价值的排序操作。

E. 向死存魏

首先采用离线处理的方式，将所有的“二操作”（具体操作含义需结合题目背景，此处默认是对序列的修改或查询操作）加入到操作序列中。在执行操作的过程中，实时记录当前序列的长度，若某一查询操作要求的答案超过当前序列的长度，则判定该查询无解。设所有操作全部结束后，序列的最终长度为 $k$。

对于删除操作，由于每个元素至多被删除一次，且序列的最终长度为 $k$，因此可使用 $set$ 数据结构对序列进行暴力修改（如标记删除或直接移除元素），操作效率可满足需求。

对于查询操作，首先利用双指针法预处理出初始状态下从序列每个位置开始查询的答案。在后续的删除操作中，针对被删除的元素 $x$，先确定其删除区间：设删除区间左边第一个未被删除的位置为 $p$（若不存在这样的位置，则令 $p = 0$），删除区间右边第一个未被删除的位置为 $q$（若不存在这样的位置，则令 $q = k + 1$）。删除该区间内所有的 $x$ 后，会对起始位置在 $[p + 1, q - 1]$ 范围内的查询产生影响——从这些起始位置开始查询时，需要到位置 $q$ 才能找到元素 $x$。

为高效处理上述区间影响，需对 $[p + 1, q - 1]$ 范围内的当前查询答案进行更新（将答案设为 $q$），此处可使用线段树维护“区间取最值、单点查询”的操作，确保查询与更新的效率。

该算法的时间复杂度为 $O((k + m) \log k)$，其中 $k$ 为序列最终长度，$m$ 为操作总数，线段树的查询与更新操作均为 $O(\log k)$ 复杂度，且需处理 $m$ 次操作。

F. 网格 III

在网格操作中，每一次操作至多会影响 $O(n)$ 个格子（$n$ 为网格的边长或相关维度参数），因此只需关注当前操作实际改变的格子数量即可。

由于行列混合操作较为复杂，可将其拆分为两个独立的部分讨论：一是计算有多少行对当前列的修改产生贡献，二是计算有多少列对当前行的修改产生贡献。下文以“计算行对当前列修改的贡献”为例展开分析。

首先为每行和每列分别记录两个关键信息：最后一次修改的时间、最后一次修改的颜色（如红色或白色）。对于网格中 $k \times k$ 的正方形区域，其对应的所有行列信息仅存在两种不同的有效情况：

1. 该正方形区域内所有列的修改颜色均为红色，且最晚的白色行修改时间在最早的红色列修改时间之前；
2. 该正方形区域内存在列的修改颜色为白色，且所有行的修改颜色均为红色，同时最早的红色行修改时间在最晚的白色列修改时间之后。

由于 $k$ 的取值较小，可直接枚举包含当前列且长度为 $k$ 的区间，暴力查询该区间内的行列信息，进而统计满足上述两种情况的行的数量。为提高效率，对于每行，预先记录所有长度为 $k$ 的区间的信息，每次修改操作仅会改变 $O(k)$ 个区间的信息，后续可通过一维偏序的方法查询满足条件的行数量。

为简化时间与颜色的判断逻辑，对修改时间进行如下处理：若修改颜色为红色，时间值保持不变；若修改颜色为白色，时间值取其相反数。初始状态下，所有行列的修改颜色默认为红色，时间值可设为初始常量（如 0）。经过这样的处理，上述两种情况的判断可转化为对区间内时间值取最小值的操作。

可使用树状数组或线段树维护区间最小值，若直接暴力求区间最小值，算法的时间复杂度为 $O(n k^2 + n k \log n)$；若采用单调队列对区间最小值查询进行优化，时间复杂度可降至 $O(n k \log n)$，其中 $n$ 为网格的相关维度参数，$k$ 为正方形区域的边长。

G. 我爱数数

设 $t_i$ 表示使 $b_i \geq a_i$ 所需的操作次数（$a_i$ 和 $b_i$ 为题目给定的数组元素），则本题的答案等价于求 $E[\max_{i=1}^{n} t_i]$（即 $t_i$ 最大值的期望）。

可通过容斥原理计算该期望，具体公式为：答案等于对所有非空子集 $S \subseteq [n]$，求和 $(-1)^{|S| - 1} \times E[\min_{i \in S} t_i]$（其中 $|S|$ 表示子集 $S$ 的元素个数，$E[\min_{i \in S} t_i]$ 表示子集 $S$ 中 $t_i$ 最小值的期望）。

期望计算分析

假设有 $x$ 个区间满足：对任意 $i \in [l_p, r_p] \cap S$，均有 $c_p < a_i$（$[l_p, r_p]$ 为区间的左右端点，$c_p$ 为区间的相关参数）。此时，剩余的 $m - x$ 个区间（$m$ 为总区间数）一旦被选中，就会覆盖子集 $S$ 中的某个元素，导致 $t_i$ 的值固定。

在上述假设下，$E[\min_{i \in S} t_i]$ 的计算过程如下：

$$ E[\min_{i \in S} t_i] = \sum_{i=0}^{+\infty} \frac{x^i (m - x) (i + 1)}{m^{i + 1}} = \frac{m}{m - x} $$

基于此，定义 $w_x$ 为：对所有满足“恰好有 $x$ 个区间符合上述条件”的子集 $S$，求和 $(-1)^{|S| - 1}$。则最终答案可表示为：

$$ \text{答案} = \sum_{x=0}^{m - 1} w_x \times \frac{m}{m - x} $$

动态规划与优化

为计算 $w_x$，引入辅助函数 $h_i$，定义如下：

$$ h_i = \begin{cases} a_i - 1 & i \in S \\ +\infty & \text{Otherwise} \end{cases} $$

此时，“对任意 $i \in [l_p, r_p] \cap S$，$c_p < a_i$”这一限制条件可转化为“对任意 $i \in [l_p, r_p]$，$c_p \leq h_i$”。

进一步构建小根笛卡尔树（基于 $h_i$ 的值），并在树上进行动态规划。定义状态 $f_{L, R, u, x, 0/1}'$，其含义为：

• 考虑区间 $[L, R]$，仅关注 $h_i \geq u$ 的位置，且 $[L, R]$ 是一个连续段（即 $h_{L - 1} < u$ 且 $h_{R + 1} < u$）；
• 满足 $L \leq l_p \leq r_p \leq R$ 且 $c_p \leq x \leq \min_{i \in [l_p, r_p]} h_i$ 的区间 $p$ 共有 $x$ 个；
• 子集 $T = S \cap [L, R]$ 的元素个数为偶数（对应“0”）或奇数（对应“1”）；
• 该状态的值表示满足上述条件的子集 $T$ 的数量。

令 $f_{L, R, u, x} = f_{L, R, u, x, 0}' - f_{L, R, u, x, 1}'$，并引入辅助数组 $g$，则动态规划的转移公式如下：

$$ g_{L, R, u, x} = f_{L, R, u + 1, x} - \sum_{i=L}^{R} [h_i = u] \sum_{y=0}^{x} f_{L, i - 1, u + 1, y} \times g_{i + 1, R, u, x - y} $$

$$ f_{L, R, u, x} = g_{L, R, u, x - s_{L, R, u}} $$

其中 $s_{L, R, u}$ 表示满足 $L \leq l_p \leq r_p \leq R$ 且 $c_p = u$ 的区间 $p$ 的数量。

时间复杂度优化

若直接按照上述转移公式计算，时间复杂度为 $O(n^4 m^2)$（$n$ 为数组长度，$m$ 为总区间数）。但通过观察可知，$h_i = u$ 的位置对于所有 $u$ 而言，总数仅为 $n$ 个，因此可将时间复杂度优化至 $O(n^3 m^2)$。

进一步利用经典的拉格朗日插值（拉插）技巧，可将转移过程中的卷积运算转化为点乘运算，此时时间复杂度可降至 $O(n^3 m + m^2)$。关于拉格朗日插值技巧的具体应用，可参考题目 CF1874E Jellyfish and Hack。

我的评价

首先，让我吐槽一下这次比赛XJ的题目分配

题目分配

开始吐槽

在我的印象里，CSP-X是小学组的难度，但是，这里为什么X组的难度有NOI，我就感觉很猎奇，而且，为什么J组的第一二题在X组没，Who can tell me?

关于各题

【MX-X23-T1】丢手绢

这道题我大概提交了有好几次，主要是老是TLE，原因是因为写了太多没用的循环，这是AC的代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,x,i,f[N],ma,s;
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>x;s=i+x;
        while(s<1) s+=n;
        while(s>n) s-=n;
        f[s]++;
        ma=max(ma,f[s]);
    }
    for(i=1;i<=n;i++) if(f[i]==ma) cout<<i<<" ";
}

注意超n和小1的数据处理

【MX-X23-T2】括号串

这道题，我当时是在洛谷搜一道题，叫做括号串匹配，然后，找到了，但是没用，然后我在CSXX上找答案，找到了，但是没用

所以只好独立思考

namespace pts70{
bool check(string s){
    int tmp,i;
    for(i=tmp=0;i<s.length();i++){
        if(s[i]=='(') tmp++;
        else if(s[i]==')'){
            tmp--;
            if(tmp<0) return 0;
        }
    }
    return tmp==0;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>s;fl1=0;
        if(check(s)) fl1=1;
        if(n>1000){cout<<(fl?"Yes":"No")<<"\n";continue;}
        ss=s;
        for(i=0;i<ss.length()-1;i++){
            ss=s;
            if(ss[i]==')'&&ss[i+1]=='('){
                ss[i]='(';ss[i+1]=')';
                if(check(ss)) fl=1;
                else ss=s;
            }
        }
        cout<<(fl?"Yes":"No")<<"\n";
    }
    return 0;
}
}

思路其实也很明显了，就是死暴力，check函数就是判断这个字符串的括号是否合法，然后，20-29行就是两个字符串一个一个往后做，替换，然后判断，可以就输出，不可以就下一个

然后我看了一眼前面那个人的代码，发现是我想多了，代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int T,n,t,w,wz,i,fl1,fl2,sts;
char s[N];
void count(){
    if(s[i]=='(') t++;
    if(s[i]==')') w++;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;t=w=0;fl1=1;
        for(i=1;i<=n;i++){
            cin>>s[i];
            count();
            if(t<w){fl1=0;wz=i;}
        }
        if(t==w){
            sts=1;
            if(fl1==1){cout<<"Yes\n";sts=0;continue;}
            swap(s[wz],s[wz+1]);
            t=w=0;fl2=1;
            for(i=1;i<=n;i++){
                count();
                if(t<w) fl2=0;
            }
            if(wz==n) fl2=0;
            if(sts==1) cout<<(fl2?"Yes":"No")<<"\n";
        }else{cout<<"No\n";continue;}
    }
}

【MX-X23-T3】猜拳游戏

不会做，这个代码 10pts

#include <bits/stdc++.h>
using namespace std;

int main(){
    cout<<1;
}

试题

上海市2025CSP-J十连测Round 7.pdf

大感

我们这一次并没有批分数，所以关于上海市2025CSP-J十连测Round 7的内容我们会分为$Part 1$和$Part 2$
这一次我估计很难

上海市2025CSP-J十连测Round 7 题干

一、单项选择题

共15题、每题2分，共计30分，每题有且仅有一个正确选项。

1. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S和字母键D的顺序循环按键，即CapsLock、A、S、D、CapsLock、A、S、D……则屏幕上输出的第2025个字符是字母（）。
   A. A
   B. S
   C. D
   D. a
2. 在8位二进制补码中，10101011表示的是十进制下的（）。
   A. -85
   B. -43
   C. 43
   D. 85
3. 给定一个含N个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要$N-1$次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要（）次比较操作。（「」表示向上取整，⌊⌋表示向下取整）
   A. $\left\lceil\frac{3N}{2}\right\rceil - 2$
   B. $\left\lfloor\frac{3N}{2}\right\rfloor - 2$
   C. $2N - 2$
   D. $2N - 4$
4. 表达式$a*(b+c)-d$的后缀表达形式为（）。
   A. $abc d*+-$
   B. $abc+*d-$
   C. $abc*+d-$
   D. $-+*abcd$
5. 约定二叉树的根节点高度为1。一棵结点数为2025的二叉树最少有（）个叶子结点；一棵结点数为2025的二叉树最小的高度值是（）。
   A. 1，11
   B. 1，12
   C. 2，11
   D. 2，12
6. 向一个栈顶指针为$hs$的链式栈中插入一个指针s指向的结点时，应执行（）。
   A. $hs \to next = s;$
   B. $s \to next = hs; hs = s;$
   C. $s \to next = hs \to next; hs \to next = s;$
   D. $s \to next = hs; hs = hs \to next$
7. 2-3树是满足两个条件的树：①所有叶结点到根的路径长度相同；②所有非叶子结点有两个或三个子结点。如果一棵2-3树有10个叶结点，那么它可能有（）个非叶结点。
   A. 3
   B. 4
   C. 6
   D. 8
8. 由四个没有区别的点构成的简单无向连通图的个数是（）。
   A. 6
   B. 7
   C. 8
   D. 9
9. 设含有10个元素的集合的全部子集数为S，其中由7个元素组成的子集数为T，则$\frac{T}{S}$的值（）。
   A. $\frac{5}{32}$
   B. $\frac{15}{128}$
   C. $\frac{1}{8}$
   D. $\frac{21}{125}$
10. 如下图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由1变0，或由0变1）。现在要使得所有的格子中的数字都变为0，至少需要（）次操作。
    A. 3
    B. 4
    C. 5
    D. 6
11. 一个1×8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色，且不允许两个黑格相邻，共有（）种填涂方案。
    A. 8
    B. 55
    C. 56
    D. 64
12. 设G是有n个结点、m条边（$n \leq m$）的连通图，必须删去G的（）条边，才能使得G变成一棵树。
    A. $m - n + 1$
    B. $m - n$
    C. $m + n + 1$
    D. $n - m + 1$
13. 有7个一模一样的苹果，放到3个一样的盘子中，一共有（）种放法。
    A. 7
    B. 8
    C. 21
    D. 2187
14. 若$f_0 = 0$，$f_1 = 1$，$f_{n+1} = \frac{f_n + f_{n-1}}{2}$，则随着i的增大，$f_i$将接近于（）。
    A. $\frac{1}{2}$
    B. $\frac{2}{3}$
    C. $\frac{\sqrt{5} - 1}{2}$
    D. 1
15. 以下是32位机器和64位机器的区别是（）。
    A. 显示器不同
    B. 硬盘大小不同
    C. 寻址空间不同
    D. 输入法不同

二、阅读程序

判断题1分，选择题3分，共计40分；判断题正确填T，错误填F。

第1题

int solve1(int n) {
    n++;
    int size = 0;
    int digit[16];
    int pow = 1;
    int s = 0;
    while (n > 0) {
        digit[size] = n % 10;
        size++;
        n /= 10;
        s += pow;
        pow *= 5;
    }
    while (size > 0) {
        --size;
        pow /= 5;
        s += (digit[size] / 2) * pow;
        if (digit[size] % 2 == 0) break;
    }
    return s - 1;
}

int solve2(int n) {
    int s = 0;
    for (int i = 1; i <= n; i += 2) {
        int t = i;
        bool pass = true;
        while (t > 0) {
            int x = t % 10;
            if (x % 2 == 0) {
                pass = false;
                break;
            }
            t /= 10;
        }
        if (pass) s++;
    }
    return s;
}

保证solve1与solve2的参数n是非负整数。

判断题

16. solve1(11)的返回值为6（）。
17. solve2(12345)的返回值为906（）。
18. 对所有的$n > 0$，必有solve1(n) <= n（）。
19. solve1(0)的返回值为0（）。

选择题

20. 关于solve1(n)与solve2(n)的大小关系，当$n \geq 0$时，下列说法正确的是（）。
    A. 必然有solve1(n) < solve2(n)
    B. 必然有solve1(n) == solve2(n)
    C. 只有当n为偶数时，才有solve1(n) = solve2(n)
    D. 只有当n为奇数时，才有solve1(n) == solve2(n)
21. 若将solve1函数中第一句n++去掉，将solve2函数中for循环的i += 2改为i += 1，则新返回值与原来相比（）。
    A. solve1不变，solve2变大
    B. solve1不变，solve2变小
    C. solve1变小，solve2不变
    D. solve1变大，solve2不变
22. solve1(n)与solve2(n)的时间复杂度为（）。
    A. $\Theta(logn)$、$\Theta(logn^2)$
    B. $\Theta(logn)$、$\Theta(n)$
    C. $\Theta(logn)$、$\Theta(nlogn)$
    D. $\Theta(n)$、$\Theta(n^2)$

第2题

int a[maxn];
int b[maxn];
int n, m;
const long long mod = 1000000007;
bool filled[maxn][maxn];
long long mem[maxn][maxn];

long long solve(int i, int j) {
    if (filled[i][j]) return mem[i][j];
    if (i == n) return 1;
    if (j == m) return 1;
    filled[i][j] = true;
    if (a[i] == b[j]) {
        long long sum = solve(i + 1, j) + solve(i, j + 1);
        return mem[i][j] = sum % mod;
    } else {
        return mem[i][j] = (solve(i + 1, j) - solve(i + 1, j + 1)) % mod;
    }
}

int main() {
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < m; ++i) std::cin >> b[i];
    std::cout << (solve(0, 0) + mod) % mod << "\n";
}

判断题

23. 若依次输入数据2 2 1 3 3 1，程序返回的结果是3（）。
24. 如果$n = 0$或$m = 0$，程序返回的结果是1（）。
25. 如果两个序列完全相同，程序返回的结果是$2^n$（）。
26. 输出时，执行solve(0,0)+mod是多余的运算（）。

选择题

27. 该程序的主要功能是（）。
    A. 计算两个序列的最长公共子序列的长度
    B. 计算两个序列的公共子序列的数量
    C. 计算两个序列的公共子串的数量
    D. 计算两个序列的相同元素个数
28. 该程序的时间复杂度为（）。
    A. $\Theta(n + m)$
    B. $\Theta(n \cdot m)$
    C. $\Theta(2^{m + n})$
    D. $\Theta(nlogm)$
29. 当$a[i] = b[j]$时，返回值需要减去solve(i+1,j+1)的原因是（）。
    A. 排除重复情况
    B. 排除错误情况
    C. 优化程序的空间效率
    D. 优化程序的时间效率

第3题

long long k;
int n;
int p[20];
bool used[20] = {false};
long long frac[20];

void gen(int i) {
    if (i > n) {
        for (int i = 1; i <= n; ++i) std::cout << p[i] << " ";
        return;
    }
    for (int a = 1; a <= n; ++a) if (!used[a]) {
        if (k <= frac[n - i]) {
            p[i] = a;
            used[a] = true;
            gen(i + 1);
            return;
        } else {
            k -= frac[n - i];
        }
    }
}

int main() {
    n = 1;
    std::cin >> k;
    frac[0] = frac[1] = 1;
    while (k > frac[n]) {
        k -= frac[n];
        frac[n + 1] = frac[n] * (n + 1);
        n++;
    }
    gen(1);
}

判断题

30. 当输入k为1时候，输出1（）。
31. 当输入k为1000时候，输出1 5 2 4 3（）。

选择题

32. 关于程序输出的序列所满足的性质，错误的是（）。
    A. 输出的每个数字各不相同
    B. 输出的数字都在1到n之间
    C. 输出的相邻的数字差距不会超过1
    D. 最先输出的数字在程序中是最先被确定的
33. 下列说法正确的是（）。
    A. 越大的k一定会输出越长的序列
    B. k若是奇数，输出序列的长度一定也是奇数
    C. 程序的时间复杂度为(k!)
    D. gen递归是树形递归
34. 若程序输出的第一个数字为2，第二数字为4，剩下还有三个数字，则输入的k（）。
    A. 最小值是60，最大值是65
    B. 最小值是65，最大值是70
    C. 最小值是70，最大值是75
    D. 最小值是75，最大值是80
35. 如果使得输出序列出现7，则输入k最少需要（）。
    A. 343
    B. 874
    C. 2170
    D. 5040

三、完善程序

单选题，每小题3分，共计30分。

第1题

有一个用户，在连续的n天里，都会收到积分，也会消费积分。积分在获得后的m天内有效（m为一个给定的整数），过期失效。在第i天，用户将会获得$p_i$分，他需要消费$c_i$分。若积分不足，则用掉全部积分后用其他方式消费。消费积分时，先用最早的。当天获取的积分可以当天消费。请计算这个用户一共消费了多少积分。

const int max_size = 100000;
int queue[max_size];
int head = 0;
int tail = 0;

int main() {
    int n, m;
    std::cin >> n >> m;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        int p, c;
        std::cin >> p >> c;
        queue[_(1)_] = p;
        while (_(2)_) {
            if (_(3)_) {
                queue[head] -= c;
                sum += c;
                c = 0;
            } else {
                int amount = _(4)_;
                c -= amount;
                sum += amount;
            }
        }
        if (_(5)_ > m) {
            head++;
        }
        std::cout << sum << "\n";
    }
}

36. （1）处应填（）。
    A. tail
    B. tail + 1
    C. i + head
    D. tail++
37. （2）处应填（）。
    A. head < tail || c > 0
    B. head < tail || p > 0
    C. head < tail && c > 0
    D. head < tail && p > 0
38. （3）处应填（）。
    A. queue[head] > c
    B. queue[tail] > c
    C. queue[head + 1] > c
    D. queue[tail - 1] > c
39. （4）处应填（）。
    A. queue[head++]
    B. queue[head]
    C. queue[tail--]
    D. queue[tail]
40. （5）处应填（）。
    A. head - tail
    B. tail - head
    C. tail + head
    D. i - head + 1

第2题

给定一个1到n的排列$p_1, p_2, ..., p_n$。请统计排列中所有长度大于等于2的连续子序列的次大数之和。定义$max_2(a_i, a_{i+1}, ..., a_j)$表示从$a_i$开始到$a_j$结束的连续子序列中，排名第二大的数，这个数就是一个连续子序列的次大数之和。题目就是要求：$\sum_{1 \leq i < j \leq n} max_2(a_i, a_{i+1}, ..., a_j)$。solve用于解决这个问题。

int q[maxn];
int prev[maxn];
int next[maxn];

long long solve(int n, int p[]) {
    for (int i = 1; i <= n; ++i) {
        _(1)_;
    }
    p[0] = q[0] = prev[0] = 0;
    p[n + 1] = q[n + 1] = next[n + 1] = n + 1;
    for (int i = 1; i <= n; ++i) {
        int num = _(2)_;
        int prev_num = p[i - 1];
        int next_num = p[i + 1];
        prev[num] = _(3)_;
        next[num] = _(4)_;
    }
    long long sum = 0;
    for (int num = 1; num <= n; ++num) {
        int prev_num = prev[num];
        int prev_prev_num = prev[prev_num];
        int next_num = next[num];
        int next_next_num = next[next_num];
        sum += (long long)num * (q[num] - q[prev_num]) * _(5)_;
        sum += (long long)num * (q[next_num] - q[num]) * _(6)_;
        _(7)_ = prev_num;
        _(8)_ = next_num;
    }
    return sum;
}

41. （1）处应填（）。
    A. $q[p[i]] = i$
    B. $q[i] = p[i]$
    C. $q[i] = i$
    D. $q[p[i]] = p[i]$
42. （2）（3）（4）处应填（）。
    A. p[i]，prev_num，next_num
    B. q[i]，next_num，prev_num
    C. p[i]，next_num，prev_num
    D. q[i]，prev_num，next_num
43. （5）处应填（）。
    A. (q[prev_num] - q[prev_prev_num])
    B. (q[next_next_num] - q[prev_num])
    C. (q[next_num] - q[prev_prev_num])
    D. (q[next_next_num] - q[next_num])
44. （6）处应填（）。
    A. (q[prev_num] - q[prev_prev_num])
    B. (q[next_next_num] - q[prev_num])
    C. (q[next_num] - q[prev_prev_num])
    D. (q[next_next_num] - q[next_num])
45. （7）（8）处应填（）。
    A. prev[prev_num]，next[next_num]
    B. prev[next_num]，next[prev_num]
    C. next[prev_num]，prev[next_num]
    D. next[next_num]，prev[prev_num]