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

文章目录

  • 第1章 绪论
    • (1)如何准备机试
    • (2)OJ和开发环境简介
    • (3)OJ的原理、OJ的几种情况
    • (4)学习建议
    • (5)23版内容
    • (6)常犯的编程小错误
    • (7)其他小问题一览
      • int取值范围
      • ②return 0 缺省问题
      • ③万能头文件 #include <bits/stdc++.h>
      • ④scanf、printf 比 cin、cout 更节约时间
      • 不确定数量的输入 while(scanf("%d",&n) != EOF){ }
      • ⑥输入m组数据:while( != EOF) + for循环
      • ⑦变量的作用域
      • ⑧scanf("%d %c %c",&n,&in,&out):%c不忽略空格
  • 第2章 枚举和模拟
    • (一) 枚举 (暴力法)
      • 1.枚举问题简介
      • 2.编程规范
        • (1)变量命名规范
        • (2)判断时,左边写常量,右边写变量/表达式
        • (3)不要省略花括号 (大括号)
        • (4)增量编写法:写一部分,就测试一部分
      • 3.程序出错的原因
        • (1)编译错误 (compile):基本语法错误 【error C2143】
        • (2)链接错误 (link):函数名写错了 【error LNK2019】
        • (3)运行错误 (run):结果与预期不符,打断点,单步调试,监视
        • (4)代码调试方法:改错只关注第一个错误
        • (5)死循环调试方法补充
      • 4.例题
        • 例题1:abc问题
        • 例题2:反序数
          • (1)Reverse函数:求反序数
      • 5.习题
        • 习题1:对称平方数1
        • 习题2:与7无关的数
        • 习题3:约数的个数
          • (2)Divisor函数:求约数 (求约数的优化是理解难点)
        • 习题4:水仙花数
        • 习题5:Old Bill
    • (二) 模拟
      • 0.模拟问题简述
      • 1.图形排版 (图案打印):列表法+找数字规律
        • (1)字符串
        • (2)二维数组
        • (3)例题
          • 例题1:输出梯形 (2001年清华复试上机)
          • 例题2:打印数字菱形
          • 例题3:叠筐问题
      • 2.日期问题:星期几/年月日
        • (1)用数组存储 月份与天数的对应关系
        • (2)闰年问题
        • (3)已知某一天,求下一天:NextDay函数
        • (4)打印日期用printf,比cout方便
        • (5)C++引用:使用引用作为函数参数
          • ①C语言的值传递:不改变主调函数中参数的值
          • ②C++的引用传递:改变主调函数中参数的值
            • &的含义
        • (6)例题
          • 例题1:今年的第几天?
          • 例题2:打印日期
            • 注意格式化输出,用printf,`%02d`
          • 例题3:日期累加
        • (7)习题
          • 习题1:日期差值
            • 注意格式化输入,用scanf,`%4d%2d%2d`
          • 习题2:打印日期
          • 习题3:日期 (求星期几)
      • 3.简单模拟
        • (1)例题
          • 例题1:xxx定律
        • (2)习题
          • 习题1:特殊乘法
          • 习题2:递推数列
          • 习题3:学分绩点
          • 习题4:买房子
          • 习题5:旋转矩阵
          • 习题6:重复者
          • 习题7:Hello World for U
          • 习题8:坠落的蚂蚁
      • 4.复杂模拟:数据结构
        • (0)和数据结构相关的模拟问题:线性数据结构(vector、list)、非线性数据结构(set、map)
          • ①静态数组、动态数组 vector
          • ②增删改查遍历:方括号运算符、迭代器
            • 迭代器 iterator、尾后指针 end()
        • (1)vector 动态数组 (顺序表)
        • (2)list 双向链表
        • (3)set 集合
        • (4)map 映射
        • (5)例题
          • 例题1:盈数和完数 (vector)
          • 例题2:剩余的树 (vector)
          • 例题3:糖果分享游戏 (vector)
          • 例题4:阶乘的和 (set)
          • 例题5:手机键盘 (map、字符串)
        • (6)习题
          • 习题1:一端进,两端出 (list)
          • 习题2:链表合并 (list或数组)
          • 习题3:谁是你的潜在朋友
          • 习题4:子串计算 (字符串、map)
          • 习题5:WERTYU (字符串)
          • 习题6:罗马数字
          • 习题7:三元组
          • 习题8:空闲块

