2024ICPC 第一场网络赛 题解

The 2024 ICPC Asia East Continent Online Contest (I)

A - World Cup

Solution

画个图分析一下就好了

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val, id;
    bool operator < (const Node &B) const{
        return val < B.val;
    }
};

bool is_ok(vector<Node> &a) {
    for (auto v : a) {
        if (v.id == 1) return true;
    }
    return false;
}

void solve() {
    vector<Node> a(33);
    for (int i = 1; i <= 32; i++) cin >> a[i].val, a[i].id = i;
    sort(a.begin() + 1, a.end());
    int cnt = 0;
    for (int i = 1; i <= 32; i++) {
        if (a[i].id == 1) {
            cnt = i - 1;
        }
    }
    if (cnt >= 31) cout << 1;
    else if (cnt >= 27) cout << 2;
    else if (cnt >= 13) cout << 4;
    else if (cnt >= 6) cout << 8;
    else if (cnt >= 2) cout << 16;
    else cout << 32;
    cout << '\n';
}

int main() {
    freopen ("A.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

C - Permutation Counting 4

Solution

一个没怎么道理的解法

对于一对 $[l,r]$ ，从 $l\to r+1$ 连边，如果最后的图为一棵树，那么答案为 $1$ 否则为 $0$

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 2, 0);
    iota(a.begin(), a.end(), 0);

    function<int(int)> find = [&] (int x) -> int {
        return a[x] == x ? x : a[x] = find(a[x]);
    };

    function<void(int, int)> merge = [&] (int x, int y) {
        if (find(x) == find(y)) return;
        a[find(x)] = find(y);
    };

    vector<pair<int, int>> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;

    for (int i = 1; i <= n; i++) {
        auto [l, r] = p[i];
        if (find(l) == find(r + 1)) {
            cout << "0\n";
            return;
        }
        merge(l, r + 1);
    }
    set<int> st;
    for (int i = 1; i <= n + 1;  i++) st.insert(find(i));

    if (st.size() == 1) cout << "1\n";
    else cout << "0\n";
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

summary

• 对于答案为 01，应该从 YES/NO 的角度去思考，不应该从算总数的角度去考虑

M - Find the Easiest Problem

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;
const ll MOD = 998244353;
ll Tex, n, a[MAXN];
ll fastPow(ll a, ll b){
    ll ret = 1;
    while(b){
        if(b & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}
string s, t, p;
void AC(){
    cin >> n;
    map<pair<string, string>, ll> mp1;
    map<string, ll> mp2;
    ll mx = 0;
    for(int i = 1; i <= n; i ++){
        cin >> s >> t >> p;
        if(p == "accepted"){
            if(!mp1[{s, t}]){
                mp2[t] ++;
                mx = max(mp2[t], mx);
            }
            mp1[{s, t}] = 1;
        }
    }
    vector<string> ans;
    for(auto it : mp2){
        if(it.second == mx) ans.push_back(it.first);
    }
    sort(ans.begin(), ans.end());
    cout << ans[0] << '\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin >> Tex;
    while(Tex --) AC();
    return 0;
}