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

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

news 来源：原创 2024/9/20 10:52:39

🍦🍦🍦由于代码都是我自己敲出来调试的，所以可能不能一次更新那么多，大家见谅，不过因为我最近在备考机试，所以会拿出大量的时间在这上边，更新的会比较勤的~~~

🧊🧊🧊2.4 日期类问题

🥥题型总结：

🥥例题：DreamJudge 1051

🥥练习题目：

DreamJudge 1011 日期

DreamJudge 1290 日期差值

DreamJudge 1410 打印日期

DreamJudge 1437 日期类

DreamJudge 1446 日期累加 🍰

DreamJudge 1053 偷菜时间表

🧊🧊🧊2.5 字符串类问题

🥥题型总结：

🥥例题：DreamJudge 1014

🥥练习题目：

DreamJudge 1012 字符移动

DreamJudge 1292 字母统计

DreamJudge 1240 首字母大写 🍰

DreamJudge 1394 统计单词

DreamJudge 1027 删除字符串 2🍰

🧊🧊🧊2.6 排序类问题

🥥例题：DreamJudge 1151

🥥例题：DreamJudge 1010

🥥特殊排序题：

普通排序（适合n<=2000的情况）：

快速排序（适合n<=50W的情况）：

🥥练习题目：

DreamJudge 1106 排序 2 🍰

DreamJudge 1159 成绩排序 2.0

DreamJudge 1217 国名排序

DreamJudge 1227 日志排序 🍰

DreamJudge 1248 整数奇偶排序

DreamJudge 1254 字符串排序

DreamJudge 1255 字符串排序 2

DreamJudge 1261 字符串排序 3

DreamJudge 1294 后缀子串排序

DreamJudge 1310 奥运排序问题

DreamJudge 1338 EXCEL 排序

DreamJudge 1360 字符串内排序

DreamJudge 1399 排序 - 华科

DreamJudge 1400 特殊排序

DreamJudge 1404 成绩排序 - 华科

DreamJudge 1412 大整数排序

DreamJudge 1817 成绩再次排序

DreamJudge 1798 数组排序

🧊🧊🧊2.4 日期类问题

🥥题型总结：

判断某年 是否为闰年
某年某月某日是 星期几 （变形：某日期到某 日期之间有多少天 ）
某天之后 x 天 是几月几日
10:15 分之后 x 分钟 是几点几分（变形：某点到 某点之间有多少分或多少秒 ）

特别注意闰年的判断，这些题目一般都是考察代码细节的把握，时间类的题目注意时间的转换， 1 天=24 小时，1 小时=60 分，1 分=60 秒。

特别注意：一天之内时针和分针会重合 22 次，而不是 24 次。

我们一般用scanf来进行输入，比较方便：

int year, month, day;
scanf("%d-%d-%d", &year, &month, &day);
scanf("%d/%d/%d", &year, &month, &day);
int hour, minute;
scanf("%d:%d", &hour, &minute);

🥥例题：DreamJudge 1051

这个题目的考点在于：一个是每个月的天数都不一样，另一个是 2 月如果是闰年则多一天，最后我们还要判断输入的日期是否存在。

