程序语言与编程实践2-> 蓝桥杯C/C++备赛记录1 | 入门了解与首周训练

寒假前班主任帮我们报了名，是得好好准备准备。作为一个CSer，coding能力一定不能太弱。我反思，好久没写C/C++代码了，净是些随手写的python脚本，刚开始上手题目bug一大堆。

由于也不是啥特别的算法竞赛，就把列入这个系列吧。整理发出来，也就是一个回顾。

00 赛事了解

00-1 oi赛制

每道题提交之后都没有任何的反馈，每个题都有多个测试点，根据通过的测试点的数量，来给予分数。每道题不限提交次数，如果提交错误没有任何惩罚，仅以最后一次提交为准，比赛过程中看不到实时排名，赛后按照总得分排名。

输入输出明确按规定来做。

00-2 基础语法

要熟悉一门语言的语法，对于我来说就是C/C++，这一点需要再翻翻书，避免一些低级错误。

00-3 算法与数据结构

这一点需要再复习一下自己的数据结构学习笔记，然后再看看网课。确保自己刷题能够不卡顿。

00-4 刷题

• 洛谷的官方题单
• 蓝桥杯真题
• 北京大学的poj
• acwing
• 力扣（只有接口函数，不是完全，所以这点不好）

递归和暴力需要多练，保证自己有办法做出来题目。另外再学学贪心、搜索（深搜极其重要、广搜一般）、动态规划。

我此前练了几十道力扣，今天注册（0310）了洛谷，做了入门题目，大致了解了一下如何把一个题目通过。

关于如何找题，这个知乎博主回答得比较好：

1. 在左侧栏里的题单广场里找，建议先做官方题单，再做用户分享题单
2. 在左侧栏里的题库里找，要搜哪道题就直接搜就行，要搜哪种题就在高级搜索里添加算法标签就行，要搜哪种难度的题直接选择，还有不要只看主题库里的题，看看CodeForces，SPOJ，AtCoder，UVA的题都不错
3. 还可以看主页的智能推荐（不过最近智能推荐挂了）
4. 终极办法（不要经常用），直接发帖求题

01 0310

01-1 P1014 [NOIP1999 普及组] Cantor 表

01-1-1 题目描述

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

1/11/1,1/21/2 , 1/31/3, 1/41/4, 1/51/5, …
2/12/1, 2/22/2 , 2/32/3, 2/42/4, …
3/13/1 , 3/23/2, 3/33/3, …
4/14/1, 4/24/2, …
5/15/1, …
…

我们以 Z 字形给上表的每一项编号。第一项是 1/11/1，然后是 1/21/2，2/12/1，3/13/1，2/22/2，…

输入格式

整数(1<= N <=10^7)。

输出格式

表中的第 N 项。

01-1-2 输入输出样例

输入

7

输出

1/4

01-1-3 解决代码

#include 
using namespace std;

int main()
{
  int n = 0, sum = 0, i = 1;
  cin >> n;
  while(sum < n)
  {
    ++i;
    //这里用for在循环上不太好，一定要让i先自增再求和，否则求出来的和少一项
    sum = i*(i - 1)/2;
    //首项公差均为1的等差数列求和，此处的和为第i行为止的Cantor表的总项数
  }
  //总项数与所找项的项数的差
  int sub = sum - n;
  if(i % 2 != 0)
  	//如果i奇数，从左开始数
    cout << i - 1 - sub << "/" << 1 + sub;
  else
    //第i行为偶数行，从右边数
    cout << 1 + sub<< "/" << i - 1 - sub;
}

01-2 P1035 [NOIP2002 普及组] 级数求和

01-2-1 题目描述

已知：

显然对于任意一个整数 k，当 n 足够大的时候，有S_n>k；现给出一个整数 k，要求计算出一个最小的 n，使得 S_n > k。

输入格式

一个正整数 k。

输出格式

一个正整数 n。

01-2-2 输入输出样例

输入

1

输出

2

01-2-3 解决代码

这个题没什么好说的，唯一值得注意的是C语言除法里的类型转换，由于sum是double，如果两个整数用 ‘/’ 运算符，会得到一个整数，所以得用1./i。

#include
using namespace std;

int main(){
    int k;
    cin >> k;
    double sum = 0;
    int count = 0,i = 1;
    while(sum <= k){
        sum += 1./i;
        count = i;
        i++;  
    }
    cout << count << endl;
    return 0;
}
//思路很简单，但最重要的是要注意1./i的数据类型转换
//改为1/i就会死循环

01-3 P1046 [NOIP2005 普及组] 陶陶摘苹果

01-3-1 题目描述

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

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

输入格式

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

输出格式

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

01-3-2 输入输出样例

输入

100 200 150 140 129 134 167 198 200 111
110

输出

5

01-3-3 解决代码

一遍过了，就是循环 / 判断结构。

#include
using namespace std;

int main(){
    int apple[10]={0};
    for(int i = 0; i < 10; i++){
        cin >> apple[i];
    }
    int height;
    cin >> height;
    int count = 0;
    for(int i = 0; i < 10; i++){
        if((height+30) >= apple[i]){
            count++;
        }
    }
    cout << count;
    return 0;
}
//值得注意的是够不着会踩板凳  +30

02 0311

02-1 P1047 [NOIP2005 普及组] 校门外的树

02-1-1 题目描述

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

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

输入格式

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

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

输出格式

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

02-1-2 输入输出样例

输入

500 3
150 300
100 200
470 471

输出

298

说明 / 提示 | 数据范围：

• 对于 20% 的数据，保证区域之间没有重合的部分。

