Codeforces-1007div2题解

A - D1题解

连续掉分ing, 什么时候才能变得又快又猛呢hehehe。。。

A. The Play Never Ends

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

using i64 = long long;

void solve() {
    i64 k;
    cin >> k;

    if (k % 3 == 1) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

B. Perfecto

打表观察 从 1 到 300 sum的和是平方数的数字，发现和是平方数的只有 1 36 1225…..， 想要不出现平方数，只需要在前 i 个（其中 i 是使得sum是平方数的数字）不全是i的排列，也就是把每个满足和是平方数的最后一个数字和下一个数字替换，如果不超出范围就可以，否则-1

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

using i64 = long long;

void solve() {
    i64 n;
    cin >> n;

    i64 sum = 0;
    vector<i64> a(n + 1);
    for (i64 i = 1; i <= n; i++) {
        a[i] = i;
    }
    for (i64 i = 1; i <= n; i++) {
        sum += a[i];
        i64 g = sqrt(sum);
        if (g * g == sum) {
            if (i + 1 > n) {
                cout << "-1" << '\n';
                return;
            }
            sum -= a[i];
            swap(a[i], a[i + 1]);
            sum += a[i];
        }
    }

    for (i64 i = 1; i <= n; i++) {
        cout << a[i] << " \n"[i == n];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 t;
    cin >> t;   

    while(t--) {
        solve();
    }

    return 0;
}

C. Trapmigiano Reggiano

以en为根， 对树进行分层，每次取深度较大的节点，之后取深度较小的节点，走最深的情况是一条链，这时候会走 n / 2个点，之后n / 2个操作又会回到根，其他情况会在某条最长链的某个节点来后跳（因为有别的树链），如果最后回到原点直接输出，否则-1

update: 看了大佬们说答案似乎不可能出现-1， 好像可以直接后序遍历，答案总会存在

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

using i64 = long long;
const int inf = 1e9 + 7;
void solve() {
    int n, st, en;
    cin >> n >> st >> en;

    vector<vector<int>> e(n + 1);
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    
    vector<int> dis(n + 1, -1);
    dis[en] = 0;

    auto dfs = [&](auto self, int u, int fa) -> void {
        for (int v : e[u]) {
            if (v != fa) {
                dis[v] = dis[u] + 1;
                self(self, v, u);
            }
        }
    };
    dfs(dfs, en, -1);
    
    vector<int> ans(n + 1);
    for (int i = 1; i <= n; i++) {
        ans[i] = i;
    }

    sort(ans.begin() + 1, ans.end(), 
        [&](int a, int b) {
            return dis[a] > dis[b];
        });
    
    //cerr << "dis:" << dis[st] << '\n';
    if (dis[st] == -1) {
        cout << "-1\n";
    } else {
        for (int i = 1; i <= n; i++) {
            cout << ans[i] << " \n"[i == n];
        }  
    }  
}

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

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

D1. Infinite Sequence (Easy Version)

手玩样例， 发现 7 = 8, 78 = 79……, 那么每对在 “^” 内（也就是除以二一样）的数字总是一样的，他们作为下一个数字的异或和的时候总是不做贡献，可以忽略。

我们不妨补全给定的n数组，使得n总是奇数（这样下一位置开始时候总是出现两两相等情况）

继续观察，发现

• 当 x / 2是奇数时候，这时除了前n个给定的数字，其他总是两两成对出现， 此时 x = s[ n ] & 1;
• 当 x / 2是偶数的时候，除了x / 2,在n + 1到x / 2之间的所有数字都是成对出现，不参与计算，故 x = s[ n ] & (x / 2),

这样递归下去可以找到答案，最坏时间复杂度为o(logn);

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

using i64 = long long;

void solve() {
    i64 n, l, r;
    cin >> n >> l >> r;

    vector<i64> a(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }   

    if (n % 2 == 0) {
        n++;
        a.push_back(s[n / 2] & 1);
        s.push_back(s[n - 1] + a[n]);
    }

    auto f = [&](auto self, i64 x) -> int {
        if (x <= n) {
            return a[x];
        }

        if (x / 2 <= n) {
            return (s[x / 2] & 1);
        }

        int g;
        if ((((x / 2) - n) & 1)) {
            g = self(self, x / 2) ^ (s[n] & 1);
        }
        else {
            g = (s[n] & 1);
        }
        return g;
    };

    // if (l <= n * 2) {
    //     for (int i = n + 1; i <= l; i++) {
    //         a.push_back(s[i / 2] & 1);
    //         s.push_back(a[i] + s[i - 1]);
    //     }
    //     cout << a[l] << '\n';
    //     return;
    // }

    cout << f(f, l) << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}