2025.10.11 P1007 独木桥

题目背景

战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 $1$ 个人通过。假如有 $2$ 个人相向而行在桥上相遇，那么他们 $2$ 个人将无法绕过对方，只能有 $1$ 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。

题目描述

突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为 $L$，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 $1$，但一个士兵某一时刻来到了坐标为 $0$ 或 $L+1$ 的位置，他就离开了独木桥。

每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。

由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

输入格式

第一行共一个整数 $L$，表示独木桥的长度。桥上的坐标为 $1, 2, \cdots, L$。

第二行共一个整数 $N$，表示初始时留在桥上的士兵数目。

第三行共有 $N$ 个整数，分别表示每个士兵的初始坐标。

输出格式

共一行，输出 $2$ 个整数，分别表示部队撤离独木桥的最小时间和最大时间。$2$ 个整数由一个空格符分开。

输入输出样例 #1

输入 #1

1
2
3
>4
>2
>1 3

输出 #1

1
>2 4

说明/提示

对于 $100%$ 的数据，满足初始时，没有两个士兵同在一个坐标，$1\le L\le5\times 10^3$，$0\le N\le5\times10^3$，且数据保证 $N\le L$。

我的代码

1

2025.10.11 P1093 [NOIP 2007 普及组] 奖学金

题目背景

NOIP2007 普及组 T1

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 $5$ 名学生发奖学金。期末，每个学生都有 $3$ 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 $3$ 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

注意，在前 $5$ 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分) 是：

1
2
>7 279  
>5 279

这两行数据的含义是：总分最高的两个同学的学号依次是 $7$ 号、$5$ 号。这两名同学的总分都是 $279$ (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 $7$ 的学生语文成绩更高一些。

如果你的前两名的输出数据是：

1
2
>5 279  
>7 279

则按输出错误处理，不能得分。

输入格式

共 $n+1$ 行。

第 $1$ 行为一个正整数 $n \le 300$，表示该校参加评选的学生人数。

第 $2$ 到 $n+1$ 行，每行有 $3$ 个用空格隔开的数字，每个数字都在 $0$ 到 $100$ 之间。第 $j$ 行的 $3$ 个数字依次表示学号为 $j-1$ 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 $1\sim n$（恰好是输入数据的行号减 $1$）。

保证所给的数据都是正确的，不必检验。

输出格式

共 $5$ 行，每行是两个用空格隔开的正整数，依次表示前 $5$ 名学生的学号和总分。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
>6
>90 67 80
>87 66 91
>78 89 91
>88 99 77
>67 89 64
>78 89 98

输出 #1

1
2
3
4
5
>6 265
>4 264
>3 258
>2 244
>1 237

输入输出样例 #2

输入 #2

1
2
3
4
5
6
7
8
9
>8
>80 89 89
>88 98 78
>90 67 80
>87 66 91
>78 89 91
>88 99 77
>67 89 64
>78 89 98

输出 #2

1
2
3
4
5
>8 265
>2 264
>6 264
>1 258
>5 258

我的代码

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
#include<iostream>
using namespace std;
struct sct{
int yw;
int sx;
int yy;
int id;
int sum;
}arr[305];
bool structSort(sct x,sct y){
if(x.sum!=y.sum){
return x.sum>y.sum;
}else{
if(x.yw!=y.yw){
return x.yw>y.yw;
}else{
return x.id<y.id;
}
}
}
int main(){
int n=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i].yw>>arr[i].sx>>arr[i].yy;
arr[i].sum=arr[i].yw+arr[i].sx+arr[i].yy;
arr[i].id=i+1;
}
for(int i=n;i>0;i--){
for(int j=0;j<i;j++){
if(structSort(arr[j],arr[j+1])){
sct temp =arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}            
}
}
int index =n;
for(int i=0;i<5;i++){
cout<<arr[index].id<<" "<<arr[index].sum<<endl;
index--;
}
return 0;
}

2025.10.10 P13787 地毯 加强版

题目描述

在 $n\times n$ 的格子上有 $m$ 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 $n,m$。意义如题所述。

接下来 $m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。

输出格式