#include<bits/stdc++.h>
using namespace std;
struct node {int year,month,day;
}p;
int f[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main(){while(cin>>p.year>>p.month>>p.day){//判断是否闰年if((p.year%400==0)||(p.year%4==0)&&(p.year%100!=0)){f[2]=29;}else f[2]=28;int flag=0;//判断月份输入是否合法if(p.month<1||p.month>12) flag=1;//判断天的输入是否合法if(p.day<0||p.day>f[p.month]) flag=1;if(flag){cout<<"Input error!"<<endl;continue;}int ans=p.day;for(int i=1;i<p.month;i++){ans+=f[i];}cout<<ans<<endl;}return 0;
}

🥥练习题目：

DreamJudge 1011 日期

#include<bits/stdc++.h>
using namespace std;
int main()
{int month[15]={0,31,29,31,30,31,30,31,31,30,31,30,31};string week[10]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};int m,d,days=0;cin>>m>>d;if(m==4) days=d-9+1;else{days=22+d;for(int i=5;i<m;i++) days+=month[i];}days%=7;cout<<week[days];return 0;
}

DreamJudge 1290 日期差值

#include<bits/stdc++.h>
using namespace std;
int main()
{int month[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};int y1=0,y2=0,m1=0,m2=0,d1=0,d2=0;string s1,s2;cin>>s1>>s2;long long ans=0;for(int i=0;i<4;i++){y1=y1*10+s1[i]-'0';y2=y2*10+s2[i]-'0';}for(int i=4;i<6;i++){m1=m1*10+s1[i]-'0';m2=m2*10+s2[i]-'0';d1=d1*10+s1[i+2]-'0';d2=d2*10+s2[i+2]-'0';}//cout<<y1<<" "<<m1<<" "<<d1<<endl;////cout<<y2<<" "<<m2<<" "<<d2<<endl;//if(y1==y2){if(y1%400==0||(y1%4==0&&y1%100!=0)) month[2]=29;if(m1==m2) ans=abs(d2-d1)+1;else{ans+=month[m1]-d1+1;ans+=d2;for(int i=m1+1;i<m2;i++) ans+=month[i];}}else{if(y1%400==0||(y1%4==0&&y1%100!=0)) month[2]=29;ans+=month[m1]-d1+1;for(int i=m1+1;i<=12;i++) ans+=month[i];month[2]=28;if(y2%400==0||(y2%4==0&&y2%100!=0)) month[2]=29;ans+=d2;for(int i=1;i<m2;i++) ans+=month[i];for(int i=y1+1;i<y2;i++){if(i%400==0||(i%4==0&&i%100!=0)) ans+=366;else ans+=365;}}cout<<ans;return 0;
}

DreamJudge 1410 打印日期

#include<bits/stdc++.h>
using namespace std;
int main()
{int month[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};int m,d;while(cin>>m>>d){if(m%400==0||(m%4==0&&m%100!=0)) month[2]=29;int cnt=1;if(d<=month[1]) {if(d<10) cout<<m<<"-01-0"<<d<<endl;else cout<<m<<"-01-"<<d<<endl;continue;}while(d>month[cnt]){d-=month[cnt];cnt++;}if(d<10&&cnt<10) cout<<m<<"-0"<<cnt<<"-0"<<d<<endl;else if(d<10) cout<<m<<"-"<<cnt<<"-0"<<d<<endl;else if(cnt<10) cout<<m<<"-0"<<cnt<<"-"<<d<<endl;else cout<<m<<"-"<<cnt<<"-"<<d<<endl;month[2]=28;}return 0;
}

DreamJudge 1437 日期类

#include<bits/stdc++.h>
using namespace std;
int main()
{int month[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};int n,y,m,d;cin>>n;for(int i=0;i<n;i++){cin>>y>>m>>d;if(d==month[m]) {m++;d=1;}else d++;if(d<10&&m<10) cout<<y<<"-0"<<m<<"-0"<<d<<endl;else if(d<10) cout<<y<<"-"<<m<<"-0"<<d<<endl;else if(m<10) cout<<y<<"-0"<<m<<"-"<<d<<endl;else cout<<y<<"-"<<m<<"-"<<d<<endl;}return 0;
}

DreamJudge 1446 日期累加 🍰

#include<bits/stdc++.h>
using namespace std;
bool isLeap(int y){//判断闰年if(y%400==0||(y%4==0&&y%100!=0)) return true;return false;
}
int month[20] = {0,31,28,31,30,31,30,31,31,30,31,30,31};int main()
{int n;cin>>n;for(int i=0;i<n;i++){int y, m, d;long long days;cin>>y>>m>>d>>days;if(isLeap(y)) month[2]=29;else month[2]=28;while(days--){d++;if(d>month[m]){d=1;m++;if(m>12){m=1;y++;//年数增加后，需要判断是不是闰年if(isLeap(y)) month[2]=29;else month[2]=28;}}}printf("%4d-%02d-%02d\n",y,m,d);}return 0;
}

DreamJudge 1053 偷菜时间表

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,h,m;cin>>n;for(int i=0;i<n;i++){int nh=13,nm=15;scanf("%d:%d",&h,&m);int mins=60*h+m;//cout<<mins<<endl;//while(mins--){nm++;if(nm>60){nm=1;nh++;if(nh>24) nh=1;}}cout<<nh<<":"<<nm<<endl;}return 0;
}

🧊🧊🧊2.5 字符串类问题

🥥题型总结：

统计字符个数
单词首字母大写
统计子串出现次数（考察基础的字符串遍历能力）
文本加密/解密（通过循环后移 x 位或直接给一个映射表是比较常见的考法）
文本中的单词反序（灵活使用 string 可秒杀，当然也可以用字符串一步步解析）
删除字符串（大小写模糊）（如果大小写不模糊，那么就是直接找到之后删除。大小写模糊的话，只是多一个判断）

🥥例题：DreamJudge 1014

往后移动 3 位是这道题的核心，这道题目就是“移位加密”，我们需要将大写、小写字母、和其他数字等分开处理。

#include <stdio.h>
#include <string.h>
int main() {char s[105];gets(s);//输入一行文本用 getsint len=strlen(s);for(int i=0;i<len;i++){if(s[i]>='A'&&s[i]<='Z'){s[i]+=3;if(s[i]>'Z') s[i]-=26;//溢出循环}else if(s[i]>='a'&&s[i]<='z'){s[i]+=3;if(s[i]>'z') s[i]-=26;//溢出循环}else {continue;}}puts(s);return 0;
}

🥥练习题目：

DreamJudge 1012 字符移动

#include<bits/stdc++.h>
using namespace std;
int main()
{string s,num="",let="";cin>>s;for(int i=0;i<s.size();i++){if(s[i]>='0'&&s[i]<='9') num+=s[i];else let+=s[i];}let+=num;cout<<let;return 0;
}

DreamJudge 1292 字母统计

输入：DFJEIWFNQLEF0395823048+_+JDLSFJDLSJFKK

输出：

A:0
B:0
C:0
D:3
E:2
F:5
G:0
H:0
I:1
J:4
K:2
L:3
M:0
N:1
O:0
P:0
Q:1
R:0
S:2
T:0
U:0
V:0
W:1
X:0
Y:0
Z:0

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;int a[30]={0};cin>>s;for(int i=0;i<s.size();i++){if(s[i]>='A'&&s[i]<='Z') a[(s[i]-'A')]+=1;else continue;}char letter;for(int i=0;i<26;i++) {letter=i+'A';cout<<letter<<":"<<a[i]<<endl;}return 0;
}

DreamJudge 1240 首字母大写 🍰

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;while(getline(cin,s)){if(s[0]>='a'&&s[0]<='z') s[0]-=32;for(int i=1;i<s.size();i++){if(s[i]==' '||s[i]=='\t'||s[i]=='\n'||s[i]=='\r'){if(s[i+1]>='a'&&s[i+1]<='z') s[i+1]-=32;}}cout<<s<<endl;}return 0;
}

DreamJudge 1394 统计单词

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;while(getline(cin,s)){int cnt=0;for(int i=0;i<s.size();i++){if(s[i]!=' '&&s[i+1]==' ') {cnt++;cout<<cnt<<" ";cnt=0;}else if(s[i]!=' '&&s[i+1]=='.'){cnt++;cout<<cnt;break;}else if(s[i]!=' ') cnt++;else continue;}}return 0;
}

DreamJudge 1027 删除字符串 2🍰

#include<bits/stdc++.h>
using namespace std;
int main()
{string s;	cin>>s;    	for(int i=0;i<s.size();i++){if((s[i]=='g'||s[i]=='G')&&(s[i+1]=='z'||s[i+1]=='Z')&&(s[i+2]=='u'||s[i+2]=='U')){i+=2; continue;}cout<<s[i];}	return 0;
}

🧊🧊🧊2.6 排序类问题

时间复杂度为O(NlogN)

排序类问题就用 sort 函数，sort本质上也是封装了快速排序，同时还做了一些优化。 sort 可以对最大 30W 个左右的元素进行排序，可以应对考研机试中的 99.9%的情况。

sort常见应用场景：

自定义函数排序
多级排序

🥥例题：DreamJudge 1151

这题唯一的一个考点在于稳定排序，sort 排序是不稳定的，排序之后相对次序有可能发生改变。解决这个问题有两个方法，一个是用 stable_sort 函数，它的用法和 sort 一样，但是它是稳定的，所以如果我们遇到有稳定的需求的排序时，可以用它。另一个方法是给每一个输入增加一个递增的下标，然后二级排序，当值相同时，下标小的排在前面。

使用stable_sort函数：

#include <bits/stdc++.h>
using namespace std;
struct Student {string name;int grade;
}stu[1005];
//从大到小排序
bool compareDesc(Student a,Student b) {return a.grade > b.grade;
}
//从小到大排序
bool compareAsc(Student a,Student b) {return a.grade < b.grade;
}
int main() {int n,order;while(cin>>n) {cin>>order;for(int i=0;i<n;i++) {cin>>stu[i].name>>stu[i].grade;}if(order==0)stable_sort(stu,stu+n,compareDesc);elsestable_sort(stu,stu+n,compareAsc);for(int i=0;i<n;i++) {cout<<stu[i].name<<" "<<stu[i].grade<<endl;}}return 0;
}

使用下标id：

#include <bits/stdc++.h>
using namespace std;
struct Student {string name;int grade, id;
}stu[1005];
//从大到小排序
bool compareDesc(Student a,Student b) {if (a.grade == b.grade) return a.id < b.id;return a.grade > b.grade;
}
//从小到大排序
bool compareAsc(Student a,Student b) {if (a.grade == b.grade) return a.id < b.id;return a.grade < b.grade;
}
int main() {int n,order;while(cin>>n) {cin>>order;for(int i=0;i<n;i++) {cin>>stu[i].name>>stu[i].grade;stu[i].id = i;//通过标记 ID 进行判断}if(order==0)sort(stu,stu+n,compareDesc);elsesort(stu,stu+n,compareAsc);for(int i=0;i<n;i++) {cout<<stu[i].name<<" "<<stu[i].grade<<endl;}}return 0;
}

🥥例题：DreamJudge 1010

题目要求：按“奇数在前，偶数在后”的排序方法，同为奇数或同为偶数再从小到大排序。有两种方法解决这个问题：第一个是将奇偶数分开，分别排好序，再合并在一起。第二个是使用 sort 进行二级排序，这里给出第二种方法的代码。

#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){if(a % 2 == b % 2)//如果同奇同偶return a < b;//直接从小到大排序else//如果奇偶性不同return (a%2) > (b%2);//奇数在偶数前
}
int main() {int n;int a[1005] = {0};cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a+n, cmp);for(int i = 0; i < n; i++) {cout << a[i] << " ";}cout << endl;return 0;
}

🥥特殊排序题：

如果题目给的数据量很大，上百万的数据要排序，但是值的区间范围很小，比如值最大只有 10 万，或者值的范围在 1000W 到 1010W 之间，对于这种情况，我们可以采用空间换时间的计数排序。
字符串的字典序排序是一个常见的问题，需要掌握，也是用 sort。下面两种情况了解即可，追求满分的同学需要掌握
如果题目给你一个数的序列，要你求逆序数对有多少，这是一个经典的问题，解法是在归并排序合并是进行统计，复杂度可以达到 nlogn。如果数据量小，直接冒泡排序即可。
如果题目让你求 top10，即最大或最小的 10 个数，如果数据量很大，建议使用选择排序，也就是一个一个找，这样复杂度比全部元素排序要低。
如果题目给的数据量有几百万，让你从中找出第 K 大的元素，这时候 sort 是会超时的。解法是利用快速排序的划分的性质，进入到其中一个分支继续寻找，

这些题目都是数据量很大且数据很特殊的题目，给出c语言模板：

普通排序（适合n<=2000的情况）：

#include <stdio.h>
const int maxn = 1005;
int a[maxn];
int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);for (int i = 1; i <= n; i++) {//两个 for 都是 1 到 n 方便好记for (int j = 1; j < n ;j++) {if (a[j] > a[j + 1]) {//交换 a[j]和 a[j+1]int temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}for (int i = 1; i <= n; i++) {printf("%d ", a[i]);}printf("\n");return 0;
}

快速排序（适合n<=50W的情况）：

#include <stdio.h>
const int maxn = 100005;
int a[maxn];
//快速排序
void Quick_Sort(int l, int r) {if(l >= r) return;int i = l,j = r,x = a[l];while (i < j) {while (i < j && a[j] >= x) j--;if (i < j) a[i++] = a[j];while (i < j && a[i] < x) i++;if (i < j) a[j--] = a[i];}a[i] = x;Quick_Sort(l, i - 1);Quick_Sort(i + 1, r);
}
int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);Quick_Sort(1, n);//传入左边界下标和右边界下标for (int i = 1; i <= n; i++) {printf("%d ", a[i]);}printf("\n");return 0;
}

