AtCoder Regular Contest 164 A~C

A题都没做出来（被自已菜晕

A. Ternary Decomposition

A - Ternary Decomposition (atcoder.jp)

题意

给定一个正整数\(N\)，问是否存在\(K\)个整数，使得\(N=3^{m_1}+3^{m_2}+...+3^{m_k}\)

思路

首先对于一个正整数\(N\)，最多有\(N\)个整数使得正式成立，即\(m_i\)全为0。再对\(N\)进行三进制拆分，可得到最少使得原式成立的个数。

在三进制拆分后，所有指数不为0的项都能再拆分为三项，使项数加二。因此，\(k\)如果在最大值和最小值之间，并且奇偶性与\(N\)相同就存在，否则不存在。

代码

void solve() {
    ll k, n;
    cin >> n >> k;
 
    ll mx = n, mn = 0;
    while(n) {
        mn += n % 3;
        n /= 3;
    }
 
    if(k >= mn && k <= mx && k % 2 == mx % 2) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

B. Switching Travel

B - Switching Travel (atcoder.jp)

题意

给定一个无向图，每个节点为白色或黑色。只有当边的两端节点颜色不一样时，才能移动，且每离开一个节点，该节点的颜色就会变成另一种颜色。可以随便选择一个节点作为起点，求能否回到起点。

思路

如果图中存在一个环，起点和终点颜色相同，其余节点颜色交替出现，则说明能回到起点。

遍历边，如果一条边的两端节点颜色不同，合并到一个集合中。之后再遍历一次边，如果边两端的节点颜色相同，则查询它们是否在同一集合中，如果是，则说明存在一个满足条件的环。

代码

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct DSU {
    vector<int> p;
    
    DSU(int n) : p(n) {iota(p.begin(), p.end(), 0);}
    
    int find(int x) {
        while(x != p[x]) x = p[x] = p[p[x]];
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return false;
        p[y] = x;
        return true;
    }
    
    bool same(int x, int y) {return find(x) == find(y);}
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> e(m);
    for(int i = 0; i < m; i++) {
        cin >> e[i].first >> e[i].second;
    }

    vector<int> c(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
    }

    DSU D(n + 1);
    for(int i = 0; i < m; i++) {
        if(c[e[i].first] != c[e[i].second]) {
            D.merge(e[i].first, e[i].second);
        }
    }

    for(int i = 0; i < m; i++) {
        if(c[e[i].first] == c[e[i].second] && D.same(e[i].first, e[i].second)) {
            cout << "Yes\n";
            return 0;
        }
    }

    cout << "No\n";

    return 0;
}

c. Reversible Card Game

C - Reversible Card Game (atcoder.jp)

题意

给定若干张牌，牌的正反两面写有数字。Alice的回合会把场上某一张牌翻转，Bob的回合会把场上一张牌拿走并获得该牌朝上的数字。Alice想要Bob获得的数字之和最小，Bob想要获得的数字之和最大。求Bob最终能获得多少数字。

思路

Bob到最后会拿走所有的牌，为了使Bob获得的值减少，Alice每次翻转正面减反面差值最大的牌，而Bob会拿走差值最大的牌不让Alice翻，因此用一个优先队列模拟即可。

代码

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

struct node {
    int a, b;
    bool operator <(const node &T) const {return a - b < T.a - T.b;}
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    priority_queue<node> q;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        q.push({a, b});
    }

    ll ans = 0;
    while(!q.empty()) {
        int x = q.top().a, y = q.top().b;
        q.pop();
        q.push({y, x});
        ans += q.top().a;
        q.pop();
    }

    cout << ans << "\n";

    return 0;
}