滴滴 9.17笔试凉经

第一题：

一个标书证书的字符串，其中有几位是问号，知道这个数字满足

1，可被3整除；2，相邻数字不同；3，首位不为0

问这个数字最小是多少

直接贪心+回溯 ac

bool f(string& str, int index, int pre){
    if(index==str.size()){
        return pre==0;
    }
    if(str[index]=='?'){
        char before=(index==0)?'0':str[index-1];
        char after=(index+1==str.size())?'*':str[index+1];
        for(int i=0;i<9;i++){
            char c='0'+i;
            if(c!=before && c!=after){
                str[index]=c;
                int left=(pre*10+i)%3;
                if(f(str,index+1,left)) return true;
                //str[index]='?';
            }
        }
        str[index]='?';
    }else{
            int left=(pre*10+str[index]-'0')%3;
            return f(str, index+1,left);
    }
    return false;
}

int main(){
    string str;
    cin>>str;
    f(str, 0, 0);
    cout<<str<<endl;
    return 0;
}

第二题：

n个栅栏，每个栅栏被涂上两种漆，每次在【l，r】区间上（左闭右闭）涂一种漆，当第一种漆涂至少p次，第二种漆涂之撒后q次时这个栅栏才是正常。问给定一系列区间，有多少个栅栏是正常的。

经典的排序+贪婪。但是问题是要考虑端点，因为全是比区间，我就是栽在这上面了。。。。后来刚改完就交卷了，服了

int main(){
    int n,p,q;
    cin>>n>>p>>q;
    vector<vector<int>> points(2*n, vector<int>(3,0));//[index, type, add/delete]
    for(int i=0;i<n;i++) {
        cin>>points[i][0];
        points[i][2]=1;
    }
    for(int i=n;i<2*n;i++) {
        cin>>points[i][0];
        points[i][2]=-1;
    }
    for(int i=0;i<n;i++){
        int type;
        cin>>type;
        points[i][1]=type;
        points[i+n][1]=type;
    }
    //for(auto& v:points) cout<<v[0]<<", "<<v[1]<<", "<<v[2]<<endl;
    sort(points.begin(), points.end());
    //cout<<"====="<<endl;
    //for(auto& v:points) cout<<v[0]<<", "<<v[1]<<", "<<v[2]<<endl;
    int type1=0,type2=0;
    int pre=points[0][0];
    if(points[0][1]==1){
        type1=points[0][2];
    }else{
        type2=points[0][2];
    }
    int result=0;
    for(int i=1;i<points.size();){
        cout<<i<<endl;
        int index=points[i][0],type=points[i][1];
        int type1_add=0,type1_minux=0,type2_add=0,type2_minux=0;
        if(type1>=p && type2>=q){
            result+=index-pre;
        }
        cout<<index<<type1<<", "<<type2<<endl;
        while(i<points.size() && points[i][0]==index){
            if(points[i][1]==1){
                if(points[i][2]>0){
                    type1_add++;
                }else{
                    type1_minux++;
                }

            }else{
                if(points[i][2]>0){
                    type2_add++;
                }else{
                    type2_minux++;
                }
            }
            i++;
        }
        type1+=type1_add;
        type2+=type2_add;
        if(type1>=p && type2>=q) result++;
        
        type1-=type1_minux;
        type2-=type2_minux;
        pre=index+1;
    }
    cout<<result;
    return 0;
}

感觉出这种类型的题应该滴滴可能也不太想招人。但是我还是没ac。。最近一直是在上机的时候考虑问题不仔细，临要弄完了就才想明白。。。心态崩了

#滴滴笔试#