从今天开始刷PAT (Basic Level) Practice，每天两道（至少<_<）💪💪
coding原则：
自顶向下->逐步细化->模块化设计->结构化编码
——1.25更新——
1001：【while循环】💯
01程序分析：
就是一个简单的while循环，没什么好多说的。
02参考解答：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
int n,re=0;
cin>>n;
while(n!=1){
if(n%2==0){
n=n/2;//equals to n/=2
}
else{
n=(3*n+1)/2;
}
re++;
}
cout<<re<<endl;
}
03题目总结：
暂无
1002：【string类、二维字符数组】
01程序分析：
一、输入
step1：输入一个正整数(string num)。
二、处理数据
step2：计算各个位置上的数字之和(int sum)，将和转化为字符串，从前到后依次读数(string s1)。
三、输入
step3：构造一个数字-拼音二维字符数组(char p[][][])，将取出的数映射到这个二维字符数组上，输出。
02参考解答：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
string num;
int sum=0;//auto sum=0
char p[11][20]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu","shi"};
cin>>num;
for(auto i:num)
sum+=i-'0';
string s1=to_string(sum);
for(int i=0;i<s1.size();i++){
if(i!=0){
cout<<' ';
}//先输入空格再输数字，就不会出现最后一个数字后有空格的现象了
cout<<p[s1[i]-'0'];
}
return 0;
}
03题目总结：
1、 auto 类型
auto类型是 C++11 新标准中的，用来自动获取变量的类型。
for (auto &x : my_array) {
x *= 2;
cout << x << endl;
}
上面for述句的第一部分定义被用来做范围迭代的变量，就像被声明在一般for循环的变量一样（而不只是循环控制变量），其作用域仅只于循环的范围。而在":"之后的第二区块，代表将被迭代的范围。
——1.26更新——
1004：【结构体类型的向量、排序】💯
01程序分析：
一、输入
step1：定义结构体(struct)，输入数据。
二、处理数据
step2：将数据进行排序(sort函数)
三、输入
step3：输出成绩最高和成绩最低的学生的姓名和学号。
02参考解答：
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
//定义一个结构体，包含姓名、学号、成绩3个成员
struct Student
{
string name;
string num;
int score;
};
bool comp(Student x, Student y) {
if (x.score != y.score)
return x.score > y.score;
return true;
}
int main()
{
vector<Student> p;
int n;
Student s;
cin>>n;
getchar();
//赋值？
for(int i=0;i<n;i++){
cin>>s.name>>s.num>>s.score;
p.push_back(s);
}
//排序
sort(p.begin(),p.begin()+n,comp);
cout<<p[0].name<<' '<<p[0].num<<endl;
cout<<p[n-1].name<<' '<<p[n-1].num<<endl;
}
03题目总结：
1、vector
一、介绍
- 定义（是什么）：向量
vector是一种对象实体, 能够容纳许多其他类型相同的元素, 因此又被称为容器。 与string相同,vector同属于STL（Standard Template Library, 标准模板库）中的一种自定义的数据类型, 可以广义上认为是数组的增强版。 - 优点（为什么用）：
vector容器与数组相比其优点在于它能够根据需要随时自动调整自身的大小以便容下所要放入的元素。此外,vector也提供了许多的方法来对自身进行操作。 - 用法（怎么用）：在使用它时, 需要包含头文件
#include<vector>。
二、向量的基本操作
1、push_back( )成员函数在向量的末尾插入值，如果有必要会扩展向量的大小。
2、size( )函数显示向量的大小，获取向量中的元素个数。
3、begin( )函数返回一个指向向量开头的迭代器。
4、end( )函数返回一个指向向量末尾的迭代器。
三、二维向量
与数组相同, 向量也可以增加维数, 例如声明一个m*n大小的二维向量方式可以像如下形式：
vector< vector<int> > b(10, vector<int>(5)); //这里，两个“>”间的空格是不可少的
在这里, 实际上创建的是一个向量中元素为向量的向量。同样可以根据一维向量的相关特性对二维向量进行操作。 除此之外, 还可以直接使用数组来初始化向量。
1005：【标记】💯
参考解答：
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
bool comp(int a,int b){
return a>b;
}
int main()
{
//step1：输入n个整数
vector<bool> flag(1000000,false);//相当于有1000000个元素的数组
int n,temp;
cin>>n;
//step2：构造一个数组标记关键数
vector<int> data(n);//用来标记关键数
for(int i=0;i<n;i++){
cin>>data[i];
if(flag[data[i]])
continue;
temp=data[i];
while(temp!=1){
if(temp%2==0){
temp/=2;
}
else{
temp=(3*temp+1)/2;
}
if(flag[temp])
break;
flag[temp]=true;
}
}
//step3：将关键数按从大到小的顺序排序（sort），再输出
sort(data.begin(),data.end(),comp);
bool space=false;
for(auto i:data){
if(!flag[i]){
if(space)
cout<<' ';
cout<<i;
space=true;
}
}
}
——1.27更新——
1006：【if条件语句】💯
参考解答：
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
//step1：输入一个正整数(int n)
int n,a,b,c;
cin>>n;
//step2：提取数字
while(n!=0){
if(n/100!=0){
//step2-1：三位数，提取百位数字（int a），输出a个B
a=n/100;
for(int i=0;i<a;i++){
cout<<'B';
}
n=n%100;
}
//step2-2：两位数，提取十位数字（int b），输出b个S
if(n/10!=0){
b=n/10;
for(int i=0;i<b;i++){
cout<<'S';
}
n=n%10;
}
//step2-3：一位数，提取出个位数字（int c），输出1…c
for(int i=0;i<n;i++){
cout<<i+1;
}
n=n/10;
}
}
【题目总结】
✨Hogan's inspiration：如遇到一些题目，for循环的框架是一样的，可以做合并处理，简化程序。
1007：【埃氏筛选法】💯
参考解答
#include <iostream>
#include <vector>
#include <string>
#include<math.h>
using namespace std;
vector<bool> data1(1000000,true);
void init(){
data1[0]=data1[1]=false;
for(int i=2;i<1000000;i++){
if(data1[i]){
for(int j=i+i;j<1000000;j+=i){
data1[j]=false;
}
}
}
}
int main(){
//step1：利用埃氏筛选法选出素数
init();
//step2：输入查找范围
int N,c;
c=0;
cin>>N;
//step3：记录素数对的个数
for(int i=2;i<N-1;i++){
if(data1[i]&&data1[i+2])
c++;
}
cout<<c;
return 0;
}
【题目总结】
✨Hogan's inspiration：埃氏筛选法是在一个数组中标记出哪些是素数、哪些不是，方便查找。比写一个判断素数的函数，然而每次都在主函数中调用更快。
——1.28更新——
1008：【数组、循环移动、反转】
参考解答
V1.0 小白版本
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
//step1：输入一个数组及要移动的次数M
int N,M,temp;
cin>>N;
cin>>M;
int a[N];
for(int i=0;i<N;i++){
cin>>a[i];
}
//step2：依次向右移动，从1次到M次
for(int i=0;i<M;i++){
temp=a[N-1];
for(int j=N-1;j>0;j--){
a[j]=a[j-1];
}
a[0]=temp;
}
//step3：输出移动后的数组
for(int i=0;i<N;i++){
if(i!=0) cout<<' ';
cout<<a[i];
}
return 0;
}
V2.0 Hogan's inspiration
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
int main(){
//step1：输入一个数组及要移动的次数M
int N,M,temp;
cin>>N;
cin>>M;
vector<int> a(N);
for(int i=0;i<N;i++){
cin>>a[i];
}
M=M%N;//*异常处理：当M>N时，防止M溢出
//step2：【算法】数组向右移动M位等价于前N-M个数反转，后M个数反转，再整体反转
reverse(a.begin(),a.begin()+N-M);
reverse(a.begin()+N-M,a.end());
reverse(a.begin(),a.end());
for(int i=0;i<N;i++){
if(i!=0) cout<<' ';
cout<<a[i];
}
//step3：输出移动后的数组
return 0;
}
1009：【字符串】💯
参考解答：
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
int main(){
//step1：将句子中的所有单词放入一个容器内
vector<string> s;
string t;
while(cin>>t){
s.push_back(t);
}
//step2：反转这个字符串向量
reverse(s.begin(),s.end());//等价于 reverse(s.begin(),s.begin()+s.size());
//step3：输出这个向量
bool space=false;//【算法】注意空格的处理
for(auto i:s){
if(space)
cout<<' ';
cout<<i;
space=true;
}
return 0;
}
——2.1更新——
1010：【求导、成对输出】💯
参考解答
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
int main(){
//step1：输入一个一元多项式
vector<int> s;//【算法】一行输入以空格隔开的数字如何存到一个数组中
int t;
while(cin>>t){
s.push_back(t);
}
//step2：求导
for(int i=0;i<s.size();i+=2){
s[i]=s[i]*s[i+1];
s[i+1]=s[i+1]-1;
}
//step3：输出
bool space=false;
for(int i=0;i<s.size()-1;i+=2){
if(s[i]==0)
break;//*异常处理：零多项式情况
if(space)
cout<<' ';
cout<<s[i]<<' '<<s[i+1];//系数和指数成对输出
space=true;
}
if(!space){
cout<<"0 0";//*异常处理：零多项式的输出
}
return 0;
}
1011：【正负数、二维向量】
参考解答
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
int main(){
//step1：输入二维数组
int n;
cin>>n;
long int b[n][3];//*异常处理：这里每个数的范围是int，但后面涉及加法，故和可能超过int，用long int
//step2：判断后输出
for(int i=0;i<n;i++){
for(int j=0;j<3;j++)
cin>>b[i][j];
}
for(int i=0;i<n;i++){
if(b[i][0]+b[i][1]>b[i][2])
cout<<"Case #"<<i+1<<": true"<<endl;
else
cout<<"Case #"<<i+1<<": false"<<endl;
}
return 0;
}
——2.4更新——
1012：【正负数】⚠️有1个测试样例未通过
参考解答
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
int main(){
vector<int> s;
vector<double> r(5,0);
int f1=1,f2=1;
int a,N;
cin>>N;
s.resize(N);
for(int i=0;i<N;i++)
cin>>s[i];
r[4]=s[0];
for(int i=0;i<N;i++){
//A1
if(s[i]%5==0&&s[i]%2==0)
r[0]=r[0]+s[i];
//A2
if(s[i]%5==1){
if(f1%2!=0)
r[1]=r[1]+s[i];
else
r[1]=r[1]-s[i];
f1++;
}
//A3
if(s[i]%5==2)
r[2]++;
//A4
if(s[i]%5==3){
r[3]=(r[3]*(f2-1)+s[i])/f2;
f2++;
}
//A5
if(s[i]%5==4){
if(r[4]<s[i])
r[4]=s[i];
}
}
bool space=false;
for(int i=0;i<5;i++){
if(space)
cout<<' ';
if(r[i]!=0){
if(i==3)
printf("%.1f",r[i]);
else
cout<<r[i];
}
else
cout<<'N';
space=true;
}
}
题目总结
本题有少量测试案例没通过，应该是特殊情况未考虑，不予深究。
1013：【素数】💯
参考解答
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
const int max_N=10000000;//定义一个常数，更方便
vector<bool> data1(max_N,true);
//埃氏筛选法
void init(){
data1[0]=data1[1]=false;//0和1不是质数（质数是指在大于1的自然数中，除了1和它本身以外不再有其它因数的自然数）
for(int i=2;i<max_N;i++){
if(data1[i]){
for(int j=i+i;j<max_N;j+=i){//除0和1外每个数的倍数都不是质数
data1[j]=false;
}
}
}
}
int main(){
//step1：先用埃氏筛选法选出素数
init(); //先调用这个函数，不然无法筛选出质数
int M,N,c=0,flag=0;
cin>>M;
cin>>N;
//step2：找到第M到N个素数，输出
for(int i=0;i<max_N;i++){
if(!data1[i])
continue;
c++;
if(c>N)
break;//*异常处理：不满足条件的直接退出
if(c>=M){
if(flag%10!=0)
cout<<' ';
cout<<i;
flag++;
if(flag%10==0)
cout<<endl;
}
}
return 0;
}
——2.5更新——
1015：【向量元素的分类】
参考解答
1016：【提取每位数】
参考解答
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
int main(){
vector<long long> s,re(2,0);//【算法】一行输入以空格隔开的数字如何存到一个数组中
int t,d;
int j=0;
//step1：输入样例
while(cin>>t){
s.push_back(t);
}
//step2：计算PA,PB
for(int i=0;i<4;i+=2){
while(s[i]!=0){
d=s[i]%10;//提取最低位
if(d==s[i+1])
re[j]=re[j]*10+d;
s[i]=s[i]/10;//去掉最低位
}
j++;
}
//step3：求PA,PB的和
cout<<re[0]+re[1];
return 0;
}
——2.6更新——
1017：💯
参考解答
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main()
{
string A, Q;
int B,R,flag,re;
cin >> A >> B;
re=0;
int t=0;
for(int i=0;i<A.size();i++)
{
t=A[i]-'0'+t*10;
if(t<B){
if(Q.size()==0)
continue;
Q.push_back('0');
// re=re*10+A[i];
}
else{
Q.push_back('0'+ t/B);
// re=re%B*10+A[i];
t=t%B;
}
}
if(Q.size()==0)
cout << 0;
else
cout << Q;
cout <<' '<< t;//*异常处理
return 0;
}
1018：💯
参考解答
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
//甲胜
int comp(char a,char b){
if((a=='C'&&b=='J')||(a=='J'&&b=='B')||(a=='B'&&b=='C'))
return 1;
if(a==b)
return 0;
return -1;
}
int main(){
//step2:输入交锋次数和交锋信息
int N;
cin>>N;
vector<int> r1(3,0),r2(3,0);//分别记录甲乙胜、平、负的次数
vector<int> max_1(3),max_2(3);//分别记录甲乙获胜的B、C、J的个数
char a,b;
getchar();
for(int i=0;i<N;i++){
cin>>a>>b;
getchar();
if(comp(a,b)==1){
r1[0]++;
r2[2]++;
if(a=='B')
max_1[0]++;
else if(a=='C')
max_1[1]++;
else
max_1[2]++;
}
else if(comp(a,b)==0){
r1[1]++;
r2[1]++;
}
else{
r1[2]++;
r2[0]++;
if(b=='B')
max_2[0]++;
else if(b=='C')
max_2[1]++;
else
max_2[2]++;
}
}
//step3:输出最大次数
bool space=false;
for(auto i:r1){
if(space)
cout<<' ';
cout<<i;
space=true;
}
space=false;
cout<<endl;
for(auto i:r2){
if(space)
cout<<' ';
cout<<i;
space=true;
}
cout<<endl;
int temp;
string s="BCJ";
temp=0;
for(int i=1;i<3;i++){
if(max_1[i]>max_1[temp])
temp=i;
}
cout<<s[temp]<<' ';
temp=0;
for(int i=1;i<3;i++){
if(max_2[i]>max_2[temp])
temp=i;
}
cout<<s[temp];
return 0;
}
——2.22更新——
1020：【结构体】💯
参考解答
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
//将每种月饼定义为结构体
struct mooncake
{
float amount;
float price;
float uprice;
};
bool comp(mooncake a, mooncake b)
{
return a.uprice > b.uprice;
}
int main()
{
int n, d, flag = 0;
float r = 0;
cin >> n >> d;
vector<mooncake> t(n);
//step1:输入n种月饼的信息
for (int i = 0; i < n; i++)
cin >> t[i].amount;
for (int i = 0; i < n; i++)
{
cin >> t[i].price;
t[i].uprice = t[i].price / t[i].amount;
}
sort(t.begin(), t.end(), comp);
for (int i = 0; i < n; i++)
{
if (d > t[i].amount)
{
r = r + t[i].amount * t[i].uprice;
d -= t[i].amount;
}
else
{
r = r + d * t[i].uprice;
break;
}
}
printf("%.2f", r);
return 0;
}
1022：【进制转换、栈的运用】💯
参考解答
#include <iostream>
#include <stack>
using namespace std;
int main()
{
int a,b,d;
cin>>a>>b>>d;
int sum=a+b;
stack<int> s;
do{
s.push(sum%d);
sum/=d;
}while(sum!=0);
while(!s.empty()){
cout<<s.top();
s.pop();
}
return 0;
}
1023：【数组向量的存放】💯
参考解答
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
//step1:输入
vector<int> s(10); //存放输入的数
int count = 0;
for (int i = 0; i < 10; i++)
{
cin >> s[i];
count += s[i];
}
vector<int> r(count); //存放输出的数
int flag = 0, i;
//step2:放数
//step2-1:放最小的非0数
for (int i = 0; i < count; i++)
{
if (i == 0)
{
for (int j = 1; j <= 9; j++)
{
if (s[j] != 0)
{
r[i] = j;
s[j]--;
break;
}
}
}
else
{
for (int j = 0; j <= 9; j++)
{
if (s[j] != 0)
{
r[i] = j;
s[j]--;
break;
}
}
}
}
for (auto i : r)
cout << i;
return 0;
}
——2.23更新——
1025：【模拟链表】💯
参考解答
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int first,n,k,temp;
cin>>first>>n>>k;
int data[100000],next[100000],list[100000];
//step1:输入数据
for(int i=0;i<n;i++)
cin>>temp>>data[temp]>>next[temp];
//step2:遍历list
int sum=0;
while(first!=-1){
list[sum++]=first;//先赋值再自增
first=next[first];
}
//step3:反转链表
for(int i=0;i<(sum-sum%k);i+=k)
reverse(begin(list)+i,begin(list)+i+k);
//step4:输出
for(int i=0;i<sum-1;i++)
printf("%05d %d %05d\n",list[i],data[list[i]],list[i+1]);
printf("%05d %d -1\n",list[sum-1],data[list[sum-1]]);
return 0;
}
1027：【打印】
参考解答
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main(){
//step1:在一行给出正整数N和一个符号
int n;
char s;
cin>>n>>s;
//step2:判断输出几行
int m=0;//m为循环次数
int sum=0;//sum是总数
for(int i=1;i<100000;i+=2){
if(sum-1+2*i > n){
break;
}//先判断再改变sum的值，提前终止
sum+=2*i;
m++;
}
//step3:打印
//step3-2:打印上面部分
for(int i=0;i<m;i++){
for(int k=0;k<i;k++)
cout<<' ';
for(int j=0;j<2*(m-i)-1;j++)
cout<<s;
cout<<endl;
}
//step3-2:打印下面部分
for(int i=0;i<m-1;i++){
for(int k=1;k<m-i-1;k++)
cout<<' ';
for(int j=0;j<2*(i+1)+1;j++)
cout<<s;
cout<<endl;
}
//step3-3:输出剩余的数
cout<<n-sum+1;
//各行符号中心对齐
return 0;
}
——2.24更新——
1030：【双重循环】
参考解答
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
//step1:输入数
long long n,p;//10^5、10^9都在int范围内
cin>>n>>p;
vector<int> s(n);
for(int i=0;i<n;i++)
cin>>s[i];
//step2:对给出的数升序排序
sort(s.begin(),s.end());
//step3:升序排序后，第一次遇到的完美数列数个数即最大
int max_c=0;
for(int i=0;i<n;i++){
for(int j=n-1;j>=i;j--){
if(s[j]<=p*s[i]){
max_c=max(j-i+1,max_c);
break;
}
}
}
cout<<max_c;
return 0;
}
1031：【标记】💯
参考解答
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int s[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
string a, check = "10X98765432";
int n, sum;
cin >> n;
int i, j;
bool flg1 = false; //标记所有身份证号中有没有错误数据
for (i = 0; i < n; i++)
{
cin >> a;
//输入一个18位身份证号
bool flg2 = false; //标记每个身份证号前17位是否正确
sum = 0;
for (j = 0; j < 17; j++)
{
if (a[j] < '0' || a[j] > '9')
{
flg1 = true;
flg2 = true;
break;
}
sum = sum + s[j] * (a[j] - '0');
}
//判断并输出
if (flg2 || check[sum % 11] != a[17])
{
cout << a << endl;
flg1 = true;
}
}
if (!flg1)
{
cout << "All passed";
}
return 0;
}
——3.1更新——
1030：【排序】⚠️有1个测试案例未通过
参考解答
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
//step1:输入数
long long n,p;//10^5、10^9都在int范围内
cin>>n>>p;
vector<int> s(n);
for(int i=0;i<n;i++)
cin>>s[i];
//step2:对给出的数升序排序
sort(s.begin(),s.end());
//step3:升序排序后，第一次遇到的完美数列数个数即最大
int max_c=0;
for(int i=0;i<n;i++){
for(int j=n-1;j>=i;j--){
if(s[j]<=p*s[i]){
max_c=max(j-i+1,max_c);
break;
}
}
}
cout<<max_c;
return 0;
}
1031：【连环判断】
题目：
参考解答
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int s[17] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
string a, check = "10X98765432";
int n, sum;
cin >> n;
int i, j;
bool flg1 = false; //标记所有身份证号中有没有错误数据
//step1:依次输入身份证号，并判断
for (i = 0; i < n; i++)
{
cin >> a;
//输入一个18位身份证号
bool flg2 = false; //标记每个身份证号前17位是否正确
sum = 0;
for (j = 0; j < 17; j++)
{
if (a[j] < '0' || a[j] > '9')
{
flg1 = true;
flg2 = true;
break;
}
sum = sum + s[j] * (a[j] - '0');
}
//step2:校验最后一位，并输出
if (flg2 || check[sum % 11] != a[17])
{
cout << a << endl;
flg1 = true;
}
}
//step3:所有都无问题，输出通过
if (!flg1)
{
cout << "All passed";
}
return 0;
}
——3.2更新——
1032：【最大值】💯
参考解答
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
int n, num, sco;
cin >> n;
vector<int> a(n);
//step1:建立一个水桶，将对应下标的学校分数纳入桶中
for (int i = 0; i < n; i++)
{
cin >> num >> sco;
a[num - 1] = a[num - 1] + sco;
}
//step2:找到最大值对应的下标
int max = 0;
for (int i = 1; i < a.size(); i++)
{
if (a[i] > a[max])
max = i;
}
//step3:按要求输出
cout << max + 1 << ' ' << a[max];
return 0;
}
1033：【连环判断】⚠️有一个测试案例答案错误
题目：旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键，打出的结果文字会是怎样？
参考解答
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string broken,orgin;
cin>>broken>>orgin;
int flag[300]={0},c=0;//！注意一位数组整体赋初值的方法
//step1:将坏掉值存入int型数组里
for(auto i:broken){
flag[i]=true;//如坏掉，则赋true（=1)，标记为坏掉
if(i>='A'&&i<='Z')
flag[i-'A'+'a']=true;//*特殊处理：坏掉的字母用大写表示，故需特别处理小写
}
//step2：判断是否缺失并输出
for(auto i:orgin){
if(i>='A'&&i<='Z'&&flag['+']==true)
continue;//*特殊处理：缺失上档键不输出大写字母
if(!flag[i]){
cout<<i;
c++;
}
}
return 0;
}
——3.3更新——
1035：【插入排序、归并排序】💯
参考解答
#include <iostream>
#include <algorithm>
using namespace std;
int n, d[110], after[110];
bool same(int *a, int *b)
{
for (int i = 1; i <= n; i++)
{
if (a[i] != b[i])
return false;
}
return true;
}
void insertSort(int *a, int start)
{
a[0] = a[start];
while (a[0] < a[start - 1])
{
a[start] = a[start - 1];
start--;
}
a[start] = a[0];
}
bool isInsert(int *a, int *after)
{
for (int i = 2; i < n; i++)
{
insertSort(a, i);
if (same(a, after))
{
printf("Insertion Sort\n");
insertSort(a, i + 1);
for (int i = 1; i <= n; i++)
{
if (i != 1)
cout << " ";
cout << a[i];
}
return true;
}
}
return false;
}
void merge(int *d, int step)
{
for (int i = 1;i<n;i+=step)
{
sort(d + i,d + ((i + step) > n+1?n+1:(i+step)));
}
}
void isMerge(int *a, int *after)
{
for (int i = 2; i <= n; i = i * 2 > n ? n : i * 2)
{
merge(a, i);
if (same(a, after))
{
printf("Merge Sort\n");
merge(a, i = i * 2 > n ? n : i * 2);
for (int i = 1; i <= n; i++)
{
if (i != 1)
cout << " ";
cout << a[i];
}
return;
}
}
return;
}
int main()
{
cin >> n;
int copy[110];
for (int i = 1; i <= n; i++)
{
cin >> d[i];
copy[i] = d[i];
}
for (int i = 1; i <= n; i++)
cin >> after[i];
if (!isInsert(d, after))
isMerge(copy, after);
return 0;
}
1036：【循环】💯
#include <iostream>
#include <vector>
using namespace std;
int main()
{
//step1:输入所需参数
int n;
char c;
cin >> n >> c;
//step2:从上往下依次打印。定义两个变量，一个控制行数、一个控制列数
for (int i = 0; i < n * 0.5; i++)//*易错：四舍五入不用'/'
{
cout << c; //每行第一个字符
for (int j = 1; j < n - 1; j++) //第2列到倒数第2列
{
if (i > 0 && i < n * 0.5 - 1)//*易错：四舍五入不用'/'
{
cout << ' ';
continue;
}
cout << c;
}
cout << c; //每行最后一个字符
cout << endl;
}
return 0;
}
1045：【快速排序】⚠️运行超时
参考解答
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool left_max(vector<int> a, int i)
{
if (i == 0)
return true; //*特殊处理
for (int j = 0; j < i; j++)
if (a[j] > a[i])
return false;
return true;
}
bool right_min(vector<int> a, int i)
{
if (i == a.size() - 1)
return true; //*特殊处理
for (int j = i + 1; j < a.size(); j++)
if (a[j] < a[i])
return false;
return true;
}
int main()
{
//step1:输入
int n, c = 0;
cin >> n;
vector<int> a(n), b;
for (int i = 0; i < n; i++)
cin >> a[i];
//step2:判断各位元素是否是主元。若是主元，存入新数组
for (int i = 0; i < n; i++)
{
if (!left_max(a, i) || !right_min(a, i))
continue;
else
{
b.push_back(a[i]);
c++;
}
}
//step3:对主元进行排序后输出
cout << c << endl;
sort(b.begin(), b.begin() + c);
bool space = false;
for (int i = 0; i < c; i++)
{
if (space)
cout << ' ';
cout << b[i];
space = true;
}
return 0;
}
——3.31更新——
1019：【do while循环】⚠️运行超时、答案错误
参考解答
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
bool down(char a, char b)
{
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
bool down(char a, char b)
{
return a>b;
}
int main()
{
string s;
cin>>s;
int d,u,c;
do
{
sort(s.begin(),s.end(),down);
d=stoi(s);
sort(s.begin(),s.end());
u=stoi(s);
c=d-u;
printf("%04d - %04d = %04d\n",d,u,c);
s=to_string(c);
if(s.size()<4){
for(int i=0;i<4-s.size();i++)
s.push_back('0');
}
}while(c!=6174&&c!=0);
return 0;
}
1034：【有理数运算】
知识点：
参考解答
灵魂拷问：
1、换行输入与一行输入的区别
读取int类型的数据时，换行输入与空格输入的笑过是一样的。