🥥练习题目：

DreamJudge 1106 排序 2 🍰

输入：

10
50 36 41 19 23 4 20 18 12 22

输出：

4 12 18 19 20 22 23 36 41 50
4 20 18 12 22 50 36 41 19 23
4 12 18 19 20 22 23 36 41 50
4 12 18 19 20 22 23 36 41 50
36 50 19 41 4 23 18 20 12 22

#include <bits/stdc++.h>
#define STEP 5
using namespace std;
int d[1024], t[1024];void insertSort(const int &n){//插入排序for(int i=1;i<n;i++){int j=i;while(j>=1&&d[j]<d[j-1]){swap(d[j],d[j-1]);j--;}}return;
}void shellSort(const int &n){//希尔排序for(int i=0; i<STEP;i++){for(int j=i;j<n-STEP;j+=STEP){for(int k=j+STEP;k<n;k+=STEP){if(d[k]<d[k-STEP]){swap(d[k],d[k-STEP]);}}}}return;
}void selectSort(const int &n){//选择排序for(int i=0;i<n-1;i++){int minPos=i;for(int j=i+1;j<n;j++){if(d[j]<d[minPos]){minPos=j;}}swap(d[i],d[minPos]);}return;
}int quickSort(const int &from, const int &to){//快速排序if(from>=to){return from;}int l=from,r=to;int pivot=d[l];while(l<r){while(l<r&&d[r]>=pivot){r--;}if(l<r){d[l]=d[r];}while(l<r&&d[l]<=pivot){l++;}if(l<r){d[r]=d[l];}}d[l]=pivot;quickSort(from,l-1);quickSort(l+1,to);return l;
}void mergeSort(const int &n){//二路归并排序for(int i=0;i<n;i+=2){if(i+1<n&&d[i]>d[i+1]){swap(d[i],d[i+1]);}}return;
}void rebuild(const int &n){//用于重置数据序列for(int i=0;i<n;i++){d[i]=t[i];}return;
}void show(const int &n){//用于输出排好序的数据序列if(0==n){return;}printf("%d",d[0]);for(int i=1;i<n;i++){cout<<" "<<d[i];}cout<<endl;return;
}int main(){int n;while(cin>>n){for(int i=0;i<n;i++){cin>>t[i];}rebuild(n);insertSort(n);show(n);rebuild(n);shellSort(n);show(n);rebuild(n);selectSort(n);show(n);rebuild(n);quickSort(0, n - 1);show(n);rebuild(n);mergeSort(n);show(n);rebuild(n);}return 0;
}

