当前位置：首页 > news >正文

保研考研机试攻略：第二章——入门经典（1）

news 来源：原创 2024/9/18 8:44:09

🍨🍨🍨该章对全国上百所院校的历年真题进行分析，总结出了其中的常见题型和最常考的知识点。

🍨学会这一章，在机试难度较低的学校基本上可以拿到 60-80 分左右的成绩，在机试难度中等的学校，也可拿到 40-60 分左右的成绩，在机试难度高的学校亦可将签到题做出来，拿到 20-40 分的成绩。

🍨认真看完这一章的内容对你的帮助会很大，加油，fighting！

🧊🧊🧊2.1 简单模拟

🥥例题：DreamJudge 1091

🥥题型总结：

🥥练习题目：

DreamJudge 1133 求 1 到 n 的和

DreamJudge 1043 计算 Sn

DreamJudge 1040 利润提成

DreamJudge 1722 身份证校验

🧊🧊🧊2.2 进制转换类问题

🥥题型总结：

反序数

10进制转x进制（x<10）

10进制转x进制（通用）

x进制转10进制（x为2）

x进制转10进制（通用）

x进制转y进制（通用）

大数的进制转换

🥥例题：DreamJudge 1178

🥥练习题目：

DreamJudge 1454 反序数

DreamJudge 1259 进制转换 2

DreamJudge 1176 十进制和二进制 🍰

DreamJudge 1380 二进制数

DreamJudge 1417 八进制

DreamJudge 1422 进制转换 3

DreamJudge 1097 负二进制🍰

🧊🧊🧊2.3 排版类问题

🥥题型总结：

字符棱形

杨辉三角

🥥练习题目：

DreamJudge 1392 杨辉三角形 - 西北工业大学

DreamJudge 1377 旋转矩阵 - 北航🍰

DreamJudge 1216 旋转方阵 🍰

DreamJudge 1221 旋转矩阵 🍰

DreamJudge 1472 2048 游戏

🧊🧊🧊2.1 简单模拟

所谓简单模拟，就是不需要去考虑什么算法，直接按照题目的意思进行模拟计算即可。

🥥例题：DreamJudge 1091

#include <bits/stdc++.h>//万能头文件
using namespace std;int main() {double a;cin>>a;//使用%g 可以自动去掉小数点后多余的 0 如果是整数则显示整数if(a<1000) printf("discount=1,pay=%g\n", a);if(a>=1000&&a<2000) cout<<"discount=0.95,pay="<<a*0.95<<endl;if(a>=2000&&a<3000) cout<<"discount=0.9,pay="<<a*0.9<<endl;if(a>=3000&&a<5000) cout<<"discount=0.85,pay="<<a*0.85<<endl;if(a>=5000) cout<<"discount=0.8,pay="<<a*0.8<<endl;return 0;
}

🥥题型总结：

简单模拟在考试中很常见，属于送分签到的题目，这类题必须会做。

对简单模拟这一类的题目，就是要通过多做题去提高，如果你想拿高分甚至满分，平时训练的时候，这类题尽量要在 8 分钟内解决；如果你只是想拿个还不错的成绩，这类题 AC 的时间尽量不要超过 15 分钟，一定要记住，最坏情况不能超过 20 分钟，如果超过了，说明你平时做的题还是太少了。

🥥练习题目：

DreamJudge 1133 求 1 到 n 的和

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,ans=0;cin>>n;for(int i=1;i<=n;i++) ans+=i;cout<<ans;return 0;
}

注意：刚开始没有将ans初始化为0，导致了结果错误，所以大家机试的时候要注意，不是所有oj都默认初始化为0的！

DreamJudge 1043 计算 Sn

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,a,ans=0,cur=0;cin>>a>>n;for(int i=1;i<=n;i++) {cur=cur*10+a;//当前要加的数ans+=cur;}cout<<ans;return 0;
}

DreamJudge 1040 利润提成

