笔试题笔记#7 根据int类型标记判断的BFS和区间覆盖复习

1 根据int类型标记判断的BFS     

        今天的模拟三道题依然是300分（悲 ），第一题简单模拟，第二题区间覆盖，都挺简单的，就这个第三题，真是给我看乐了。

•         首先是学到了一个神奇的思路，BFS搜的时候根据一个非bool类型来标记，这题大概是一个初始值和初始坐标，每走一步都会改变值，让你找有几个点满足到的时候正好为某个值。

        这时BFS的判断条件就变成了是否以某个值到达过，而不是简单的到没到过。

•         其次学到了（被那个题的输入恶心到了）输入的小技巧，如果输入的值以一个字符为分隔，不管那个字符是什么，就cin>>int然后getchar()，就这题的输入格式很神奇：

        m*n的数组给你放在一行里，然后类似这样让你输入1,2 3,4 5,6 ,那是一个空格一个逗号啊.              cin从输入流中读取一个整数。它会跳过前导的空白字符（如空格、换行等），然后读取连续的数字字符，直到遇到非数字字符（如逗号、空格等）为止。

#include<bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> tp;
const int N=101;
int v[N][N];
int h[N][N];
int o[N][N];
int m,n;

const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int main(){
    string a;
    cin>>a;
    for(int i=0;i<a.size()-1;i++){
        if(a[i]>='0'&&a[i]<='9'){
            while(a[i]!=','){
                m=m*10+a[i]-'0';
                i++;
            }
            while(i<a.size()-1){
                n=n*10+a[++i]-'0';
            }
        }
    }

    int stx,sty=0;
    char ch;
    cin>>stx>>ch>>sty;

    vector<int> ss(m*n);

    for(int i=0;i<m*n;i++){
        cin>>ss[i];
        if(i<m*n-1)
            ch=getchar();
    }
    int idx=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            h[i][j]=ss[idx++];
        }
    }

    for(int i=0;i<m*n;i++){
        cin>>ss[i];
        if(i<m*n-1)
            ch=getchar();
    }
    idx=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            o[i][j]=ss[idx++];
        }
    }

    set<int> st[N][N];
    queue<tuple<int,int,int>>q;
    q.push({stx,sty,1});
    st[stx][sty].insert(1);
    int ans=0;
    while(!q.empty()){

        tp fr=q.front();
        //cout<<"fr=={"<<get<0>(fr)<<","<<get<1>(fr)<<","<<get<2>(fr)<<"}"<<endl;
        q.pop();

        for(int i=0;i<4;i++){
            int row=get<0>(fr)+dir[i][0];
            int col=get<1>(fr)+dir[i][1];


            if(row<0||row>=m||col<0||col>=n)continue;

            //cout<<"row=="<<row<<endl;
            //cout<<"col=="<<col<<endl;

            int TempV=get<2>(fr)+h[get<0>(fr)][get<1>(fr)]-h[row][col]-o[row][col];
            //cout<<"TempV=="<<TempV<<endl;

            if(TempV<=0||st[row][col].count(TempV))
            continue;

            if(TempV==1)
            ans++;

            st[row][col].insert(TempV);
            q.push({row,col,TempV});
        }
    }
    cout<<ans;

}

2 区间覆盖版子

必要时记得换成C风格的输入输出，某些情况快不少

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
typedef pair<int,int> PII;

PII range[N];
int n;
int st,ed;

int main(){

    cin>>st>>ed;//表示要求的区间的起点和终点

    cin>>n;//输入的区间个数

    for(int i=1;i<=n;i++){
        cin>>range[i].first>>range[i].second;
    }
    
    sort(range+1,range+n+1);//默认第一个元素升序
  
    bool isSuccess=false;//记录是否成功覆盖
    
    int res=0;//记录所需最少区间个数
    
    for(int i=1;i<=n;i++){
        
        int j=i;
        int r=-2e9;
       
        while( j <= n && range[j].first <= st ){
            r=max(r,range[j].second);
            j++;
        }//向后找到所有左端点小于当前st的区间中最远的右端点
        
        res++;

        //cout<<"range["<<j-1<<"]=={"<<range[j-1].first<<","<<range[j-1].second<<"}"<<endl;
        //若需要输出答案，此时的j-1就是选中的区间的id，即选中的区间为range[j-1]

        if(r >= ed){
            isSuccess=true;
            break;
        }

        if(r < st){//说明区间断了，不能继续找了，此时的r就是能找到的最远了（从最左开始）
            break;
        }
        
        st=r;//更新st

        i=j-1;//更新i,有必要回退一次，让r至少更新一次为上次找到的最右值即此时r=st，不然r保持初值-2e9小于st会break导致答案错误
        
    }
    
    if(!isSuccess){
        cout<<-1;
    }
    else{
        cout<<res;
    }

    return 0;
}