A. Min Or Sum(位或运算)

题解思路

这道题还是经过当时群友提醒才知道怎么做的 XD
赛后再整理了一会，我是这样理解的：
每次操作可以贪心地将一组数字的每一个对应位都只变成剩余1个1或者没有1
比如 3 | 5 = 011 | 101 = 011 | 100 = 3 | 4这样就实现了5->4的变小过程
最后答案就是所有数字的或和

Code

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

int main () 
{
    int t;
    cin >> t;
    while (t--) 
    {
        int n, ans = 0;
        cin >> n;
        for (int i = 0, x; i < n; ++i) 
        {
            cin >> x;
            ans |= x;
        }
        cout << ans << endl;
    }
}

B. Avoid Local Maximums

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
 
int n, a[N];
 
int main()
{
    int T;
    cin >> T;
    
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)    cin >> a[i];
 
        int res = 0;
        for (int i = 2; i <= n - 1; i++)
            if (a[i] > a[i - 1] && a[i] > a[i + 1])
            {
                a[i + 1] = max(a[i], a[i + 2]);
                res++;
            }
        
        cout << res << endl;
 
        for (int i = 1; i <= n; i++)
            cout << a[i] << ' ';
        cout << endl; 
    }
    return 0;
}

C. Differential Sorting(贪心)

题面描述

题意：给定数组 a。可选的操作如下：
·选择 x < y < z，令 a[x] = a[y] - a[z] 。
能否进行若干操作，使得 a 数组单调不减。

解题思路

由于题目不要求最少次数，所以这道题完全可以利用贪心思想
Situ1:
如果a[n - 1] > a[n]的话直接输出-1 => 因为最后的两个数是找不到更靠后的y,z来修改的;
Situ2:
如果a[n - 1] <= a[n]并且a[n] < 0，如果是已经排好序的，直接输出0即可
否则如果出现一个逆序对，无论怎么修改都不能成功。
因为a[n]是负数，并且要做到非递减，那么a[n]的前面几个数都是比它更小的数
$a_y - a_z$ = 较小的负数 - 较大的负数 > 较小的负数 = $a_y$, 即$a_x > a_y$，不能形成非递减
Situ2:
如果a[n - 1] <= a[n]并且a[n] >= 0
用贪心：直接将前面n - 2个数全部用a[n - 1]和a[n]来修改。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 200020;

int n, a[N];

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)    cin >> a[i];

        if (a[n - 1] > a[n])    cout << -1 << endl;  // 最后的两个数是找不到更靠后的y,z来修改的;
        else 
        {
            if (a[n] < 0)  // 如果最后一个数是负数
            {
                if (is_sorted(a + 1, a + 1 + n))  cout << 0 << endl;  // 已经是非递减的话就不需要操作了
                else cout << -1 << endl;  // 否则直接失败
            }
            else 
            {
                cout << n - 2 << endl;
                for (int i = 1; i <= n - 2; i++)    cout << i << ' ' << n - 1 << ' ' << n << endl;
            }
        }
    }
    return 0;
}

D. Big Brush(前缀和、DP)

题目大意

解题思路

参考题解1和题解2
一开始看这两位的题解有点懵
后来仔细看了好一会才总算明白，整理以下问题：

问：为什么最后是pre[p -bit]而不是pre[p]?

因为fib[i]的定义为“当前元素增长i个长度的方案数量”， 如fib[3]意思是增长3个长度有多少种方案！
而pre[i]是“当前元素增长1~i个长度的方案总数量”, 假设一个数长度为bit = 3，p长度为8，那么最多增长p - len = 5;

问：为什么要删除一些没用的元素？

因为最后累计的是前缀和pre[i],不删除的话会导致某个元素的拓展会被重复计算

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 200020, mod = 1e9 + 7;

int n, p;
int a[N], fib[N], pre[N];
set<int> s;

int main()
{
    fib[0] = 0, fib[1] = 1, fib[2] = 1;
    for (int i = 3; i < N; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % mod;  // 预处理dp数组
    for (int i = 1; i < N; i++) pre[i] = (pre[i - 1] + fib[i]) % mod;  // 前缀和

    cin >> n >> p;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        s.insert(a[i]);   
    }

    for (int i = 1; i <= n; i++)  // 删除没用的元素， 保留二进制长度最小的那个值
    {
        int x = a[i];
        while (x)
        {
            if (x % 2 == 1) x /= 2;   // x <- 2 * y + 1
            else if (x % 4 == 0) x /= 4;   // x <- 4 * y
            else break;
            if (s.count(x))
            {
                s.erase(s.find(a[i]));
                break;
            }
        }
    }

    int res = 0;
    for (auto x : s) 
    {
        int bit = log2(x);  // 求出该数字的二进制长度
        res = (res + pre[max(0 , p - bit)]) % mod; // p - bit是最多增加的长度， 有可能超出，所以要和0取max
    }

    cout << res << endl;
    return 0;
}