# 模拟题总结

一、字符串处理

1、将数字转化为字符串
    （1）c++11中的to_string()函数
    （2）自己写一个i2s函数
     例：

#include<iostream>
#include<sstream>

using namespace std;

void i2s(int num,string &str){
    stringstream ss; 
    ss<<num;
    ss>>str;
}

int main(){
    int a;
    cin>>a;
    string s;
    i2s(a,s);

    cout<<s<<endl;
    return 0;
} 

2、散列映射(将数字与字母建立数组关系)
记得加双引号" "  
例：
char word[10][10]={
    "zero","one","two","three","four",
    "five","six","seven","eight","nine"
};

3、用hash表存数字(字符)，可做到O(1)的时间复杂度
例：AcWing 1534

#include <iostream>
#include <unordered_set>

using namespace std;

string s1, s2;

int main()
{
    getline(cin, s1);
    getline(cin, s2);

    unordered_set<char> hash;  // 定义哈希表
    for (auto c : s2) hash.insert(c);  // 将s2中的字符插入哈希表

    string res;
    for (auto c : s1)
        if (!hash.count(c))
            res += c;

    cout << res << endl;

    return 0;
}

二、字符串读入

1、读取一行中有空格的一串字符串(getline)
    由于用cin读时，cin遇到空格会停止继续读下去，故此时应使用getline进行读取
    例：
    string a,b;
    getline(cin,a);
    getline(cin,b);

 2、在输入中读取所需的信息
    例：从这串字符中读取小时、分钟、秒 (1494.银行排队)
            07:55:00 16
        scanf("%d:%d:%d %d", &hour, &minute, &second, &service_time);

 3、在已知的字符串中读取所需的信息
    例：从字符串line(string类)中读取小时、分钟、秒 (1231.航班时间)
        string line;
        getline(cin,line);
        if(line.back()!=')')  line+="(+0)";
        int h1,m1,s1,h2,m2,s2,d;
        sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);

三、存放一组数据并对这些组排序

利用结构体进行储存，并对<进行重载操作(1494.银行排队)
例：
struct Person
{
int arrive_time;
int service_time;

bool operator< (const Person& t) const  
{
    return arrive_time < t.arrive_time;
}
}persons[N];
sort(persons, persons + n);

四、常用函数

1、判断年月日是否满足要求(1229.日期问题)
    bool check(int year,int month,int day){
    if(month==0||month>12)  return false;
    if(day==0)  return false;
    if(month!=2){
        if(day>days[month]) return false;
    }
    else{
        int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }
    return true;
    }

之后继续补充！！！！！！

更新2022.04.08

2、判断一个数是不是回文
bool check(string s){//检查s是否是回文
    for(int i=0,j=s.size()-1;i<j;i++,j--)
        if(s[i]!=s[j])
            return false;
    return true;        
}

3、分解质因数(acwing867. 分解质因数)
进来一个数，输出这个数的所有质因子和数量
void divide(int x){
    for(int i=2;i*i<=x;i++)
        if(x%i==0){
            int s=0;
            while(x%i==0)   x/=i,s++;
            cout<<i<<' '<<s<<endl;//输出底数和次数
        }
    if(x>1) cout<<x<<' '<<1<<endl;    
    cout<<endl;
}

4、最大公约数、最小公倍数
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
int lcm(int a,int b){
    return a*b/(gcd(a,b));
}

5、STL中的__gcd()函数（为两个下划线）
#include<iostream>
#include<algorithm>//头文件
using namespace std;
int main(){
    int n, a,b;
    cin>>n;
    while(n--){
        cin>>a>>b;
        cout<<__gcd(a,b)<<endl;
    }
    return 0;
}

6、两种二分模板
    1、从左往右数第一个
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;
            if(x<=q[mid])   r=mid;    
            else l=mid+1;
        }
    2、从右往左数第一个
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r+1>>1;
            if(x>=q[mid])   l=mid;
            else r=mid-1;
        }

7、lower_bound和upper_bound

对于一个排序数组 nums[5]{1, 2, 4, 7, 9}; 

    (1)int i = lower_bound(nums, nums + n, val) - nums;
函数解释：lower_bound函数返回数组 nums 中大于等于 val 的第一个元素的地址，若 nums 中的元素均小于 val 则返回尾后地址。

    (2)int i = upper_bound(nums, nums + n, val) - nums;
函数解释：upper_bound函数返回数组 nums 中大于 val 的第一个元素的地址，若 nums 中的元素均小于等于 val 则返回尾后地址。