为了减少输出量，设 $F_{i,j}$ 表示 $(i,j)$ 这个格子被多少个地毯覆盖，你只需要输出 $\sum_{i=1}^n\sum_{j=1}^n (i+j)\oplus F_{i,j}$ 的值。注意这个值可能会超过 $2^{31}$。

输入输出样例 #1

输入 #1

1
2
3
4
>5 3
>2 2 3 3
>3 3 5 5
>1 2 1 4

输出 #1

1
>146

说明/提示

对于 $50%$ 的数据，有 $n,m\le 5000$。

对于 $100%$ 的数据，有 $n\le 5000$，$m\le 2\times 10^5$。

我的答案

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
#include<iostream>
using namespace std;
int main(){
int n;
int m;
cin>>n>>m;
int arr[5002][5002]={0};
for(int i =0;i<m;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
arr[x1][y1]++;
arr[x1][y2+1]--;
arr[x2+1][y1]--;
arr[x2+1][y2+1]++;
}
long long sum=0;
for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
arr[i][j]+=arr[i][j-1]+arr[i-1][j]-arr[i-1][j-1];
sum+=((i+j)^arr[i][j]);
// cout<<arr[i][j]<<" ";
}
// cout<<endl;
}
cout<<sum;
   return 0;
}

2025.10.10 P3397 地毯

题目背景

加强版

题目描述

在 $n\times n$ 的格子上有 $m$ 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 $n,m$。意义如题所述。

接下来 $m$ 行，每行两个坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$，代表一块地毯，左上角是 $(x_1,y_1)$，右下角是 $(x_2,y_2)$。

输出格式

输出 $n$ 行，每行 $n$ 个正整数。

第 $i$ 行第 $j$ 列的正整数表示 $(i,j)$ 这个格子被多少个地毯覆盖。

输入输出样例 #1

输入 #1

1
2
3
4
>5 3
>2 2 3 3
>3 3 5 5
>1 2 1 4

输出 #1

1
2
3
4
5
>0 1 1 1 0
>0 1 1 0 0
>0 1 2 1 1
>0 0 1 1 1
>0 0 1 1 1

说明/提示

样例解释

覆盖第一个地毯后：

$0$ $0$ $0$ $0$ $0$
$0$ $1$ $1$ $0$ $0$
$0$ $1$ $1$ $0$ $0$
$0$ $0$ $0$ $0$ $0$
$0$ $0$ $0$ $0$ $0$

覆盖第一、二个地毯后：

$0$ $0$ $0$ $0$ $0$
$0$ $1$ $1$ $0$ $0$
$0$ $1$ $2$ $1$ $1$
$0$ $0$ $1$ $1$ $1$
$0$ $0$ $1$ $1$ $1$

覆盖所有地毯后：

$0$ $1$ $1$ $1$ $0$
$0$ $1$ $1$ $0$ $0$
$0$ $1$ $2$ $1$ $1$
$0$ $0$ $1$ $1$ $1$
$0$ $0$ $1$ $1$ $1$

数据范围

对于 $20%$ 的数据，有 $n\le 50$，$m\le 100$。

对于 $100%$ 的数据，有 $n,m\le 1000$。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int main(){
int n;
int m;
cin>>n>>m;
int arr[1002][1002]={0};
for(int i =0;i<m;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
arr[x1][y1]++;
arr[x1][y2+1]--;
arr[x2+1][y1]--;
arr[x2+1][y2+1]++;
}
for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
arr[i][j]+=arr[i][j-1]+arr[i-1][j]-arr[i-1][j-1];
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
   return 0;
}

2025.10.10 P1055 [NOIP 2008 普及组] ISBN 号码

题目描述

每一本正式出版的图书都有一个 ISBN 号码与之对应，ISBN 码包括 $9$ 位数字、$1$ 位识别码和 $3$ 位分隔符，其规定格式如 x-xxx-xxxxx-x，其中符号 - 就是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言，例如 $0$ 代表英语；第一个分隔符 - 之后的三位数字代表出版社，例如 $670$ 代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。

识别码的计算方法如下：

