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 << "YESn"; else cout << "NOn"; } 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] = i; } for(int i = 1;i <= n;i ++) { if(vis.count(pre + a[i])) { swap(a[i], a[i + 1]); } pre += a[i]; } for(int i = 1;i <= n;i ++) { cout << a[i] << " 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[i]); } sort(g[now].begin(), g[now].end(), [] (const int &u, const int &v) { return dp[u] < dp[v]; }); } void dfs1(int now, int pre) { for(auto &i : g[now]) { if(i == pre) { continue; } if(dp[i])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[i].clear(); dp[i] = 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[u].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 + 1) / 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[i]; for(int i = 1;i <= n;i ++)pre[i] = pre[i - 1] ^ a[i]; 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'; } 
