Codeforces Round 1007 (Div. 2)

我有罪，休息了好久，这次来补补题

A.The Play Never Ends

签到，找到规律就可以

void solve(){
    int x;
    cin >> x;
    if(x%3 == 1){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

B. Perfecto

找规律，发现如果他如果前缀和组成了完全平方数，与后面的进行交换就能防止

bool judge(int x){
    return int(sqrt(x))*int(sqrt(x)) == x;
}
int sum[N];
int a[N];
void solve(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        sum[i] = 0;
    }
    for(int i = 1;i <= n;i++){
        a[i] = i;
    }
    int ans = n*(n+1)/2;
    if(judge(ans)){
        cout << -1 << '\n';
        return;
    }
    for(int i = 1;i <= n;i++){
        sum[i] = sum[i-1] + a[i];
    }
    for(int i = 1;i <= n;i++){
        if(judge(sum[i])){
            std::swap(a[i],a[i+1]);
        }
    }
    for(int i = 1;i <= n;i++){
        cout << a[i] <<' ';
    }
    cout << '\n';
}

C. Trapmigiano Reggiano

倒序输出bfs序即可

void solve(){
    cin >> n >> st >> en;
    for(int i = 1;i <= n;i++){
        e[i].nxt = 0;
        head[i] = 0;
        vis[i] = 0;
        e[i].to = 0;
    }
    for(int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        add(u,v);
        add(v,u);
    }
    vector<int> ans;
    queue<int> q;
    q.push(en);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 1;
        ans.push_back(u);
        for(int i = head[u];i;i = e[i].nxt){
            int v = e[i].to;
            if(!vis[v]){
                q.push(v);
            }
        }
    }
    std::reverse(ans.begin(),ans.end());
    for(int i = 0;i < ans.size();i++){
        cout << ans[i] << " ";
    }
    cout << '\n';
    
}

D1. Infinite Sequence (Easy Version)

如果n是偶数，则n+1为奇数 $a_{n+1}\bigoplus a_{n + 2} = 0$ 可以得出更多的规律，由此可以推出计算的公式
进行递归计算就可

int cal(int x){
    if ( x <= n ) return a[x];
    else if ( x / 2 <= n ) return pre[x / 2];
    else if ( (x / 2 - n) % 2 ){
        return pre[n] ^ cal(x / 2);
    }else{
        return 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&1)){
       n++;
       a[n] = pre[n/2];
       pre[n] = pre[n - 1]^a[n];
   }
   cout << cal(r) << '\n';
    
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while(T--) solve();
    return 0;
}