比赛时间：2025-03-01

Codeforces Round 1007 (Div. 2)¶

比赛链接: https://codeforces.com/contest/2071

最丢人的一集，再次 div2 只写出两题。但是有一说一，感觉这场C是比上场D难的，或者说差不多。。。

赛时差不多也是三千多人过了C，赛时我好像没怎么写出过通过这个人数的题。。。10分钟把AB写了，然后后面想了一小时C，一点思路没有。看了题解的想法，怎么这么简单。且有道理。。

D我后面自己看看先。

A¶

自己推一下然后看看样例猜一下，比如第一场肯定不行，第三场也不行，因为如果第一场休息的人第三场休息，那么就会有一个人赢了三场。看看样例，大概也是只有模三等于一的时候是YES。

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

B¶

看着有点吓人，但其实思路很简单。只要求每个前缀的和不为完全平方数，那么我们其实顺着放就行了，如果加上下一个数会变成完全平方数，那么我们就跳一个加呗。所以直接用个数组或者队列操作一下就行。如果是最后一个数字了，那么说明n个数字加起来恰好是完全平方数，那么就肯定不行。

void solve()
{
    int n;
    cin>>n;
    long long sum=0;
    priority_queue<int>q;
    for(int i=n;i>=1;i--)
        q.push(i);
    auto check=[](long long x){
        long long y=(long long)sqrt(x);
        return x!=y*y;
    };
    vector<int>ans;
    while(!q.empty()){
        if(check(sum+q.top())){
            ans.push_back(q.top());
            sum+=q.top();
            q.pop();
        }else{
            int x=q.top();
            q.pop();
            if(q.empty()){
                cout<<"-1\n";
                return;
            }
            ans.push_back(q.top());
            sum+=q.top();
            q.pop();
            q.push(x);

        }
    }
    for(auto x:ans)
        cout<<x<<" ";
    cout<<'\n';
}

用数组啥的都行。其实我判得是不是也不够严格，有没有可能加上下一个数，仍是完全平方数，但是应该很少很少的可能性。

C¶

自己看感觉非常的难受，看完题解怎么这么爽。。

以 $en$ 为根节点，然后每次我们使用深度最深的点。把这个深度的点用完之后，老鼠所在的点就不可能会小于这个深度。所以我们只要一层一层的使用，就一定会让它移动到根节点。

void solve()
{
    int n, st, en;
    cin >> n >> st >> en;
    vector<vector<int>> adj(n + 1, vector<int>());
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> dep(n + 1);
    vector<vector<int>> g(n + 1, vector<int>());
    auto dfs1 = [&](auto&& self, int u, int pre) -> void {
        g[dep[u]].push_back(u);
        for (auto v : adj[u]) {
            if (v == pre)
                continue;
            dep[v] = dep[u] + 1;
            self(self, v, u);
        }
    };
    dfs1(dfs1, en, -1);
    vector<int> ans;
    for (int i = n; i >= 0; i--) {
        for (auto v : g[i])
            ans.push_back(v);
    }
    for (auto x : ans)
        cout << x << " ";
    cout << '\n';
}

D¶

我真傻真的，我只注意到新加入的数字，一定第奇数位是和前一位相同。但我没有想到这意味着中间的 $a_{n+1}\oplus a_{n+2}=0 $ , $a_{n+3}\oplus a_{n+4}=0 $ ,$a_{n+5}\oplus a_{n+6}=0 $ ... 大部分都会被消掉的。

而且我还没注意到这题里 $l=r$ ，我一直想怎么求和呢。。。

先让 $n$ 为奇数，若不是奇数加一项就行。这样后面每次都是连着出现两个一样的。设 $pre$ 为前缀异或和数组。

$a_{2m}=a_{2m+1}=pre_{m} $ ，若 $m$ 为奇数，显然 $pre_m=pre_n$ .

否则 $pre_m=pre_n \oplus a_m $ , 因为中间的项全被消了。

所以递归求就行。因为考虑的是 $\frac{m}{2}$ 的情况，所以我们先把 $2n$ 的情况预先处理出来。

constexpr int N = 2e5+1;
int a[N<<1], pre[N<<1];

void solve()
{
    // n为奇数时
    // a[n+1]=a[n+2]
    // a[n+3]=a[n+4]
    // a[2m]=a[2m+1] 设 p = xor[1,n]
    // 那么如果 m&1 ,res=p
    // 可以弄到 m<=2*n
    int n;
    long long l, r;
    cin >> n >> l >> r;
    for (int i = 1; i <= n; i++)
        cin >> a[i], pre[i] = pre[i - 1] ^ a[i];
    if (n % 2 == 0) {
        n++;
        a[n] = pre[n >> 1];
        pre[n] = pre[n - 1] ^ a[n];
    }
    for (int i = n + 1; i <= 2 * n; i++) {
        a[i] = pre[i >> 1];
        pre[i] = pre[i - 1] ^ a[i];
    }
    // 刚刚还在想 不是求和吗。。。
    // 原来在这个题里 l=r。。。才发现啊··
    //  n]
    auto query = [&](auto self, long long i) -> int {
        if (i <= 2 * n)
            return a[i];
        if (i >> 1 & 1)
            return pre[n];
        return pre[n] ^ self(self, i / 2);
    };
    cout << query(query, l) << '\n';
}