DreamJudge 1159 成绩排序 2.0

#include<bits/stdc++.h>
using namespace std;
struct student
{int id,score;
};
bool cmp(student a,student b)
{if(a.score==b.score) return a.id<b.id;return a.score<b.score;
}int main()
{int n;cin>>n;student a[200];for(int i=0;i<n;i++) cin>>a[i].id>>a[i].score;sort(a,a+n,cmp);for(int i=0;i<n;i++) cout<<a[i].id<<" "<<a[i].score<<endl;return 0;
}

DreamJudge 1217 国名排序

sort可以直接对string排序

#include <bits/stdc++.h>
using namespace std;int main()
{int n;string s;	vector<string> a;while(cin>>n){a.clear();for(int i=0;i<n;i++){cin>>s;a.push_back(s);}	sort(a.begin(),a.end());	for(int i=0;i<n;i++) cout<<a[i]<<endl;}return 0;
}

DreamJudge 1227 日志排序 🍰

stod函数：将string类型的字符串转换为double类型的浮点数，会自动忽略字符串开头的空白字符

#include<bits/stdc++.h>
using namespace std;
struct T{string name;string data;double run;
};bool cmp(T x,T y){if(x.run==y.run)return x.data<y.data;else return x.run<y.run;
}int main(){string temp;T t[10000];int cnt=0;while(getline(cin,temp)){if(temp=="")break;t[cnt].name=temp;t[cnt].data=temp.substr(13,23);t[cnt].run=stod(temp.substr(36,12));//stod函数：将string类型的字符串转换为double类型的浮点数，会自动忽略字符串开头的空白字符cnt++;}sort(t,t+cnt,cmp);for(int i=0;i<cnt;i++) cout<<t[i].name<<endl;return 0;
}

DreamJudge 1248 整数奇偶排序

#include<bits/stdc++.h>
using namespace std;
int main()
{int a[20];vector<int> ji,ou;while(cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]>>a[7]>>a[8]>>a[9]){for(int i=0;i<10;i++){if(a[i]%2==0) ou.push_back(a[i]);else ji.push_back(a[i]);}sort(ou.begin(),ou.end());sort(ji.begin(),ji.end(),greater<int>());for(int i=0;i<ji.size();i++) cout<<ji[i]<<" ";for(int i=0;i<ou.size();i++) cout<<ou[i]<<" ";cout<<endl;}return 0;
}