[数据结构与算法]Codeforces Round#772 Div.2

A. Min Or Sum 题目链接

题意：给你n个数，通过若干次操作，使得最后序列和最小。每次操作可以选取两个下标，i < j, 在满足ai | aj = x | y 的条件下，将ai替换为x, aj替换为y（其中，| 操作为或运算）。

思路：考虑或运算的性质，只有0和0进行或运算，结果才会是0。所以，但凡原数列的某一个位置含有数字1，那么进行异或操作之后的结果此位置结果必然为1。所以，在进行最后算数的时候，只需要将原数列的所有数进行或运算。

#include<bits/stdc++.h>
using namespace std;

int t, n;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t -- ){
        cin >> n;
        int x = 0;
        while(n -- ){
            int y;
            cin >> y;
            x = x | y;
        }
        cout << x << endl;
    }
    return 0;
}

B. Avoid Local Maximums 题目链接

题意：给你一个序列，让你通过改变序列某些位置的值，使得序列不存在局部最大值（a[i] > a[i - 1] && a[i] > a[i + 1])。

思路：贪心。当我们找到一个i值，使得a[i] > [i - 1] && a[i] > a[i + 1]的时候，那么我们就接着去判断a[i + 1] 与 a[ i + 2]的关系，如果a[i + 1] < a[i + 2], 那么就从把a[i + 1] 变成 a[i], a[i + 2] 中更大的一个数，反之，就可以把a[i+ 1] 变成a[i]。

代码：

#include<bits/stdc++.h>
#define int long long int
using namespace std;

const int N = 2e5 + 10;
int t, n, a[N], b[N], c[N], d[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t -- ){
        cin >> n;
        int cnt = 0;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 2; i < n; i++){
            if(a[i] > a[i + 1] && a[i] > a[i - 1]){
                if(a[i + 1] < a[i + 2] && i + 2 < n){
                    a[i + 1] = max(a[i], a[i + 2]);
                }
                else a[i + 1] = a[i];
                cnt ++;
            }
        }
        cout << cnt << endl;
        for(int i = 1; i <= n;i ++){
            if(i == n) cout << a[i] << endl;
            else cout << a[i] <<" ";
        }
    }
    return 0;
}

C. Differential Sorting 题目链接

题意：给一个长度为n的序列，判断这个序列能否通过操作数小于等于n，使得序列变成一个非递减的序列。具体操作就是，选取下标x, y, z 满足x < y < z， 令 a[x] = a[y] - a[z]。

思路：关键的一点，是判断什么时候序列是不合法的。序列不合法的情况，无非就是a[n - 1] > a[n] 以及a[n] < 0两种情况。假设，a[k] <= a[k + 1]， 一直到a[n]， 那么说明a[k,n]中所有的数都是负数。如果a[k - 1] > a[k], 那么从后边选取k - 1 < x < y， 那么a[x] - a[y] 一定会破坏后边序列的不减性，因为减去一个负数等于加上一个整数。

代码：

#include<bits/stdc++.h>
#define int long long int
using namespace std;

const int N = 2e5 + 10;
int t, n, a[N], b[N], c[N], d[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t -- ){
        cin >> n;
        int cnt = 0;
        for(int i = 1; i <= n; i++) cin >> a[i];
        if(is_sorted(a + 1, a + 1 + n)){
            cout <<"0" << endl;
        }
        else if(a[n - 1] > a[n] || a[n] < 0){
            cout <<"-1" << endl;
        }
        else{
            cout << n - 2 << endl;
            for(int i = 1; i <= n - 2; i ++){
                if(i == n -2) cout <<i<<" "<< n - 1 <<" " <<n <<endl;
                else cout <<i<<" "<< n - 1 <<" " <<n << endl;
            }
        }
    }
    return 0;
}