CodeForces【Pinely Round 4 (Div. 1 + Div. 2)】赛后总结

赛时提交情况：

3144298-20240729205732465-294465862

CF1991A. Maximize the Last Element

赛时思路

首先，~~CF判断了足足2min确定我是真人~~，看到题目时首先想到的是，最后保留的数字之前及之后必然有偶数个数字，且 $n$ 为奇数，所以我们可以确定若 $a_i$ 是最后保留的数字， $i$ 必然为奇数（输入时从 i=1 开始）。

赛时 AC 代码

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define MAXN 0x3f3f3f3f3f3f3f3f
#define MINN -0x3f3f3f3f3f3f3f3f
#define Trubiacy ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;

//const int N=+29;
int n;

signed main(){
    Trubiacy;
    // int Tracy=1;
    int Tracy; cin>>Tracy;//多组输入
    while(Tracy--){
        cin>>n;
        int ans=MINN;///由于a[i]的数据范围最小为1，所以ans可以初始化为0
        for(int i=1;i<=n;i++){
            int x;cin>>x;
            if(i%2) ans=max(ans,x);//若i为奇数，则a[i]可能是保留到最后的数字，取最大值即可
        }
        cout<<ans<<endl;
    }
    return 0;
}

CF1991B. AND Reconstruction

赛时思路

这道题卡了我很久，~~位运算实在是太阴间了~~，我们可以想到，$ai$ 既参与到 $b_i$ 的计算中，也参与到了 $b{i-1}$ 的计算中，既然要通过与运算计算出 $bi$ 和 $b{i-1}$ 的值， $bi$ 和 $b{i-1}$ 的每一位1都会出现在 $ai$ 中，结合对样例的观察可以得出，**对于 $1<i<n-1$ , $a_i=b_i | b{i-1}$ ，同时我们可以得知，为了得到 $b1$ 与 $b{n-1}$ 的值，$a1=b_1$, $a_n=b{n-1}$**。

这里还存在一个问题，最后的答案可能会输出 -1 ，我的解决方式是模拟题目中的情况从头到尾跑一遍看是否符合题目描述。

赛时 AC 代码

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define MAXN 0x3f3f3f3f3f3f3f3f
#define MINN -0x3f3f3f3f3f3f3f3f
#define Trubiacy ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;

const int N=1e5+29;
int n,a[N],ans[N];//代码中数组命名有点乱，a数组为原题中b数组（使用a是因为我习惯输入的数组是a数组），ans为原题中a数组（使用ans是因为此数组为最终需要输出的数组）

signed main(){
    Trubiacy;
    // int Tracy=1;
    int Tracy; cin>>Tracy;
    while(Tracy--){
        cin>>n;
        for(int i=1;i<n;i++){
            cin>>a[i];
        }
        ans[1]=a[1];
        for(int i=1;i<n-1;i++){
            ans[i+1]=(a[i]|a[i+1]);
        }
        ans[n]=a[n-1];
        
        //判断是否成立（即有无可能输出-1）
        bool f=true;
        for(int i=1;i<n;i++){
            // cout<<(ans[i]&ans[i+1])<<" ";
            if((ans[i]&ans[i+1])!=a[i]){//不符合题目描述，即答案不存在
                f=false;
                break;
            }
        }
        if(!f) cout<<-1;
        else{
            for(int i=1;i<=n;i++){
                cout<<ans[i]<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}

CF1991C. Absolute Zero

赛时思路

先浅浅吐槽一下这个人机翻译都不如让我直接读英文原文） 3144298-20240729205817366-682912441

这个题，~~我也不知道我是怎么过的~~，做这个题自闭到想哭，刚要哭~~发现周深新专track9出了~~，跑去听歌听了几遍突然冒出思路来了，可以想到的是，我们需要找到一个方法在每次循环之后缩小元素的范围，所以我选择每次进行排序，选择 $x=\lceil\frac{a_{max}}{2}\rceil$ 进行操作。

另外在想到上面的思路之前我就想到过，若序列中各元素奇偶性不一致，则无解，但我最终没有运用上，因为我担心可能会有奇偶性一致的情况超出40步（官方题解说明了不存在这种情况），所以选择手动进行了40次操作。

赛时 AC 代码

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define MAXN 0x3f3f3f3f3f3f3f3f
#define MINN -0x3f3f3f3f3f3f3f3f
#define Trubiacy ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;

const int N=2e5+29;
int n,a[N];

signed main(){
    Trubiacy;
    // int Tracy=1;
    int Tracy; cin>>Tracy;
    while(Tracy--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+1+n);
        int t=0;
        vector<int> ans;
        bool f=false;
        while(t<40){
            if(a[n]==0){
                f=true;
                break;
            }
            t++;
            int op=a[n]/2+(a[n]%2==1);//取x的值为最大值/2上取整
            ans.push_back(op);//将答案暂存因为后面还要判断是否有解
            for(int i=1;i<=n;i++){
                a[i]=abs(a[i]-op);
            }
            sort(a+1,a+1+n);
        }
        // cout<<t<<endl;
        // if(a[n]==0) f=true;
        if(f){
            cout<<t<<endl;
            for(auto i:ans) cout<<i<<" ";
        }
        else cout<<-1;
        cout<<endl;
    }
    return 0;
}

赛后补充

看过官方和洛谷的题解之后发现，这道题的核心思路在于找到一个方法在每次循环之后缩小元素的范围，而这个方法有很多.

CF1991D. Prime XOR Coloring

赛时感想

~~这什么破题刚刚那个破题怎么做的我好困我好饿我不想打了~~，能想到或许要找到出度最大的值，其出度即颜色数，~~但是一想到码量可能会非常大我就睡过去了~~。

赛后整理

可以证明，当 $n\ge 6$ 时，$k=4$ ，理由如下：

首先可以证明，$k\ge 4$ 。$1,3,4,6$ 相异或会两两连接，所以它们必然是四种不同的颜色。

其次等号可以取到。考虑这种染色方式：将点 $i$ 染色成 $i\bmod 4+1$ 。那么若 $u,v$ 同色，即若 $u\equiv v (\bmod 4)$ ，那么它们在二进制表示下，最后 $2$ 位一定是相同的。那么 $u\oplus v$ 的最后两位一定都是 $0$ 。显然这个异或值是 $4$ 的倍数，不可能是质数。

那么 $n<6$ 时的情况好巧不巧样例还都给了，所以打个表就好啦。

赛后 AC 代码

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define MAXN 0x3f3f3f3f3f3f3f3f
#define MINN -0x3f3f3f3f3f3f3f3f
#define Trubiacy ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;

//const int N=+29;
int n,ans[6]={0,1,2,2,3,3};

signed main(){
    Trubiacy;
    // int Tracy=1;
    int Tracy; cin>>Tracy;
    while(Tracy--){
        cin>>n;
        if(n<6){
            cout<<ans[n]<<endl;
            for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
            cout<<endl;
            continue;
        }
        cout<<4<<endl;
        for(int i=1;i<=n;i++){
            cout<<i%4+1<<" ";
        }
        cout<<endl;
    }
    return 0;
}

总结

~~首先不要趴在床上打比赛容易打着打着睡着~~，比赛过程中感觉脑子挺乱，这次题目比较青睐位运算而位运算 ex 得一批我还不会做，，（所以要多被位运算坑一坑）。