首位数字乘以 $1$ 加上次位数字乘以 $2$ ……以此类推，用所得的结果 $ \bmod 11$，所得的余数即为识别码，如果余数为 $10$，则识别码为大写字母 $X$。例如 ISBN 号码 0-670-82162-4 中的识别码 $4$ 是这样得到的：对 067082162 这 $9$ 个数字，从左至右，分别乘以 $1,2,\dots,9$ 再求和，即 $0\times 1+6\times 2+……+2\times 9=158$，然后取 $158 \bmod 11$ 的结果 $4$ 作为识别码。

你的任务是编写程序判断输入的 ISBN 号码中识别码是否正确，如果正确，则仅输出 Right；如果错误，则输出你认为是正确的 ISBN 号码。

输入格式

一个字符序列，表示一本书的 ISBN 号码（保证输入符合 ISBN 号码的格式要求）。

输出格式

一行，假如输入的 ISBN 号码的识别码正确，那么输出 Right，否则，按照规定的格式，输出正确的 ISBN 号码（包括分隔符 -）。

输入输出样例 #1

输入 #1

1
>0-670-82162-4

输出 #1

1
>Right

输入输出样例 #2

输入 #2

1
>0-670-82162-0

输出 #2

1
>0-670-82162-4

说明/提示

2008 普及组第一题

我的答案

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
#include<iostream>
using namespace std;
int main() {
//一共十三个字符
char arr[10] = {0};
int index = 0;
int sum = 0;
for (int i = 0;i < 12;i++) {
char ch;
cin >> ch;
if (ch >= '0' && ch <= '9') {
arr[index] = ch;
index++;
sum += (ch - '0') * (index);
}
}
char ch;
cin >> ch;
if (ch == 'X'||(ch >= '0' && ch <= '9')) {
arr[index++] = ch;
}
   int mo = sum % 11;
   // cout << mo << endl;
   // cout << arr[9] << endl;
   // cout << arr[9] - '0' << endl;
   if (mo == (arr[9] - '0')||(mo==10&&arr[9]=='X')) {
       cout << "Right";
       return 0;
   }else{
       int index = 0;
       for(int i=0;i<12;i++){
           if(i==1||i==5||i==11){
               cout<<"-";
           }else{
               cout<<arr[index++];
           }
       }
       if(mo==10){
           cout<<"X";
           return 0;
       }
       cout << mo;
   }
   return 0;
}

2025.10.09 P1051 [NOIP 2005 提高组] 谁拿了最多奖学金

题目描述

某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：

  1. 院士奖学金，每人 $8000$ 元，期末平均成绩高于 $80$ 分（$>80$），并且在本学期内发表 $1$ 篇或 $1$ 篇以上论文的学生均可获得；
  2. 五四奖学金，每人 $4000$ 元，期末平均成绩高于 $85$ 分（$>85$），并且班级评议成绩高于 $80$ 分（$>80$）的学生均可获得；
  3. 成绩优秀奖，每人 $2000$ 元，期末平均成绩高于 $90$ 分（$>90$）的学生均可获得；
  4. 西部奖学金，每人 $1000$ 元，期末平均成绩高于 $85$ 分（$>85$）的西部省份学生均可获得；
  5. 班级贡献奖，每人 $850$ 元，班级评议成绩高于 $80$ 分（$>80$）的学生干部均可获得；

只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是 $87$ 分，班级评议成绩 $82$ 分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是 $4850$ 元。

现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。

输入格式

第一行是$1$个整数 $N$，表示学生的总数。

接下来的 $N$ 行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过 $20$ 的字符串（不含空格）；期末平均成绩和班级评议成绩都是 $0$ 到 $100$ 之间的整数（包括 $0$ 和 $100$）；是否是学生干部和是否是西部省份学生分别用 $1$ 个字符表示，$\tt Y$ 表示是，$\tt N$ 表示不是；发表的论文数是 $0$ 到 $10$ 的整数（包括 $0$ 和 $10$）。每两个相邻数据项之间用一个空格分隔。

输出格式

共 $3$ 行。

  • 第 $1$ 行是获得最多奖金的学生的姓名。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。
  • 第 $2$ 行是这名学生获得的奖金总数。
  • 第 $3$ 行是这 $N$ 个学生获得的奖学金的总数。

输入输出样例 #1

