【一】【算法分析与设计】基础测试

排列式

题目描述

　　7254是一个不寻常的数，因为它可以表示为7254 = 39 x 186，这个式子中1~9每个数字正好出现一次

　　输出所有这样的不同的式子（乘数交换被认为是相同的式子）

　　结果小的先输出；结果相同的，较小的乘数较小的先输出。

输入描述:

　　每一行输出一个式子，式子中的等号前后空格、乘号（用字母x代表）前后空格

　　较小的乘数写在前面

输出描述:

示例1

输入

输出

4396 = 28 x 157

5346 = 18 x 297

5346 = 27 x 198

5796 = 12 x 483

5796 = 42 x 138

6952 = 4 x 1738

7254 = 39 x 186

7632 = 48 x 159

7852 = 4 x 1963

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;bool isValid(int a, int b, int c) {int count[10] = {0}; // 0-9的计数器，0位置不使用while (a > 0) { count[a % 10]++; a /= 10; }while (b > 0) { count[b % 10]++; b /= 10; }while (c > 0) { count[c % 10]++; c /= 10; }for (int i = 1; i <= 9; i++) {if (count[i] != 1) return false; // 检查1-9是否每个恰好出现一次}return count[0] == 0; // 确保数字0没有出现
}int main() {for (int i = 1234; i <= 9876; i++) {for (int j = 2; j <= sqrt(i); j++) {if (i % j == 0) {int k = i / j;if (isValid(i, j, k)) {cout << i << " = " << j << " x " << k << endl;}}}}return 0;
}

思路

首先我们要明确题目需要我们做的事情，我们需要输出一个等式形如a=b*c，这一个等式有一定的要求，a、b、c三个数中，1-9的数字必须有且仅出现1次。

也就是我们需要做两件事情，第一件事情，需要保证a=b*c等式成立，第二件事情，a、b、c三个数中，1-9的数字必须有且仅出现1次。

代码解析

这段代码的目标是找到所有的四位数i（从1234到9876），这些四位数可以分解为两个因子j和k（i = j * k），并且在这个等式中，数字1到9每个恰好出现一次，而数字0不出现。

函数isValid

三个整数a、b和c，分别代表要检查的四位数和它的两个因子。

检查这三个数组成的集合中，数字1到9是否每个恰好出现一次，而0不出现。

使用一个count数组来计数数字0到9的出现次数，数组的索引对应于数字本身。

遍历a、b和c中的每个数字，将其分解为单个数字，并在count数组中相应位置增加计数。

遍历count数组（从1到9），检查每个数字是否恰好出现一次。如果任何一个数字出现次数不为1，返回false。

最后，确保数字0没有出现，即count[0]应该为0。

主函数main

找到所有符合条件的四位数及其因子。

遍历从1234到9876的所有四位数，对于每个数i，尝试找到所有可能的因子j。

因子j的范围是从2到sqrt(i)，因为超过sqrt(i)的因子将会产生重复的乘积组合。

对于每个j，如果j是i的因子（即i % j == 0），则计算另一个因子k = i / j。

调用isValid函数检查i、j和k是否符合条件（即在这三个数中，数字1到9每个恰好出现一次，而0不出现）。

如果符合条件，输出等式i = j x k。

乘法表

题目描述

输出九九乘法表，输出格式见样例。

输入描述:

此题没有输入

输出描述:

输出乘法表，对齐方式见样例输出

示例1

输入

无

输出

1*1= 1

1*2= 2 2*2= 4

1*3= 3 2*3= 6 3*3= 9

1*4= 4 2*4= 8 3*4=12 4*4=16

1*5= 5 2*5=10 3*5=15 4*5=20 5*5=25

1*6= 6 2*6=12 3*6=18 4*6=24 5*6=30 6*6=36

1*7= 7 2*7=14 3*7=21 4*7=28 5*7=35 6*7=42 7*7=49

1*8= 8 2*8=16 3*8=24 4*8=32 5*8=40 6*8=48 7*8=56 8*8=64

1*9= 9 2*9=18 3*9=27 4*9=36 5*9=45 6*9=54 7*9=63 8*9=72 9*9=81

#include<iostream>
using namespace std;
int main(){for(int i=1;i<=9;i++){for(int j=1;j<=i;j++){if(j!=1) cout<<" ";cout<<j<<"*"<<i<<"=";printf("%2d",i*j);}cout<<endl;}
}

送分题

题目描述

数据结构之神ccz又在出毒瘤数据结构了