#include<bits/stdc++.h>
using namespace std;
int main()
{int num;cin>>num;if(num<=1e5) cout<<num*0.1;else if(num>1e5&&num<=2e5) cout<<1e4+(num-1e5)*0.075;else if(num>2e5&&num<=4e5) cout<<1e4+7500+(num-2e5)*0.05;else if(num>4e5&&num<=6e5) cout<<1e4+7500+1e4+(num-4e5)*0.03;else if(num>6e5&&num<=1e6) cout<<2e4+7500+6000+(num-6e5)*0.015;else cout<<2e4+7500+6000+6000+(num-1e6)*0.01;return 0;
}

DreamJudge 1722 身份证校验

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;int a[20]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};int y[15]={1,0,'x'-'0',9,8,7,6,5,4,3,2};//x用ASCII码char cur;while(cin>>s){if(s.size()<18) {cout<<"ID Wrong"<<endl;continue;}int ans=0;for(int i=0;i<17;i++) ans+=(s[i]-'0')*a[i];ans%=11;if(s[17]=='X') s[17]='x';if(y[ans]==s[17]-'0') cout<<"ID Corrent"<<endl;else cout<<"ID Wrong"<<endl;}return 0;
}

🧊🧊🧊2.2 进制转换类问题

进制转换类的题目在绝大多数学校都是必考题目之一，这类题目的既基础又灵活，能看出学生的编程功底，这类题目一定要掌握。

🥥题型总结：

反序数：输入一个整数如 12345，将其转换为反序之后的整数 54321
10 进制转 2 进制：10 进制整数转化为 2 进制的整数
10 进制转 16 进制：10 进制整数转化为 16 进制的整数
10 进制转 x 进制：10 进制整数转化为 x 进制的整数，前面两种会做这个也一定会
x 进制转 10 进制： x 进制整数转化为 10 进制的整数，上一种情况的反例
x 进制转 y 进制： x 进制整数转化为 y 进制的整数，遇到这种情况，可以拆解为 x 先转为 10 进制，然后再将 10 进制转为 y 进制
字符串转浮点数：可以先转整数部分，再转小数部分，最后字符串相加即可
浮点数转字符串：可以将整数和小数拆开再合并成一个字符串
字符串转整型和整形转字符串：直接用 atoi 函数和 itoa 函数

反序数

#include <stdio.h>
int main() {int n;cin>>n;int ans=0;//将反序之后的答案存在这里while(n>0) {//将 n 逐位分解ans*=10;//将最低位空出来ans+=(n%10);//放入最低位的数值n/=10;}cout<<ans;return 0;
}

10进制转x进制（x<10）

#include <stdio.h>
int main() {int n,x;int s[105];//输入10进制数n和要转换的进制x cin>>n>>x;int cnt=0;//数组下标while(n>0) {//将 n 逐位分解int w=(n%x);//1对目标进制取余s[cnt++]=w;//2存入数组n/=x;//3数据更新}//余数反序输出for(int i=cnt-1;i>=0;i--) {cout<<s[i];}cout<<endl;return 0;
}

10进制转x进制（通用）

#include <stdio.h>
int main() {int n,x;char s[105];//十进制以上有字符，所以用 char 存储//输入10进制n和要转换的进制x cin>>n>>x;int cnt=0;//数组下标while(n>0) {//将 n 逐位分解int w=(n%x);if(w<10) s[cnt++]=w+'0';//变成字符需要加'0' else s[cnt++]=(w-10)+'A';//如果转换为小写则加'a' //如果大于10则从A字符开始n/=x;}//反序输出for(int i=cnt-1;i>=0;i--) {cout<<s[i];}cout<<endl;return 0;
}

x进制转10进制（x为2）

#include <stdio.h>
#include <string.h>
int main() {char s[105];//输入二进制字符串cin>>s;int ans=0;int len=strlen(s);for(int i=0;i<len;i++){if(s[i]=='0'){ans=ans*2;}else{ans=ans*2+1;}}cout<<ans;return 0;
}

x进制转10进制（通用）

#include <stdio.h>
#include <string.h>
int main() {char s[105];int x;//输入 X 进制字符串 和 代表的进制 x cin>>s>>x;int ans=0;int len=strlen(s);for(int i=0;i<len;i++){ans=ans*x;if(s[i]>='0'&&s[i]<='9') ans+=(s[i]-'0');else ans+=(s[i]-'A')+10;}cout<<ans;return 0;
}

x进制转y进制（通用）

