Codeforces Round 1007 (Div. 2) 比赛记录

h0Wggs0HZ

Codeforces Round 1007 (Div. 2) 比赛记录

比赛链接
很喜欢的一场比赛，题目质量很高，不是手速场，做出题超级有成就感，赛时切掉了 A - D1，上大分了。
B卡得有点久，其实是一个很常用的构造手法但一开始没想到。
过题记录：

A. The Play Never Ends

题意大概就是，每场两个人打，一个人观战。如果有一个人以及连续打了两场，则这场无论如何这个人都要下去，否则输的那个下去，问第 \(k\) 场的时候第一场观战的人能否观战。
假设第一场打的人分别是 A 和 B，A 获胜，观战者是 C，手玩一下小一点的样例发现，第二场 C 一定上场，此时 A 已经打了一场，那么 A 和 C 打完后，无论如何，下的都是 A，再打一场后，由于 C 已经打了两场了，所以无论如何，下的都是 C，如此进行下去可以发现，输赢无所谓，因为总有一方连续打了两场，必须下，因此实际上就是三个人轮换，所以 C 观战的时候就是 \(k \bmod 3 = 1\) 的时候
void solve(){    int n;cin >> n;    if(n % 3 == 1)cout << "YES\n";    else cout << "NO\n";}B. Perfecto

我愿称之为本场前四题最难题，因为我好友列表都被卡了。
一开始我天真地以为只有 \(1\) 是不可能的，因为公差为 \(1\) 的等差数列求和公式，一个奇数一个偶数，偶数除以 \(2\) 后一定不和这个奇数相等，除了 \(1\)，但是，有没有可能，他们乘起来还是一个平方数，比如：\(8\)。
因此首先判断 \(-1\) 的情况，也就是总和为平方数的情况，此时无论如何都无解因为总和是平方数。
然后再看如何构造，这里用到了一个构造题很常用的手法，就是先把一般的搞出来，再去修。
我们先初始化答案排列为 \(1 - n\) 升序排列。
然后依次遍历，并且记录前缀和，一旦当前 \(i\) 的前缀和是平方数，那就交换 \(a_i\) 和 \(a_{i + 1}\)，为什么？因为 \(a_{i + 1} = a_i + 1\)，一个平方数 \(+1\) 一定不是一个平方数。
然后再来证一个事情，就是交换的时候 \(a_{i + 1} = a_i + 1\)。
假设当前为第 \(i\)，因为前 \(i\) 项和为 \((1 + i) \times i / 2\)，那么前 \(i + 1\) 项的和为 \((1 + i) \times (2 + i) / 2\)，我们通过打表可以发现，平方数一定不会在相邻两项连续出现，因此若前 \(i\) 项是平方数，交换后，前 \(i + 1\) 项的值不会改变，仍然不是平方数，因此不会进行交换，也就不会影响后续相邻两项的 \(a_{i + 1} = a_i + 1\)。
const int N = 5e5 + 9;map<int, bool> vis;int a[N];void solve(){    int pre = 0;    int n;cin >> n;    if(vis.count((n + 1) * n / 2)) {        cout << -1 << '\n';        return;    }    for(int i = 1;i <= n;i ++) {        a = i;    }    for(int i = 1;i <= n;i ++) {        if(vis.count(pre + a)) {            swap(a, a[i + 1]);        }        pre += a;    }    for(int i = 1;i <= n;i ++) {        cout << a << " \n"[i == n];    }}void init() {    for(int i = 1;i < N;i ++) {        vis[i * i] = true;    }}signed main(){    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);    init();    int t = 1;cin >> t;    while(t --)solve();    return 0;}C. Trapmigiano Reggiano

本场最有趣最好玩的题出现了！
题意大概就是，一只老鼠，在树上一个起点，要去树上一个终点，现在要你构造出一个长度为 \(n\) 的排列，逐一进行，每次老鼠都会朝着排列中这一位的数的结点的方向走去，让老鼠最后能抵达终点。
手玩了好多样例后发现一定有解，以下是我的见解：
我们以起点作为根，对于每一个结点，它至多有一个子结点的子树是包含终点的，因此我们要让老鼠先把非终点的子树走完。对于非终点的子树，我们从下往上选，一定是可以回到当前结点的，因为我们选的数是从下往上走的，我们的老鼠是从上往下走的，那么二者一定会相遇，而后就一起往上走回去。把非终点的子树选完后，再选择当前这个结点，把老鼠引回来，而后往终点子树走，继续按照上述流程递归下去，最后一定会到达终点。
因此我的代码思路就是：先以起点为根 DFS 一次，标记一下每一棵子树是否有终点，然后再来一次 DFS，按照上述流程加点形成答案序列。
赛后看了群里面大佬的解析并细细品味了一下我的代码，这不就是拓扑排序嘛，我们每次选择度为 \(1\) 的非终点结点加进来，最后加终点，一定有解，或者是以终点为起点 BFS，按深度倒序输出。
const int N = 1e5 + 9;vector<int> g[N];bool dp[N];int n, st, ed;vector<int> ans;void dfs(int now, int pre) {    dp[now] = (now == ed);    for(auto &i : g[now]) {        if(i == pre) {            continue;        }        dfs(i, now);        dp[now] = (dp[now] || dp);    }    sort(g[now].begin(), g[now].end(), [] (const int &u, const int &v) {        return dp < dp[v];    });}void dfs1(int now, int pre) {    for(auto &i : g[now]) {        if(i == pre) {            continue;        }        if(dp)ans.push_back(now);        dfs1(i, now);    }    if(!dp[now])ans.push_back(now);}void init(int n) {    for(int i = 1;i <= n;i ++) {        g.clear();        dp = 0;    }    ans.clear();} void solve(){    cin >> n >> st >> ed;    init(n);    for(int i = 1;i < n;i ++) {        int u, v;cin >> u >> v;        g.push_back(v);        g[v].push_back(u);    }    dfs(st, 0);    dfs1(st, 0);    ans.push_back(ed);    for(auto &i : ans) {        cout << i << ' ';    }    cout << '\n';}D1. Infinite Sequence (Easy Version)

思维难度远小于 C 题，我们可以发现，对于一个偶数 \(x\) 和一个奇数 \(x + 1\)，一定有 \(\lfloor x / 2 \rfloor = \lfloor x / 2 \rfloor\)，若 \(n\) 为偶数，我们先多算一项把 \(n\) 变成奇数，因此在第 \(n\) 项后，相邻两项的值一定是相同的，又根据异或的性质，相同的数异或后的值为 \(0\)，因此后面看似一段连续的序列，实则是离散的，有效点很少。
我们采取递归实现，使用一个 \(get(x)\) 函数来获取一个数 \(x\) 的前缀异或和，如果 \(x\) 为奇数，直接返回 \(pre_n\)，因为 \(n\) 之后全是 \(0\)，如果 \(x\) 为偶数，则用这个偶数的单点值，异或上 \(pre_n\)，因为这个偶数之前到 \(n\) 也全是 \(0\)。
int get(int x) {    if(x <= n)return pre[x];    if(x & 1) {        return pre[n];    } else {        return get(x / 2) ^ pre[n];    }}void solve(){    cin >> n >> l >> r;    for(int i = 1;i <= n;i ++)cin >> a;    for(int i = 1;i <= n;i ++)pre = pre[i - 1] ^ a;        if(n % 2 == 0) {        n ++;        a[n] = pre[n / 2];        pre[n] = pre[n - 1] ^ a[n];    }     if(l <= n) {        cout << a[l] << '\n';        return;    }        cout << get(l / 2) << '\n';}