题解与反思

前三题在大佬的带领下，做的飞快，我的脑子转的太慢了

B 小苯的好数组

1. 猜证题。
2. 我们根据题意可以得知，只要数组不是完全单调递增的，好数组的长度就是n，我们要找的就是，不完全单调递增的序列的最大长度。刚开始以为是DP。。。
3. 我们再进一步想一下，是不是一个序列就分为：完全单调递增和不完全单调递增两类。
4. 所以只要数组不是完全单调递增，答案就是n，反之就是0。

#include<iostream>
#include<vector>

using namespace std;

int main()
{

    int n;
    cin >> n;
    vector<int> a(n + 10);
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
    }
    int flag = 0;
    for(int i = 1; i < n; i ++)
    {
       //数组不是单调递增的
        if(a[i] < a[i - 1])
        {
            flag = 1;
            break;
        }
    }
    if(flag) cout << n << endl;
    else cout << 0;
    return 0;
}

C 小苯的数字合并

1. 贪心+前缀和
2. 数组的极差肯定是，最大值越大，最小值越小越好，根据题目给的操作，最大值越大就是合并的数字越多，最小值最小，就是单独的一个数字，所以我们极差的更新，应该是每次留一个数，其他数字合并，算一下极差。
3. 题目给的合并操作是相邻两个数的合并，也就是一段来连续数字的合并，我们可以想到用前缀和来计算这段连续的和。
4. 我们每次枚举一个数，作为极小值，左右两边的数字分别合并，最后数组变为三个数a，b，c，我们更新答案即可：res = max({res, abs(a - b), abs(c - b)}。
5. 关键就是想到最大的极差一定出现在，最小值只有一个数，剩下的数合并再一起的情况，并且理解题目的合并其实是连续一段序列的合并。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N], sum[N];
signed main()
{

    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int res = -1e18;
    for(int i = 1; i <= n; i ++)
    {
        int t = a[i];
        int x = sum[i - 1];
        int y = sum[n] - sum[i];
        res = max({res, abs(y - t), abs(x - t)});
    }
    cout << res << endl;
    return 0;
}

D 小苯的排列构造

1. 神奇的数学推理题目。
2. 参考大佬的推理过程：

a[i] = gcd(ans[1],...ans[i])
a[i-1] = gcd(ans[1],...ans[i-1]
∴ a[i] = gcd(a[i-1],ans[i])
∴ a[i-1]%a[i]=0, (a[i - 1]是a[i] 的倍数) ans[i]%a[i]=0（p[i]也是a[i]的倍数）
由 a[i-1] % a[i] = 0可知,a是一个非增序列, a[i-1]与a[i]只有两种情况, a[i-1]==a[i], a[i-1]>a[i]

现在从前往后依次确定ans:

(1) 如果a[i - 1] > a[i]:  
意味着a[i]是第一次出现, 那么数a[i]一定是没使用过的, 该位需要填a[i] 

    证明:
    a[i-1] = gcd(ans[1],...ans[i-1]) > a[i] = gcd(ans[1],...ans[i])
    min(ans[1],...ans[i-1]) > min(ans[1],...ans[i])
    min(ans[1],...ans[i-1]) > ans[i]
    ∴ ans[1]~ans[i-1] 与 ans[i] 不相等, a[i]一定未使用
    
    填a[i]是否会导致无解:
    例如: a[i-1] = 4, a[i] = 2, n≥6
    显然6也可以填, 那么2可以填在哪
    如果 a[i+1] = 2, 则2可以填在i+1位, 这样的话,2与6可以互换, 不影响正确性
    如果 a[i+1] = 1, 则后面都是1, 可填数字是任意的, 2和6依旧可以互换
    所以填a[i] 不会导致无解
    
(2) 如果a[i-1] = a[i]:
那么需要找一个a[i]的未使用倍数

填多少倍: 
    与1的互换同理, 找一个最小的满足条件的倍数即可

从哪开始找:
    不能直接从a[i]开始查找, 数组a末尾有很长串的1, 会超时
    ∵ a[i] = gcd(ans[1],...ans[i])
    ∴ ans[i]是a[i]的倍数, ans[i-1]也是a[i]的倍数, 且 ans[i] > ans[i-1]
    为啥ans[i] > ans[i-1]?
     因为每个ans[i]一定是a[i]的倍数，而我们填的时候是从小的倍数开始填的所以ans[i] > ans[i - 1], 并且他俩都是a[i]的倍数。
    所以我们可以从大于ans[i-1]的第一个a[i]的倍数：ans[i-1]+a[i] 开始查找，保证不会超时。
    

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int a[N], res[N], vis[N];
signed main()
{

    int n,flag = 0;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if(a[i - 1] % a[i] != 0)
        {
            flag = 1;
        }
    }
    if(flag)
    {
        cout << -1 << endl;
        return 0;
    }

    res[1] = a[1];
    vis[res[1]] = 1;
    for(int i = 2; i <= n; i ++)
    {
        if(a[i] == a[i - 1])
        {
            for(int k = res[i - 1] + a[i]; k <= n; k += a[i])
            {
                if(vis[k] == 0 && __gcd(k, a[i - 1]) == a[i])
                {
                    res[i] = k;
                    break;
                }
            }
        }
        else
        {
            res[i] = a[i];
        }
        if(res[i] == 0)
        {
            flag = 1;
            break;
        }
        vis[res[i]] = 1;
    }

    if(flag) cout << -1 << endl;
    else
    {
        for(int i = 1; i <= n; i ++)
        {
            cout << res[i] << " ";
        }
    }

    return 0;
}

