题解 | #牛客小白月赛87——苯环场#

前言：

这次总体难度偏低
多谢苯环gg的手下留情

A-小苯的石子游戏

思路：

如果 $n$ 为奇数的话，一定是先手赢
数组为升序排列，所以最优解一定是从后往前取数字
所以 $Bob$ 赢只能是在 $Alice$ 和 $Bob$ 取的数之和相等
- 如果 $n$ 为偶数的话，数字两两相等，那么一定是后手赢（先手和后手的和相等）

以下是代码部分

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

typedef long long ll;
const int N = 1e2 + 10;
int a[N];
//检查数是否两两相等
bool check(int n)
{
    for(int i = 2; i <= n; i += 2)
        if(a[i] != a[i - 1])
            return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        for(int i = 1; i <= n; i ++) cin >> a[i];
      //如果n为奇数
        if(n & 1) cout << "Alice\n";
        else
        {
          //检查
            if(check(n))
                cout << "Bob\n";
            else
                cout << "Alice\n";
        }
            
    }
    return 0;
}

B-小苯的排序疑惑

思路：

只有当最小值不在第一位并且最大值不在最后位时，才输出NO
否则输出YES

以下是代码部分

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

const int N = 2e5 + 10;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        int minx = INT_MAX, maxn = INT_MIN;
        for(int i = 1; i <= n; i ++)
            cin >> a[i];
      //找到数组中的最大值和最小值
        for(int i = 2; i <= n; i ++)
            minx = min(a[i], minx);
        for(int i = 1; i < n; i ++)
            maxn = max(a[i], maxn);
      //判断
        if(a[1] > minx && a[n] < maxn)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
    return 0;
}

C & D-小苯的IDE括号问题

直接发hard版本的得了。

思路：

模拟
注意不要数组越界

以下是代码部分 （string），这是菜鸟的代码

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

string s;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, pos;
    cin >> n >> k >> s;
  //找到光标的初始位置
    for(int i = 0; i < n; i ++)
        if(s[i] == 'I')
            pos = i;
    while(k --)
    {
        string op;
        cin >> op;
      //操作
        if(op == "backspace")
        {
          //如果不在边界， 分两种情况讨论
            if(pos > 0 && pos < s.length() - 1)
            {
                if(s[pos - 1] == '(' && s[pos + 1] == ')')
                    s.erase(pos + 1, 1), s.erase(pos - 1, 1);
                else
                    s.erase(pos - 1, 1);
                pos --;
            }
          //如果在边界
            else if(pos > 0)
            {
                s.erase(pos - 1, 1);
                pos --;
            }
        }
      //操作
        else if(op == "delete")
        {
            if(s.length() - 1 > pos)
                s.erase(pos + 1, 1);
        }
      //操作
        else if(op == "<-")
        {
            if(pos > 0)
            {
                s.erase(pos, 1);
                pos --;
                s.insert(s.begin() + pos, 'I');
            }
        }
      //操作
        else if(op == "->")
        {
            if(pos < s.length() - 1)
            {
                s.erase(pos, 1);
                pos ++;
                s.insert(s.begin() + pos, 'I');
            }
                
        }
    }
    cout << s << '\n';

    return 0;
}

以下是代码部分 （栈），代码参考来源——苯环大佬的代码

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

