机试指南:Ch1:绪论 Ch2:枚举和模拟

发布时间:2024年01月21日

文章目录

第1章 绪论

(1)如何准备机试

机试:做过的题目考试时一定要做对。第一次见的题目基本上是做不出来。机试只有满分和零分。所以要多刷题,且保证刷一道精一道,保证下次再做一定是满分。

考研机试的题目是有题库的,都是原题。


在这里插入图片描述


(2)OJ和开发环境简介

1.OJ,Online Judge,在线评测系统

在这里插入图片描述


2.集成开发环境 IDE (integrated development environment)

重型IDE:Clion

在这里插入图片描述




例题1:a+b
提交网址:百练OJ

#include <stdio.h>

int main() {
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",a+b);
    return 0;
}

scanf和printf包含在头文件<stdio.h>中,而不在<iostream>中,不规范。虽然有的编译器默认链接<stdio.h>。


测试案例有多行:while((xxx)!= EOF) { }

#include <cstdio>

int main(){
    int a,b;
    while(scanf("%d %d",&a,&b) != EOF){
        printf("%d\n",a+b);
    }
    return 0;
}

C++中,<stdio.h>写作<cstdio>,功能是一样的,但名字不同。
C++标准为了和C区别开,也为了正确地使用命名空间,规定头文件不使用后缀.h



(3)OJ的原理、OJ的几种情况

1.OJ原理
在这里插入图片描述


2.OJ的几种情况:
Compilation Error:编译错误,语法问题,可能是复制粘贴少了东西,如}
Presentation Error:多了换行
Wrong Answer:边界问题
Accepted:通过

在这里插入图片描述


(4)学习建议


(5)23版内容

1.安装IDE:clion或vs
新手不要直接在clion上写代码,要在强大的IDE(集成开发环境)中练习,能方便的找出低级错误。
在IDE上通过后,再把代码复制到OJ中。

2.OJ的运行原理:OJ不会直接评判代码,而是用测试用例来测试你的输出结果是否与它的答案相符。如此便能在某些情况下“作弊”。
若OJ中某个测试用例超时,可以提前准备好答案,以便通过用例。例如,“打表”。

3.机试需要的函数:输入(scanf 或 cin)、输出(printf 或 cout)、读取一行(fgets 或 cin.getline)
机试考察的数据结构:数组、链表、二叉树
机试需要的算法:枚举、模拟、递归、分治、搜索

在这里插入图片描述

会50%、会70%和会90%都是零分。要会,就要100%会。要么满分,要么零分!
练精一道题,胜于浅尝辄止10道题!



(6)常犯的编程小错误

1.scanf 要加取地址 &

否则会导致内存错误
在这里插入图片描述

2.scanf里%d的数量,和后面取地址的参数数量不一致


3.问题:等价条件判断是 == ,写成了 =
情况:不好定位。段错误,且半天没看出问题,逻辑都是对的。最后找助教才帮忙看出来,花了十几分钟。尴尬。
解决:遵守编程规范,在写等价判断时,值写在左边,变量写在右边。 这样即使把==写成了=,也会是编译错误,直接报语法错误,好定位。

4.数学上的倍数关系如3h-2,代码里要加星号*。写作3*h-2

5.定义的需要持续记录的变量放在了for循环内部,导致生命周期变短,无法起到持续记录的效果。

6.printf里加了&导致数据异常
在这里插入图片描述

7.排序题:只有string字符串才可以直接比大小,c语言的字符数组不能直接比大小。



(7)其他小问题一览

int取值范围

①int(32位)的取值范围为:-231 ~231-1 ,即:-2147483648 - 2147483647。即±2.1×10^9,±21亿,10位数。
②long long int()64位的取值范围:-263 ~263-1,即-9,223,372,036,854,775,808-9,223,372,036,854,775,807。即±9.2×1018,19位数。

注意题目要求的n的范围,判断f(n)是否会超过int的取值范围。若超过,则需要换成float或double或long long int 或 unsigned int。


②return 0 缺省问题

main函数结尾好多人不写return 0,程序也能跑通?
答:尽量写return 0。不要依赖编译器的自动补全。

C99(全称 ISO/IEC 9899:1999)中规定,若结尾处没有碰到return 0;则编译器会自动补全。
所以即使漏了没写(缺省),编译器也帮你补上。所以main函数结尾不写return 0;程序也能跑通。
但是老师还是希望大家能手动写上return 0; ,不要依赖补全而忘记了这件事。毕竟手写代码的时候并没有编译器帮你补上。


③万能头文件 #include <bits/stdc++.h>

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

④scanf、printf 比 cin、cout 更节约时间


不确定数量的输入 while(scanf(“%d”,&n) != EOF){ }

//输入n,然后输入n个数
int n;
int arr[101];
while (scanf("%d",&n) != EOF){
	for(int i=0;i<n;++i){
		scanf("%d",&arr[i]);
	}
}

注意:输入一串数据后,要先按Enter换行,再按Crtl+D。不换行则这一行数据没有输入缓冲区。

输入EOF:
①clion/gcc/clung:crtl+d
②vs:crtl+c


⑥输入m组数据:while( != EOF) + for循环

输入个数m,后面有n行数据。最后实际输出和预计输出行数不同:
忘记在while里面加for循环了。没有循环scanf导致只读了一行。

int m;
while(scanf("%d",&m) != EOF){
    for(int i = 0; i < m; ++i){
    	声明数据
    	scanf();
    }
}

⑦变量的作用域

放在花括号内部的变量,生命周期只能在花括号里。
有时候有的变量需要设在全局,或者函数外部,才能被调用。


⑧scanf(“%d %c %c”,&n,&in,&out):%c不忽略空格




第2章 枚举和模拟

(一) 枚举 (暴力法)

1.枚举问题简介

枚举,又称穷举,俗称暴力求解。
枚举类问题的特点是,数据量较小,可以列举出问题的所有情况,用循环逐个地判断所有的数据是否符合题目的要求。

在这里插入图片描述


2.编程规范

(1)变量命名规范

①跟随试题:
题目中变量用的什么名字,代码中就用什么名字

②自己定义的变量,尽量以单词作为变量名,命名准确表达变量的含义

③类名的首字母大写。(类包括struct、class)

④外层循环使用不常见的变量名,减少内外层冲突的可能性
在这里插入图片描述


(2)判断时,左边写常量,右边写变量/表达式

防止 if(n==0) 漏写为 if(n=0),导致死循环。而且这不是编译错误,检查不出来。
要写成if(0 == n),把固定值写左边。这样,如果漏写为 if( 0 =n)是不符合语法的,将错误提前到了编译阶段。
最简单的错误就是编译错误(语法错误)


(3)不要省略花括号 (大括号)

因为搞不好你待会还要再添加新语句,所以即使if、for、while里只有一句话,也要加花括号。

虽然有些if里面只有一句话,可以省略花括号。但是对于企业级的项目来说,if里经常可能会添加新语句,而忘记花括号。对于这种经常变动的代码,务必全都加上大括号(即使只有一行),以防日后又增又删的调试。
即使你自己注意到了,难免后续接手的程序员不会忘记if里又加了几行时忘记使用花括号,而且这里加了没有调试,最终bug,花了半天时间才找到是因为这里if忘记加花括号了。
同时,维护别人写的代码时也要注意,在向单行循环体里加语句时,检查它是否有大括号


