Pinely Round 4 (Div. 1 + Div. 2)

赛时提交情况：

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

赛时思路

这道题卡了我很久，位运算实在是太阴间了，我们可以想到，\(a_i\) 既参与到 \(b_i\) 的计算中，也参与到了 \(b_{i-1}\) 的计算中，既然要通过与运算计算出 \(b_i\) 和 \(b_{i-1}\) 的值， \(b_i\) 和 \(b_{i-1}\) 的每一位1都会出现在 \(a_i\) 中，结合对样例的观察可以得出，对于 \(1<i<n-1\) , \(a_i=b_i | b_{i-1}\) ，同时我们可以得知，为了得到 \(b_1\) 与 \(b_{n-1}\) 的值，\(a_1=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

赛时思路

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

这个题，我也不知道我是怎么过的，可以想到的是，我们需要找到一个方法在每次循环之后缩小元素的范围，所以我选择每次进行排序，选择 \(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;
}

赛后补充

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