文章目录
- 第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(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/i
与 if(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/