Codeforces Round ＃805 (Div. 3)（8/8）

Problem - A - Codeforces

AC代码：

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

void Solve() {
    LL m;
    cin >> m;
    LL a = 1;
    while (a * 10 <= m) {
        a *= 10;
    }
    cout << m - a << '\n';
}

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

    int T;
    cin >> T;
    while (T--) {
         Solve();
    }

    return 0;
}

Problem - B - Codeforces

AC代码：

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

void Solve() {
    string s;
    cin >> s;
    int len = s.size();
    set<int> se;
    vector<bool> vis(26);
    int ans = 0;
    for (int i = 0; i < len; i++) {
        se.insert(s[i] - 'a');
        if (i == len - 1 && se.size() > 0) {
            if (se.size() != 4) {
                ans++;
            }
            else {
                ans += 2;
            }
            break;
        }
        if (se.size() == 4) {
            ans++;
            se.clear();
            se.insert(s[i] - 'a');
        }

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

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

    int T;
    cin >> T;
    while (T--) {
         Solve();
    }

    return 0;
}

Problem - C - Codeforces

AC代码：

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

int T, n, k, a[200010];
map<int, pair<int, int>> mp;

void Solve() {
    cin >> n >> k;
    mp.clear();
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (mp[a[i]].first == 0) {
            mp[a[i]].first = i + 1;
            mp[a[i]].second = i + 1;
        }
        else {
            mp[a[i]].second = i + 1;
        }
    }
    while (k--) {
        int x, y;
        cin >> x >> y;
        if (mp[x].first > mp[y].second || mp[x].first == 0 || mp[y].first == 0) {
            cout << "No\n";
        }
        else {
            cout << "Yes\n";
        }
    }
}

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

    cin >> T;
    while (T--) {
        Solve();
    }
 
    return 0;
}

Problem - D - Codeforces

AC代码：

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

void Solve() {
    string s;
    cin >> s;
    int p;
    cin >> p;
    int len = s.size();
    LL sum = 0;
    vector<int> cnt(26);
    for (int i = 0; i < len; i++) {
        sum += s[i] - 'a' + 1;
        cnt[s[i] - 'a']++;
    }
    for (int i = 25; sum > p;) {
        while (cnt[i] == 0) {
            i--;
        }
        cnt[i]--;
        sum -= i + 1;
    }
    for (int i = 0; i < len; i++) {
        if (cnt[s[i] - 'a']) {
            cout << s[i];
            cnt[s[i] - 'a']--;
        }
    }
    cout << '\n';
}

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

    int T;
    cin >> T;

    while (T--) {
        Solve();
    }
 
    return 0;
}

Problem - E - Codeforces

AC代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int n;
int fa[200010], cnt[200010], sum[200010];
int getfa(int x) {
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
void Solve() {
    cin >> n;
    iota(fa, fa + n + 1, 0);
    memset(cnt, 0, sizeof(cnt));
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        cnt[u]++, cnt[v]++;
        fa[getfa(u)] = getfa(v);
    }
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] != 2) {
            flag = false;
        }
        sum[getfa(i)]++;
    }
    for (int i = 1; i <= n; i++) {
        if (sum[getfa(i)] & 1) {
            flag = false;
        }
    }
    flag ? cout << "YES\n" : cout << "NO\n";
}

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

    int T;
    cin >> T;

    while (T--) {
        Solve();
    }
 
    return 0;
}

Problem - F - Codeforces

AC代码：

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

void Solve() {
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        while (a[i] > 0 && a[i] % 2 == 0) {
            a[i] /= 2;
        }
        mp[a[i]]++;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        while (b[i] > 0 && b[i] % 2 == 0) {
            b[i] /= 2;
        }
        while (b[i] > 0) {
            if (mp[b[i]] > 0) {
                mp[b[i]]--;
                break;
            }
            else {
                b[i] /= 2;
            }
        }
    }
    bool ok = true;
    for (int i = 0; i < n; i++) {
        if (mp[a[i]] > 0) {
            ok = false;
            break;
        }
    }
    if (ok) cout << "YES\n";
    else cout << "NO\n";
}

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

    int T;
    cin >> T;

    while (T--) {
        Solve();
    }
 
    return 0;
}

Problem - G1 - Codeforces

LCA板板题

AC代码：

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

vector<int> G[200005];
LL dep[200005], fa[200005][32];

void dfs(int root, int father) {
    fa[root][0] = father;
    dep[root] = dep[fa[root][0]] + 1;
    for (int i = 1; i <= 30; i++) {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
    }
    int sz = G[root].size();
    for (int i = 0; i < sz; i++) {
        if (G[root][i] == father) {
            continue;
        }
        dfs(G[root][i], root);
    }
}
int lca(int u, int v) {
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    int d = dep[v] - dep[u];
    for (int i = 0; d; i++, d >>= 1) {
        if (d & 1) {
            v = fa[v][i];
        }
        
    }
    if (u == v) {
        return v;
    }
    for (int i = 30; i >= 0 && u != v; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    cin >> m;
    while (m--) {
        int len;
        cin >> len;
        vector<int> v(len);
        for (int i = 0; i < len; i++) {
            cin >> v[i];
        }
        int x = v[0], y = -1;
        for (int i = 1; i < len; i++) {
            if (dep[v[i]] > dep[x]) {
                x = v[i];
            }
        }
        for (int i = 0; i < len; i++) {
            if (v[i] != x) {
                int ans = lca(v[i], x);
                if (ans != v[i] && (y == -1 || dep[y] < dep[v[i]])) {
                    y = v[i];
                }
            }
        }
        if (y == -1) {
            cout << "YES\n";
            continue;
        }
        bool ok = true;
        int head = lca(x, y);
        for (int i = 0; i < len; i++) {
            int j = lca(x, v[i]), k = lca(y, v[i]);
            if (!((j == v[i] && k == head) || (k == v[i] && j == head))) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
 
    return 0;
}

Problem - G2 - Codeforces

AC代码：

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

vector<int> G[200005];
LL dep[200005], fa[200005][32];

void dfs(int root, int father) {
    fa[root][0] = father;
    dep[root] = dep[fa[root][0]] + 1;
    for (int i = 1; i <= 30; i++) {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
    }
    int sz = G[root].size();
    for (int i = 0; i < sz; i++) {
        if (G[root][i] == father) {
            continue;
        }
        dfs(G[root][i], root);
    }
}
int lca(int u, int v) {
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    int d = dep[v] - dep[u];
    for (int i = 0; d; i++, d >>= 1) {
        if (d & 1) {
            v = fa[v][i];
        }
        
    }
    if (u == v) {
        return v;
    }
    for (int i = 30; i >= 0 && u != v; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    cin >> m;
    while (m--) {
        int len;
        cin >> len;
        vector<int> v(len);
        for (int i = 0; i < len; i++) {
            cin >> v[i];
        }
        int x = v[0], y = -1;
        for (int i = 1; i < len; i++) {
            if (dep[v[i]] > dep[x]) {
                x = v[i];
            }
        }
        for (int i = 0; i < len; i++) {
            if (v[i] != x) {
                int ans = lca(v[i], x);
                if (ans != v[i] && (y == -1 || dep[y] < dep[v[i]])) {
                    y = v[i];
                }
            }
        }
        if (y == -1) {
            cout << "YES\n";
            continue;
        }
        bool ok = true;
        int head = lca(x, y);
        for (int i = 0; i < len; i++) {
            int j = lca(x, v[i]), k = lca(y, v[i]);
            if (!((j == v[i] && k == head) || (k == v[i] && j == head))) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
 
    return 0;
}