void solve()
{
    string s;
    int n, q;
    cin >> n >> q >> s;
    int pos = (int)s.find('I');
    vector<char> a, b;
    //光标之前的部分
    for(int i = 0; i < pos; i ++)
        a.emplace_back(s[i]);
    //光标之后的部分
    for(int i = pos + 1; i < n; i ++)
        b.emplace_back(s[i]);
    //反转b,方便操作
    reverse(b.begin(), b.end());
    while(q --)
    {
        string op;
        cin >> op;
        if(op == "delete")
        {
            //如果光标后半部分存在，直接删除即可
            if((int)b.size()) b.pop_back();
        }
        else if(op == "backspace")
        {
            //如果光标前半部分存在
            if((int)a.size())
            {
                //如果光标在一个括号内部，需要删除后半部分
                if(a.back() == '(' && (int)b.size() && b.back() == ')')
                    b.pop_back();
                //删除前半部分
                a.pop_back();
            }
        }
        else if(op == "<-")
        {
            //如果前半部分存在
            if((int)a.size())
            {
                b.emplace_back(a.back());
                a.pop_back();
            }
        }
        else
        {
            //如果后半部分存在
            if((int)b.size())
            {
                a.emplace_back(b.back());
                b.pop_back();
            }
        }
    }
    //输出前半部分
    for(char i : a)
        cout << i;
    //输出光标
    cout << 'I';
    //输出后半部分
    for(int i = (int)b.size() - 1; ~i; i --)
        cout << b[i];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();

    return 0;
}

E-小苯的数组构造

思路：

要得到一条非降数组并且要满足 $b$ 的极差最小。
- 易得，只需要做到非降序数组尽量不升序即可

以下是代码部分

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

typedef long long ll;
const int N = 2e5 + 10;
ll a[N], b[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 2; i <= n; i ++)
    {
        if(a[i] < a[i - 1])
        {
            b[i] = a[i - 1] - a[i];
          //一定要注意更新a的值
            a[i] = a[i - 1];
        }
    }
    for(int i = 1; i <= n; i ++)
        cout << b[i] << " \n"[i == n];

    return 0;
}

F-小苯的数组切分

注意事项：

淦，又忘记开 $long$ $long$ 了。

思路：

$and$ 运算一定是越多，数值越小的趋势，而 $and$ 运算和 $or$ 贴近，所以 $and$ 只占最后一位即可
对于 $xor$ 和 $or$ ，可以通过枚举进行判断应取什么边界

以下是代码部分，代码参考来源——bilibili官方讲解

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

const int N = 2e5 + 10;
typedef long long ll;
ll a[N], pre[N], suf[N];

void solve()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
  //前缀异或
    for(int i = 1; i <= n; i ++)
        pre[i] = pre[i - 1] ^ a[i];
  //后缀异或
    for(int i = n - 1; i >= 1; i --)
        suf[i] = suf[i + 1] | a[i];
    ll ans = 0;
  //比较，取最大
    for(int i = 1; i <= n - 2; i ++)
        ans = max(ans, pre[i] + suf[i + 1] + a[n]);
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();

    return 0;
}

G-小苯的逆序对

思路：

求逆序对数
- 树状数组求逆序对
- 类似于前缀和，但树状数组修改更快
  - 每次添加一个数，查询小于这个数的且在这个数排列之前的个数
求互质数
- bilibili炸鸡君视频讲解
两者结合

以下是代码部分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=2e5 + 10;
int n, a[N], c[N];
ll dp[N];
//求二进制下最低位的1
int lowbit(int x){return x & -x;}
//加入到树状数组中
void add(int u,int v)
{
    while(u)
    {
        c[u] += v;
        u-= lowbit(u);
    }
}
//查询逆序数
int ask(int u)
{
    int res = 0;
    while(u <= n)
    {
        res += c[u];
        u += lowbit(u);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int tem;
        cin >> tem;
        //根据大小排列，并记录原位置
        a[tem] = i;
    }
    //逆向遍历
    for(int i = n; i >= 1; i --)
    {
        //j代表i的倍数
        //计算逆序数
        for(int j = i; j <= n; j += i)
        {
          //加上j这个位置的逆序数
            dp[i] += ask(a[j]);
            //把j位置上的数加入到树状数组当中
            add(a[j],1);
        }
        for(int j = i; j <= n; j += i)
        {
            //减去除本身倍数以外的数之和即可，鸡哥在bilibili讲了。
            add(a[j], -1);
            if(j != i)
                dp[i] -= dp[j];
        }
    }
    //gcd(a, b) == 1时，且是逆序的个数
    cout << dp[1] << endl;
    return 0;
}