526互联

Codeforces Round 501 (Div. 3)

发布时间 2023-07-21 16:37:18作者: bible_w

Codeforces Round 501 (Div. 3)

A - Points in Segments

思路：记录每个区间

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e4+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


void solve(){
    int n,m;cin>>n>>m;
    vector<int>a(m+1,0);
    for(int i=0,l,r;i<n;++i){
        cin>>l>>r;
        for(int j=l;j<=r;++j)a[j]=1;
    }
    int ans=0;
    for(int i=1;i<=m;++i){
        ans+=!a[i];
    }
    cout<<ans<<'\n';
    for(int i=1;i<=m;++i){
        if(!a[i])cout<<i<<' ';
    }
    return ;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

B - Obtaining the String

思路：枚举每个字符，使前i个字符都相等

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e4+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


void solve(){
    int n;cin>>n;
    string a,b;cin>>a>>b;
    vector<int>aa(26,0),bb(26,0);
    for(int i=0;i<n;++i){
        aa[a[i]-'a']++;
        bb[b[i]-'a']++;
    }
    for(int i=0;i<26;++i){
        if(aa[i]!=bb[i]){
            cout<<-1;return ;
        }
    }
    vector<int>ans;
    for(int i=0;i<n;++i){
        if(b[i]!=a[i]){
            int p=0;
            for(int j=i+1;j<n;++j){
                if(a[j]==b[i]){
                    p=j;break;
                }
            }
            for(int j=p;j>i;--j){
                ans.push_back(j);
                swap(a[j],a[j-1]);
            }
        }
    }
    cout<<ans.size()<<'\n';
    for(auto v:ans)cout<<v<<' ';
    return ;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

C - Songs Compression

思路：需要改越少的数，那么把所有差值排序，从差值大的开始改

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e4+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


void solve(){
    int n,m;cin>>n>>m;
    vector<int>d(n);
    int all=0;
    for(int i=0,x,y;i<n;++i){
        cin>>x>>y;
        all+=x;
        d[i]=x-y;
    }
    sort(d.begin(),d.end(),greater<int>());
    if(all<=m)cout<<0;
    else{
        all-=m;
        int ans=-1;
        for(int i=0;i<d.size();++i){
            all-=d[i];
            if(all<=0){
                ans=i+1;break;
            }
        }
        cout<<ans;
    }
    return ;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

D - Walking Between Houses

思路：每次最多加n-1，判断下是否能移动k次，以及s不能超过最大增值（n-1）*k；

判断满足条件后，一定是存在答案的，每次加的数就是min（n-1，s-k）（满足的条件：最多加n-1、剩下的需要加的数至少够加满k次）

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e4+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


void solve(){
    int n,k,s;cin>>n>>k>>s;
    int c=n-1;
    if(s>c*k||k>s){
        cout<<"NO";return ;
    }
    cout<<"YES\n";
    int now=1;
    while(k--){
        int d=min(s-k,n-1);
        s-=d;
        if(now+d<=n)now+=d;
        else now-=d;
        cout<<now<<' ';
    }

}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

E1 - Stars Drawing (Easy Edition)

思路同下题

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;

int l[N][N],r[N][N],u[N][N],d[N][N];
char g[N][N];
int n,m;
void P(int x,int y,int s){
    int ll=max(1ll,y-s+1),rr=min(m,y+s-1),uu=max(1ll,x-s+1),dd=min(n,x+s-1);
    for(int i=ll,j=uu;i<=rr||j<=dd;++i,++j){
        if(i>=ll&&i<=rr)g[x][i]='.';
        if(j>=uu&&j<=dd)g[j][y]='.';
    }
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j){
            cin>>g[i][j];
            if(g[i][j]=='*'){
                l[i][j]=r[i][j]=u[i][j]=d[i][j]=1;
                if(g[i][j-1]=='*')l[i][j]+=l[i][j-1];
                if(g[i-1][j]=='*')u[i][j]+=u[i-1][j];
            }

        }
    }
    for(int i=n;i>=1;--i){
        for(int j=m;j>=1;--j){
            if(g[i][j]=='*'){
                if(g[i][j+1]=='*')r[i][j]+=r[i][j+1];
                if(g[i+1][j]=='*')d[i][j]+=d[i+1][j];
            }
        }
    }
    vector<pair<PII,int>>ans;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            int s=min(min(l[i][j],r[i][j]),min(u[i][j],d[i][j]));
            if(s>1){
                ans.push_back({{i,j},s-1});
                P(i,j,s);
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(g[i][j]=='*'){
                cout<<-1;
                return ;
            }
        }
    }
    cout<<ans.size()<<'\n';
    for(auto v:ans){
        cout<<v.first.first<<' '<<v.first.second<<' '<<v.second<<'\n';
    }
};

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

E2 - Stars Drawing (Hard Edition)

思路：维护每个点（i，j）的上下左右连续的‘*’个数；枚举每个点（i，j），若四个方向的连续‘*’数大于1，说明能构成星星

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;

int l[N][N],r[N][N],u[N][N],d[N][N];
char g[N][N];
int n,m;
void P(int x,int y,int s){
    int ll=max(1ll,y-s+1),rr=min(m,y+s-1),uu=max(1ll,x-s+1),dd=min(n,x+s-1);
    for(int i=ll,j=uu;i<=rr||j<=dd;++i,++j){
        if(i>=ll&&i<=rr)g[x][i]='.';
        if(j>=uu&&j<=dd)g[j][y]='.';
    }
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j){
            cin>>g[i][j];
            if(g[i][j]=='*'){
                l[i][j]=r[i][j]=u[i][j]=d[i][j]=1;
                if(g[i][j-1]=='*')l[i][j]+=l[i][j-1];
                if(g[i-1][j]=='*')u[i][j]+=u[i-1][j];
            }

        }
    }
    for(int i=n;i>=1;--i){
        for(int j=m;j>=1;--j){
            if(g[i][j]=='*'){
                if(g[i][j+1]=='*')r[i][j]+=r[i][j+1];
                if(g[i+1][j]=='*')d[i][j]+=d[i+1][j];
            }
        }
    }
    vector<pair<PII,int>>ans;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            int s=min(min(l[i][j],r[i][j]),min(u[i][j],d[i][j]));
            if(s>1){
                ans.push_back({{i,j},s-1});
                P(i,j,s);
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(g[i][j]=='*'){
                cout<<-1;
                return ;
            }
        }
    }
    cout<<ans.size()<<'\n';
    for(auto v:ans){
        cout<<v.first.first<<' '<<v.first.second<<' '<<v.second<<'\n';
    }
};

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code