Codeforces Round 998 (Div. 3）

题目链接：Codeforces Round 998 (Div. 3)

总结：复建，Cwa两发，E读假题了。

A. Fibonacciness

tag：签到

Solution：简单模拟一下即可。

void solve(){
    int a[5];
    for (int i = 0; i < 5; i ++){
        if (i == 2){
            continue;
        }
        cin >> a[i];
    }
    a[2] = a[0] + a[1];
    int ans = 0;
    for (int i = 2;  i < 5; i ++){
        if (a[i] == a[i - 1] + a[i - 2])
            ans ++;
        else
            continue;
    }
    a[2] = a[3] - a[1];
    int ans2 = 0;
    for (int i = 2;  i < 5; i ++){
        if (a[i] == a[i - 1] + a[i - 2])
            ans2 ++;
        else
            continue;
    }
    cout << max(ans, ans2) << endl;
}

B. Farmer John’s Card Game

tag：签到

Solution：显然需要按顺序一个人一个人递增的出牌，将每个人的牌排序以后，模拟出牌顺序，看是否能够满足。

void solve(){
    int n, m;
    cin >> n >> m;
    vector<pii> ans(n);  // 
    set<int> a[n];

    for (int i = 0; i < n; i ++){
        ans[i].se = i;  // 每个人的位置
        for (int j = 0; j < m; j ++){
            int x;
            cin >> x;
            a[i].insert(x);
        }
        ans[i].fi = *(a[i].begin());  // 每个人最小的牌
    }

    sort(ans.begin(), ans.end());
    int t = 0;
    for (int j = 0; j < m; j ++)
        for (int i = 0; i < n; i ++){
            if (*(a[ans[i].se].begin()) == t){
                a[ans[i].se].erase(t);
                t ++;
            }
            else{
                cout << -1 << endl;
                return;
            }
        }

    for (int i = 0; i < n; i ++){
        cout << ans[i].se + 1 << " \n"[i + 1 == n];
    }
}

C. Game of Mathletes

tag：思维

Solution：得分是固定的，只要有两个数能够加起来等于K，那么b就能得分。

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);

    multiset<int> st;
    for (int i = 0; i < n; i ++){
        cin >> a[i];
        st.insert(a[i]);
    }
    sort(a.begin(), a.end());

    int ans = 0;
    for (int i = 0; i < n; i ++){
        if (st.size() == 0 || a[i] >= k)
            break;
        int b = k - a[i];
        if (st.find(a[i]) != st.end() && st.find(b) != st.end()){
            auto x = st.find(a[i]);
            st.erase(x);
            if (st.find(b) == st.end()){  // 当a == b时，避免RE
                st.insert(a[i]);
                continue;
            }
            auto y = st.find(b);
            st.erase(y);
            ans ++;
        }
    }

    cout << ans << endl;
}

D. Subtract Min Sort

tag：思维

Description：给定n个数，可以进行任意次操作，每次操作令 a i a_i ai​和 a i + 1 a_{i + 1} ai+1​同时减去 m i n ( a i , a i + 1 ) min(a_i, a_{i +1}) min(ai​,ai+1​)。问能否将原序列变为非递减序列。

Solution：从第一个数开始模拟，显然第一个数比第二个数大不行，否则我们让它们进行操作，则第一个数变为零，向后继续操作即可。

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i ++){
        cin >> a[i];
    }

    for (int i = 1; i < n; i ++){
        if (a[i - 1] > a[i]){
            cout << "NO\n";
            return;
        }
        a[i] -= a[i - 1];
    }

    cout << "YES\n";
}

E. Graph Composition

tag：并查集

Description：给定两个无向图F和G，可以对F操作：

• 在u，v之间建一条边。
• 删除一条u，v之间的边。
• 求最小操作次数，使得F中u，v之间有一条路径，当且仅当G中u，v之间有一条路径。

Solution：建两个并查集f和g，将g中的点进行合并，首先枚举F中的边，如果两点在g中不属于同一个并查集则将它们删除，否则在f中合并它们。然后枚举g中的边，如图两点在同一个并查集中，则在f中将它们合并，记录操作次数。

Competing：将图看成了连通图。

void solve(){
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    set<pii> a1, a2;
    DSU f(n + 1), g(n + 1);
    
    for (int i = 0; i < m1; i ++){
        int x, y;
        cin >> x >> y;
        if (x > y)
            swap(x, y);
        a1.insert({x, y});
    }

    for (int i = 0; i < m2; i ++){
        int x, y;
        cin >> x >> y;
        a2.insert({x, y});
        g.merge(x, y);
    }

    int ans = 0;
    for (auto [x, y] : a1){
        if (g.find(x) != g.find(y)){ // 必须删
            ans ++;
        }
        else{
            f.merge(x, y);
        }
    }

    for (auto [x, y] : a2){
        if (g.find(x) == g.find(y)){
            ans += f.merge(x, y);
        }
    }
    cout << ans << endl;
    
}