携程笔试 2023.09.07

第一题，一个next_permutation搞定

第二题，统计从左到右，从上到下的前缀和，然后四个方向求值

第三题，用两个优先队列来维护就好了

第四题，一个简单的贪心，不要把它想难了

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
int k[15];
int sushu[20];
void init(){
    memset(sushu,0,sizeof(sushu));
    sushu[2]=1;
    sushu[3]=1;
    sushu[5]=1;
    sushu[7]=1;
    sushu[11]=1;
    sushu[13]=1;
    sushu[17]=1;
    sushu[19]=1;
}
int main(){
    init();
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        k[i]=i;
    }
    int ans=0;
    do{
        int flag=0;
        for(int i=1;i<n;i++){
            int u=k[i]+k[i+1];
            if(sushu[u]==1){
                flag=1;
                break;
            }
        }
        if(flag==0)ans++;
    }while(next_permutation(k+1,k+1+n));
    cout<<ans<<endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#define ll long long
using namespace std;
const int N = 1e3+5;
int l2r[N][N][3];
int u2d[N][N][3];
int m,n;
string s[N];
int main(){
    ll ans=0;
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='y'){
                if(j!=0){
                    l2r[i][j][0]=l2r[i][j-1][0]+1;
                    l2r[i][j][1]=l2r[i][j-1][1];
                    l2r[i][j][2]=l2r[i][j-1][2];
                }else{
                    l2r[i][j][0]=1;
                    l2r[i][j][1]=0;
                    l2r[i][j][2]=0;
                }
            }else if(s[i][j]=='o'){
                if(j!=0){
                    l2r[i][j][0]=l2r[i][j-1][0];
                    l2r[i][j][1]=l2r[i][j-1][1]+1;
                    l2r[i][j][2]=l2r[i][j-1][2];
                }else{
                    l2r[i][j][0]=0;
                    l2r[i][j][1]=1;
                    l2r[i][j][2]=0;
                }
            }else if(s[i][j]=='u'){
                if(j!=0){
                    l2r[i][j][0]=l2r[i][j-1][0];
                    l2r[i][j][1]=l2r[i][j-1][1];
                    l2r[i][j][2]=l2r[i][j-1][2]+1;
                }else{
                    l2r[i][j][0]=0;
                    l2r[i][j][1]=0;
                    l2r[i][j][2]=1;
                }
            }else{
                if(j!=0){
                    l2r[i][j][0]=l2r[i][j-1][0];
                    l2r[i][j][1]=l2r[i][j-1][1];
                    l2r[i][j][2]=l2r[i][j-1][2];
                }else{
                    l2r[i][j][0]=0;
                    l2r[i][j][1]=0;
                    l2r[i][j][2]=0;
                }
            }
        }
    }
    

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(s[j][i]=='y'){
                if(j!=0){
                    u2d[j][i][0]=u2d[j-1][i][0]+1;
                    u2d[j][i][1]=u2d[j-1][i][1];
                    u2d[j][i][2]=u2d[j-1][i][2];
                }else{
                    u2d[j][i][0]=1;
                    u2d[j][i][1]=0;
                    u2d[j][i][2]=0;
                }
            }else if(s[j][i]=='o'){
                if(j!=0){
                    u2d[j][i][0]=u2d[j-1][i][0];
                    u2d[j][i][1]=u2d[j-1][i][1]+1;
                    u2d[j][i][2]=u2d[j-1][i][2];
                }else{
                    u2d[j][i][0]=0;
                    u2d[j][i][1]=1;
                    u2d[j][i][2]=0;
                }
            }else if(s[j][i]=='u'){
                if(j!=0){
                    u2d[j][i][0]=u2d[j-1][i][0];
                    u2d[j][i][1]=u2d[j-1][i][1];
                    u2d[j][i][2]=u2d[j-1][i][2]+1;
                }else{
                    u2d[j][i][0]=0;
                    u2d[j][i][1]=0;
                    u2d[j][i][2]=1;
                }
            }else{
                if(j!=0){
                    u2d[j][i][0]=u2d[j-1][i][0];
                    u2d[j][i][1]=u2d[j-1][i][1];
                    u2d[j][i][2]=u2d[j-1][i][2];
                }else{
                    u2d[j][i][0]=0;
                    u2d[j][i][1]=0;
                    u2d[j][i][2]=0;
                }
            }
        }
    }

    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         for(int w=0;w<3;w++){
    //             cout<<l2r[i][j][w];
    //         }cout<<' ';
    //     }
    //     cout<<endl;
    // }
    // cout<<endl<<endl;
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<m;j++){
    //         for(int w=0;w<3;w++){
    //             cout<<u2d[i][j][w];
    //         }cout<<' ';
    //     }
    //     cout<<endl;
    // }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='y'){
                ll x1=u2d[i][j][1];
                ll y1=l2r[i][j][2];
                ans+=x1*y1;
                x1=u2d[i][j][2];
                y1=l2r[i][j][1];
                ans+=x1*y1;

                ll x2=l2r[i][m-1][1]-l2r[i][j][1];
                ll y2=u2d[n-1][j][2]-u2d[i][j][2];
                ans+=x2*y2;
                x2=l2r[i][m-1][2]-l2r[i][j][2];
                y2=u2d[n-1][j][1]-u2d[i][j][1];
                ans+=x2*y2;

                ll x3=u2d[i][j][1];
                ll y3=l2r[i][m-1][2]-l2r[i][j][2];
                ans+=x3*y3;
                x3=u2d[i][j][2];
                y3=l2r[i][m-1][1]-l2r[i][j][1];
                ans+=x3*y3;

                ll x4=l2r[i][j][1];
                ll y4=u2d[n-1][j][2]-u2d[i][j][2];
                ans+=x4*y4;
                x4=l2r[i][j][2];
                y4=u2d[n-1][j][1]-u2d[i][j][1];
                ans+=x4*y4;

            }else if(s[i][j]=='o'){
                ll x1=u2d[i][j][0];
                ll y1=l2r[i][j][2];
                ans+=x1*y1;
                x1=u2d[i][j][2];
                y1=l2r[i][j][0];
                ans+=x1*y1;

                ll x2=l2r[i][m-1][0]-l2r[i][j][0];
                ll y2=u2d[n-1][j][2]-u2d[i][j][2];
                ans+=x2*y2;
                x2=l2r[i][m-1][2]-l2r[i][j][2];
                y2=u2d[n-1][j][0]-u2d[i][j][0];
                ans+=x2*y2;

                ll x3=u2d[i][j][0];
                ll y3=l2r[i][m-1][2]-l2r[i][j][2];
                ans+=x3*y3;
                x3=u2d[i][j][2];
                y3=l2r[i][m-1][0]-l2r[i][j][0];
                ans+=x3*y3;

                ll x4=l2r[i][j][0];
                ll y4=u2d[n-1][j][2]-u2d[i][j][2];
                ans+=x4*y4;
                x4=l2r[i][j][2];
                y4=u2d[n-1][j][0]-u2d[i][j][0];
                ans+=x4*y4;
            }else if(s[i][j]=='u'){
                ll x1=u2d[i][j][1];
                ll y1=l2r[i][j][0];
                ans+=x1*y1;
                x1=u2d[i][j][0];
                y1=l2r[i][j][1];
                ans+=x1*y1;

                ll x2=l2r[i][m-1][1]-l2r[i][j][1];
                ll y2=u2d[n-1][j][0]-u2d[i][j][0];
                ans+=x2*y2;
                x2=l2r[i][m-1][0]-l2r[i][j][0];
                y2=u2d[n-1][j][1]-u2d[i][j][1];
                ans+=x2*y2;

                ll x3=u2d[i][j][1];
                ll y3=l2r[i][m-1][0]-l2r[i][j][0];
                ans+=x3*y3;
                x3=u2d[i][j][0];
                y3=l2r[i][m-1][1]-l2r[i][j][1];
                ans+=x3*y3;

                ll x4=l2r[i][j][1];
                ll y4=u2d[n-1][j][0]-u2d[i][j][0];
                ans+=x4*y4;
                x4=l2r[i][j][0];
                y4=u2d[n-1][j][1]-u2d[i][j][1];
                ans+=x4*y4;
            }
            // cout<<ans<<' ';
        }
        // cout<<endl;
    }
    cout<<ans<<endl;
}

