当前位置：首页 > article >正文

Codeforces Round 1007 (Div. 2)(ABCD1)

article 2025/3/3 13:47:56

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();
    }
}