E 小苯的01背包

1. 刚开始以为就是01背包的变形，后来发现都WA了。
2. 因为体积和价值的总和都是，所有物品相与的结果，我们知道越与越小，所以我们选的物品越多，体积越小，同时价值也越小。
3. 所以我们在选择物品的时候尽量选择可以让答案不发生变化的物品，同时这样还可以减小总的体积。
4. 所以我们可以从大到小枚举答案，每次check一下，是否能够达到。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 10;
int v[N], w[N];
signed main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i] >> w[i];
    }
    int res;
   //枚举答案res
    for(res = 2000; res > 0; res --)
    {
       //体积最大为2000，我们用11个1来作为初始值（2^11 > 2000）
        int vsum = (1 << 11) - 1;
        for(int j = 1; j <= n; j ++)
        {
           //如果这个物品不改变答案，我们就选它
            if((w[j] & res) == res)
            {
                vsum &= v[j];
            }
        }
        if(vsum <= m)
        {
            break;
        }
    }
    cout << res << endl;
    return 0;
}

F 小苯的01背包（hard）

1. 本题的res 达到了1e^9, 所以我们不能直接枚举答案了，但是我们可以枚举答案的二进制位上的每一位是否为1。
2. 然后检测是否可行和E题相同。
3. 大佬的题解：

与运算, 选的越多, 价值越低, 但总体积也越小越可行
现在需要找到最大价值, 设其为ans
如果 value[1] & value[2] & ... = ans
那么 ans & value[i] = ans (ans在任意一位的1, 每个value在对应位上都有)

假设ans = 10110
那么只要第1位、第3位、第4位都为1, 那么这个物品对于这个答案来说就是可选的
而体积是选的越多越可行（越多体积越小）, 所以可以枚举答案
然后按"ans & value[i] = ans"这个条件,选出所有物品
计算出这些物品的总体积, 如果满足容量k限制, 则找到一个可行解 
对于E, 数据范围2e3, 可以直接从2000开始枚举答案

对于F, 数据范围1e9, 可以从高位开始, 用试填法, 逐位确定

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int v[N], w[N];
signed main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i] >> w[i];
    }
    int res = 0;
    for(int i = 30; i >= 0; i --)
    {
        //1e9 < 2 ^ 30
        int vsum = (1 << 30) - 1;
       //让第i位为1，试一下这个答案行不行
        int tryres = res | (1 << i);
        for(int j = 1; j <= n; j ++)
        {
            if((w[j] & tryres) == tryres)
            {
                vsum &= v[j];
            }
            if(vsum <= m)
            {
                res = tryres;
            }
        }
    }
    cout << res << endl;
    return 0;
}