#include <iostream>
#include <queue>
#include <cmath>
#define ll long long
using namespace std;
priority_queue<ll,vector<ll>,greater<ll> >p1;
priority_queue<ll,vector<ll>,less<ll> >p2;


priority_queue<ll,vector<ll>,greater<ll> >p3;
priority_queue<ll,vector<ll>,less<ll> >p4;
queue<ll>q3;
int main(){
    int t;cin>>t;
    while(t--){
        while(!p1.empty()){
            p1.pop();
        }
        while(!p2.empty()){
            p2.pop();
        }
        while(!p3.empty()){
            p3.pop();
        }
        while(!p4.empty()){
            p4.pop();
        }
        while(!q3.empty()){
            q3.pop();
        }
        ll n,l,r;
        cin>>n>>l>>r;
        for(int i=0;i<n;i++){
            ll w;cin>>w;
            if(w<l){
                p1.push(w);
            }else if(w>r){
                p2.push(w);
            }else{
                q3.push(w);
            }
        }
        // while(!p1.empty()){
        //     cout<<p1.top()<<' ';
        //     p1.pop();
        // }cout<<endl;
        // while(!p2.empty()){
        //     cout<<p2.top()<<' ';
        //     p2.pop();
        // }cout<<endl;
        ll ans=0;
        while(1){
            if(p1.empty()||p2.empty()){
                break;
            }
            ll val1=p1.top();
            ll val2=p2.top();
            ll res1=l-val1;
            ll res2=val2-r;
            if(res1==res2){
                ans+=res1;
                p1.pop();
                p2.pop();
                q3.push(l);
                q3.push(r);
            }else if(res1>res2){
                ans+=res2;
                p2.pop();
                q3.push(r);
                p1.pop();
                p1.push(val1+res2);
            }else if(res1<res2){
                ans+=res1;
                p1.pop();
                q3.push(l);
                p2.pop();
                p2.push(val2-res1);
            }
        }
        // if(!p1.empty()){
        //     cout<<"p1"<<endl;
        // }
        // if(!p2.empty()){
        //     cout<<"p2"<<endl;
        // }
        if(p1.empty()&&p2.empty()){
            cout<<ans<<endl;
        }else if(!p1.empty()){
            // cout<<123<<endl;
            ll all1=0;
            while(!p1.empty()){
                all1+=l-p1.top();
                p1.pop();
            }
            ll all2=0;
            while(!q3.empty()){
                all2+=q3.front()-l;
                q3.pop();
            }
            if(all2<all1)cout<<-1<<endl;
            else{
                ans+=all1;
                cout<<ans<<endl;
            }
            // cout<<all1<<' '<<all2<<endl;
        }else if(!p2.empty()){
            ll all1=0;
            while(!p2.empty()){
                all1+=p2.top()-r;
                p2.pop();
            }
            ll all2=0;
            while(!q3.empty()){
                all2+=r-q3.front();
                q3.pop();
            }
            if(all2<all1)cout<<-1<<endl;
            else{
                ans+=all1;
                cout<<ans<<endl;
            }
        }
    }
}

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    string str;
    cin>>str;
    ll res,count;
    res=count=0;
    for(int i=0;i<str.length();i++){
        if(str[i]=='0'){
            count+=1;
        }else{
            count=max((ll)0,count-1);
        }
        res+=count;
    }
    cout<<res<<endl;
}