神出了这样一个题：

给你三个数，在这三个数中间任意加*或者是+，然后可以随便打括号，只要这个表达式合法

比如说1 2 3可以得到：

1+2*3=7

1*(2+3)=5

1*2*3=6

(1+2)*3=9

不能改变这三个数的原顺序

最大化表达式的值

输入描述:

输入三行，每行一个数

分别表示a，b，c

输出描述:

输出一行一个数表示答案

示例1

输入

1

2

3

输出

9

示例2

输入

2

10

3

输出

60

备注:

1 <= a , b , c <= 10

#include<iostream>
using namespace std;int main() {int a,b,c;cin>>a>>b>>c;int ret1,ret3;int x12=max(a+b,a*b);int x23=max(b+c,b*c);ret1=max(x12+c,x12*c);ret3=max(x23+a,x23*a);cout<<max(ret1,ret3);return 0;
}

思路

首先我们有三个数字a，b，c，我们不可以改变这三个数字的相对位置，可以任意添加+或者*以及括号。整个过程相当于需要进行两次运算，第一次运算，要么是a和b运算，要么是b和c运算，因为无法改变相对位置，所以没办法让a和c运算，如果a和b运算，我们需要得到较大的值，只需要在+和*两种情况中选出最大的即可，max(a+b,a*b);。如果b和c运算，我们需要得到较大的值，只需要在+和*两种情况中选出最大的即可，max(b+c,b*c);。最后对于这两种情况，可以得到相应的答案，ret1=max(x12+c,x12*c); ret3=max(x23+a,x23*a);。最后选出最大值输出即可。

对于不同的情况，计算出结果。贪心的思想，每次都做最优的选择，得到的结果就是最优的。

代码解析

这段代码的目的是接收三个整数a、b、c作为输入，然后通过在这三个数之间插入加法或乘法运算符，尝试找出能够得到的最大结果。这个过程没有改变数字的原始顺序，即只考虑在给定顺序下的运算。

通过cin从标准输入读取三个整数a、b、c。

x12=max(a+b,a*b);：计算a和b这两个数通过加法或乘法能得到的最大值，并将结果存储在x12中。

x23=max(b+c,b*c);：计算b和c这两个数通过加法或乘法能得到的最大值，并将结果存储在x23中。

ret1=max(x12+c,x12*c);：以x12为基础，考虑将c加到x12的结果上或将c与x12相乘，从这两个操作中选择能得到的最大值，结果存储在ret1中。

ret3=max(x23+a,x23*a);：以x23为基础，考虑将a加到x23的结果上或将a与x23相乘，从这两个操作中选择能得到的最大值，结果存储在ret3中。

通过cout输出ret1和ret3之间的最大值，即所有考虑过的运算组合中可能得到的最大结果。

[NOIP2008]ISBN号码

题目描述

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

识别码的计算方法如下：

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

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

输入描述:

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

输出描述:

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

示例1

输入

0-670-82162-4

输出

Right

示例2

输入

0-670-82162-0

输出

0-670-82162-4

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){vector<int> d;string str;cin>>str;for(auto x:str){if(x-'0'>=0&&x-'0'<=9){d.push_back(x-'0');}}int sum=0;for(size_t i=0;i<d.size()-1;i++){sum+=d[i]*(i+1);}sum=sum%11;if(sum==10&&str[str.length()-1]=='X') cout<<"Right";else if(sum==(str[str.length()-1]-'0')) cout<<"Right";else{if(sum==10){str[str.length()-1]='X';}else{str[str.length()-1]=sum+'0';}cout<<str;}return 0;
}

这段代码的目的是验证并纠正一个包含ISBN（国际标准书号）的字符串。ISBN的最后一位是一个校验码，可以是0到9之间的任何数字，或者是字符'X'来代表10。这个校验码是通过前面的数字按照一定的规则计算得出的，以确保ISBN的正确性。具体来说，这段代码执行以下步骤：

用户输入一个字符串str，代表一个可能的ISBN号。

遍历字符串str，将其中的数字字符转换为整数，并存储在向量d中。

通过遍历d向量，计算前面所有数字（除了最后一个数字，它是待验证的校验码）的加权和。加权规则是：每个数字乘以它的位置索引（从1开始计数），然后将这些乘积相加。

将加权和对11取模，得到的结果就是计算出的校验码sum。

如果sum为10，并且字符串的最后一个字符是'X'，则输出"Right"，表示校验码正确。

如果sum与字符串最后一个字符代表的数字相等，也输出"Right"。

