【Atcoder训练记录】AtCoder Beginner Contest 393

猿柒

6个月前更新

训练情况

忙着处理训练数据，赛后打的，没有排名

赛后反思

这场太典了，感觉我能力范围内都是一眼题，剩下的真不会了

A题

显然有问题的就是 sick或fine补集，对应的交集，如果交集为空答案就是 4，我们直接大力分类讨论，fine fine是 4，sick fine是 2，fine sick是 3，sick sick是 1

点击查看代码

#include <bits/stdc++.h>
// #define int long long
#define endl '\n'

using namespace std;

void solve(){
    string s,t; cin>>s>>t;
    if(s == "fine" && t == "fine") cout<<4<<endl;
    else if(s == "sick" && t == "fine") cout<<2<<endl;
    else if(s == "fine" && t == "sick") cout<<3<<endl;
    else if(s == "sick" && t == "sick") cout<<1<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

B题

按照题目所述大力枚举三个位置即可，判断三个位置对应的字符是否为 ABC，并且位置间隔相同

点击查看代码

#include <bits/stdc++.h>
// #define int long long
#define endl '\n'

using namespace std;

void solve(){
    string s; cin>>s;
    int n = s.size();
    int ans = 0;
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            for(int k = j+1;k<n;k++){
                if(s[i] == 'A' && s[j] == 'B' && s[k] == 'C' && j-i==k-j) ans++;
            }
        }
    }
    cout<<ans<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

C题

显然我们先处理自环的问题，就是输入的 u v 相同就是自环，重边只要 u v 和 v u 都算，所以我这边直接小编号的节点的当成 u，大编号的节点当成 v，开个 pair<int,int> 的 map 记录是否出现过即可，重复出现则答案加一

点击查看代码

#include <bits/stdc++.h>
// #define int long long
#define endl '\n'
#define pii pair<int,int>

using namespace std;

void solve(){
    int n,m; cin>>n>>m;
    map<pii,bool> v;
    int ans = 0;
    for(int i = 1;i<=m;i++){
        int x,y; cin>>x>>y;
        if(x == y){
            ans++;
            continue;
        }
        if(x > y) swap(x,y);
        if(v[{x,y}]) ans++;
        else v[{x,y}] = 1;
    }
    cout<<ans<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

D题

盲猜了一个中间答案最优，我记得有个中位数定理的，1 有奇数个的情况下，直接无脑移中间，但是对于 1 有偶数个的情况下，中间的数有两个，我们两个都计算一下答案，注意一下答案的贡献不是一致的，是递减的，结果取最小值即可

点击查看代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

void solve(){
    int n; string s; cin>>n>>s;
    vector<int> a;
    for(int i = 0;i<n;i++){
        if(s[i] == '1') a.emplace_back(i);
    }
    n = a.size();
    int ans1 = 0,ans2 = 0;
    int pos1 = (n-1)/2,pos2 = n/2;
    for(int i = 0;i<pos1;i++) ans1 += a[pos1] - a[i] - (pos1 - i - 1) - 1;
    for(int i = 0;i<pos2;i++) ans2 += a[pos2] - a[i] - (pos2 - i - 1) - 1;
    for(int i = pos1+1;i<n;i++) ans1 += a[i] - a[pos1] - (i - pos1 - 1) - 1;
    for(int i = pos2+1;i<n;i++) ans2 += a[i] - a[pos2] - (i - pos2 - 1) - 1;
    cout<<min(ans1,ans2)<<endl;
}

signed main(){
    // int T; cin>>T; while(T--)
    solve();
    return 0;
}

来源链接：https://www.cnblogs.com/longxingx/p/18717727

评分

欢迎为Ta评分