• 对于 100% 的数据，保证：

  \[1 \leq L \leq 10^4 \\ 1 \leq m \leq 100，\\ 0 \leq u \leq v \leq L \]

02-1-3 解决代码

这基本就是查表思想，如果树在拆的范围内，就给标志一下，重复拆也是给相同的标志，最后遍历输出树的数组，如果没有标志，则说明是剩余下来的。

不过值得注意的代码后面我也列出来了：

• 弄清楚取值范围，题目中是从0到L，左闭右闭；
• 提交代码要注释掉测试的代码；

#include
using namespace std;

int main(){
    int n,m;
    cin >> n >> m;
    int A[n+1]={0};
    // for(int i = 0; i < n; i++){
    //     A[n] = 1;
    // }
    int B[m][2];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < 2; j++){
            cin >> B[i][j];
        }
    }
    // for(int i = 0; i < m; i++){
    //     for(int j = 0; j < 2; j++){
    //         cout << B[i][j]<

明明想在学校中请一些同学一起做一项问卷调查，
为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数(N≤100)，
对于其中重复的数字，只保留一个，把其余相同的数去掉，
不同的数对应着不同的学生的学号。
然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。
请你协助明明完成“去重”与“排序”的工作。

输入有两行，第1行为1个正整数，表示所生成的随机数的个数N*

第2行有N*个用空格隔开的正整数，为所产生的随机数。

输出也是两行，第1行为1个正整数M，表示不相同的随机数的个数。

第2行为M*个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

10
20 40 32 67 40 20 89 300 400 15

8
15 20 32 40 67 89 300 400

#include
#include
using namespace std;

int main(){
    int N;
    cin >> N;
    int A[N];
    for(int i  = 0; i < N; i++){
        cin >> A[i];
    }
    sort(A,A+N);
    // for(int i = 0; i < N; i++){
    //     cout << A[i] << " ";
    // }
    // 排序完成，下面看看能不能删掉重复的
    int hash[1000]={0};
    for(int i = 0; i < 1000;i++){
        for(int j = 0; j < N; j++){
            if(A[j]==i){
                hash[i]=1;
            }
        }
    }
    //cout << endl;
    int count = 0;
    int result[100]={0};
    int j = 0;
    for(int i = 0; i < 1000; i++){
        if(hash[i]==1){
            //cout << i+1 << " ";
            result[count++]=i;
        }
    }
    cout << count << endl;
    for(int i = 0; result[i]!=0&&i<100;i++){
        cout << result[i]<< " ";
    }
    //哈希表实现

    //双指针
    // for(int i = 0; i

已知正整数n是两个不同的质数的乘积，试求出两者中较大的那个质数。

一个正整数n。

一个正整数p*，即较大的那个质数。

21

7

#include
using namespace std;

int main(){
    long int num, i;
    cin >> num;
    for( i = 2 ; i * i < num; i++){
        if(num%i==0){
            break;
        }
    }
    cout << num/i <

津津上初中了。
妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。
另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。
但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。
假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。
请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。

输入包括7行数据，分别表示周一到周日的日程安排。
每行包括两个小于10的非负整数，用空格隔开，
分别表示津津在学校上课的时间和妈妈安排她上课的时间。

一个数字。如果不会不高兴则输出0，
如果会则输出最不高兴的是周几
（用1, 2, 3, 4, 5, 6, 71,2,3,4,5,6,7分别表示周一，周二，周三，周四，周五，周六，周日）。
如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。

5 3
6 2
7 2
5 3
5 4
0 4
0 6

3

#include
#include
using namespace std;

int main(){
    int data[7][2],sum[7];
    for(int i = 0 ; i < 7; i++){
        for(int j = 0; j < 2; j++){
            cin >> data[i][j];
        }
    }
    for(int i = 0; i < 7; i++){
        sum[i] = data[i][0] + data[i][1];
    }
    int count = 0, tag = 0;
    for(int i = 0; i < 7; i++){
        if(sum[i]<=8){
            tag++;
            continue;
        }
        else{
            int* temp = max_element(sum,sum+7);
            for(int j = 0; j < 7; j++){
               if(sum[j]==*temp){
                   cout << j+1 <

#include
using namespace std;

int main(){
    int num1，num2, sum;
    int day = 0, max = 0;
    for(int i = 1; i < 8; i++){
        cin >> a >>b;
        sum = num1 + num2;
        if((s > max)&&(sum>8)){
            max = sum;
            day =i;
        }
    }
    cout << day;
    return 0;
}

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。
因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，
如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。津津预计1111月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，
X表示出现这种情况的第一个月；
否则输出到20042004年年末津津手中会有多少钱。

注意，洛谷不需要进行文件输入输出，而是标准输入输出。

290
230
280
200
300
170
340
50 
90 
80 
200
60 

-7 

290 
230 
280 
200 
300 
170 
330 
50 
90 
80 
200 
60 

1580

//上面思路走不下去，借鉴题解再来一次
#include
using namespace std;
int main(){
    int money = 0, cost[12] = {0}, save = 0, flag = 1, failid = 0;
    for(int i = 0; i < 12; i++){
        cin >> cost[i];
    }
    for(int i = 1; i <= 12; i++){
        money+=300;
        //cin >> cost;
        money-=cost[i-1];
        if(money<0){
            flag = 0;
            //说明已经透支
            failid = i;
            break;
        }
        save+=money/100;//用100的个数代替100
        money%=100;//存款后剩余的前
        //与我最初的思路相差在于，我冗余了一个判断是否超过100的语句
        //事实上money不超过100的话，%100还是它自己。

    }
    if(flag==1){
        money+=save*120;
        cout << money;
    }
    else{
        cout <<-failid;
    }
    return 0;
}