写在前面

俗话事出反常必有妖
那究竟是什么让一个 杂文博主 突然开始更新 OI题解
这究竟是这究竟是道德的沦丧，还是人性的扭曲
敬请关注 今晚23点59分 CCAV5年度巨献 《OIer的不归之路》

真心话：
虽然OI对升学确实有作用，但是太卷了..京爷沪爷从小就开始卷OI了
至于我这种把OI当成救命稻草的普通人 不当做题狗真的看不到任何希望...
还是上题解罢

详细题解

A. Satisfying Constraints

大意分析

这题题目倒是不怎么绕，直接把需要求的东西给出来了，是一道 关于约束条件满足 的题目，需要 找出满足所有约束的整数k的数量
这里题中给出了三种类型的约束：
1.k必须大于或等于某个整数x
2.k必须小于或等于某个整数x
3.k不能等于某个整数x
题目看懂了，直接开始理思路解题

解题思路

这种题目嘛..翻译题，把题目中给定的约束条件从 文字 翻译成 代码 就行了
解题思想有点像 贪心算法 （最近贪心做多了，看什么都像贪心）
可以先初始化一个 最小的lower 和一个 最大的upper ，分别表示k的下界和上界
然后遍历 所有 约束（满足题目中的三个条件，翻译嘛，简单嘞）
根据约束类型更新 lower 和 upper
最后统计所有满足约束3 （k不能等于某个整数x） 的整数的数量，并从可能的k的总数中减去这个数量，AC！

代码分析

1.读入测试用例的数量t，然后对每个测试用例进行处理