输入 #1

1
2
3
4
5
>4
>YaoLin 87 82 Y N 0
>ChenRuiyi 88 78 N Y 1
>LiXin 92 88 N N 0
>ZhangQin 83 87 Y N 1

输出 #1

1
2
3
>ChenRuiyi
>9000
>28700

说明/提示

【数据范围】

对于 $100%$ 的数据，满足 $1 \le N \le 100$。

【题目来源】

NOIP 2005 提高组第一题

我的答案

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
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
int main(){
//结果变量
int N=0;
string finalName;
int max=0;
long allSum=0;
   //临时变量
   string name;
   int score1;
   int score2;
   char b1;
   char b2;
   int num;
   cin>>N;
   for(int i=0;i<N;i++){
           cin>>name>>score1>>score2>>b1>>b2>>num;
       int money=0;
       if(score1>80&&num>=1){
           money+=8000;
       }
       if(score1>85&&score2>80){
           money+=4000;
       }
       if(score1>90){
           money+=2000;
       }
       if(score1>85&&b2=='Y'){
           money+=1000;
       }
       if(score2>80&&b1=='Y'){
           money+=850;
       }
           allSum+=money;
           if(max<money){
               max=money;
               finalName=name;
           }
   }
   cout<<finalName<<endl;
   cout<<max<<endl;
   cout<<allSum<<endl;
   return 0;
}

2025.10.08 P1090 [NOIP 2004 提高组] 合并果子

题目背景

P6033 为本题加强版。

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

输入格式

共两行。
第一行是一个整数 $n(1\leq n\leq 10000)$ ，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i(1\leq a_i\leq 20000)$ 是第 $i$ 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$ 。

输入输出样例 #1

输入 #1

1
2
>3 
>1 2 9

输出 #1

1
>15

说明/提示

对于 $30%$ 的数据，保证有 $n \le 1000$；

对于 $50%$ 的数据，保证有 $n \le 5000$；

对于全部的数据，保证有 $n \le 10000$。

我的答案

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
#include<iostream>
#include<queue>
#include<vector>
int main() {
   int n;
   std::cin >> n;
   std::priority_queue<int,std::vector<int>,std::greater<int> > que;
   for (int i = 0;i < n;i++) {
       int temp=0;
       std::cin >> temp;
       que.push(temp);
   }
   //some代表暂时合成的那堆
   int some=0;
   //结果
   int result = 0;
   while (que.size()>1) {
       int first = que.top();
       que.pop();
       int second = que.top();
       que.pop();
       some = first + second;
       result += some;
       que.push(some);
   }
   //输出
   std::cout << result << std::endl;
   return 0;
}

2025.10.8 P1035 [NOIP 2002 普及组] 级数求和

题目描述

已知：$S_n= 1+\dfrac{1}{2}+\dfrac{1}{3}+…+\dfrac{1}{n}$。显然对于任意一个整数 $k$，当 $n$ 足够大的时候，$S_n>k$。

现给出一个整数 $k$，要求计算出一个最小的 $n$，使得 $S_n>k$。

输入格式

一个正整数 $k$。

输出格式

一个正整数 $n$。

输入输出样例 #1

输入 #1

1
>1

输出 #1

1
>2

说明/提示

【数据范围】

对于 $100%$ 的数据，$1\le k \le 15$。

【题目来源】

NOIP 2002 普及组第一题

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
int main() {
   double s = 0;
   double n = 0;
   int k;
   std::cin >> k;
   while (s <= k) {
       s += 1.0 / ++n;
   }
   int result = n;
   std::cout << result << std::endl;
   return 0;
}

2025.10.07 P1143 进制转换

题目描述

请你编一程序实现两种不同进制之间的数据转换。

输入格式

共三行，第一行是一个正整数，表示需要转换的数的进制 $n\ (2\le n\le 16)$，第二行是一个 $n$ 进制数，若 $n>10$ 则用大写字母 $\verb!A!\sim \verb!F!$ 表示数码 $10\sim 15$，并且该 $n$ 进制数对应的十进制的值不超过 $10^9$，第三行也是一个正整数，表示转换之后的数的进制 $m\ (2\le m\le 16)$。

