Codeforces Round 1007 (Div. 2)(ABCD1)

A. The Play Never Ends

翻译：

        让我们来介绍一种双人游戏--乒乓球，在这种游戏中，胜负永远分明，不可能出现平局。

        索赛、福福和浩海三人想用一生的时间打乒乓球。他们决定用以下方式永远打下去：

        在每场比赛中，两名选手比赛，第三名选手旁观。
        为了保证公平，任何选手都不能连续打三次。连续两次比赛的选手必须在下一场比赛中作为观众退场，由另外两名选手进行比赛。否则，获胜者和旁观者将参加下一场比赛，而失败者将作为旁观者。

        现在，玩家们完全沉浸在这无限循环的比赛中，委托你们解决以下问题：

        给定一个整数 k，判断第一场比赛的观众能否成为第 k 场比赛的观众。

思路：

推几场，可知从第一场开始每过3场，第一场比赛的观众还是观众（即场1，4，7。。。）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){int n;cin>>n;if (n%3==1){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();int t;cin>>t;while (t--){solve();}
}

B. Perfecto

翻译：

长度为 n 的排列 p 是完美的。如果对于每个索引 i (1≤i≤n)，它满足以下条件：

前 i 个元素 p1+p2+...+pi 的和不是完全平方†。

你希望事情是完美的。给定一个正整数 n，找出长度为 n 的完美排列，如果不存在，则打印-1。

思路：

直接暴力深搜，dfs( i , sum) 维护当前的位置 i 与 [ : i ]的和sum。并使用set维护值是否选过。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;bool check (ll now){return now==pow((ll)pow(now,0.5),2);
}
vector<ll> ans(1e6);
void solve(){ll n;cin>>n;ll now = n*(n+1)/2;if (check(now)){cout<<-1<<endl;return;}ans[n] = -1;set<ll> s;for (ll i=1;i<=n;++i) s.insert(i);ll summ = 0;for (int i=1;i<=n;++i){int f = 1;for (auto& num:s){if (!check(summ+num)){ans[i] = num;summ+=num;s.erase(num);f = 0;break;}}if (f){cout<<-1<<endl;return;}}if (ans[n]==-1){cout<<-1<<endl;}else{for (ll i=1;i<=n;++i){if (i!=1) cout<<" ";cout<<ans[i];}cout<<"\n";}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();int t;cin>>t;while (t--){solve();}
}

C. Trapmigiano Reggiano

翻译：

        在意大利的一个村庄里，一只饥饿的老鼠从一棵有 n 个顶点的树上的顶点 st 开始。

        给定长度为 n 的排列 p，共有 n 个步骤。在第 i 步中

一块诱人的帕马森奶酪出现在顶点 pi 处。如果小鼠当前位于顶点 pi，它将停留在那里享受这一刻。否则，它会沿着简单路径移动一条边到顶点 pi。

        你的任务是找到这样一种排列，使小鼠在走完 n 步之后，必然到达顶点 en，那里有一个陷阱在等着它。

        请注意，小老鼠必须经过 n 步之后到达 en 处，尽管在此过程中它可能会在更早的时候经过 en 在此过程中可能会提前经过 en。

思路：

题目中步骤的意思是按到pi的路径走一边，之后目标就会变了。

想到的排除的方法，我们以en节点为根节点建树。我们先遍历深度为i-1的一批节点，那么在之后的遍历中节点一定就到不了i-1以上深度的节点了，以此类推再遍历出i-2深度的节点，此时节点一定到不了i-2以上深度的节点了，一直推到深度为0，en点，记录到这结束后节点一定会在en点了。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){int n,st,en;cin>>n>>st>>en;vector<vector<int>> graph(n+1);for (int x,y,i=1;i<n;i++){cin>>x>>y;graph[x].push_back(y);graph[y].push_back(x);}vector<int> depth(n+1,0);vector<vector<int>> ans(n+1);auto dfs = [&](auto&& dfs,int now,int pre)->void{depth[now]=depth[pre]+1;ans[depth[now]].push_back(now);for (int i:graph[now]){if (i!=pre){dfs(dfs,i,now);}}};dfs(dfs,en,0);for (int i=n;i>=1;i--){for (int j:ans[i]){cout<<j<<" ";}}cout<<"\n";
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();int t;cin>>t;while (t--){solve();}
}

D1. Infinite Sequence (Easy Version)

翻译：

这是问题的简单版本。不同版本之间的区别在于，在这个版本中，l=r。只有解决了这个问题的所有版本，才能进行破解。

给你一个正整数 n 和一个无限二进制数列 a 的前 n 项，其定义如下：

对于 m>n， $a_{m}=a_{1}\oplus a_{2}\oplus...\oplus a_{\frac{m}{2}}$ 。

你的任务是计算给定范围 [l,r] 内元素的和： $a_{l}+a_{l+1}+...+a_{r}$

思路：

因为l==r，故而题目要求得到a[l]的值，由提供的式子可看出当m>n时 $a_{2m+1}=a_{2m}$ ，此时求 $a_{2m}=a_{1}\oplus a_{2}\oplus a_{3}...\oplus a_{m}$ ，当n为偶数时满足，a[n+1]是可能与a[n]不同的，所以要当n为偶数时，要推到a[++n]。而从 $a_{2m+1}=a_{2m}$ 可得到，

当m为偶数时， $a_{2m}=a_{1}\oplus a_{2}\oplus a_{3}...\oplus a_{n}\oplus a_{m}$ ，区间（n,m）中两两相同，最终会变为0，无影响。

当m为奇数时， $a_{2m}=a_{1}\oplus a_{2}\oplus a_{3}...\oplus a_{n}$ ，区间（n,m】中两两相同，最终会变为0，无影响。

注意 $a_{1}\oplus a_{2}\oplus a_{3}...\oplus a_{n}$ 可以提前计算

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MX = 1e5+10;void solve(){ll n,l,r;cin>>n>>l>>r;// pre[i] ,a1^a2^...^a[i]的值vector<ll> a(n+1),pre(n+1);for (ll i=1;i<=n;i++){cin>>a[i];pre[i] = pre[i-1]^a[i];}// 将n变为奇数if (n%2==0){++n;a.push_back(pre[n/2]);pre.push_back(pre.back()^a[n]);}// 得到受a影响的所有数组for (int i=n+1;i<=2*n;i++){a.push_back(pre[i/2]);pre.push_back(pre[i-1]^a[i]);}ll res = 0;while (1){if (r<=n*2){res ^= a[r];break;}res ^= pre[n];r/=2;if (r%2==1){break;}}cout<<res<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();ll t;cin>>t;while (t--){solve();}
}