模拟的深入

日期类模拟

日期类模拟题主要有两个值得记忆的地方。

  • 预处理,即用空间换时间,用数组存储两种年份的月份的天数
  • 判断平年和闰年的条件
//  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;
}

一个草图