(4)增量编写法:写一部分,就测试一部分

要写1000行代码,每写大约100行就测试一下。当第350行出错时,单步调试不必从第1行开始,因为前300行都测试过没问题。可以直接从301行打断点。


3.程序出错的原因

(1)编译错误 (compile):基本语法错误 【error C2143】

1.编译错误,是指代码不符合C/C++等语言的语法。

2.[1/2]或[50%],指的就是编译过程

3.定位第一个编译错误,根据行号、列号、提示,去解决第一个编译错误。
编译错误只看第一个错误。因为解决一个问题可能就会解决一片编译错误。


(2)链接错误 (link):函数名写错了 【error LNK2019】

1.编译通过,说明基本的语法没有错误。
链接错误,并不提示链接错误的位置。一般就是函数名字写错了。

2.[2/2]或[100%],指的就是链接过程

在这里插入图片描述


(3)运行错误 (run):结果与预期不符,打断点,单步调试,监视

运行时错误,构建(build)成功,即编译、链接都通过,但结果与预期不符。
运行错误也不会提示哪里有问题,这就需要通过打断点来进行断点调试了。

在这里插入图片描述


例如abc问题中,在for循环后面误加了分号。打断点 + 单步调试 + 监视,发现每轮循环c的值都是10,说明第三层for循环在没执行循环体时就完成了。去查看那句for循环,会发现多了分号。

单步调试:clion:步入、vs:逐过程/逐语句

在这里插入图片描述


(4)代码调试方法:改错只关注第一个错误

debug只关注第一个错误,因为后续错误可能是第一个错误的连锁反应。
例如有10个bug,应当的做法是,改正第一个bug,然后重新调试,再改正当前的第一个bug。绝对不是一口气把这10个bug都修复,后9个大概率是无用功!


前两步统称构建(build)


(5)死循环调试方法补充

1.写了死循环并执行,CPU占用率会飙升。
2.有时候卡住也可能是scanf函数在等待输入。这时检查任务管理器,发现CPU占用率没有上升。

在这里插入图片描述

在这里插入图片描述


4.例题

例题1:abc问题

在这里插入图片描述



例题1:abc (清华上机)
提交网址:http://t.cn/E9WMRTE
解法:暴力枚举:循环 + if + printf

#include <cstdio>

int main(){
    int a,b,c;
    for(a=0; a<=9; ++a){
        for(b=0; b<=9; ++b){
            for(c=0; c<=9; ++c){
                if(532 == 100*a+10*b+c + 100*b+11*c){
                    printf("%d %d %d\n",a,b,c);
                }
            }
        }
    }
    return 0;
}



例题2:反序数

%10取余,再/10,直到为0

remain 余数,reverse 反序数的中间变量

在这里插入图片描述


(1)Reverse函数:求反序数

当不知道循环多少次,只知道循环条件时,用while循环。

int Reverse(int n) {
    int remain = 0,reverse = 0; //remain余数,reverse反序数
    while(n>0){
        remain = n%10;
        n /= 10;
        reverse = 10*reverse + remain;
    }
    return reverse;
}


例题1:反序数 (清华上机)
提交网址:http://t.cn/E9WBrut

解法1:Reverse函数(用Reverse函数来枚举)

#include <cstdio>

int Reverse(int n){
    int reverse = 0,remain;
    while(n>0){
        remain = n%10;
        n /= 10;
        reverse = reverse*10 + remain;
    }
    return reverse;
}

int main(){
    for(int n=1000; n<=9999; ++n){ //9倍是四位数,实际上原数n最大为1111
        if(Reverse(n) == 9*n){
            printf("%d\n",n);
        }
    }
    return 0;
}

解法2:暴力枚举(n位数,用n层for循环来暴力枚举)

#include <cstdio>
 
int main(){
    int a,b,c,d;
    for(int a=1;a<=9;++a){ //四位数,a不能为0
        for(int b=0;b<=9;++b){
            for(int c=0;c<=9;++c){
                for(int d=0;d<=9;++d){
                    if((1000*a+100*b+10*c+d)*9 == 1000*d+100*c+10*b+a){
                        printf("%d%d%d%d",a,b,c,d);
                    } 
                }
            }
        }
    }
    return 0;
}



5.习题



习题1:对称平方数1

提交网址:http://t.cn/E9lUYRn

在这里插入图片描述

#include <cstdio>

int Reverse(int n){
    int remain,reverse=0;
    while(n>0){
        remain = n%10;
        n /= 10;
        reverse = reverse*10+remain;
    }
    return reverse;
}

int main(){
    for(int i=0; i<=256; ++i){
        if(Reverse(i*i) == i*i){
            printf("%d\n",i);
        }
    }
    return 0;
}

习题2:与7无关的数

提交网址:http://t.cn/E9lOOZQ

在这里插入图片描述


#include <cstdio>

bool relatedto7(int m){
    if(m%7==0) return true; //7的倍数
    if(m/10==7) return true; //十位为7
    if(m%10==7) return true; //个位为7
    return false;       //与7无关
}