int t;
scanf("%d", &t);
while(t--) {

2.读入约束数量n，初始化lower、upper和not_equal

int n;
scanf("%d", &n);
int lower = INT_MIN, upper = INT_MAX, cnt = 0;
vector<int> not_equal;

3.遍历所有约束，读入约束类型a和整数x

while(n--) {
    int a, x;
    scanf("%d%d", &a, &x);
}

4.判断，如a=1，更新lower；如a=2，更新upper；如a=3，将x添加到not_equal中

while(n--) {
    if(a == 1) lower = max(lower, x);
    else if(a == 2) upper = min(upper, x);
    else not_equal.push_back(x);
}

5.遍历not_equal，统计所有在lower和upper之间整数的数量

for(int i = 0; i < not_equal.size(); i++)
    if(not_equal[i] >= lower && not_equal[i] <= upper) cnt++;

6.计算满足所有约束的k的数量，输出结果

int ans = max(0, upper - lower + 1 - cnt);
printf("%d\n", ans);

关键步骤复盘

1.读题，明白这题是要把题目中给定的约束条件从 文字 翻译成 代码 。对于 约束1和约束2 ，需要找到所有可能的k的范围；对于 约束3 ，需要找到所有不能作为k的整数。
2.使用 贪心算法 （可能吧，我不确定），通过不断更新 lower 和 upper 来找到 所有可能的k的范围 。

3. 使用vector来存储所有不能作为k的整数 ，然后在计算结果时减去这些整数的数量。
   4.使用 max函数 来保证结果 不会是负数 。如所有约束都不能被满足，那么 upper - lower + 1 - cnt 会是负数。

B. Summation Game

大意分析

这种策略题目最生草了，Alice和Bob在 打电动 ，他们有一个数组
这个电动游戏 有两个步骤 :

1. Alice 最多可以从数组中 移除k个元素 ，Alice的目标为 最大化数组元素的和
2. Bob 最多可以将数组中的 x个元素乘以-1 ，Bob的目标为 最小化数组元素的和
   需要找出如果两个玩家 都采取最优策略 ，游戏结束后 数组元素的和

解题思路

这题的关键在于理解Alice和Bob如何 优雅 最优 地进行他们的操作
Alice会尽可能地 移除最大的元素 ，而Bob会尽可能地 将最大的元素乘以-1 （重要的事情说两遍）
所以这题我们可以 先对数组进行排序 ，然后让Alice和Bob 开始他们的 花活 操作

代码分析

1.读入测试用例的数量t，然后对每个测试用例进行处理

int main() {
    int t;
    scanf("%d", &t);
    while(t--) solve();
    return 0;
}

2.在solve函数中，读入n, k, x，然后读入数组v，对其进行降序排序

void solve() {
    ll n, k, x;
    scanf("%lld %lld %lld", &n, &k, &x);
    vector<ll> v(n);
    for(int i=0; i<n; i++) scanf("%lld", &v[i]);
    sort(v.begin(), v.end(), greater<ll>());

3.计算Bob最多可以乘以-1的元素的和xsum，剩余元素的和sum

    ll xsum = 0;
    for(int i=0; i<x && i<n; i++) xsum += v[i];

    ll sum = accumulate(v.begin(), v.end(), 0LL) - xsum;

4.初始化答案ans为sum - xsum

    ll ans = sum - xsum;

5.尝试将数组中的每一个元素从sum中移除，加入到xsum中

    ll j=0, count = 0;

    for(int i=x; i<n; i++) {
        sum -= v[i];
        xsum += v[i];
        xsum -= v[j++];
        count++;
    }

6.更新答案ans，如果移除的元素数量达到了k，直接break

    for(int i=x; i<n; i++) {
        ans = max(ans, sum - xsum);
        if (count == k) break;
    }

7.如移除的元素数量没有达到k，继续移除、更新直到k

    ll index = count;
    if(count < k) {
        for(int i=index; i<n; i++) {
            xsum -= v[i];
            ans = max(ans, -xsum);
            count++;
            if(count == k) break;
        }
    }

8.如k等于n，那么答案ans直接返回0

    if(k == n) ans = max(ans, 0LL);

9.输出答案ans

    printf("%lld\n", ans);
}

关键步骤复盘

1.理解Alice和Bob的最优策略，及如何实现策略
2.对数组进行排序，模拟Alice和Bob的操作
3.模拟的过程中需要注意答案需要保存，而元素需要移除
4.做的时候还给我弹了个公告 The game ends after one Alice's move and one Bob's move. 虽然当时弹完了我也没搞明白这题是啥意思，好像这个公告有用，又好像没用

完整代码

就知道你们喜欢这个

A. Satisfying Constraints

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

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        int lower = INT_MIN, upper = INT_MAX, cnt = 0;
        vector<int> not_equal;
        while(n--) {
            int a, x;
            scanf("%d%d", &a, &x);
            if(a == 1) lower = max(lower, x);
            else if(a == 2) upper = min(upper, x);
            else not_equal.push_back(x);
        }
        for(int i = 0; i < not_equal.size(); i++)
            if(not_equal[i] >= lower && not_equal[i] <= upper) cnt++;
        int ans = max(0, upper - lower + 1 - cnt);
        printf("%d\n", ans);
    }
    return 0;
}

B. Summation Game

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

typedef long long ll;

void solve() {
    ll n, k, x;
    scanf("%lld %lld %lld", &n, &k, &x);
    vector<ll> v(n);
    for(int i=0; i<n; i++) scanf("%lld", &v[i]);
    sort(v.begin(), v.end(), greater<ll>());

    ll xsum = 0;
    for(int i=0; i<x && i<n; i++) xsum += v[i];

    ll sum = accumulate(v.begin(), v.end(), 0LL) - xsum;
    ll ans = sum - xsum;
    ll j=0, count = 0;

    for(int i=x; i<n; i++) {
        sum -= v[i];
        xsum += v[i];
        xsum -= v[j++];
        count++;
        ans = max(ans, sum - xsum);
        if (count == k) break;
    }

    ll index = count;
    if(count < k) {
        for(int i=index; i<n; i++) {
            xsum -= v[i];
            ans = max(ans, -xsum);
            count++;
            if(count == k) break;
        }
    }

    if(k == n) ans = max(ans, 0LL);

    printf("%lld\n", ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) solve();
    return 0;
}

写在最后

虽然俩小时只做出来两题第三题实在借不出来了，但是本蒟蒻已经很努力了 Orz
以后得猛干题目了 再摆下去要被大佬卷死了
附上当时比赛的提交记录和排名，见证每一次进步