输出格式

一个正整数，表示转换之后的 $m$ 进制数。

输入输出样例 #1

输入 #1

1
2
3
>16
>FF
>2

输出 #1

1
>11111111

我的答案

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
#include<stdio.h>
#include<string.h>
#include<math.h>
int main() {
   int n=0;
   scanf("%d",&n);
   char num[31];
       scanf("%s", num);
       int len = strlen(num);
       int tenNum = 0;
       int templen = len-1;
       for (int i = 0;i < len;i++) {
           if (num[i] >= 'A' && num[i] <= 'F') {
                       num[i] -= ('A' - 10);
           }
           else if (num[i] >= '0' && num[i] <= '9') {
			num[i] -= '0';
           }
           tenNum += num[i] * pow(n,templen);
           templen--;
       }
       int goal = 0;
       scanf("%d", &goal);
       char result[100];
       int temp = 1;
	int index = 0;
       if(tenNum==0){
           printf("0");
           return 0;
	}
	int digit = 0;
       while (tenNum > 0) {
		digit = tenNum % goal;
           if (digit < 10) {
			result[index++] = digit + '0';
           }
           else {
			result[index++] = digit - 10 + 'A';
           }
           tenNum /= goal;
  //         result += (tenNum% goal)*temp;
		//temp *= 10;
  //         tenNum /= goal;
       }
       for (int i = index - 1;i >= 0;i--) {
		printf("%c", result[i]);
       }
   return 0;
}

2025.10.06 P2367 语文成绩

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 $n$，$p$，代表学生数与增加分数的次数。

第二行有 $n$ 个数，$a_1 \sim a_n$，代表各个学生的初始成绩。

接下来 $p$ 行，每行有三个数，$x$，$y$，$z$，代表给第 $x$ 个到第 $y$ 个学生每人增加 $z$ 分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

输入输出样例 #1

输入 #1

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

输出 #1

1
>2

说明/提示

对于 $40%$ 的数据，有 $n \le 10^3$。

对于 $60%$ 的数据，有 $n \le 10^4$。

对于 $80%$ 的数据，有 $n \le 10^5$。

对于 $100%$ 的数据，有 $n \le 5\times 10^6$，$p \le n$，学生初始成绩 $ \le 100$，$z \le 100$。

我的答案

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
#include<iostream>
#include<algorithm>
int main() {
int n = 0, p = 0;
std::cin >> n >> p;
int arr[n];
int diff[n+2];
for (int i = 0;i < n;i++) {
std::cin >> arr[i];
}
for(int i=0;i<n+2;i++){
diff[i]=0;
}
for(int i =0;i<p;i++){
int start=0;
int end=0;
int plus=0;
std::cin>>start>>end>>plus;
int left=start-1;
int right=end;
diff[left]+=plus;
diff[right]-=plus;
}
// for (int i = 0;i < p;i++) {
//     int start = 0, end = 0, plus = 0;
//     std::cin >> start >> end >> plus;
//     for (int j = start - 1;j < end;j+=2) {
//         arr[j] += plus;
//         arr[j+1]+=plus;
//     }
// }
int sum=0;
for(int i=0;i<n;i++){
sum+=diff[i];
arr[i]+=sum;
}
int min = arr[0];
for (int i = 0;i < n;i++) {
min = std::min(arr[i], min);
}
std::cout << min << std::endl;
return 0;
}

2025.10.06 P1047 [NOIP 2005 普及组] 校门外的树

题目描述

某校大门外长度为 $l$ 的马路上有一排树，每两棵相邻的树之间的间隔都是 $1$ 米。我们可以把马路看成一个数轴，马路的一端在数轴 $0$ 的位置，另一端在 $l$ 的位置；数轴上的每个整数点，即 $0,1,2,\dots,l$，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

第一行有两个整数，分别表示马路的长度 $l$ 和区域的数目 $m$。

接下来 $m$ 行，每行两个整数 $u, v$，表示一个区域的起始点和终止点的坐标。

输出格式

输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

输入输出样例 #1

输入 #1

1
2
3
4
>500 3
>150 300
>100 200
>470 471

输出 #1

1
>298

说明/提示

