526互联

Educational Codeforces Round 71 (Rated for Div. 2)

发布时间 2023-07-25 13:22:05作者: bible_w

Educational Codeforces Round 71 (Rated for Div. 2)

A - There Are Two Types Of Burgers

思路：价格高的优先取

#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=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;

int st[205][205],vis[205][205];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

void solve(){
    int ans=0;
    int b,p,f;cin>>b>>p>>f;
    int h,c;cin>>h>>c;
    if(h>=c){
        int cp=min(b/2,p);
        b-=cp*2;
        ans+=cp*h;
        int cf=min(b/2,f);
        ans+=cf*c;
    }else{
        int cf=min(b/2,f);
        b-=cf*2;
        ans+=cf*c;
        int cp=min(b/2,p);
        ans+=cp*h;
    }
    cout<<ans<<'\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

 

B - Square Filling

思路：遍历每个点，若以该点为左上角的2*2矩阵都为1，则取该点，并将b对应的点都覆盖为1，最后判断a、b是否相等

#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=50+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;


int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int a[N][N],b[N][N];
void solve(){
    int n,m;cin>>n>>m;
    vector<PII>ans;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)cin>>a[i][j];
    }
    for(int i=1;i<n;++i){
        for(int j=1;j<m;++j){
            if(a[i][j]&&a[i+1][j]&&a[i][j+1]&&a[i+1][j+1]){
                b[i][j]=b[i+1][j]=b[i][j+1]=b[i+1][j+1]=1;
                ans.push_back({i,j});
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(a[i][j]!=b[i][j]){
                cout<<"-1\n";
                return ;
            }
        }
    }
    cout<<ans.size()<<'\n';
    for(auto v:ans)cout<<v.first<<' '<<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

 

C - Gas Pipeline

题意：1的高度一定为2，0的高度可以为1/2，问管道和柱子的最小总cost

思路：

  • dp

　　dp[i][j]表示前i段高度为j的最小cost；

　　首尾都是0，所以dp[0][1]=a+b，若s[1]='1'，则dp[0][2]=2*a+b；

　　从1开始遍历所有s，若s[i]=1，dp[i][2]=dp[i-1][2]+2*b+a；

　　　　　　　　　　　若s[i]=0，1. s[i-1]=='1'且s[i+1]=='1'　：dp[i][2]=dp[i-1][2]+2*b+a；

　　　　　　　　　　　　　　　  2. s[i-1]=='0'且s[i+1]=='1'　：dp[i][2]=min(dp[i-1][2]+2*b+a,dp[i-1][1]+2*a+b)；

　　　　　　　　　　　　　　　  3. s[i-1]=='1'　：dp[i][2]=dp[i-1][2]+2*b+a；

　　　　　　　　　　　　　　　　　　　　　　　dp[i][1]=dp[i-1][2]+2*a+2*b；

　　　　　　　　　　　　　　　  4.s[i-1]=='0'且s[i+1]=='0'　：dp[i][2]=min(dp[i-1][1]+2*a+b,dp[i-1][2]+2*b+a)；

　　　　　　　　　　　　　　　　　　　　　　　　　　　　 dp[i][1]=min(dp[i-1][2]+2*a+2*b,dp[i-1][1]+a+b)；

  • 贪心

　　对于0的地方，可以选两种高度，找到每段连续的0，取两种高度cost少的

 

#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=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int dp[N][3];
void solve(){
    int n,a,b;cin>>n>>a>>b;
    string s;cin>>s;
    for(int i=0;i<=n;++i)dp[i][1]=dp[i][2]=inf;
    if(s[1]=='0')dp[0][1]=a+b;
    else dp[0][2]=2*a+b;
    for(int i=1;i<n;++i){
        if(s[i]=='1')dp[i][2]=dp[i-1][2]+2*b+a;
        else{
            if(s[i-1]=='1'&&s[i+1]=='1')dp[i][2]=dp[i-1][2]+2*b+a;
            else if(s[i-1]=='1'){
                dp[i][2]=dp[i-1][2]+2*b+a;
                dp[i][1]=dp[i-1][2]+2*a+2*b;
            }else if(s[i-1]=='0'&&s[i+1]=='1')dp[i][2]=min(dp[i-1][2]+2*b+a,dp[i-1][1]+2*a+b);
            else{
                dp[i][2]=min(dp[i-1][1]+2*a+b,dp[i-1][2]+2*b+a);
                dp[i][1]=min(dp[i-1][2]+2*a+2*b,dp[i-1][1]+a+b);
            }
        }
    }
    cout<<dp[n-1][1]+b<<'\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;
}
dp
#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=50+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int T=1;

void solve(){
    int n,a,b;cin>>n>>a>>b;
    string s;
    cin>>s;
    bool ok=false;
    int ans=n*2*b+(n+2)*a;
    for(int i=0,l=-1,r;i<n;++i){
        if(l==-1&&s[i]=='0'){
            l=i;r=i;
        }else if(s[i]=='0'){
            r=i;
        }else if(l!=-1){
            if(l==0){
                ans-=(r-l)*b;
            }else if(r-l>0){
                int aa=2;
                int bb=r-l;
                int d=aa*a-bb*b;
                if(d<0)
                    ans+=d;
            }
            l=-1;
        }
        if(i==n-1){
            ans-=(r-l)*b;
            if(l==0)ans-=2*a;
        }
    }//cout<<aa<<' '<<bb<<"\n";
    cout<<ans<<'\n';//cout<<'\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;
}
贪心

 

D - Number Of Permutations

题意：问s有多少种排序，使得p的a和b分别是递减的

思路：找出所有递增的，那么递减的即为n！减去递增的。

对于 1 2 2 3 4 4 4 5，可以求出递增的序列有 2！* 3！种，即每种数的个数的阶乘的积。

可以求出a和b的序列分别递增的数目，但还需减去其中重复的（在某种递增的序列中，另一个ai和令一个bi又组成了同样的序列）

将所有（a，b）按a从小到大排序，看是否存在a和b都是递增的情况，若存在则重复的情况就是该种情况的数量，同样的方法求出递增的数量即为重复的数量

#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=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};

vector<int>fac(N);
vector<PII>ve;
map<int,int>mp1,mp2;
map<PII,int>mp3;
void init(){
    fac[0]=1ll;
    for(int i=1;i<N;++i)fac[i]=fac[i-1]*i%mod;
}
void solve(){
    int n;cin>>n;
    ve=vector<PII>(n);
    bool ok=true;
    for(int i=0;i<n;++i){
        cin>>ve[i].first>>ve[i].second;
        mp1[ve[i].first]++,mp2[ve[i].second]++;
        if(mp1[ve[i].first]==n||mp1[ve[i].second]==n)ok=false;
    }
    if(!ok){
        cout<<0;return ;
    }
    int ans,t=1;
    for(auto v:mp1)t=(t%mod*fac[v.second]%mod)%mod;
    ans=t%mod;
    t=1;
    for(auto v:mp2)t=(t%mod*fac[v.second]%mod)%mod;
    ans=(ans%mod+t%mod)%mod;
    sort(ve.begin(),ve.end());
    for(int i=1;i<ve.size();++i){
        if(ve[i].second<ve[i-1].second){ok=false;break;}
    }
    if(ok){
        for(auto v:ve)mp3[v]++;
        t=1;
        for(auto v:mp3){
            t=(t%mod*fac[v.second]%mod)%mod;
        }
        ans-=t;
    }
    cout<<((fac[n]%mod-ans)%mod+mod)%mod;
}
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

 

E - XOR Guessing

思路：第一次的数中二进制的第7~14位都为0，第二次的数中二进制的第0~6位都为0，这样两次就可以分别求出x的二进制情况

#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=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};


void init(){

}
void solve(){
    cout<<"? ";
    for(int i=1;i<=100;++i)cout<<" "<<i;cout<<'\n';
    int x;cin>>x;
    int ans=0;
    for(int i=7;i<14;++i)ans+=((x>>i&1)<<i);
    cout<<"? ";
    for(int i=1;i<=100;++i)cout<<" "<<(i<<7);cout<<'\n';
    cin>>x;
    for(int i=0;i<7;++i)ans+=((x>>i&1)<<i);
    cout<<"! "<<ans<<'\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

 

F - Remainder Problem

思路：分块√5e5=707，对于大于707的可以直接暴力求，小于707的用ans[i][j]存%i等于j的答案

#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=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};

int ans[705][705],a[N];

void solve(){
    int q;cin>>q;
    while(q--){
        int op,x,y;cin>>op>>x>>y;
        if(op==1){
            a[x]+=y;
            for(int i=1;i<=700;++i)ans[i][x%i]+=y;
        }else{
            if(x<=700)cout<<ans[x][y]<<'\n';
            else{
                int res=0;
                for(int i=y;i<N;i+=x)res+=a[i];
                cout<<res<<'\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