如果两个条件都不满足，则说明校验码错误，需要纠正：

如果sum为10，则将字符串最后一个字符替换为'X'。

否则，将其替换为sum对应的数字字符。

然后输出纠正后的完整ISBN字符串。

代码中的逻辑基于ISBN的校验码计算规则，即通过特定的加权和模11得到的结果。这种校验机制用于检测ISBN号中的输入错误或偶然的错误。

前天是哪天

题目描述

给定公元2000年到公元3000年之间的某一天，请你给出该天的前天是哪一天.

输入描述:

输入在一个日期，格式如"yyyy-mm-dd"，题目保证所有输入日期为合法日期。

输出描述:

在一行中输出日期，格式如"yyyy-mm-dd"。

示例1

输入

2020-11-15

输出

2020-11-13

备注:

注意日期格式，月份或者天数不足2位要补零。

/*日期类代码实现*/
#include <iostream>
using namespace std;
#include<string>
class Date {
public:int GetMonthDay(int year, int month) {static int monthDays[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};if (month == 2 && ( (year % 4 == 0 && year % 100 != 0) || year % 400 == 0)) {return 29;}return monthDays[month];}Date(int year = 0, int month = 1, int day = 1) {if (year >= 0&& month >= 1 && month <= 12&& day >= 1 && day <= GetMonthDay(year, month)) {_year = year;_month = month;_day = day;} else {cout << "非法日期" << endl;}}bool operator<(const Date& d) {if (_year < d._year)return true;else if (_year == d._year && _month < d._month)return true;else if (_year == d._year && _month == d._month && _day < d._day)return true;elsereturn false;}bool operator==(const Date& d) {return _year == d._year && _month == d._month && _day == d._day;}bool operator<=(const Date& d) {return (*this) < d || (*this) == d;}bool operator>(const Date& d) {return !((*this) <= d);}bool operator>=(const Date& d) {return !((*this) < d);}bool operator!=(const Date& d) {return !((*this) == d);}Date& operator+=(int day) {if (day < 0) {return (*this) -= -day;}_day += day;while (_day > GetMonthDay(_year, _month)) {_day -= GetMonthDay(_year, _month);_month++;if (_month == 13) {_year++;_month = 1;}}return *this;}Date operator+(int day) {if (day < 0) {return (*this) - (-day);}Date ret(*this);ret += day;return ret;}Date& operator-=(int day) {if (day < 0) {return (*this) += -day;}_day -= day;while (_day <= 0) {_month--;if (_month == 0) {_year--;_month = 12;}_day += GetMonthDay(_year, _month);}return *this;}Date operator-(int day) {if (day < 0) {return (*this) + (-day);}Date ret(*this);ret -= day;return ret;}Date& operator++() {(*this) += 1;return *this;}Date operator++(int) {Date ret(*this);(*this) += 1;return ret;}Date& operator--() {(*this) -= 1;return *this;}Date operator--(int) {Date ret(*this);(*this) -= 1;return ret;}void Show() {printf("%d-%02d-%02d",_year,_month,_day);}
private:int _year;int _month;int _day;
};int main() {string str;cin>>str;int year,month,day;int pos1=str.find("-");int pos2=str.rfind("-");year=stoi(str.substr(0,pos1));month=stoi(str.substr(pos1+1,pos2-(pos1+1)));day=stoi(str.substr(pos2+1));Date d(year,month,day);d-=2;d.Show();return 0;
}

小名的回答

题目描述

总算到暑假了，小姐姐是非常的闲，所以想去找梅溪湖的小名玩，可是她从没去过梅溪湖，所以只能凭小名告诉她的地方走，每次只能向上下左右四个方向走1步。小姐姐的坐标为(0,0)，小名在(a,b)，小姐姐有点近视，小名也有点近视。所以到了(a,b)也不一定能和小名会面，不过还好，小姐姐最后找到了小名。小姐姐想要小名知道自己来一趟是多么不容易，所以在聊天的过程中小姐姐说自己为了到这里走了n步。小名，你觉得她说的可能是真话么。有可能就输出YES,否则输出NO(如果用random的话,小姐姐觉得你好像不在意她，明年暑假就不来了)

输入描述:

a,b,n(-1000<=a,b<=1000,a*b>0,1<=n<=2000)

输出描述:

"YES" or "NO"

示例1

输入

2 2 4

输出

YES

示例2

输入

1 9 2

输出

NO