【数据范围】

  • 对于 $20%$ 的数据，保证区域之间没有重合的部分。
  • 对于 $100%$ 的数据，保证 $1 \leq l \leq 10^4$，$1 \leq m \leq 100$，$0 \leq u \leq v \leq l$。

【题目来源】

NOIP 2005 普及组第二题

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
int main(){
   int l=0,m=0;
   std::cin>>l>>m;
   int arr[l+1];
   for(int i =0;i<=l;i++){
       arr[i]=0;
   }
   for(int i=0;i<m;i++){
       int start,end;
       std::cin>>start>>end;
       for(int i =start;i<=end;i++){
           arr[i]=1;
       }
   }
   int count=0;
   for(int i=0;i<=l;i++){
       if(arr[i]==0){
           count++;
       }
   }
   std::cout<<count<<std::endl;
   return 0;
}

2025.10.05 P1106 删数问题

题目描述

键盘输入一个高精度的正整数 $n$（不超过 $250$ 位），去掉其中任意 $k$ 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 $n$ 和 $k$，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。

第一行输入一个高精度的正整数 $n$。

第二行输入一个正整数 $k$，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

输入输出样例 #1

输入 #1

1
2
>175438 
>4

输出 #1

1
>13

说明/提示

用 $\operatorname{len}(n)$ 表示 $n$ 的位数，保证 $1 \leq k < \operatorname{len}(n) \leq 250$。

注意：去掉若干数字后剩下的数可以存在前导零，而输出时不要输出前导零。

我的答案

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
#include<stdio.h>
#include<string.h>

// int getDigit (int num,int n,int N){

//     n=N/n-1;
//     for(int i =0;i<n;i++){
//         num/=10;
//     }
//     return num%10;
// }

int main(){
   char n[251];
   scanf("%s",n);
   int k=0;
   scanf("%d",&k);
   int len = strlen(n);
   // for(int i =0;i<count;i++){
   //     // if(getDigit(n,i,count)>getDigit(n,i-1,count)&&getDigit(n,i,count)<getDigit(n,i+1,count)){
   //     // }
   //     arr[i]=getDigit(n,i,count);
   // }
   for(int l=0;l<k;l++){
       int tempBoolean=0;
       for(int i =0;i<len-1;i++){
       if(n[i]>n[i+1]){
           for(int j=i;j<len-1;j++){
               n[j]=n[j+1];
           }
           len--;
           tempBoolean=1;
           break;
       }
   }
       if(tempBoolean==0){
           len--;
       }
   }
   int first=0;
   while(n[first]=='0'){
       first++;
   }
   if(first>=len){
       printf("0");
   }else{
           for(int i=first;i<len;i++){
       printf("%c",n[i]);
   }
   }
   return 0;
}


2025.10.05 P8598 [蓝桥杯 2013 省 AB] 错误票据

题目背景

某涉密单位下发了某种票据，并要在年终全部收回。

题目描述

每张票据有唯一的 ID 号，全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。

你的任务是通过编程，找出断号的 ID 和重号的 ID。

数据保证断号不可能发生在最大和最小号。

输入格式

一个整数 $N(N<100)$ 表示后面数据行数，接着读入 $N$ 行数据，每行数据长度不等，是用空格分开的若干个（不大于 $100$ 个）正整数（不大于 $10^5$），每个整数代表一个 ID 号。

输出格式

要求程序首先输入要求程序输出 $1$ 行，含两个整数 $m$，$n$，用空格分隔，其中，$m$ 表示断号 ID，$n$ 表示重号 ID。

输入输出样例 #1

输入 #1

1
2
3
>2
>5 6 8 11 9
>10 12 9

输出 #1

1
>7 9

输入输出样例 #2

输入 #2

1
2
3
4
5
6
7
>6
>164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
>172 189 127 107 112 192 103 131 133 169 158
>128 102 110 148 139 157 140 195 197
>185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
>149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
>113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119

输出 #2

1
>105 120

我的答案

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
#include<stdio.h>
#include<stdbool.h>