#include <stdio.h>
#include <string.h>
int main() {char s[105];int x, y;//输入二进制字符串 和 代表的进制 x 以及要转换的进制 ycin>>s>>x>>y;int ans=0;int len=strlen(s);//转十进制for(int i=0;i<len;i++){ans=ans*x;if(s[i]>='0'&&s[i]<='9') ans+=(s[i]-'0');else ans+=(s[i]-'A')+10;}//转y进制char out[105];int cnt=0;while(ans>0){int w=(ans%y);if(w<10) out[cnt++]=w+'0';else out[cnt++]=(w-10)+'A';ans/=y;}for(int i=cnt-1;i>=0;i--){cout<<out[i];}cout<<endl;return 0;
}

大数的进制转换

这一类题目建议大家学完第四章高精度问题，学会大数的加减乘除算法之后再看下边这道例题

🥥例题：DreamJudge 1178

#include<bits/stdc++.h>
using namespace std;
//十进制转二进制
char s[40], buf[200];int main(){int num[40];while(cin>>s!=EOF){int len=strlen(s);for(int i=0;i<len;i++){//字符串转成 int 数组num[i]=s[i]-'0';}int i=0,len_str=0;while(i<len){//除2取余法buf[len_str++]=num[len-1]%2+'0';//余数//大数除法,更新num[]数组int c=0;for(int j=i;j<len;j++){int tmp=num[j];num[j]=(num[j]+c)/2;//高位除 2（数的高位对应数组低位if(tmp%2==1){//判断 tmp 是否为奇数c=10;// 若 tmp 为奇数, 则该位必有余数 10}else c=0;}if(num[i]==0) i++;//高位变为 0}for(int j=len_str-1;j>=0;j--){cout<<buf[j];}cout<<endl;}return 0;
}

🥥练习题目：

DreamJudge 1454 反序数

#include<bits/stdc++.h>
using namespace std;
int main(){for(int i=1000;i<=9999;i++){int x=i,rev=0;while(x>0){rev=rev*10+x%10;x=x/10;}if(i*9==rev) cout<<i<<endl;}return 0;
}

DreamJudge 1259 进制转换 2

#include<bits/stdc++.h>
using namespace std;
int main()
{char s[100000];int x;while(cin>>s){	int ans=0;int len=strlen(s);for(int i=2;i<len;i++){ans=ans*16;if(s[i]>='0'&&s[i]<='9') ans+=(s[i]-'0');else if(s[i]>='a'&&s[i]<='z') ans+=(s[i]-'a')+10;else ans+=(s[i]-'A')+10;}cout<<ans<<endl;}return 0;
}

DreamJudge 1176 十进制和二进制 🍰

#include<bits/stdc++.h>
using namespace std;//由m进制转换成n进制
string convers(string s,int m,int n) {string ans;int rem;//保存余数for(int i=0;i<s.size();){rem=0;for(int j=i;j<s.size();j++){int pos;//暂存rem的值int v;//暂存整除的值pos=(rem*m+s[j]-'0')%n;v=(rem*m+s[j]-'0')/n;s[j]=v+'0';rem=pos;}ans+=(rem+'0');while(s[i]=='0') i++;}return ans;
}
int main(){string s;while(cin>>s){string temp=convers(s,10,2);temp=convers(temp,2,10);reverse(temp.begin(),temp.end());cout<<temp<<endl;}
}

DreamJudge 1380 二进制数

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;while(cin>>n){string ans;while(n>0){ans+=n%2+'0';n/=2;}reverse(ans.begin(),ans.end());cout<<ans<<endl;}return 0;
}

DreamJudge 1417 八进制

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;while(cin>>n){string ans;while(n>0){int w=(n%8);if(w<10) ans+=w+'0';else ans+=(w-10)+'A';n/=8;}reverse(ans.begin(),ans.end());cout<<ans<<endl;}return 0;
}

DreamJudge 1422 进制转换 3

#include<bits/stdc++.h>
using namespace std;
int main()
{long long m,n,ans=0;string s;cin>>m>>n>>s;//转10进制for(long long i=0;i<s.size();i++){ans*=m;if(s[i]>='0'&&s[i]<='9') ans+=(s[i]-'0');else ans+=(s[i]-'A')+10;}//转n进制string res;while(ans>0){long long w=(ans%n);	if(w<10) res+=w+'0';else res+=(w-10)+'a';ans/=n;}reverse(res.begin(),res.end());cout<<res;return 0;
}

