9.10 div1+2-526互联

2022-2023 ACM-ICPC German Collegiate Programming Contest (GCPC 2022)

思路：模拟每一步，下一个人从上一个人掉水的位置开始

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
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 double eps=1e-6;

void solve(){
    int n,k;cin>>n>>k;
    string s;cin>>s;
    int c=0,p=0;
    for(int i=0;i<n;++i){
        if(s[i]=='L'&&p!=0){
            c++;
            continue;
        }else if(s[i]=='R'&&p!=1){
            c++;
            continue;
        }
        p=(p+1)%2;
    }
    cout<<max(0ll,k-c);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

E - Enjoyable Entree

思路：打表发现n大于30后答案一样，其余暴力即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n;cin>>n;
    if(n==1)cout<<"100 0\n";
    else if(n==2)cout<<"0 100\n";
    else{
        if(n>30)cout<<"33.333333 66.666667\n";
        else{
            double ans,a=100,b=0;
            for(int i=3;i<=n;++i){
                ans=a/2+b/2;
                a=b,b=ans;
            }
            cout<<fixed<<setprecision(6)<<ans<<' '<<100.0-ans<<'\n';
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

C - Chaotic Construction

思路：用set存每个障碍物的位置，每个st和ed能走两个方向，二分st和ed的位置，判断是否有障碍物即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n,q;cin>>n>>q;
    set<int>se;
    char op;
    int a,b;
    map<int,int>mp;
    for(int i=0;i<q;++i){
        cin>>op;
        if(op=='-'){
            cin>>a;mp[a]=1;
            se.insert(a),se.insert(a+n);
        }else if(op=='+'){
            cin>>a;mp[a]=0;
            se.erase(a),se.erase(a+n);
        }else{
            cin>>a>>b;
            if(a>b)swap(a,b);
            if(mp[a]||mp[b])cout<<"impossible\n";
            else{
                auto l=se.lower_bound(a);
                auto r=se.lower_bound(b);
                bool ok1=true,ok2=true;
                if(r!=se.end()&&*r<a+n)ok1=false;
                if(l!=se.end()&&*l<b)ok2=false;
                if(se.empty()||ok1||ok2)cout<<"possible\n";
                else cout<<"impossible\n";
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code

L - Lots of Land

思路：若总面积能整除n一定可以，假设每个矩形一样大，枚举下边a和b，发现若w和h能塞下一定是合法的

I - Improving IT

思路：维护以i结尾需要的最少花费

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
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 double eps=1e-6;


void solve(){
    int n,m;cin>>n>>m;
    vector<int>ve[n+5];
    for(int i=1;i<=n;++i){
        for(int j=0,x;j<=min(m,n-i+1);++j){
            cin>>x;
            ve[i].push_back(x);
        }
    }
    ve[n+1].push_back(0);
    vector<int>dp(n+5,1e15);
    dp[1]=ve[1][0];
    for(int i=2;i<=n+1;++i){
        for(int j=max(1ll,i-m);j<i;++j){
            dp[i]=min(dp[i],dp[j]+ve[i][0]-ve[j][i-j]);
        }
    }
    cout<<dp[n+1];
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

View Code

D - Diabolic Doofenshmirtz

思路：倍增的问，记录上一次跑的长度，若当前长度小于last，说明跑过了一圈，那么一圈为当前跑了的长度-当前位置

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
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 double eps=1e-6;


void solve(){
    int s=1,last=0,x;
    while(1){
        cout<<"? "<<s<<'\n';
        cin>>x;
        if(x<=last){
            cout<<"! "<<s-x<<'\n';
            break;
        }
        last=x;
        s*=2;
    }
}
signed main(){
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

View Code

A - Alternative Architecture

思路：将格子转成线段，边长需要减一，那么枚举构成边a的直角边x和y，由相似三角形可得x和y是否满足构成边b；若a和b不同，答案乘二，再加上与轴线平行的矩形数

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
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 double eps=1e-6;


void solve(){
    int a,b;cin>>a>>b;
    a--,b--;
    int ans=0;
    if(a>b)swap(a,b);
    for(int x=1,y;x<a;++x){
        y=a*a-x*x;
        int r= ::sqrt(y);
        if(y==r*r){
            if((x*b)%a==0&&(r*b)%a==0){
                ans++;
            }
        }
    }
    if(a!=b)ans*=2,ans+=2;
    else ans+=1;
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

View Code

H - Hardcore Hangman

思路1：将a~z表示成1~26的二进制数，第i次询问为：所有第i位为1的数，即返回的所有位置上的数的第i位为1，那么5次便可知道所有位置上的数

思路2：对于abc，询问ab和bc可以分别知道a、b、c的位置，那么对于长度为26的abc...xyz，将其分为s1、s2、s3三段，询问s1s2和s2s3可以分别知道s1、s2、s3的所有位置，同理对每段再进行分三段操作。由于每段的位置互不干扰，所以一次询问中可同时对s1、s2、s3进行分三段操作，那么最多只需要6次

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e4+5;
void solve(){
    string s[5];
    for(int i=1;i<=26;++i){
        for(int j=0;j<5;++j){
            if(i>>j&1){
                s[j].push_back('a'+i-1);
            }
        }
    }
    vector<int>ans(N);
    for(int i=0,c;i<5;++i){
        cout<<"? "<<s[i]<<'\n';
        cin>>c;
        for(int j=0,x;j<c;++j){
            cin>>x;
            ans[x]|=(1<<i);
        }
    }cout<<"! ";
    for(int i=1;ans[i];++i){
        cout<<char('a'+ans[i]-1);
    }cout<<'\n';
}
signed main(){
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

View Code 1

找毒药问题

有1000瓶水，其中一瓶含毒药，有若干只小鼠，每只小鼠可喝任意瓶水，若小鼠喝到毒药会在一小时后死亡。

题1：用一个小时找出毒药需要的最少小鼠数

思路：将每瓶水用二进制数表示，为1~1000，第i只小鼠喝所有第i位为0的水；若一小时后第i只小鼠死亡，说明毒药的第i位为0，否则为1；那么只需要10只小鼠

题2：用两个小时找出毒药需要的最少小鼠数

思路：不同于题1的是，小鼠可重复用，在两个小时中，小鼠的情况有3种：死、生死、生生，这里可以用三进制数表示每瓶水；第i只小鼠喝所有第i位为0的水，若一个小时后小鼠死亡，则毒药的第i位为0，否则第i只小时再喝第i位为1的水，若一个小时后小鼠死亡，则毒药的第i位为1，否则第i位为2；那么最少需要5只小鼠

J - Jesting Jabberwocky

思路：要求相同的字母要排在一起，有四种字母，且操作后的顺序不确定，考虑用dp做；由于只有四种字母，那么枚举所有的排列，f[i][j]表示前i个字符已排好，且第i个是第j种的情况，如果s[i]=j，那么只要的<=j的结尾都满足，则f[i][j]=min（f[i-1][0~j]），否则需要删除当前字符，则f[i][j]=f[i-1][j]+1

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
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 double eps=1e-6;


void solve(){
    string s;cin>>s;
    int n;n=s.size();
    s.insert(s.begin(),' ');
    vector<int>p;
    vector<vector<int>>f(n+5,vector<int>(5));
    string str=" hcds";
    for(int i=1;i<=4;++i)p.push_back(i);
    int ans=INF;
    auto V=[&](vector<int>num){
        vector<char>t;
        for(int i=0;i<num.size();++i)t.push_back(str[num[i]]);
        for(int i=1;i<=n;++i){
            for(int j=0;j<4;++j){
                if(s[i]==t[j]){
                    f[i][j]=INF;
                    for(int k=0;k<=j;++k)f[i][j]=min(f[i][j],f[i-1][k]);
                }else{
                    f[i][j]=f[i-1][j]+1;
                }
            }
        }
        int res=INF;
        for(int i=0;i<4;++i)res=min(res,f[n][i]);
        return res;
    };
    ans=min(ans,V(p));
    while(next_permutation(p.begin(),p.end())){
        ans=min(ans,V(p));
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

View Code

codeforces div1a div1 865

codeforces div1a div1 div

1404 div1 div cf

9.10 10