int main(){
    int n,sum=0;
    while(scanf("%d",&n) != EOF){
        for(int i=1; i<=n; ++i){
            if(false==relatedto7(i)){
                sum += i*i;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

习题3:约数的个数

提交网址:https://www.acwing.com/problem/content/3380/

在这里插入图片描述


解法1:暴力枚举会TLE (超时)

时间复杂度: O ( n ? a i ) O(n*a_i) O(n?ai?)
按题中的数据即为 1 0 12 10^{12} 1012

#include <cstdio>

int Divisor(int x){
    int sum=0;
    for(int i=1; i<=x; ++i){  //枚举1到x所有的值
        if( 0== x%i){
            sum++;
        }
    }
    return sum;
}

int main(){
    int n;
    while((scanf("%d",&n)) != EOF){
        int k;
        for(int i=0; i<n; ++i){
            scanf("%d",&k);
            printf("%d\n", Divisor(k));
        }
    }
    return 0;
}

(2)Divisor函数:求约数 (求约数的优化是理解难点)

最优解: i<=x/iif(x/i != i) sum++; 两者配对使用

i<=x/i 使得代码 相较于之前 只需要循环到sqrt(x)

#include <cstdio>

int divisor(int x){
    int sum=0; //sum是约数的个数
    for(int i=1; i<=x/i; ++i){ //只遍历到x/i:约数成对出现,一个数的较小的约数不可能大于x/i
        if(0 == x%i){  //若满足x%i==0,则i是x的约数
            sum++;
            if(x/i != i) sum++; //非平方数,约数有两个,sum自增两次
        }						//平方数跳过该句,sum只自增一次
    }
    return sum;
}

int main(){
    int n;
    while((scanf("%d",&n)) != EOF){
        int k;
        for(int i=0; i<n; ++i){
            scanf("%d",&k);
            printf("%d\n", divisor(k));
        }
    }
    return 0;
}

习题4:水仙花数

提交网址:https://www.acwing.com/problem/content/3647/

在这里插入图片描述
在这里插入图片描述


解法1:原始粗糙解法判断水仙花数,有待优化,看解法2

#include <cstdio>

//判断是否为水仙花数
bool Narcissistic_number(int n){ //n为三位数:100-999
    //求n的百位、十位、个位
    int bai,shi,ge;
    bai = n/100;
    shi = (n/10)%10;
    ge  = n%10;
    //判断水仙花数
    if(n == bai*bai*bai+shi*shi*shi+ge*ge*ge){
        return true;
    }
    return false;
}

int main(){
    int m,n;
    while((scanf("%d%d",&m,&n))!= EOF){
        if(0==m && 0==n) break;
        int i,count=0;
        for(i=m; i<=n;++i){
            if(true == Narcissistic_number(i)){
                printf("%d ",i);
                count++;
            }
        }
        if(0==count){
            printf("no\n");
        }else{
            printf("\n");
        }
    }
    return 0;
}

解法2:ACwing视频讲解

#include <cstdio>

//判断是否为水仙花数
bool Narcissistic_number(int x){ //n为三位数:100-999
    int y=x,sum=0;
    while(x>0){ //求各个位的立方和
        int t = x%10;
        x /= 10;
        sum += t*t*t;
    }
    return sum==y;
}

int main(){
    int m,n;
    while((scanf("%d%d",&m,&n))!= EOF){
        if(0==m && 0==n) break;
        int count=0;
        for(int i=m; i<=n;++i){
            if(true == Narcissistic_number(i)){
                printf("%d ",i);
                count++;
            }
        }
        if(0==count){
            printf("no");
        }
        printf("\n");
    }
    return 0;
}

解法3:打表
100-999的水仙花数只有4个:153 370 371 407


习题5:Old Bill

提交网址:http://t.cn/E9jqijR
在这里插入图片描述
在这里插入图片描述


#include <cstdio>

int main(){
    int N,X,Y,Z;
    while((scanf("%d %d %d %d",&N,&X,&Y,&Z)) != EOF){
        int total=0,temp=0,A,B; //price为每只火鸡的单价,total为N只火鸡的总价(最贵的),即total=N*price
                                //temp为 total的中间过程值
        for(int i=1;i<=9;++i){  //注意最高位不能为0,应该从1起
            for(int j=0;j<=9;++j){
                temp = 10000*i+1000*X+100*Y+10*Z+j;
                if(temp%N==0 && temp>total){  //能整除
                    total = temp;   //循环结束时,得到最大的total与最高位A,最低位B
                    A=i,B=j;
                }
            }
        }
        int price = total/N;
        if(price==0){
            printf("0\n");
        }else{
            printf("%d %d %d\n",A,B,price);
        }
    }
    return 0;
}




(二) 模拟

0.模拟问题简述

在这里插入图片描述



1.图形排版 (图案打印):列表法+找数字规律

(1)字符串

只能按行分解,一行相当于一个字符串


(2)二维数组

1.二维数组初始化,每一个元素都是 \0

char arr[100][100] = {0};//定义二维数组并初始化,长度固定

在这里插入图片描述

在这里插入图片描述


(3)例题
例题1:输出梯形 (2001年清华复试上机)

在这里插入图片描述
在这里插入图片描述

①规律1:(我的答案)

#include <cstdio>

int main(){
    int h;
    scanf("%d",&h);
    for(int i=0; i<h; ++i){ //i为行号
        for(int j=0; j<h+2-2*i; ++j){
            printf(" ");
        }
        for(int j=h+2-2*i; j<2*h+2; ++j){
            printf("*");
        }
        printf("\n");
    }
    return 0;
}

②规律2:(官方答案)

#include <cstdio>

int main()
{
    int h;
    while(scanf("%d",&h)!= EOF){  //crtl+d 表示 输入结束
        //scanf("%d",&h);
        for(int i=0;i<h;++i){
            for (int j=0; j<3*h-2; ++j) {
                if (j < 2*h-2-2*i){
                    printf(" ");
                }else{
                    printf("*");
                }
            }
            printf("\n");
        }
    }
    return 0;
}

解法2:用二维数组解决梯形问题

#include <cstdio>

char arr[1010][3030];

int main(){
    int h;
    scanf("%d",&h);
    //1.涂白
    for(int i = 0;i < h; ++i){//每行
        for(int j = 0; j < 3*h-2;++j){//每列
            arr[i][j] = ' ';
        }
    }
    //2.涂星
    int x = 0;
    for(int i=h-1; i>=0; --i){//每行,从最后一行开始。数组下标从0开始,到h-1
        for(int j=2*(x++);j<3*h-2;++j){
            arr[i][j] = '*';
        }
    }
    //3.输出
    for(int i = 0; i < h;++i){
        for(int j = 0;j < 3*h-2;++j){
            printf("%c",arr[i][j]);
        }
        printf("\n");
    }
    return 0;
}


例题2:打印数字菱形

提交网址:https://www.acwing.com/problem/content/3666/

在这里插入图片描述
在这里插入图片描述


列表法 (找规律)

在这里插入图片描述


解法1:自然想到的解法 (每行最后多一个空格,不影响AC)

#include <cstdio>

int main(){
    int n;
    scanf("%d",&n);
    //行数递增
    for(int i=0; i<=n; i++){  //i为行号
        int j;
        for(j=0; j<2*n-2*i; j++ ){   //j:打印空格
            printf(" ");
        }
        for(int k=0; k<i+1; k++){   //k打印每行的递增字符
            printf("%d ",k);
        }
        for(int k=i-1; k>=0; k--){   //k打印每行的递减字符
            printf("%d ",k);
        }
        printf("\n");
    }
    //行数递减
    for(int i=n+1; i<=2*n+1; i++){  //i为行号
        int j,k;
        for(j=(i-n)*2; j>0; j-- ){   //j:打印空格
            printf(" ");
        }
        for(k=0; k<=2*n-i; k++){   //k打印每行的递增字符
            printf("%d ",k);
        }
        for(k=2*n-i-1; k>=0; k--){   //k打印每行的递减字符
            printf("%d ",k);
        }
        if(i<2*n+1)    printf("\n");  //最后一行不回车
    }
    return 0;
}

解法2:字符串

#include <cstdio>
#include <cstring>

int main() {
    char str[1000] = {0};
    int n;
    scanf("%d",&n);
    int i;
    //每行长度递增
    for(i=0; i<=n; ++i){
        int j;
        memset(str,0,1000);
        for(j=0; j<2*n-2*i; ++j){  //空格
            str[j] = ' ';
        }
        for(int k=0; k<=i; ++k){  //数字
            str[j] = '0'+k;
            str[j+1] = ' ';
            j += 2;
        }
        for(int k=i-1; k>=0; k--){
            str[j] = '0'+k;
            str[j+1] = ' ';
            j += 2;
        }
        printf("%s\n",str);
    }
    //每行长度递减
    for(i=n+1; i<=2*n;++i){
        int j;
        memset(str,0,1000);
        for(j=0; j<2*i-2*n; ++j){  //空格
            str[j] = ' ';
        }
        for(int k=0; k<=2*n-i; ++k){  //数字
            str[j] = '0'+k;
            str[j+1] = ' ';
            j += 2;
        }
        for(int k=2*n-i-1; k>=0; k--){
            str[j] = '0'+k;
            str[j+1] = ' ';
            j += 2;
        }
        printf("%s\n",str);
    }
    return 0;
}

解法3:二维数组

#include <cstdio>
#include <cstring>

int main() {
    char str[1000] = {0};
    char arr[100][100] = {0};
    int n;
    scanf("%d",&n);
    int i;
    //每行长度递增
    for(i=0; i<=n; ++i){
        int j;
        for(j=0; j<2*n-2*i; ++j){  //空格
            arr[i][j] = ' ';
        }
        for(int k=0; k<=i; ++k){  //数字
            arr[i][j] = '0'+k;
            arr[i][j+1] = ' ';
            j += 2;
        }
        for(int k=i-1; k>=0; k--){
            arr[i][j] = '0'+k;
            arr[i][j+1] = ' ';
            j += 2;
        }
    }
    //每行长度递减
    for(i=n+1; i<=2*n;++i){
        int j;
        memset(str,0,1000);
        for(j=0; j<2*i-2*n; ++j){  //空格
            arr[i][j] = ' ';
        }
        for(int k=0; k<=2*n-i; ++k){  //数字
            arr[i][j] = '0'+k;
            arr[i][j+1] = ' ';
            j += 2;
        }
        for(int k=2*n-i-1; k>=0; k--){
            arr[i][j] = '0'+k;
            arr[i][j+1] = ' ';
            j += 2;
        }
    }
    for(i=0; i<2*n+1; ++i){
        printf("%s\n",arr[i]);
    }
    return 0;
}


例题3:叠筐问题

提交网址:http://acm.hdu.edu.cn/showproblem.php?pid=2074
在这里插入图片描述
在这里插入图片描述


找规律 + 二维数组
在这里插入图片描述

#include <cstdio>
#include <cstring>

int main(){
    int n;       //层数(外框尺寸)n
    char in,out; //中心花色字符in,外层花色字符out
    char pattern[100][100];   //二维数组
    while(scanf("%d %c %c",&n,&in,&out) != EOF){
        int layer; //层级 0~n/2
        memset(pattern,0,10000);
        char current = in; //current表示当前层级的花色
        for(layer=0;layer<=n/2;++layer){
            //左上:n/2-layer,n/2-layer
            //右上:n/2-layer,n/2+layer
            //左下:n/2+layer,n/2-layer
            //右下:n/2+layer,n/2+layer
            for(int x=n/2-layer,y=n/2-layer;y<=n/2+layer;++y){  //左上到右上
                pattern[x][y] = current;
            }
            for(int x=n/2+layer,y=n/2-layer;y<=n/2+layer;++y){  //左下到右下
                pattern[x][y] = current;
            }
            for(int x=n/2-layer,y=n/2-layer;x<=n/2+layer;++x){  //左上到左下
                pattern[x][y] = current;
            }
            for(int x=n/2-layer,y=n/2+layer;x<=n/2+layer;++x){  //右上到右下
                pattern[x][y] = current;
            }
            if(current == in){  //填一圈换一个花色
                current = out;
            }else{   //若current == out
                current = in;
            }
        }
        //磨掉四个角
        if(n != 1){
            pattern[0][0] = ' ';
            pattern[0][n-1] = ' ';
            pattern[n-1][0] = ' ';
            pattern[n-1][n-1] = ' ';
        }
        //输出
        for(int i=0; i<n; ++i){
            printf("%s\n",pattern[i]);
        }
    }

    return 0;
}



2.日期问题:星期几/年月日

但凡日期问题,先写出NextDay函数,然后只需要稍微修改主函数,按照题目要求想办法调用NextDay函数就完事了。

在这里插入图片描述


(1)用数组存储 月份与天数的对应关系

辅助数组 (用空间换时间)

int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

(2)闰年问题

闰年:是400的倍数 或 是4的倍数但不是100的倍数
(&&的逻辑优先级高于||,实际上不需要加括号)

bool isLeap = (year%400==0) || (year%4==0 && year%100!=0);  //true是闰年
if(isLeap)  dayOfMonth[2] = 29; 						//若为闰年,则2月为29天

(3)已知某一天,求下一天:NextDay函数
#include <cstdio>

void NextDay(int &year,int &month,int &day){
    int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    bool isLeap = year%400==0 || year%4==0 && year%100 != 0;
    if(isLeap)  dayOfMonth[2] = 29;  //判断闰年
    day++;
    if(day > dayOfMonth[month]){
        day = 1;
        month++;
    }
    if(month > 12){
        month = 1;
        year++;
    }
}

int main() {
    int year,month,day;
    while(scanf("%d%d%d",&year,&month,&day) != EOF){
        NextDay(year,month,day);
        printf("%04d-%02d-%02d\n",year,month,day);//通过引用传递修改主调函数的值
    }
    return 0;
}

(4)打印日期用printf,比cout方便

%d:打印数字
%4d:打印数字,至少4个位置宽,不足则用空格填充
%04d:打印数字,至少4个位置宽,不足则用0填充
在这里插入图片描述

cout的运行效率、格式控制,不如printf。只是书写上比printf简便。


(5)C++引用:使用引用作为函数参数
①C语言的值传递:不改变主调函数中参数的值

C语言的值传递:
①克隆关系。
②克隆到被调函数的值发生改变,不影响主调函数的值。
③在内存栈帧中是两份数据。

在这里插入图片描述


②C++的引用传递:改变主调函数中参数的值

C++ 引用:
①就是起别名,是同一个参数。
②在被调函数中值改变,同时会影响主调函数中的值。
③在内存存储中是同一份数据。

在这里插入图片描述


举例,求下一天的NextDay函数,若在被调函数的形参中加上引用&,则主调函数main中的值也会改变

#include <cstdio>

void NextDay(int &year,int &month,int &day){
    int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    bool isLeap = (year%400==0) || (year%4==0 && year%100 != 0);
    if(isLeap==true)  dayOfMonth[2]=29;
    day++;
    if(day > dayOfMonth[month]){
        day = 1;
        month++;
    }
    if(month > 12){
        month = 1;
        year++;
    }
    printf("%d %d %d\n",year,month,day);
}

int main() {
    int year,month,day;
    while(scanf("%d%d%d",&year,&month,&day) != EOF){
        NextDay(year,month,day);
        printf("main %d %d %d\n",year,month,day);
    }
    return 0;
}

&的含义

①&出现在定义声明 或 被调函数的形参 当中,表示引用的意思
②&出现在其他位置,表示取地址


(6)例题
例题1:今年的第几天?

提交网址:http://t.cn/E9jXK5A
在这里插入图片描述


思路:在NextDay函数的基础上,略微修改即可

#include <cstdio>

void NextDay(int year,int &month,int &day){
    int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    bool isLeap = (year%400==0) || (year%4==0 && year%100 != 0);
    if(isLeap==true)  dayOfMonth[2]=29;
    day++;
    if(day > dayOfMonth[month]){
        day = 1;
        month++;
    }
    if(month > 12){
        month = 1;
        year++;
    }
}

int main() {
    int year,month,day;
    while(scanf("%d%d%d",&year,&month,&day) != EOF){
        int count = 1,current_month = 1,current_day = 1;
        while(!(current_day==day && current_month==month)){
            NextDay(year,current_month,current_day);
            count++;
        }
        printf("%d\n",count);
    }
    return 0;
}

例题2:打印日期

提交网址:http://t.cn/E9YP2a8
在这里插入图片描述


注意格式化输出,用printf,%02d

在这里插入图片描述


2024答案:借用NextDay函数,只改一下主函数

#include <cstdio>

void NextDay(int year,int &month,int &day){
    int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    bool isLeap = (year%400==0) || (year%4==0 && year%100 != 0);
    if(isLeap==true)  dayOfMonth[2] = 29;  //判断闰年
    day++;
    if(day > dayOfMonth[month]){
        day = 1;
        month++;
    }
    if(month > 12){
        month = 1;
        year++;
    }
}

int main() {
    int year,n; //n为今年的第几天
    while(scanf("%d%d",&year,&n) != EOF){
        int current_month = 1,current_day = 1,count = 1;
        while(n != count){
            NextDay(year,current_month,current_day);
            count++;
        }
        printf("%04d-%02d-%02d\n",year,current_month,current_day);
    }
    return 0;
}

2023答案:把功能实现在main函数里面了,高耦合度,可复用性差

#include <cstdio>

//输入年份、第几天,求日期。yyyy-mm-dd格式。
int main(){
        int year,n;
        int  mday[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
        while(scanf("%d%d",&year,&n) != EOF){
            int mon = 1;
            int day = 1;
            for(int i = 0;i < n-1; ++i){
                //nextDay
                bool isLeap = (year%400 == 0) || (year%100 != 0 && year%4 == 0);
                if(isLeap){
                    mday[2] = 29;
                }else{
                    mday[2] = 28;
                }
                ++day;
                if(day > mday[mon]){
                    ++mon;
                    day = 1;
                    if(mon > 12){
                        mon = 1;
                        ++year;
                    }
                }
            }
            printf("%d-%02d-%02d\n",year,mon,day);
        }
}

例题3:日期累加

提交网址:http://t.cn/E9Yw0Cr

在这里插入图片描述


#include <cstdio>

void NextDay(int &year,int &month,int &day){
    int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    bool isLeap = (year%400==0) || (year%4==0 && year%100 != 0);
    if(isLeap==true)  dayOfMonth[2]=29;
    day++;
    if(day > dayOfMonth[month]){
        day = 1;
        month++;
    }
    if(month > 12){
        month = 1;
        year++;
    }
}

int main() {
    int year,month,day,count,m;
    while(scanf("%d",&m) != EOF){
        for(int i=0; i<m; ++i){
            scanf("%d%d%d%d",&year,&month,&day,&count);
            while(count--)  NextDay(year,month,day);
            printf("%d-%02d-%02d\n",year,month,day);//通过引用传递修改主调函数的值
        }
    }
    return 0;
}

(7)习题
习题1:日期差值

提交网址:http://t.cn/E9Yz0LE

在这里插入图片描述


注意格式化输入,用scanf,%4d%2d%2d

2024答案:依然是依托于NextDay函数,仅修改主函数。3分钟就AC了。

#include <cstdio>

void NextDay(int &year,int &month,int &day){
    int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    bool isLeap = (year%400==0) || (year%4==0 && year%100 != 0);
    if(isLeap==true)  dayOfMonth[2]=29;
    day++;
    if(day > dayOfMonth[month]){
        day = 1;
        month++;
    }
    if(month > 12){
        month = 1;
        year++;
    }
}

int main() {
    int year1,month1,day1,year2,month2,day2,count=1;
    while(scanf("%4d%2d%2d%4d%2d%2d",&year1,&month1,&day1,&year2,&month2,&day2) != EOF){
        while(!(year1==year2 && month1==month2 && day1==day2)){
            NextDay(year1,month1,day1);
            count++;
        }
        printf("%d\n",count);
    }
    return 0;
}

别人的答案:未考虑闰年问题

#include <cstdio>

int main(){
    int YYYY1,MM1,DD1,YYYY2,MM2,DD2;
    int Day = 1;
        scanf("%4d %2d %2d %4d %2d %2d",&YYYY1,&MM1,&DD1,&YYYY2,&MM2,&DD2);
        Day += (YYYY2-YYYY1)*365;
        Day += (MM2-MM1)*30;
        Day += DD2-DD1;
        printf("%d",Day);
    return 0;
}

习题2:打印日期

提交网址:https://www.acwing.com/problem/content/3610/

在这里插入图片描述

本题就是例题2原题,只是数据加强了,年份也要求格式化输出 %04d

#include <cstdio>

void NextDay(int &year,int &month,int &day){
    int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    bool isLeap = year%400==0 || year%4==0 && year%100!=0;
    if(isLeap)  dayOfMonth[2] = 29;
    day++;
    if(day > dayOfMonth[month]){
        day = 1;
        month++;
    }
    if(month > 12){
        month = 1;
        year++;
    }
}

int main(){
    int year,n;
    while(scanf("%d%d",&year,&n) != EOF){
        int month = 1,day = 1,count = 1;
        while(n != count){
            NextDay(year,month,day);
            count++;
        }
        printf("%04d-%02d-%02d\n",year,month,day);  //C++引用传递修改主调函数的值
    }
    return 0;
}

习题3:日期 (求星期几)

提交网址:https://www.acwing.com/problem/content/3622/

在这里插入图片描述

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

void NextDay(int &year,int &month,int &day){
    int dayOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    bool isLeap = year%400==0 || year%4==0 && year%100 != 0;
    if(isLeap)  dayOfMonth[2] = 29;  //判断闰年
    day++;
    if(day > dayOfMonth[month]){
        day = 1;
        month++;
    }
    if(month > 12){
        month = 1;
        year++;
    }
}

int main() {
    int year = 2012,month,day;
    while(scanf("%d%d",&month,&day) != EOF){
        //2012年4月12日 是 星期四
        int weekday = 4;      //char的C风格字符数组,每一个单元只能存储一个字符
        string str[8] = {"0","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
        int cur_month = 4,cur_day = 12;
        while(cur_month!=month || cur_day!=day){
            NextDay(year,cur_month,cur_day);
            weekday++;
            if(weekday > 7) weekday -= 7;
        }
        cout<<str[weekday]<<endl;
    }
    return 0;
}



3.简单模拟

(1)例题
例题1:xxx定律

提交网址:https://www.nowcoder.com/share/jump/2891302591705051511174

在这里插入图片描述


#include <cstdio>

int main(){
    int n;
    while((scanf("%d",&n))!=EOF){
        int count=0;
        while(n != 1){
            if(n%2==0){  //n为偶
                n = n/2;
            }else{     //n为奇
                n = (3*n+1)/2;
            }
            count++;
        }
        printf("%d\n",count);
    }
    return 0;
}



(2)习题
习题1:特殊乘法

提交网址:https://www.acwing.com/problem/content/3393/
在这里插入图片描述

思路:
A ? B = ( a 1 + a 2 + . . . + a n ) × ( b 1 + b 2 + . . . + b m ) A?B =(a_1+a_2+...+a_n)×(b_1+b_2+...+b_m) A?B=(a1?+a2?+...+an?)×(b1?+b2?+...+bm?)
故只要得到A和B的各位之和,再相乘即可。

代码:

#include <cstdio>

int main() {
    int A,B;
    scanf("%d%d",&A,&B);
    int sumA=0,sumB=0; //sum为各位之和
    while(A>0){
        sumA += A%10;
        A /= 10;
    }
    while(B>0){
        sumB += B%10;
        B /= 10;
    }
    printf("%d",sumA*sumB);
    return 0;
}

习题2:递推数列

提交网址:https://www.acwing.com/problem/content/3395/
在这里插入图片描述


解法1:纯递归方法,TLE超时了

#include <cstdio>

int an(int a0,int a1,int p,int q,int n){
    if (n==0) return a0;   //递归出口
    if (n==1) return a1;   //递归出口
    return p*an(a0,a1,p,q,n-1)+q*an(a0,a1,p,q,n-2);  //递归调用
}

int main() {
    int a0,a1,p,q,k;
    scanf("%d%d%d%d%d",&a0,&a1,&p,&q,&k);
    int ak = an(a0,a1,p,q,k);
    printf("%d\n",ak % 10000);
    return 0;
}

解法2:使用数组,用for循环迭代 【最优解:用数组+迭代 代替 递归】

#include <cstdio>

const int mod = 10000, N = 10010;
int a[N];

int main() {
    int p,q,k;
    scanf("%d%d%d%d%d",&a[0],&a[1],&p,&q,&k);
    //迭代
    for(int i = 2; i<=k ; ++i){
        a[i] = (p*a[i-1]+q*a[i-2]) % mod;
    }
    printf("%d\n",a[k]%mod);
    return 0;
}

习题3:学分绩点

提交网址:https://www.acwing.com/problem/content/3395/
在这里插入图片描述
在这里插入图片描述

#include <cstdio>

float calc_Grade(int grade){
    float Grade; //某一科的单科绩点
    if(grade>=90 && grade<=100)     Grade = 4.0;
    else if(grade>=85 && grade<=89) Grade = 3.7;
    else if(grade>=82 && grade<=84) Grade = 3.3;
    else if(grade>=78 && grade<=81) Grade = 3.0;
    else if(grade>=75 && grade<=77) Grade = 2.7;
    else if(grade>=72 && grade<=74) Grade = 2.3;
    else if(grade>=68 && grade<=71) Grade = 2.0;
    else if(grade>=64 && grade<=67) Grade = 1.5;
    else if(grade>=60 && grade<=63) Grade = 1.0;
    else if(grade>= 0 && grade<=59) Grade =   0;
    return Grade;
}

int main() {
    int n,weight[20],grade[20],sum=0; //sum为学分之和
    float GPA;  //总评绩点
    scanf("%d",&n);
    for(int i=0; i<n; ++i){
        scanf("%d",&weight[i]);
        sum += weight[i];
    }
    for(int i=0; i<n; ++i){
        scanf("%d",&grade[i]);
    }
    //计算GPA
    for(int i=0; i<n; ++i){
        GPA += calc_Grade(grade[i])*weight[i];
    }
    GPA = GPA/sum;
    printf("%.2f",GPA);
    return 0;
}

习题4:买房子

提交网址:https://www.acwing.com/problem/content/3447/

在这里插入图片描述


提醒:这题的关键在于,增长K%,∴K和房价price都得是float类型,不能是int类型。因为int K/100=0

#include <cstdio>

int main() {
    int N;
    float K;
    while(scanf("%d%f",&N,&K) != EOF){
        int year = 1,money = N;
        float price = 200;
        bool flag = false;
        while(year <= 20){
            money += N;
            price *= 1+K/100;
            year++;
            if(money >= price){
                printf("%d\n",year);
                flag = true; //20年内买的起房子
                break;
            }
        }
        if(flag == false) printf("Impossible\n");
    }
    return 0;
}

习题5:旋转矩阵

提交网址:https://www.acwing.com/problem/content/3530/


习题6:重复者

提交网址:https://www.acwing.com/problem/content/3444/


习题7:Hello World for U

提交网址:http://t.cn/E9jizni


习题8:坠落的蚂蚁

提交网址:http://t.cn/E9dhoRA



4.复杂模拟:数据结构

(0)和数据结构相关的模拟问题:线性数据结构(vector、list)、非线性数据结构(set、map)

线性表
(1)顺序表(数组)
静态数组:长度不可变
动态数组vector:长度可变

(2)链表 list


①静态数组、动态数组 vector

在这里插入图片描述


②增删改查遍历:方括号运算符、迭代器

在这里插入图片描述


迭代器 iterator、尾后指针 end()

在这里插入图片描述


(1)vector 动态数组 (顺序表)

1.增
①push_back(数据):尾后插入
②insert(it,数据):配合迭代器,任意位置插入

2.删
①pop_back():尾后删除
②clear():清空
③erase(it):配合迭代器,任意位置删除

3.遍历:迭代器、size()

vector<int>::iterator it;
for(it = vec.begin(); it != vec.end(); ++it)

4.查找:方括号运算符
vec[i]

5.vector的完整使用

#include <cstdio>
#include <vector>
using namespace std;

struct MyType{
    int val1;
    double val2;
};

int main() {
    //0.构造,声明
    vector<int> vec1;    //vector是模板,不是类型。vector<type>才是类型
    vector<double> vec2;
    vector<MyType> vec3;
    vector< vector<int> > vec4;  //动态数组的动态数组,即二维数组
    vector<int> arr[10];   //动态数组的静态数组,机试推荐用法,图的邻接表法
    //0.初始化
    vector<int> vec5(100); //申请动态数组空间,并全部初始化为0
    //1.增:(1)尾部插入: push_back 往动态数组的尾部插入数据: 为尾部申请一个内存,把数据放入尾部,效率高
    int a;
//    while(scanf("%d",&a) != EOF){
        vec1.push_back(a);
//    }
    //2.查找(查):方括号运算符
    vector<int> vec6 = {1,3,5,7,9};
    int i = 4;
    printf("vec[%d]=%d\n",i,vec6[i]);
    //3.遍历数组:(1)利用vector的长度:size()函数
    printf("size=%d\n",vec6.size());
    for(int i=0; i<vec6.size(); ++i){
//        printf("vec[%d]=%d\n",i,vec6[i]);
    }
    //3.遍历数组:(2)利用迭代器 iterator (提供了一种通用方法来访问不同的数据结构,迭代器可理解为一种高级指针)
    vector<int>::iterator it; //声明(构造)迭代器
    for(it = vec6.begin(); it != vec6.end(); ++it){
        printf("*it = %d\n",*it); //it是指针,可以用星号运算符* 取内容
    }
    //1.增:中间插入,insert(it,内容)函数。但效率低,需要后移数组
    it = vec6.begin();
    vec6.insert(it,10); //在数组中间插入
    //插入完成后,迭代器位置失效。若想继续使用迭代器,需要重新给迭代器赋值位置
    it = vec6.begin();
    it = it + 3;  //it+3相当于做了3次it++自增操作,仅vector的迭代器支持
    vec6.insert(it,100); //在数组中间插入
    //4.删除:(1)pop_back()函数,删除最后一个元素
    vec6.pop_back();
    //4.删除:(2)erase()函数,删除任意一个位置的元素。增删完迭代器失效,需要重新赋值
    it = vec6.begin()+3; //删除insert的100
    vec6.erase(it);
    //4.删除:(3)clear()函数,清空动态数组
    vec6.clear();
    return 0;
}

(2)list 双向链表

list是链表,使用insert和erase效率高
list所支持的操作与vector几乎相同,但list不能使用下标访问
list提供了归并函数merge(): ls1.merge(ls2)


(3)set 集合

1.分类:
①set
②multiset
③unordered_set
④unordered_multiset

2.增、删、改、查、遍历
①增删:set不需要指明新增或删除元素的位置,而vector需要用迭代器指明位置
②查:find、count

#include <cstdio>
#include <set>
#include <unordered_set>
using namespace std;

int main() {
    //0.构造
    set<int> set1 = {1,3,5};
    multiset<int> set2 = {1,3,5,1,3,5};
    unordered_set<int> set3 = {2,4,6};
    unordered_multiset<int> set4 = {2,4,6,2,4,6};
    //5.遍历
    unordered_multiset<int>::iterator it;
    for(it = set4.begin(); it != set4.end(); ++it){
        printf("%d ",*it);
    }
    printf("\n");
    //4.查找:(1)find() 若找到,则返回一个迭代器,若找不到则返回尾后指针
    if(set3.find(2) == set3.end()){
        printf("2 is not in the set.\n");
    }else{
        printf("2 is in the set.\n");
    }
    //4.查找:(2)count() 元素在集合中的数量
    printf("2 occurs %d times\n",set4.count(2));
    //1.新增元素
    set1.insert(2);
    set1.insert(1);
    set2.insert(2);
    set2.insert(1);
    //2.删除
    set1.erase(1);
    set2.erase(1); //若为multiset,erase会删除所有的该值元素
    //3.改:set的元素不允许直接修改,可以先删除再插入
    return 0;
}

在这里插入图片描述


(4)map 映射

1.map本质上是键值对的集合,通过键(key)来找值(value)。(而set是单个元素的集合)

2.map和set底层相同,也有4种:
①map:不允许键key重复
②multimap:允许键key重复
③unordered_map:空间换时间,效率高,时间开销小
④unordered_multimap

3.键值对:pair< , >
①first:键
②second:值

4.map的完整应用

#include <cstdio>
#include <map>
#include <unordered_map>
using namespace std;

int main() {
    //0.构造map
    map<char,int> map1; //有序,不允许重复
    multimap<char,int> map2; //有序,允许重复
    unordered_map<char,int> map3; //无序,不允许重复
    unordered_multimap<char,int> map4; //无序,允许重复
    //键值对
    pair<char,int> pair1 = {'h',0};
    printf("%c %d\n",pair1.first,pair1.second);
    printf("\n");
    //1.增:在map中新增
    map1.insert(pair1);
    map2.insert(pair1);
    map1.insert({'e',1});
    //(1)map不允许key重复,multimap允许键key重复,即一个key对应多个value
    map1.insert({'h',2});
    map2.insert({'h',2});
    //2.删:在map中删除,erase('key'),可同时删除键相同的多个键值对
    map1.erase('h');
    map2.erase('h');
    //3.遍历
    map<char,int> map5 = {
            {'w',0},{'o',1},{'r',2},{'l',3},{'d',4}
    };
    map<char,int>::iterator it;
    for(it = map5.begin(); it != map5.end(); ++it){
        printf("%c %d\n",it->first,it->second);
    }
    printf("\n");
    //4.查:(1)方括号运算符:按键查找。若不存在,则新增一个键值对,value值为0
    //仅map支持方括号运算符,multimap不支持方括号运算符
    printf("%d\n",map5['d']);
    printf("%d\n",map5['h']);
    //4.查:(2)find() / count()
    if(map5.find('a') == map5.end()){
        printf("key is not in map.\n");
    }else{
        printf("value = %d\n",map5['a']);
    }
    //5.改:修改map的某键对应的值
    map5['w'] = 8;
    //3.multimap遍历某一个key对应的所有value
    //lower_bound(key) 返回key对应的第一个值的位置,类似begin()
    //upper_bound(key) 返回key对应的最后一个值的位置,类似end()
    multimap<char,int> map6 = {
            {'w',0},{'o',1},{'r',2},{'l',3},{'d',4}
    };
    map6.insert({'o',8});
    multimap<char,int>::iterator it1;
    for(it1 = map6.lower_bound('o'); it1 != map6.upper_bound('o'); it1++){
        printf("key = %c, value = %d\n",it1->first,it1->second);
    }
    return 0;
}

在这里插入图片描述

在这里插入图片描述


(5)例题
例题1:盈数和完数 (vector)

提交网址:http://t.cn/AiKEyQWW
在这里插入图片描述


vec存储 + 迭代器遍历

#include <cstdio>
#include <vector>
using namespace std;
//完数与盈数

int FactorSum(int i){ //求因子之和
    int sum = 0;
    for(int j=1; j<i; ++j){
        if(i%j == 0){
            sum += j;
        }
    }
    return sum;
}

int main() {
    vector<int> Evec;//完数
    vector<int> Gvec;//盈数
    for(int i = 2; i <= 60; ++i){
        if(FactorSum(i) == i){
            Evec.push_back(i);
        }else if(FactorSum(i) > i){
            Gvec.push_back(i);
        }
    }
    printf("E: ");
    vector<int>::iterator it;
    for(it=Evec.begin(); it!=Evec.end(); ++it){
        printf("%d ",*it);
    }
    printf("\n");
    printf("G: ");
    for(it=Gvec.begin(); it!=Gvec.end(); ++it){
        printf("%d ",*it);
    }
    return 0;
}


vec存储 + 数组下标+size() 遍历

    printf("E:");
    for (int i = 0; i < Evec.size(); ++i) {
        printf(" %d", Evec[i]);
    }
    printf("\n");
    printf("G:");
    for (int i = 0; i < Gvec.size(); ++i) {
        printf(" %d", Gvec[i]);
    }
    printf("\n");
}

例题2:剩余的树 (vector)

提交网址:http://t.cn/E9ufYo5

在这里插入图片描述


#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int L,M;
    scanf("%d%d",&L,&M);
    vector<int> road(L+1); //下标为0~L,初始化为0
    // road[i]==0表示有树,若为road[i]==1表示无树
    int left,right;
    for(int i = 0; i < M; ++i){
        scanf("%d%d",&left,&right);
        for(int j = left; j <= right; ++j){
            road[j] = 1;
        }
    }
    int treeNum = 0;
    vector<int>::iterator it;
    for(it = road.begin(); it != road.end(); ++it){
        if(*it == 0) treeNum++;
    }
    printf("%d\n",treeNum);
    return 0;
}

例题3:糖果分享游戏 (vector)

提交网址:https://www.acwing.com/problem/content/3429/
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


#include <cstdio>
#include <vector>
using namespace std;

void ShareCandy(vector<int> &student,int N){
    vector<int> share(N);
    //同时传递,先存储一下每个人的一半数量是多少
    for(int i = 0; i < N; ++i){
        share[i] = student[i]/2;
    }
    //传递糖果
    for(int i = 0; i < N; ++i){
        student[i] = student[i] - share[i];
        student[(i+1)%N] += share[i];
    }
    //奇数多拿一个
    for(int i = 0; i < N; ++i){
        if(student[i]%2 ==1) student[i]++;
    }
}

bool CheckCandy(vector<int> &student,int N){
    for(int i = 0; i < N; ++i){
        if(student[0] != student[i]){
            return false;
        }
    }
    return true;
}

int main() {
    int N;
    while(scanf("%d",&N) != EOF){
        if(N == 0) break;
        vector<int> student(N);
        for(int i = 0; i < N; ++i){
            scanf("%d",&student[i]);
        }
        int turn = 0;
        while(CheckCandy(student,N) == false){
            ShareCandy(student,N);
            turn++;
        }
        printf("%d %d\n",turn,student[0]);
    }
    return 0;
}

例题4:阶乘的和 (set)

提交网址:https://www.acwing.com/problem/content/3484/
在这里插入图片描述

#include <cstdio>
#include <vector>
#include <set>
using namespace std;

int main(){
    //1.计算0!~9!
    vector<int> FacArr; //保存0!~9!
    FacArr.push_back(1);//先把0!=1放入动态数组
    int cur_Factorial = 1;
    for(int i = 1 ; i <= 9; ++i){ //依次将1!~9~放入动态数组
        cur_Factorial = cur_Factorial * i;
        FacArr.push_back(cur_Factorial);
    }
    //2.用set保存0!~9!
    set<int> allPossible; //所有的阶乘和的可能性
    allPossible.insert(0);
    for(int i = 0 ; i <= 9; ++i){
        set<int> tempSet;
        set<int>::iterator it;
        for(it = allPossible.begin(); it != allPossible.end(); ++it ){
            tempSet.insert(*it + FacArr[i]);
        }
        for(it = tempSet.begin(); it != tempSet.end(); ++it){
            allPossible.insert((*it));
        }
//        for(it = allPossible.begin(); it != allPossible.end(); ++it ){
//            allPossible.insert(*it + FacArr[i]); //不能遍历自己的时候插自己,否则迭代器指针就失效了
//        }
    }
    allPossible.erase(0);
    //3.处理输入
    int n;
    while(scanf("%d",&n) != EOF){
        if(n < 0)  break;
        if(allPossible.count(n) == 0){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    return 0;
}

例题5:手机键盘 (map、字符串)

提交网址:http://t.cn/E9ulcIc

在这里插入图片描述
在这里插入图片描述


解:使用两个map,分别记录按某一个字母需要按几下,及该字母对应的键

#include <cstdio>
#include <map>
#include <string>
using namespace std;

int main() {
    //记录每个键的输入时间
    map<char,int> InputTime = {
            {'a',1},{'b',2},{'c',3},
            {'d',1},{'e',2},{'f',3},
            {'g',1},{'h',2},{'i',3},
            {'j',1},{'k',2},{'l',3},
            {'m',1},{'n',2},{'o',3},
            {'p',1},{'q',2},{'r',3},{'s',4},
            {'t',1},{'u',2},{'v',3},
            {'w',1},{'x',2},{'y',3},{'z',4}
    };
    //记录每个键所在的键的位置
    map<char,int> Key = {
            {'a',2},{'b',2},{'c',2},
            {'d',3},{'e',3},{'f',3},
            {'g',4},{'h',4},{'i',4},
            {'j',5},{'k',5},{'l',5},
            {'m',6},{'n',6},{'o',6},
            {'p',7},{'q',7},{'r',7},{'s',7},
            {'t',8},{'u',8},{'v',8},
            {'w',9},{'x',9},{'y',9},{'z',9}
    };
    int lastKey = 0; //记录上次的按键
    char str[200];
    while(scanf("%s",str) != EOF){
        int time = 0;
        for(int i = 0; str[i] !='\0'; ++i){  //C风格字符数组的遍历
            if(Key[str[i]] == lastKey)   time += 2;
            time += InputTime[str[i]];
            lastKey = Key[str[i]];
        }
        printf("%d\n",time);
    }
    return 0;
}

另外的写法:C++的string字符串

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;

    string str;
    while(cin >> str){
        int time = 0;
        for(int i = 0; i < str.size(); ++i){  //C风格字符数组的遍历

(6)习题
习题1:一端进,两端出 (list)

提交网址:https://www.acwing.com/problem/content/5072/

在这里插入图片描述
在这里插入图片描述


习题2:链表合并 (list或数组)

提交网址:https://www.acwing.com/problem/content/3642/

在这里插入图片描述


解法1:链表实现,利用algorithm里现成的merge函数进行归并

#include <cstdio>
#include <list>
using namespace std;

int main() {
    int S1,S2;
    scanf("%d",&S1);
    list<int> ls1;
    int value;
    for(int i = 0; i < S1; ++i){
        scanf("%d",&value);
        ls1.push_back(value);
    }
    scanf("%d",&S2);
    list<int> ls2;
    for(int i = 0; i < S2; ++i){
        scanf("%d",&value);
        ls2.push_back(value);
    }
    ls1.merge(ls2); //利用merge函数归并两链表
    list<int>::iterator it;
    for(it=ls1.begin(); it!=ls1.end(); ++it){
        printf("%d ",*it);
    }
    printf("\n");
    return 0;
}

解法2:数组实现 + 408数据结构排序中的顺序表Merge函数

#include <cstdio>

int Merge(int A[],int B[],int C[],int n,int m){
    int i=0, j=0, k=0;
    while(i<n && j<m){
        if(A[i] <= B[j]) C[k++] = A[i++]; //小的放前面,=号是为了保持稳定性
        else             C[k++] = B[j++];
    }
    while(i<n)    C[k++] = A[i++];
    while(j<m)    C[k++] = B[j++];
}

int main(){
    int n,m;
    int A[110],B[110],C[220];
    scanf("%d",&n);
    for(int i = 0; i < n; ++i){
        scanf("%d",&A[i]);
    }
    scanf("%d",&m);
    for(int i = 0; i < m; ++i){
        scanf("%d",&B[i]);
    }
    Merge(A,B,C,n,m);
    for(int i = 0; i<n+m; ++i){
        printf("%d ",C[i]);
    }
    printf("\n");
    return 0;
}

习题3:谁是你的潜在朋友

提交网址:http://t.cn/AiCux4f7

在这里插入图片描述
在这里插入图片描述


#include <cstdio>
#include <cstring>

int main() {
    int N,M;
    while(scanf("%d%d",&N,&M) != EOF){
        int book[210];  //存储某书对应的读者数量
        int index[210];//存储输入的书的编号
        memset(book,0,sizeof(book));
        memset(index,0,sizeof(index));
        for(int i = 0; i < N; ++i){
            scanf("%d",&index[i]);
            book[index[i]]++;
        }
        for(int i = 0; i < N; ++i){
            if(book[index[i]] > 1){
                printf("%d\n",book[index[i]]-1);
            }else{
                printf("BeiJu\n");
            }
        }
    }
    return 0;
}

习题4:子串计算 (字符串、map)

提交网址:https://www.acwing.com/problem/content/3450/
https://www.nowcoder.com/share/jump/2891302591705805685202

在这里插入图片描述

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string,int> map1;
    string str;
    cin >> str;
    for(int i = 0; i < str.size(); ++i){
        for(int j = 1; j<=str.size()-i; ++j){
            string sub_str = str.substr(i,j);  //substr(起始下标,截取长度)
            map1[sub_str]++;
        }
    }
    map<string,int>::iterator it;
    for(it = map1.begin(); it != map1.end(); ++it){
        if(it->second > 1){
            printf("%s %d\n",it->first.c_str(),it->second);
        }
    }
    return 0;
}

习题5:WERTYU (字符串)

提交网址:https://www.acwing.com/problem/content/3479/
https://www.nowcoder.com/share/jump/2891302591705809024955
在这里插入图片描述


习题6:罗马数字

提交网址:https://www.acwing.com/problem/content/5081/

在这里插入图片描述
在这里插入图片描述

在这里插入代码片

习题7:三元组

提交网址:https://www.acwing.com/problem/content/3546/

在这里插入图片描述
在这里插入图片描述


习题8:空闲块

提交网址:https://www.acwing.com/problem/content/5076/

文章来源:https://blog.csdn.net/Edward1027/article/details/135511540
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。