DreamJudge 1097 负二进制🍰

#include <bits/stdc++.h>
using namespace std;
int main()
{int n;while(cin>>n){string ans;if(n==0){cout<<0<<endl;continue;}while(n){int w=n%(-2);if(w==-1){ans+='1';n=n/(-2)+1;}else{ans+=w+'0';n/=-2;}}reverse(ans.begin(),ans.end());cout<<ans<<endl;}return 0;
}

🧊🧊🧊2.3 排版类问题

排版类问题也是机试中经常出现的题目，这类题目表面上看起来很简单，但是对大部分没有认真研究过的同学来说，这些题可能会搞半天才能搞出来。

🥥题型总结：

输出字符棱形 ：这类题目的变形可以是输出长方形、三角形、梯形等，如DreamJudge 1473
旋转数字输出
矩阵顺/逆指针旋转
矩阵翻转 ：这类题目的变形可以是轴对称翻转、中心对称翻转等
杨辉三角形
2048 问题

字符棱形

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;//上三角for(int i=1;i<=n;i++){for(int j=1;j<=n-i;j++) cout<<" ";for(int j=n-i+1;j<n+i;j++) cout<<"*";cout<<endl;}//下三角，只需要将上三角反过来输出就行for(int i=n-1;i>=1;i--){for(int j=1;j<=n-i;j++) cout<<" ";for(int j=n-i+1;j<n+i;j++) cout<<"*";cout<<endl;}return 0;
}

杨辉三角

杨辉三角公式：a[ i ][ j ] = a[ i-1 ][ j ] + a[ i-1 ][ j-1 ] ;

