模拟的深入
日期类模拟
日期类模拟题主要有两个值得记忆的地方。
- 预处理,即用空间换时间,用数组存储两种年份的月份的天数
- 判断平年和闰年的条件
// Created by 章笙 on 2021/1/9. // // 例题2.6 今年的第几天,这是日期模拟型题目 // 日期类题目常见的做法就是预处理 // 预处理是用空间换取时间的方法 #include <iostream> using namespace std; bool isleapyear(int year){ if ((year%4==0&&year%100)||(year%400==0)) return true; else return false; } int calendar[2][13]={ {0,31,28,31,30,31,30,31,31,30,31,30,31}, {0,31,29,31,30,31,30,31,31,30,31,30,31} }; int main(int argc, const char * argv[]) { int y,m,d; while(cin>>y>>m>>d){ int num=0; int row=isleapyear(y); for(int j=0;j<m;j++){ num+=calendar[row][j]; } num+=d; cout<<num<<endl; } return 0; }
日期类的题目一般分成两个基本类型:
- 给出日期,算是一年中的第几天,使用加的方法;
- 给出第几天,算出具体的日期,使用减的方法。
然后是一个综合题,是以上两种题目的结合,注意跨年的情况,在这种情况下可以使用统一起点的方法。
// // main.cpp // Pra0108-02 // // Created by 章笙 on 2021/1/9. //例题2.7,设计一个程序能计算一个日期加上若干天后是什么日期 #include <iostream> #include<cstdio> using namespace std; bool isleapyear(int year){ if ((year%4==0&&year%100)||(year%400==0)) return true; else return false; } int dayyear(int year){ if(isleapyear(year)) return 366; else return 365; } int calendar[2][13]={ {0,31,28,31,30,31,30,31,31,30,31,30,31}, {0,31,29,31,30,31,30,31,31,30,31,30,31} }; int main(int argc, const char * argv[]) { int t; cin>>t; int y,m,d,num; for(int i=0;i<t;i++){ cin>>y>>m>>d>>num; int row=isleapyear(y); for(int j=0;j<m;j++){ num+=calendar[row][j]; } num+=d; //这一步是为了统一起点到本年度伊始 while(num>dayyear(y)){ num-=dayyear(y); y++; } m=0; row=isleapyear(y); while(num>calendar[row][m]){ num-=calendar[row][m]; m++; } d=num; printf("%04d-%02d-%02d \n",y,m,d); } return 0; }
其他模拟
一般出了上述模拟,还有一些不是很典型的模拟,遇到这种情况只需要使用按部就班的方法就行了。
坠落的蚂蚁
一根长度为1米的木棒上有若干只蚂蚁在爬动。它们的速度为每秒一厘米或静止不动,方向只有两种,向左或者向右。如果两只蚂蚁碰头,则它们立即交换速度并继续爬动。三只蚂蚁碰头,则两边的蚂蚁交换速度,中间的蚂蚁仍然静止。如果它们爬到了木棒的边缘(0或100厘米处)则会从木棒上坠落下去。在某一时刻蚂蚁的位置各不相同且均在整数厘米处(即1,2,3,…99厘米),有且只有一只蚂蚁A速度为0,其他蚂蚁均在向左或向右爬动。给出该时刻木棒上的所有蚂蚁位置和初始速度,找出蚂蚁A从此时刻到坠落所需要的时间。
这里的核心思想就是从宏观视觉上来看,其余的蚂蚁相遇后并没有发生视觉上的变化「类似于穿过对方的样子」,而且对于A左边向左爬和A右边向右爬的蚂蚁来说,他们不会对程序产生影响。只有当在A左边向右爬和A右边向左爬的蚂蚁数量不同的时候,A才会掉下去。
将蚂蚁A想象为红点,其余蚂蚁为黑点,因此,只需要考虑黑点与红点相撞的情况即可。红点左边向左运动的点永远不会与红点相撞,同理右边向右运动的点亦然。因此只需考虑红点左边向右运动的点数left和红点右边向左运动的点right数。
- 若left=right,则两边与红点交换的速度相互抵消,红点不会坠落。
- 若left>right,则红点将与第left-right个点交换速度并最终向右坠落,坠落时间是第left-right个点运动到100的时间。
- 若left<right,红点最终向左坠落,坠落时间是right与left抵消之后右边第一个right点运动到0的时间。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct Ant{ int pos; //蚂蚁位置 int dir; //蚂蚁运动方向 bool operator< (const Ant& a)const { return pos<a.pos; //规定按pos进行排序 } }; int main(){ int n,apos,left=0,right=0; scanf("%d",&n); Ant ants[n]; for(int i=0;i<n;i++){ scanf("%d%d",&ants[i].pos,&ants[i].dir); if(ants[i].dir==0) apos=ants[i].pos; //记录蚂蚁A的位置 } sort(ants,ants+n); //将输入按位置从左到右排序 for(int i=0;i<n;i++){ if(ants[i].pos<apos&&ants[i].dir==1) left++; //蚂蚁A左边向右走的蚂蚁数 if(ants[i].pos>apos&&ants[i].dir==-1) right++; //蚂蚁A右边向左走的蚂蚁数 } if(left==right){ printf("Cannot fall!"); return 0; } else if(left>right){ int k=0; for(int i=0;i<n;i++){ if(ants[i].dir==1) k++; if(k==left-right){ printf("%d",100-ants[i].pos); return 0; } } } else{ int k=0; for(int i=n-1;i>=0;i--){ if(ants[i].dir==-1) k++; if(k==right-left){ printf("%d",ants[i].pos); return 0; } } } }
排序和查找
排序
这里强烈安利一个头文件:<algorithm>
,这个文件里面有一个很OK的基于快排的函数sort(int a,int b, function)。这三个参数分别代表着排序的初始地址、终止地址和排序方式(缺省的排序方式是升序排列)
例题:
该类型的核心:
定义结构体来编写自定义的比较函数compare
sort(arr,arr+n,compare)
的使用#include <iostream> #include<cstdio> #include<string> #include <algorithm> using namespace std; struct student{ string name; int age; int score; }; const int MAXN=1000; student arr[MAXN]; bool compare(student s1,student s2){ if(s1.score!=s2.score) return s1.score<s2.score; else if(s1.name!=s2.name) return s1.name<s2.name; else return s1.age<s2.age; } int main() { int n; cin>>n; for (int i=0;i<n;i++){ cin>>arr[i].name>>arr[i].age>>arr[i].score; } sort(arr,arr+n,compare); for(int i=0;i<n;i++){ cout<<arr[i].name<<" "<<arr[i].age<<" "<<arr[i].score<<endl; } return 0; }
备注:⚠️在输出时给予空格作为数据间隔的时候,注意最后一个数据后一般是是没有空格的,那么这时候就应该用下面这种方法予以解决:
tmp = n-2; if(tmp >= 0) { for(int i = 0; i <= tmp; ++i) { cout << num[i]; //⚠️ if(i < tmp) cout << " "; } }
查找
查找一般跟着排序出现,在有大量排序案例出现的时候,二分查找更适合,原因见王道考研。
下面是一个利用STL解题的问题。
对给定的一个字符串,找出有重复的字符,并给出其位置,如:abcaaAB12ab12 输出:a,1;a,4;a,5;a,10,b,2;b,11,1,8;1,12, 2,9;2,13。
#include<iostream> #include<vector> #include<string> using namespace std; //unordered_map<char,vector<int>> mp; map是hash表,不能保证插入顺序(弃用) struct st{ char a; vector<int> index; st(char aa,int i){ a=aa; index.push_back(i); } }; vector<st> vec; string s; int j; int main(){ while(cin>>s){ vec.clear(); for(int i=0;i<s.size();i++){ for(j=0;j<i;j++){ if(vec[j].a==s[i]){ vec[j].index.push_back(i); break; } } if(j==i) vec.push_back(st(s[i],i)); } for(int i=0;i<vec.size();i++){ if(vec[i].index.size()>1){ for(int j=0;j<vec[i].index.size();j++){ if(j==0) printf("%c:%d",vec[i].a,vec[i].index[j]); else printf(",%c:%d",vec[i].a,vec[i].index[j]); }printf("\n"); } } } return 0; }