#include<iostream>
using namespace std;
int main(){int a,b,n;cin>>a>>b>>n;int c=abs(a)+abs(b);if(n>=c&&(n-c)%2==0) cout<<"YES";else cout<<"NO";
}

if(n>=c&&(n-c)%2==0)这个if语句检查是否可以在n步内到达(a, b)。首先，n必须大于或等于c，即有足够的步数到达目标。其次，(n-c)%2==0确保在到达目标后，剩余的步数是偶数。因为每多出一步，都需要再多一步才能回到目标点，所以剩余步数必须是偶数。

如果姐姐可以到目标位置，那么她走的路线一定含有必须行走的最短路径，其他走的路都是多余的，多出来的步数是否合理，只需要看是否可以走出目标地点再走回目标地点，也就是偶数即可。

[NOIP2004]不高兴的津津

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

5 3

6 2

7 2

5 3

5 4

0 4

0 6

输出

3

#include<iostream>
#include<vector>
using namespace std;
int main(){vector<vector<int>> vv(7, vector<int>(2, 0));for(int i=0;i<7;i++){cin>>vv[i][0]>>vv[i][1];if(vv[i][0]+vv[i][1]>8) {cout<<i+1;return 0;}}cout<<0;
}

代码解析

这行代码使我们可以直接使用std命名空间中的所有成员，而不需要在每个标准库类或函数前加std::前缀。

vector<vector<intvv(7, vector<int(2, 0));

这行代码声明了一个名为vv的二维向量（向量的向量），并初始化为7行2列，所有元素初始值为0。这意味着vv可以存储7天的数据，每天有两个整数。 for(int i=0;i<7;i++){

这个循环从0迭代到6，用于逐天读取输入数据。 cin>>vv[i][0]>>vv[i][1];

这行代码从标准输入读取两个整数，并将它们存储在vv的第i行中。vv[i][0]和vv[i][1]分别代表第i天的两个整数。 if(vv[i][0]+vv[i][1]>8) {

这个if语句检查第i天的两个整数之和是否大于8。

cout<<i+1;

如果某天的整数之和首次超过8，则输出那天的编号（因为编号从1开始，所以输出i+1），然后： cout<<0;

如果循环结束后没有找到任何一天的整数之和超过8，则输出0。

C++格式化的探究

在C++中，cout确实可以用于格式化输出，但它的方式与传统的C语言中的printf函数略有不同。C++中的cout是基于流的输出，使用<<操作符来连续地将数据发送到输出。为了实现格式化输出，可以在cout语句中使用一些特殊的控制符号来修改输出的格式，如设置宽度、填充字符和小数点精度等。

设置宽度和填充

你可以使用setw()和setfill()来设置下一个输出字段的宽度和填充字符。设置宽度仅仅对下一个数据有效。设置填充依旧是持续的效果。

#include <iostream>
#include <iomanip> // 需要包含这个头文件来使用setw和setfillusing namespace std;int main() {cout << setw(10) << setfill('*') << 123 << endl;cout << setw(10) << 123 << endl;// 输出: //*******123//*******123return 0;}

控制浮点数精度

使用setprecision()来控制浮点数的输出精度。设置精度是持续的效果。

#include <iostream>
#include <iomanip> // 需要包含这个头文件来使用setprecisionusing namespace std;int main() {double pi = 3.14159265358979;cout << setprecision(5) << pi <<  endl << pi << endl; // 显示5位有效数字cout << setprecision(9) << pi << endl; // 显示9位有效数字cout << fixed << setprecision(3) << pi << endl; // 固定小数点显示3位小数// 输出://3.1416//3.1416//3.14159265//3.142return 0;}

设置左对齐或右对齐

使用left和right控制符来设置对齐方式。setw设置宽度只对下一个输出的数据有效，而设置左右对齐一直都有效。

#include <iostream>
#include <iomanip>using namespace std;int main() {cout << setw(10) << left << 123 << "end" << setw(5) << 234 << right <<"end"<< setw(5) << 123 << "end" << endl; // 左对齐cout << setw(10) << right << 123 << "end" << endl; // 右对齐// 输出://123       end234  end  123end//123endreturn 0;}

十六进制、八进制和十进制输出

可以使用hex、oct和dec来控制整数的输出格式。设置进制也是持续的效果。

#include <iostream>
using namespace std;int main() {int num = 255;cout << hex << num << endl; // 十六进制cout << 255 << endl;cout << oct << num << endl; // 八进制cout << dec << num << endl; // 十进制// 输出://ff//ff//377//255return 0;}