#include<bits/stdc++.h>
using namespace std;
int main()
{int a[21][21]={0};int n;while(cin>>n){if(n==0) break;a[1][1]=1;for(int i=2;i<=n;i++)//行{//列for(int j=1;j<=i;j++) a[i][j]=a[i-1][j]+a[i-1][j-1];}for(int i=1;i<=n;i++){for(int j=1;j<=i;j++) cout<<a[i][j]<<" ";cout<<endl;}}return 0;
}

这类题目解法时要注意把大问题进行分解，一部分一部分地实现，找到其中的规律，然后再写出来。最好是平时有练习，考试遇到就不用担心了。

🥥练习题目：

DreamJudge 1392 杨辉三角形 - 西北工业大学

#include<bits/stdc++.h>
using namespace std;
int main()
{int a[105][105]={0};int n;while(cin>>n){if(n==0) break;a[1][1]=a[2][1]=a[2][2]=1;for(int i=3;i<=n;i++)//行{//列for(int j=1;j<=i;j++) a[i][j]=a[i-1][j]+a[i-1][j-1];}for(int i=2;i<=n;i++){for(int j=1;j<=i;j++) cout<<a[i][j]<<" ";cout<<endl;}}return 0;
}

DreamJudge 1377 旋转矩阵 - 北航🍰

#include <iostream>
using namespace std;
int a[20][20],b[20][20];
int n;
int main()
{while(cin>>n){//输入第一个矩阵for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];//输入第二个矩阵for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>b[i][j];//旋转判断if(b[0][0]==a[0][0])//旋转角度为0{int flag=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(b[i][j]!=a[i][j]){cout<< "-1"<<endl;flag=1;break;}if(flag==1) break;}if(flag==0) cout<<"0"<<endl;}else if(b[0][0]==a[n-1][0])//旋转角度为90{int flag=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(b[i][j]!=a[n-1-j][i]){cout<<"-1"<<endl;flag=1;break;}if(flag==1) break;}if(flag==0) cout<<"90"<<endl;}else if(b[0][0]==a[n-1][n-1])//旋转角度为180{int flag=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(b[i][j]!=a[n-1-i][n-1-j]){cout<<"-1"<<endl;flag=1;break;}if(flag==1) break;}if(flag==0) cout<<"180"<<endl;}else if(b[0][0]==a[0][n-1])//旋转角度为270{int flag=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(b[i][j]!=a[j][n-1-i]){cout<<"-1"<<endl;flag=1;break;}if(flag==1) break;}if(flag==0) cout<<"270"<<endl;}else cout<<"-1"<<endl;}return 0;
}

DreamJudge 1216 旋转方阵 🍰

#include<bits/stdc++.h>
using namespace std;
int main(){int dir[4][2]={1,0,0,1,-1,0,0,-1};      //下右上左int n;cin>>n;int ans[n+2][n+2]={0};int visit[n+2][n+2]={0};for(int i=0;i<n+2;i++){//将矩阵四周一圈的位置标记好visit[i][0]=1;visit[i][n+1]=1;visit[0][i]=1;visit[n+1][i]=1;}int x=1;int y=1;int cnt=0;int judge=0;while(cnt!=n*n){//访问该方向上的所有未被访问的格子while(visit[x][y]==0&&cnt!=n*n){ans[x][y]=++cnt;visit[x][y]=1;x+=dir[judge][0];y+=dir[judge][1];}//该方向上遇到已经访问的格子，从方向回退一格x-=dir[judge][0];y-=dir[judge][1];//改变方向judge=(judge+1)%4;x+=dir[judge][0];y+=dir[judge][1];}//输出旋转矩阵for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){printf("%-4d",ans[i][j]);//-表示左对其，4表示宽度为4}cout<<endl;}return 0;}

DreamJudge 1221 旋转矩阵 🍰

#include<bits/stdc++.h>
using namespace std;
int ans1[110][110]={0};
int ans2[110][110]={0};
int flag=0;
void rotate90(int &n,int &m){if(flag==1){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ans2[j][n-i+1]=ans1[i][j];}}flag=2;}else if(flag==2){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ans1[j][n-i+1]=ans2[i][j];}}flag=1;}swap(n,m);
}
void rotate_90(int &n,int&m){if(flag==1){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ans2[m-j+1][i]=ans1[i][j];}}flag=2;}else if(flag==2){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ans1[m-j+1][i]=ans2[i][j];}}flag=1;}swap(n,m);
}
void reverse(int &n,int &m){for(int i=1;i<=n;i++){for(int j=1;j<=m/2;j++){if(flag==1){swap(ans1[i][j],ans1[i][m-j+1]);}else{swap(ans2[i][j],ans2[i][m-j+1]);}}}
}
int main(){int n,m,k;int op;while(cin>>n>>m>>k){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cin>>ans1[i][j];}flag=1;for(int i=1;i<=k;i++){cin>>op;switch(op){case 1:rotate90(n,m);break;case 2:reverse(n,m);break;case 3:rotate_90(n,m);break;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(flag==1){cout<<ans1[i][j]<<" ";}else{cout<<ans2[i][j]<<" ";}}cout<<endl;}}return 0;
}

DreamJudge 1472 2048 游戏

#include<bits/stdc++.h>
using namespace std;
int main()
{int turn;cin>>turn;int R[4][4]={0};int ans[4][4]={0};for(int i=0;i<4;i++){for(int j=0;j<4;j++)cin>>R[i][j];}for(int i=0;i<4;i++){vector<int> v;int last=0;for(int j=0;j<4;j++){int n;if(turn==1) n=R[j][i];else if(turn==2) n=R[3-j][i];else if(turn==3) n=R[i][j];else if(turn==4) n=R[i][3-j];if(n!=0){if(n==last){v.push_back(n+n);last=0;}else if(last==0) last=n;else{v.push_back(last);last=n;}}}if(last!=0) v.push_back(last);for(int j=0;j<v.size();j++){if(turn==1) ans[j][i]=v[j];else if(turn==2) ans[3-j][i]=v[j];else if(turn==3) ans[i][j]=v[j];else if(turn==4) ans[i][3-j]=v[j];}}for(int i=0;i<4;i++){for(int j=0;j<4;j++)cout<<ans[i][j]<<" ";cout<<endl;}return 0;
}

创作不易，点个赞吧~点赞收藏不迷路，感兴趣的宝子们欢迎关注该专栏~

勤奋的宝子们，看到这里辛苦了！🌹🌹🌹休息下吧，我们下部分再见👋👋👋~