Educational Codeforces Round 109 (Rated for Div. 2)

Educational Codeforces Round 109 (Rated for Div. 2)

A - Potion-making

思路：求最小操作数即药水最简比

#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 init(){

}
void solve(){
    int x,y;cin>>x;
    y=100-x;
    int d=gcd(x,y);
    x/=d,y/=d;
    cout<<x+y<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    init();
    while(t--){
        solve();
    }
    return 0;
}

B - Permutation Sort

思路：可以选连续n-1个任意排序；已经是有序的操作为0

当1在第n个位置，n在第1个位置时：操作3次；

当1已经在第1位置或n已经在第n个位置时，且还有逆序的：操作1次

其他情况需要2次

#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 init(){

}
void solve(){
    int n;cin>>n;
    bool ok=false;
    vector<int>ve(n);
    for(int i=0;i<n;++i){
        cin>>ve[i];
        if(i==0&&ve[i]==1)ok=true;
        if(i==n-1&&ve[i]==n)ok=true;
    }
    vector<int>s=ve;
    sort(s.begin(),s.end());
    int ans=0;
    for(int i=0;i<s.size();++i){
        if(s[i]!=ve[i]){
            ans=2;break;
        }
    }
    if(ans&&ok)ans=1;
    if(ans==2&&ve[0]==n&&ve[n-1]==1)ans=3;
    cout<<ans<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    init();
    while(t--){
        solve();
    }
    return 0;
}

C - Robot Collisions

思路：可以发现分别在奇数和偶数位置的机器会撞在一起，那么将所有机器按奇偶位置分开

有4种爆炸的情况：1. l1→ ←l2 ，t =（l2-l1）/2

　　　　　　　　  2. ←l1 ←l2 ，t =（l1+l2）/2

　　　　　　　　  3. l1→ l2→ ，t =（2m-l1-l2）/2

　　　　　　　　  4. ←l1 l2→ ，t =（m+l1-l2）/2

将所有位置排序后，从前开始遍历，→会与下一个←碰撞，可以用栈放每个→；碰到一个←，即取出栈顶计算爆炸时间，若栈为空的，将←放进栈；←会与下一个←碰撞，栈顶为←时同样计算爆炸时间。

当遍历完之后，栈不为空时，从栈顶开始取，每次取的两个会碰撞；若栈中还剩一个，即为不会爆炸

#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 init(){

}

map<int,int>mp,op;
int n,m;

void P(vector<int>ve){
    stack<int>stk;
    for(int i=0;i<ve.size();i++){
        if(op[ve[i]]==1)stk.push(ve[i]);
        else{
            if(!stk.empty()){
                int s;
                if(op[stk.top()]==1)s=(ve[i]-stk.top())/2;
                else s=(ve[i]+stk.top())/2;
                mp[stk.top()]=s,mp[ve[i]]=s;
                stk.pop();
            }else stk.push(ve[i]);
        }
    }
    if(!stk.empty()){
        int k=stk.size()/2;
        for(int i=1;i<=k;++i){
            int a=stk.top();stk.pop();
            int s;
            if(op[stk.top()]==1)s=(2*m-a-stk.top())/2;
            else s=(2*m+stk.top()-a)/2;
            mp[stk.top()]=mp[a]=s;
            stk.pop();
        }
        if(!stk.empty()){
            mp[stk.top()]=-1;
            stk.pop();
        }
    }
}
void solve(){
    mp.clear(),op.clear();
    cin>>n>>m;
    vector<int>ve(n+1);
    vector<int>ve1,ve2;
    for(int i=1;i<=n;++i){
        cin>>ve[i];
        if(ve[i]%2)ve1.push_back(ve[i]);
        else ve2.push_back(ve[i]);
    }
    sort(ve1.begin(),ve1.end());
    sort(ve2.begin(),ve2.end());
    for(int i=1;i<=n;++i){
        char c;cin>>c;
        if(c=='R')op[ve[i]]=1;
        else op[ve[i]]=2;
    }
    P(ve1);P(ve2);
    for(int i=1;i<=n;++i){
        cout<<mp[ve[i]]<<' ';
    }cout<<'\n';
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    init();
    while(t--){
        solve();
    }
    return 0;
}

D - Armchairs

思路：f[i][j]表示前i个有人的座位，前j个无人的座位已换好需要的最小移动数；

f[i][j]=min（f[i-1][j]，f[i-1][j-1]+abs（p1[i]-p0[j]））分别表示第i个人不坐和坐第j个空位

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


void solve(){
    int n;cin>>n;
    vector<int>p1,p0;
    p1.push_back(0),p0.push_back(0);
    for(int i=1,x;i<=n;++i){
        cin>>x;
        if(x==1)p1.push_back(i);
        else p0.push_back(i);
    }
    vector<vector<int>>f(p1.size(),vector<int>(p0.size(),0));
    for(int i=1;i<p1.size();++i)
        for(int j=i;j<p0.size();++j){
            if(i==j)f[i][j]=f[i-1][j-1]+abs(p1[i]-p0[j]);
            else f[i][j]=min(f[i][j-1],f[i-1][j-1]+abs(p1[i]-p0[j]));
        }
    cout<<f[p1.size()-1][p0.size()-1];
    return;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}