Codeforces Round #541 (Div. 2)（ABCF）-蒲公英云

Codeforces Round #541 (Div. 2)（ABCF）

水深无声 2023-06-03 13:52 40阅读 0赞

A. Sea Battle（水）

题意：两个长方形拼在一起，求出拼完后周围的面积；

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a1,b1,a2,b2;
    cin>>a1>>b1>>a2>>b2;
    int ans=a1+2*b1+abs(a1-a2)+a2+2*b2;
    cout<<ans+4<<endl;
    return 0;
}

B. Draw!

题意：从（0，0）开始，给出n个分数，问最大可能平局的次数；

转化成求两个区间相交的点有多少；模拟一遍就行了；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int main(){
    ll n,a,b,x;
    cin>>n;
    ll ans=1LL;
    ll lasta=0,lastb=0;
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        if(a>=b){
            if(lasta>=lastb){
                x=b-lasta;
            }
            else{
                x=b-lastb;
            }
            if(lasta!=lastb)x++;
            if(x<0)x=0;
            ans+=x;
        }
        else{
            if(lastb>=lasta){
                x=a-lastb;
            }
            else {
                x=a-lasta;
            }
            if(lasta!=lastb)x++;
            if(x<0)x=0;
            ans+=x;
        }
        lasta=a;lastb=b;
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    return 0;
}
/*
3
5 6 5 7 5 8
*/

C. Birthday

题意：n个人，围成一圈，重排序，让全部相邻的两个差值最小；

解：排序，然后跳着输出，1-3-5-7-9…… 然后从后面再往前面输出每输出过的值

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;
ll a[maxn],b[maxn],c[maxn];
bool vis[maxn];
int main(){
    int n;
    cin>>n;
    ll maxx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxx=max(a[i],maxx);
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i+=2){
        cout<<a[i]<<' ';
        vis[i]=true;
    }
    if(n%2==0){
        cout<<a[n]<<' ';
        vis[n]=true;
    }
    for(int i=n;i>=1;i--){
        if(!vis[i])cout<<a[i]<<' ';
    }
    cout<<endl;
    return 0;
}

F. Asya And Kittens

题意：n个格子，每次给出一对x，y，说明x，y相邻，然后输出最初始的样子；

解：并查集，然后输出路径；

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
vector<int>g[maxn];
int f[maxn];
int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}
void gao(int x){
    cout<<x<<' ';
    for(int i=0;i<g[x].size();i++){
        gao(g[x][i]);
    }
}
int main(){
    int n;
    cin>>n;
    int rt;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        int uu=find(u),vv=find(v);
        if(uu==vv)continue;
        rt=uu;
        g[rt].push_back(vv);
        f[vv]=uu;
    }
    gao(rt);
    cout<<endl;
    return 0;
}