第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(nai)
按题中的数据即为 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) AB=(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/

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/338266.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

鸿蒙常用容器组件介绍

鸿蒙常用容器组件介绍 前言总结1. Row/Column2. flex3. Stack4. List5. RelativeContainer6. Grid7. Scroll8. Tabs9. WaterFlow参考资料 前言 本文不介绍Text&#xff0c;Image这种单独的视图控件&#xff0c;主要还是过一下在构成一个复杂页面时所需要的外层的容器组件。免得…

【Unity学习笔记】New Input System 部分源码和测试用例补充

转载请注明出处&#xff1a;&#x1f517;https://blog.csdn.net/weixin_44013533/article/details/135630016 作者&#xff1a;CSDN|Ringleader| 主要参考&#xff1a; Unity官方Input System手册与API【Unity学习笔记】Unity TestRunner使用【Unity学习笔记】第十二 New Inp…

【征服redis14】认真理解一致性Hash与Redis的三种集群

前面我们介绍了主从复制的方式和sentinel方式&#xff0c;这里我们看第三种模式-Cluster方式。 目录 1.前两种集群模式的特征与不足 2.Cluster模式 2.1 Cluster模式原理 2.2 数据分片与槽位 2.3 Cluster模式配置和实现 3.一致性Hash 3.1 哈希后取模 3.2 一致性Hash算法…

proteus8.15安装教程

proteus8.15安装教程 1.管理员运行 2.一直NEXT到这一步&#xff0c;需要注意&#xff0c;一定要选这一个 3.选中后出现 4.一直下一步到更新 这边结束后准备激活&#xff1a; 1.安装激活插件&#xff0c;先关闭防火墙 2.下一步 3.最后&#xff0c;将数据库放在根目录下 …

RHEL - 更新升级软件或系统

《OpenShift / RHEL / DevSecOps 汇总目录》 文章目录 小版本软件更新yum update 和 yum upgrade 的区别升级软件和升级系统检查软件包是否可升级指定升级软件使用的发行版本方法1方法2方法3方法4 查看软件升级类型更新升级指定的 RHSA/RHBA/RHEA更新升级指定的 CVE更新升级指定…

【C语言】深度探讨文件操作(一)

文章目录 &#x1f4dd;前言&#x1f320; 为什么使用文件&#xff1f;&#x1f309;什么是文件&#xff1f; &#x1f320;程序文件&#x1f309;数据文件 &#x1f320;文件名&#x1f309;二进制文件和文本文件&#xff1f; &#x1f320;文件的打开和关闭&#x1f309; 流和…

机器人电机综述 — 电机分类、舵机、步进与伺服、物理性质和伺服控制系统

电机综述 图片与部分素材来自知乎大佬不看后悔&#xff01;最全的电机分类&#xff0c;看这一篇就够了&#xff01; - 知乎 (zhihu.com)&#xff0c;本文只是把机器人中常用的电机知识提炼了一下 1 按照结构和工作原理划分 1. 同步电机 ​ 电机的转速与定子磁场的转速相同步…

《WebKit 技术内幕》之八(1):硬件加速机制

《WebKit 技术内幕》之八&#xff08;1&#xff09;&#xff1a;硬件加速机制 1 硬件加速基础 1.1 概念 这里说的硬件加速技术是指使用GPU的硬件能力来帮助渲染网页&#xff0c;因为GPU的作用主要是用来绘制3D图形并且性能特别好&#xff0c;这是它的专长所在&#xff0c;它…

k8s 使用cert-manager证书管理自签

个人建议使用安装更快&#xff0c;比helm快&#xff0c;还要等待安装crd kubectl apply -f https://github.com/cert-manager/cert-manager/releases/download/v1.13.3/cert-manager.yaml#官网 https://cert-manager.io/docs/installation/kubectl/#创建自签的ClusterIssuer c…

数据库设计最佳实践:学院个人信息管理系统中的MySQL优化

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

【C++记忆站】类和对象(一)

类和对象(一) 1.面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解决问题 C是基于面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情拆分成不同的对象&#xff0c;靠对象之间…

2024年热门项目管理软件推荐:提升项目管理效率的工具集合

项目管理系统软件有哪些&#xff1f;本文将根据项目管理系统软件的功能、选择项目管理系统软件对公司的好处&#xff0c;根据国际上知名软件评测网站G2 Grid的评测结果对8款2024年好用的项目管理软件&#xff1a;Zoho Projects、Smartsheet、monday、Asana、ClickUp、Notion、A…

elasticsearch备份恢复,elasticdump使用

准备环境 1. 将node-v10.23.1-linux-x64.tar.xz上传到服务器/usr/local目录下 2. tar xf node-v10.23.1-linux-x64.tar.xz 3. 将node_modules.tar.gz上传到服务器/usr/local目录 4. tar -zxvf node_modules.tar.gz 5. 设置NODE环境 5.1 vim /etc/profile export NODEJS_…

YOLOv5全网首发:新一代高效可形变卷积DCNv4如何做二次创新?高效结合SPPF

💡💡💡本文独家改进:DCNv4更快收敛、更高速度、更高性能,与YOLOv5 SPPF高效结合 收录 YOLOv5原创自研 https://blog.csdn.net/m0_63774211/category_12511931.html 💡💡💡全网独家首发创新(原创),适合paper !!! 💡💡💡 2024年计算机视觉顶会创…

[python]使用pyqt5搭建yolov8钢筋计数一次性钢材计数系统

【官方框架地址】 github地址&#xff1a;https://github.com/ultralytics/ultralytics 【算法介绍】 Yolov8是一种先进的深度学习模型&#xff0c;用于目标检测和识别。在钢筋计数任务中&#xff0c;Yolov8可以有效地识别和计数图像中的钢筋。下面是对如何使用Yolov8实现钢筋…

Java SE入门及基础(25)

目录 方法带参&#xff08;续第24篇&#xff09; 6.方法参数传递规则 方法传参来自官方的说明 基本数据类型传值案例 基本数据类型传值时传递的是值的拷贝 引用数据类型传值案例 引用数据类型传值时传递的是对象在堆内存上的空间地址 Java SE文章参考:Java SE入门及基础知…

【C++第二课 - 类和对象上 - 入门知识】struct类、class类、访问限定符、this指针

目录 面向过程与面向对象初步认识类的定义struct定义类class定义类 类的访问限定符及封装访问限定符 声明与定义分离this指针类成员的命名问题this 类的实例化类的对象大小的计算成员函数为何不在对象里面类对象大小计算 面向过程与面向对象初步认识 C语言是面向过程的&#x…

线程和进程的区别(从JVM角度出发)

进程与线程的区别 线程具有许多传统进程所具有的特征&#xff0c;故又称为轻型进程(Light—Weight Process)或进程元&#xff1b;而把传统的进程称为重型进程(Heavy—Weight Process)&#xff0c;它相当于只有一个线程的任务。在引入了线程的操作系统中&#xff0c;通常一个进…

Linux 的提示符太长了,帮你精简一下

普通用户修改文件 ~/.bashrc 修改 50 行左右的代码&#xff0c;将两个w改为大写的W 如果是root用户则修改文件/root/.bashrc&#xff0c;同样的方法。

自然语言推断:注意力之注意(Attending)

注意&#xff08;Attending&#xff09; 第一步是将一个文本序列中的词元与另一个序列中的每个词元对齐。假设前提是“我确实需要睡眠”&#xff0c;假设是“我累了”。由于语义上的相似性&#xff0c;我们不妨将假设中的“我”与前提中的“我”对齐&#xff0c;将假设中的“累…