int main(){
   int N=0;
   int index=0;
   int arr[10000];
   int number;
   scanf("%d",&N);
   for(int i =0;i<N;i++){
       while(scanf("%d",&number)==1){
           // scanf("%d",&number);
           arr[index]=number;
           index++;
           if(getchar()=='\n'){
               break;
           }
       }
   }
   for(int i=0;i<(index-1);i++){
       for(int j=0;j<(index-1);j++){
           if(arr[j]>arr[j+1]){
               int temp = arr[j+1];
               arr[j+1] = arr[j];
               arr[j]=temp;
           }
       }
   }
   int duan=0;
   int chong=0;
   for(int i = 0 ;i<index;i++){
       if(arr[i+1]-arr[i]>1){
           duan = arr[i]+1;
       }
       if(arr[i+1]==arr[i]){
           chong =arr[i];
       }
   }
   printf("%d %d",duan,chong);
   return 0;
}

2025.10.04 P8637 [蓝桥杯 2016 省 B] 交换瓶子

题目描述

有 $N$ 个瓶子，编号 $1 \sim N$，放在架子上。

比如有 $5$ 个瓶子：

$$2,1,3,5,4$$

要求每次拿起 $2$ 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

$$1,2,3,4,5$$

对于这么简单的情况，显然，至少需要交换 $2$ 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式

第一行：一个正整数 $N$（$N<10000$），表示瓶子的数目。

第二行：$N$ 个正整数，用空格分开，表示瓶子目前的排列情况。

输出格式

输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。

输入输出样例 #1

输入 #1

1
2
>5
>3 1 2 5 4

输出 #1

1
>3

输入输出样例 #2

输入 #2

1
2
>5
>5 4 3 2 1

输出 #2

1
>2

说明/提示

时限 1 秒, 256M。蓝桥杯 2016 年第七届省赛

蓝桥杯 2016 年省赛 B 组 I 题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
int main(){

   int arr[10000];
   int num=0;
   int count=0;
   scanf("%d",&num);
   for(int i = 0;i<num;i++){
       scanf("%d",&arr[i]);
       
   }
   for(int i=0;i<num;i++){
       if(arr[i]!=(i+1)){
           int index = arr[i]-1;
           int temp = arr[index];
           arr[index] = arr[i];
           arr[i] = temp;
           count++;
           i--;
       }
   }
   printf("%d",count);
   return 0;
}

2025.10.04 P8706 [蓝桥杯 2020 省 AB1] 解码

题目描述

小明有一串很长的英文字母，可能包含大写和小写。

在这串字母中，有很多连续的是重复的。小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 + 出现次数的形式。 例如，连续的 $5$ 个 a，即 aaaaa，小明可以简写成 a5（也可能简写成 a4a、aa3a 等）。

对于这个例子：HHHellllloo，小明可以简写成 H3el5o2。为了方便表达，小明不会将连续的超过9个相同的字符写成简写的形式。

现在给出简写后的字符串，请帮助小明还原成原来的串。

输入格式

输入一行包含一个字符串。

输出格式

输出一个字符串，表示还原后的串。

输入输出样例 #1

输入 #1

1
>H3el5o2

输出 #1

1
>HHHellllloo

说明/提示

对于所有评测用例，字符串由大小写英文字母和数字组成，长度不超过 $100$。请注意原来的串长度可能超过 $100$。

蓝桥杯 2020 第一轮省赛 A 组 F 题（B 组 G 题）。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<string.h>
int main(){
   char str[110];
   scanf("%s",str);
   int len = strlen(str);
   // for(int i =0;i<110;i++){
   //     scanf("%c",&str[i]);
   // }
   for(int i=0;i<len;i++){
       if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')){
           if(str[i+1]>='0'&&str[i+1]<='9'){
               for(int j=0;j<str[i+1]-'0';j++){
                   printf("%c",str[i]);
               }
           }else{
               printf("%c",str[i]);
           }
       }
   }
   return 0;
}

2025.10.03 P1115 最大子段和

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

1
2
>7
>2 -4 3 -1 2 -4 3

输出 #1

1
>4

说明/提示

样例 1 解释

选取 $[3, 5]$ 子段 ${3, -1, 2}$，其和为 $4$。

