Codeforces998(Div3 A-E)

A. Fibonacciness

​
题目链接:https://codeforces.com/contest/2060/problem/A

​处于前面位置不用多想直接暴力写

void solve() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    map<int,int>mp;
    mp[a + b]++;
    mp[c - b]++;
    mp[d - c]++;

    int ans = 0;
    for(auto [c,v] : mp) ans = max(ans, v);

    cout<<ans<<'\n';
}

B. Farmer John’s Card Game

题目链接:https://codeforces.com/contest/2033/problem/B

首先我们要思考什么情况下有解？我们把整体想成一个二维数组，要想使得每头牛都能把牌出完,贪心的想肯定是每头牛都先出自己最小的牌。

首先满足的条件是对于每一列的数据必须按照同一个排序方式(出牌方式);

同时根据题意，如果能把牌放到堆顶那么当前牌的编号一定大于当前堆顶牌的编号;

也就是前一列的最大值一定是小于后一列的最小值的，这样的顺序出牌才能满足条件，因为数据很小，直接暴力排序处理即可。

void solve() {
    int n,m;
    cin>>n>>m;
    vector<vector<int>>v(n,vector<int>(m));
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) cin>>v[i][j];
        sort(v[i].begin(), v[i].end());
    }

    vector<int>ans;
    int next = 0;
    for(int j = 0;j < m;j++) {
        vector<PII>sen;
        for(int i = 0;i < n;i++) sen.emplace_back(v[i][j], i);

        sort(sen.begin(), sen.end());

        if(!j) {
            for(auto c : sen) ans.emplace_back(c.second);
            next = sen[n - 1].first;
        } else {
            for(int k = 0;k < n;k++) {
                if(sen[k].second != ans[k] || sen[k].first <= next) {
                    cout<<-1<<'\n';
                    return;
                }

                next = sen[k].first;
            }
        }
    }

    for(auto c : ans) cout<<c + 1<<" ";
    cout<<'\n';
}

C. Game of Mathletes

​
题目链接:https://codeforces.com/contest/2060/problem/C

​初看好像是道博弈题，但是仔细想想后发现

因为Alice先手，所以如果Alice所选的数和数组中其它某个数能组成k那么后手的Bob是一定能够获得这1分的。

这样本题就和博弈无关了，我们只要统计整个数组中有多少对数之和等于k即可

void solve() {
    int n,k;
    cin>>n>>k;
    vector<int>v(n + 1);
    map<int,int>mp;
    for(int i = 1;i <= n;i++) {
        cin>>v[i];
        mp[v[i]]++;
    }

    int ans = 0;
    for(auto [c,v] : mp) {
        int sen = k - c;
        if(sen == c) {
            ans += v / 2;
        } else if(mp[sen]) {
            int mi = min(mp[sen], mp[c]);
            ans += mi;
            mp[sen] -= mi;
            mp[c] -= mi;
        }
    }
    cout<<ans<<'\n';
}

D. Subtract Min Sort

​
题目链接:https://codeforces.com/contest/2060/problem/D

​对于任意一个 i 我们只能处理后一个数也就是 i + 1;

所以假设存在第 i 个数是大于第 i + 1 个数，那个很明显无解，所以我们就顺着这个方向去模拟即可

void solve() {
    int n;
    cin>>n;
    vector<int>v(n + 1);
    for(int i = 1;i <= n;i++) cin>>v[i];

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

        v[i + 1] -= v[i];
    }

    cout<<"YES\n";
}

E. Graph Composition

​
题目链接:https://codeforces.com/contest/2060/problem/E

​首先题目大意是,我们有两个图F,G,二者顶点数相同但是连边情况不一定相同;

我们可以对图F操作,连通的点我们可以断开,未连通的点可以连接起来,现在求使得两个图连边情况一致的最小操作次数。

我们直接根据题意模拟即可，分别计算出F需要断开的边数和需要连通的边数，可能需要注意的是无向图，连边会计算两次的情况。

可以使用并查集或者直接dfs

void solve() {
    int n,m1,m2;
    cin>>n>>m1>>m2;
    vector<int>edge1[n + 1],edge2[n + 1];
    for(int i = 1;i <= m1;i++) {
        int u,v;
        cin>>u>>v;
        edge1[u].emplace_back(v);
        edge1[v].emplace_back(u);
    }
    for(int i = 1;i <= m2;i++) {
        int u,v;
        cin>>u>>v;
        edge2[u].emplace_back(v);
        edge2[v].emplace_back(u);
    }

    int cnt2 = 0;
    vector<int>adj(n + 1);
    vector<int>st2(n + 1);
    function<void(int)> dfs2 = [&](int u) -> void {
        adj[u] = cnt2;
        st2[u] = 1;
        for(auto c : edge2[u]) {
            if (!st2[c]) dfs2(c);
        }
    };

    for(int i = 1;i <= n;i++) {
        if(!st2[i]) {
            cnt2++;
            dfs2(i);
        }
    }

    int res = 0;
    map<PII, int>mp;
    for(int i = 1;i <= n;i++) {
        for(auto c : edge1[i]) {
            if(adj[i] != adj[c]) {
                res++;
                mp[{i, c}] = 1;
            }
        }
    }

    int cnt1 = 0;
    vector<int>st1(n + 1);
    function<void(int)> dfs1 = [&](int u) -> void {
        st1[u] = 1;
        for(auto c : edge1[u]) {
            if(!st1[c] && !mp[{u, c}]) dfs1(c);
        }
    };

    for(int i = 1;i <= n;i++) {
        if(!st1[i]) {
            cnt1++;
            dfs1(i);
        }
    }

    int ans = res / 2 + (cnt1 - cnt2);
    cout<<ans<<'\n';
}