数据规模与约定

  • 对于 $40%$ 的数据，保证 $n \leq 2 \times 10^3$。
  • 对于 $100%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$-10^4 \leq a_i \leq 10^4$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>

int main() {
   int n;
   scanf("%d", &n);
   int arr[n];
   for (int i = 0;i < n;i++) {
       scanf("%d", &arr[i]);
   }
   int max = arr[0];
   int current_max =arr[0];
   for (int i = 1;i < n;i++) {
       if(current_max>0){
           current_max =current_max+arr[i];
       }else{
           current_max =arr[i];
       }
       if(current_max>max){
           max=current_max;
       }
   }
   printf("%d", max);
   return 0;
}

2025.10.03 P8680 [蓝桥杯 2019 省 B] 特别数的和

题目描述

小明对数位中含有 $2$、$0$、$1$、$9$ 的数字很感兴趣（不包括前导 $0$），在 $1$ 到 $40$ 中这样的数包括 $1$、$2$、$9$、$10$ 至 $32$、$39$ 和 $40$，共 $28$ 个，他们的和是 $574$。

请问，在 $1$ 到 $n$ 中，所有这样的数的和是多少？

输入格式

输入一行包含一个整数 $n$。

输出格式

输出一行，包含一个整数，表示满足条件的数的和。

输入输出样例 #1

输入 #1

1
>40

输出 #1

1
>574

说明/提示

对于 $20%$ 的评测用例，$1 \le n \le 10$。

对于 $50%$ 的评测用例，$1 \le n \le 100$。

对于 $80%$ 的评测用例，$1 \le n \le 1000$。

对于所有评测用例，$1 \le n \le 10000$。

蓝桥杯 2019 省赛 B 组 F 题。

我的答案

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

#include<stdio.h>
#include<stdbool.h>
int main() {
   int n;
   int count = 0;
   int digit = 0;
   int num = 1;
   int sum = 0;
   scanf("%d", &n);
   for (int i = 1;i <= n;i++) {
       int tempNum = i;
           if (tempNum / num != 0) {
               num = num * 10;
               digit++;
           }
           int a = num;
           int temp = tempNum;
       while (true) {
           tempNum = temp / (a/10);
           temp = temp % (a / 10);
           if (tempNum== 2 || tempNum == 0 || tempNum== 1 || tempNum== 9) {
               sum += i;
               count++;
               break;
           }
           a = a /10;
           if (a==1) {
               break;
           }
       }
   }
   printf("%d", sum);
   return 0;
}

2025.10.02 P1046 [NOIP 2005 普及组] 陶陶摘苹果

题目描述

陶陶家的院子里有一棵苹果树，每到秋天树上就会结出 $10$ 个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个 $30$ 厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。

现在已知 $10$ 个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。

输入格式

输入包括两行数据。第一行包含 $10$ 个 $100$ 到 $200$ 之间（包括 $100$ 和 $200$）的整数（以厘米为单位）分别表示 $10$ 个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个 $100$ 到 $120$ 之间（包含 $100$ 和 $120$）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。

输出格式

输出包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。

输入输出样例 #1

输入 #1

1
2
>100 200 150 140 129 134 167 198 200 111
>110

输出 #1

1
>5

说明/提示

【题目来源】

NOIP 2005 普及组第一题

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
int main() {
   int chair = 30;
   int height;
   int count = 0;
   int heightAll;
   int arr[10];
   int i;
   for (i = 0;i < 10;i++) {
       scanf("%d", &arr[i]);
   }
   scanf("%d", &height);
   heightAll = height + chair;
   //printf("heightAll=%d\n",heightAll);
   for (int j = 0;j < 10;j++) {
       if (heightAll>=arr[j]) {
           count++;
       }
   }
   printf("%d", count);
   return 0;
}

2025.10.01 B2002 Hello,World!

题目描述

编写一个能够输出 Hello,World! 的程序。

提示：

  • 使用英文标点符号；
  • Hello,World! 逗号后面没有空格。
  • H 和 W 为大写字母。

输入格式

无

输出格式

无

输入输出样例 #1

输入 #1

1
>无

输出 #1

1
>Hello,World!

我的答案

1
2
3
4
5
#include<stdio.h>
int main (){
printf("Hello,World!");
}