题目1

题目链接
题目大意：
在一个国际象棋的棋盘上，有一个棋子，它的移动规则类似马，能够朝着横or竖方向移动距离a，然后朝竖or横（和之前不同）移动距离b；
比如说马的移动规则就是a=1，b=2；

现在棋盘上还有另外两个棋子K和Q，问棋盘上有多少个特殊位置，在该位置上面可以移动棋子K所在位置，也可以移动到棋子Q所在位置。

如下，该图上面的马，可以移动到另外两个棋子的位置。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例3行
第1行整数 𝑎 and 𝑏 (1≤𝑎,𝑏≤1e8)
第2行整数 𝑥𝐾 and 𝑦𝐾 (0≤𝑥𝐾,𝑦𝐾≤1e8 )
第3行整数 𝑥𝑄 and 𝑦𝑄 (0≤𝑥𝑄,𝑦𝑄≤1e8 )

输出：
每个样例一行，输出满足要求的位置数量。

Examples
input
4
2 1
0 0
3 3
1 1
3 1
1 3
4 4
0 0
8 0
4 2
1 4
3 4

output
2
1
2
0

题目解析：
能够攻击到k的位置，应该有左右上下8个角落；
同理，能够攻击到q的位置，也同样有8个角落；
接下来枚举前面的位置，看是否有位置与后面的角落重合，即可。

tips：
1、为了方便枚举，可以把4个方向用dir[4][2]的数组来枚举；
2、a和b不相同的时候，要考虑a和b互换的情况；

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    int dir[4][2] = {1,1,  -1,1,  1,-1,   -1,-1};
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int val[2], x1, y1, x2, y2;
            cin >> val[0] >> val[1];
            cin >> x1 >> y1;
            cin >> x2 >> y2;
            int ans = 0;
            for (int i = 0; i < 8; ++i) {
                int a = val[i % 2];
                int b = val[(i + 1) % 2];
                if (a == b && i % 2) continue;;
                int idx1 = dir[i/2][0] * a + x1;
                int idy1 = dir[i/2][1] * b + y1;
                for (int j = 0; j < 8; ++j) {
                    int a2 = val[j % 2];
                    int b2 = val[(j + 1) % 2];
                    if (a2 == b2 && j % 2) continue;;
                    if ((idx1 + dir[j/2][0] * a2 == x2) && (idy1 + dir[j/2][1] * b2 == y2)) {
                        ++ans;
                        break;
                    }
                }
            }
            cout << ans << endl;
        }
    }
}
ac;

题目2

题目链接
题目大意：
有n个元素的整数数组a，现在进行以下操作：
1、选择某个元素a[i]，移除当前元素a[i]，获得初始分数score=a[i]；
2、寻找某个元素a[j]，并且满足score>=a[j]，可以移除元素a[j]，同时使得分数score增加a[j]；
3、不断重复操作2，直到无法执行；

现在想知道，每个元素被作为初始元素时，最多能够移除的元素数量；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤5000)
每个样例2行
第1行整数 𝑛 (1≤𝑛≤1e5 )
第2行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)

输出：
每个样例一行，每行n个整数，第i个数字，表示当第i个元素作为初始元素时，能够移除的最多元素数量。（也就是操作2的最多执行次数）

Examples
input
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000

output
4 3 0 3 1
1 0 2
0
4 4 4 4 4

题目解析：
将整数数组进行从大到小排序，接着下来再考虑如何决策；
由于题目的规则很像“大鱼吃小鱼”，可以从数字较小者开始，也就是从右到左：
1、最小的元素，除非和倒数第二个相同，否则无法吃下任何数字；
2、从倒数第二个数字开始，每次可以直接累加右边所有的数字，然后如果数字和大于等于左边的数字，就可以一直累加，然后左移一位，直到无法移动；
此时，该段区间内的所有数字，最终的数字和都是一样的；
3、重复上面的过程，直到将整个数组分为若干段；
比如说[20, 5,4,2,1]就可以分为[20],[5,4], [2], [1]，划分规则就是每次从右到左累加和，小于左边一个数字。

类似的思考过程，假设我们排序之后是从左到右去思考，还是以[20, 5,4,2,1]为例子。
当处理数字20时，按照规则，右边所有数字都能吃掉，ans[0]=4；
当处理数字5时，如果5左边所有数字累加和大于20，那么就可以吃掉20，此时结果ans[1]=ans[0]; 但是5左边累加数字和，结果是12，那么此时结果就是3；
因为数组比较长，右边和可以先计算整个数组和sum，然后不断累积减去当前数字。

typedef long long lld;
 
class Solution {
    static const int N = 101010;
    pair<int, int> a[N];
    int ans[N];
    static bool cmp(pair<int, int> x, pair<int, int> y) {
        return x.first > y.first;
    }
    
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            lld sum = 0;
            for (int i = 0; i < n; ++i) {
                cin >> a[i].first;
                a[i].second = i;
                sum += a[i].first;
            }
            sort(a, a + n, cmp);
            for (int i = 0; i < n; ++i) {
                sum -= a[i].first;
                if (i == 0) {
                    ans[a[i].second] = n - i - 1;
                }
                else {
                    if (sum + a[i].first >= a[i - 1].first) {
                        ans[a[i].second] = ans[a[i - 1].second];
                    }
                    else {
                        ans[a[i].second] = n - i - 1;
                    }
                }
            }
            for (int i = 0; i < n; ++i) cout << ans[i] << " ";
            cout << endl;
        }
    }
}
ac;

题目3

题目链接
题目大意：
有n个整数的数组a，现在可以进行下面的操作：
选择数组中任意两个元素，将两个元素差值的绝对值，插入到数组中的最后面；

现在可以进行上面的操作k次，要求让数组中的最小值在操作之后，尽可能的小；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例2行
第1行整数𝑛 and 𝑘 (2≤𝑛≤2⋅1e3 , 1≤𝑘≤1e9 )
第2行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e18)

输出：
每个样例一行，输出操作后的最小值。

Examples
input
4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000

output
1
0
3
500000000000000000

题目解析：
数组a都是大于1的值，那么最终的结果必然是大于等于0；
当n=2的时候，如果a1=a2，那么结果就是0；
如果a1!=a2，那么|a1-a2|必然会产生一个新的数字，以[4, 2]为例：
4 2
4 2 2
4 2 2 0

但是，当a1和a2差距较大时，我们有：
10 2
10 2 8
10 2 8 2
10 2 8 2 0

也就是当操作次数没有限制时，我们必然能够产生0，比如说：
c=b-a；
d=b-c=(b-(b-a))=a;
这样数组[a, b, c, d]，只需要选择a-d=a-a=0；
只要k>=3，必然可以得到0。

当k==1时，直接枚举两两想减的情况，得到结果；
当k==2时，我们枚举数组两两想减，得到新的数字，假设是数组b；
这样我们就有[a1, a2, a3... an] 和 [b1, b2, b3...bn]两个数组；
这样只需要再枚举数组a和数组b相减，得到数组c；
最小值就是数组a、b、c中的最小值。

这样的复杂度，首先是数组b的生成，O(N^2)，最多会生成1e6个数字；
最后再枚举生成c的时候，复杂度就达到了O(N^3），最终复杂度超标。

重新审视问题分析过程，当k==1时，其实不需要所有数字两两相减，举一个例子：
当数组为[9,7,5,1]，当枚举9与其他数字的差值时，只需要考虑[9,7]的情况，也就是整个数组其实只需要考虑3个情况[9, 7] 、[7,5]、[5,1]；
这里的前提，是数组是有序的。可以对数组进行排序，复杂度是O(NlogN），接下来枚举复杂度就是O(N）；
但是，当k==2时，是否可以继续只考虑相邻数字呢？
是不可以的，因为相邻数字想减，生成的只是当前最小，不意味着再一次操作的更小，比如说[9,7,5,4]，第一次无法生成9-5=4，那么第二次操作就无法归零。
所以首次操作，需要生成N^2个数字的数字b；
在第二次操作的时候，我们会从数组a选择1个数字，再从数组b选择1个数字，此时可以参考k=1的时候的做法，将数组b排序，对于每个数字a[i]，我们只需要考虑数组b中离a[i]数字最接近的数字。
此时可以用二分法，在数组b中寻找。但是我们有更简单的做法：
将数组a和数组b一起排序，然后对于a[i]，我们就往左右遍历，这样就能更方便去找到数字。

typedef long long lld;

class Solution {
   static const int N = 4010100;
   lld a[N];
   pair<lld, lld> b[N];
   
public:
   void solve() {
       int t;
       cin >> t;
       while (t--) {
           int n, k;
           cin >> n >> k;
           
           for (int i = 0; i < n; ++i) cin >> a[i];
           sort(a, a + n);
           
           if (k >= 3) {
               cout << 0 << endl;
           }
           else if (k == 2) {
               int cnt = 0;
               for (int i = 0; i < n; ++i) {
                   b[cnt].first = a[i];
                   b[cnt].second = 0;
                   cnt++;
               }
               
               for (int i = 0; i < n; ++i) {
                   for (int j = i + 1; j < n; ++j) {
                       b[cnt].first = abs(a[i] - a[j]);
                       b[cnt].second = 1;
                       ++cnt;
                   }
               }
               
               sort(b, b + cnt);
               
               lld ans = a[0];
               for (int i = 0; i < cnt; ++i) {
                   ans = min(ans, b[i].first);
                   if (b[i].second == 0) { // 数组a来匹配最近的一个数字
                       int x = i, y = i;
                       while (x > 0) {
                           --x;
                           if (b[x].second == 1) break;
                       }
                       
                       while (y < cnt - 1) {
                           ++y;
                           if (b[y].second == 1) break;
                       }
                       if (x != i) {
                           ans = min(ans, abs(b[i].first - b[x].first));
                       }
                       if (y != i) {
                           ans = min(ans, abs(b[i].first - b[y].first));
                       }
                   }
               }
               
               cout << ans << endl;
           }
           else if (k == 1) {
               lld ans = a[0];
               for (int i = 1; i < n; ++i) ans = min(ans, min(a[i], a[i] - a[i - 1]));
               cout << ans << endl;
           }
       }
   }
}
ac;

题目4

题目链接
题目大意：
给出n个整数的数组a和b，现在可以对数组a进行操作：
选择数组内任意区间[l, r]，将区间[l, r]内的整数都改为区间的最大值。
比如，对于数组[1, 2, 3, 4, 5]，选择区间[1, 3]进行操作，则会生成[3, 3, 3, 4, 5]；

现在想知道，数组a是否可以进行若干次上面的操作，最终变成数组b。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例3行
第1行整数 n (1≤n≤1000)
第2行整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛)
第3行整数 𝑏1,𝑏2,…,𝑏𝑛 (1≤𝑏𝑖≤𝑛)

输出：
每个样例一行，如果可行则输出YES，如果不可行则输出NO；

Examples
input
5
5
1 2 3 2 4
1 3 3 2 4
5
3 4 2 2 4
3 4 3 4 4
5
3 2 1 1 1
3 3 3 2 2
2
1 1
1 2
3
1 1 2
2 1 2

output
YES
NO
YES
NO
NO

题目解析：
从数据量较小的情况开始分析，比如说n=2时，数组数字可以简化成1和2；
那么就会有[1,2]和[2,2]，比较容易得到结果；
当n=3时，我们增加个数组3，如果放在数组[1,2]左右两边，对结果不影响；但是如果放在中间，数组[1, 3, 2]是无法变成[2, 3, 2]；
由此我们可以知道，较大的数字会阻断较小的数字传递；
当n=4时，我们可以看到一个有意思的样例：
1,2,3,4
3,4,4,4
数字3，跨过第2个数字影响到了第1个数字，然后第2、3个数字最终又被数字4覆盖。
由此我们可以知道，数字的影响是最终可能非间隔，但是必须传递过去，并且中间路径可能被更大数字覆盖。

至此，我们的思路就清晰起来：
1、从小到大来枚举数字，因为当x覆盖过某个数字后，只有x+1才能覆盖这个覆盖；
2、每一个数字，都可以向左右蔓延，蔓延条件有两个，隔壁数字小于等于当前数字，隔壁数字对应的数组b元素要大于等于当前数字；
3、重复上面所有的过程，直到所有数字结束；

这里的核心依据，就是通过数组b的元素作为数组a元素的上限，尽可能让每一个数组a元素去变大。

思考：
当N的范围再扩大1000倍呢？上面的这个做法在效率上就会不足，但是思路可以沿用扩展。
首先回顾这里的耗时操作，首先是枚举数字从小到大，然后找到和这个位置对应的数字，简单实现是O（N^2）的复杂度，但是我们先预处理一遍数组，记录每个数字对应的下标，这样就可以做到O（N）的复杂度；
其次是在数字覆盖的过程中，有时会出现每个位置被重复覆盖多次的情况，但是对于结果而言，我们只需要知道某个位置不匹配时（a[i] != b[i]），它应该往数组a左边/右边去找到等于b[i]的元素。
这个过程，同样可以预处理。
比如说对于下面的样例，当a[3] != b[3]，我们要往数组a两边去找数组元素等于3的情况；
3 3 2 1 4 3 3
3 3 3 3 4 3 3
首先在前面的预处理步骤，我们记录每一个数字的位置，那么对于数字3，我们同样记录了3在数组a的位置为[0,1,5,6]，这样我们很容易知道对于a[3]而言，最近数字3位置在a[1]和a[5]；

接下来的问题是，对于某个位置i和某个位置j，是否能够匹配？
还是用上面的样例，我们才用采样这样的策略：
1、对于数组a，我们从小到大枚举的元素的过程，我们把枚举过的数字（包括当前数字），在数组a出现的位置都用1来标明；（某个位置为1，表示该位置可以延伸）
2、对于数组b，我们从小到大枚举的元素的过程，我们把还没有枚举过的数字（包括当前数字），在数组b出现的位置都用1来标明；（某个位置为1，表示该位置可以延伸）
样例数据
3 3 2 1 4 3 3
3 3 3 3 4 3 3
就可以转义为
1 1 1 1 0 1 1
1 1 1 1 1 1 1
这样， 当我们在判断a[1]和a[3]是否能够匹配时，其实就是判断数组a区间[1, 3]的数字和是否为3，并且数组b区间[1,3]的数字和是否为3；

那么如何做快速的标记、以及计算累加和呢？
1、标记问题，通过预处理我们能O(1)获取对应位置，并且每个数字我们只会标记一次，所以总的标记复杂度是O(N)；
2、计算累加和，在一个数组里面，可以对某些元素进行数值修改、然后要求区间和，可以用线段树来解决。

class Solution {
    static const int N = 201010;
    int a[N], b[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; ++i) cin >> a[i];
            for (int i = 0; i < n; ++i) cin >> b[i];
            for (int k = 1; k <= n; ++k) {
                for (int i = 0; i < n; ++i) {
                    if (a[i] == k) {
                        int x = i - 1, y = i + 1;
                        while (x >= 0 && a[x] <= k && k <= b[x]) {
                            a[x] = k;
                            --x;
                        }
                        while (y < n && a[y] <= k && k <= b[y]) {
                            a[y] = k;
                            ++y;
                        }
                    }
                }
            }
            int ans = 1;
            for (int i = 0; i < n; ++i) ans = ans && (a[i] == b[i]);
            cout << (ans ? "YES" : "NO") << endl;
        }
    }
}
ac;

题目5

题目链接
题目大意：
有n个正整数的数组a，现在Alice和Bob在玩游戏，Alice先操作，Bob再操作；
Alice会移除数组中，最多k个元素；
Bob会将数组中，最多x个元素乘以-1；

每个人只行动一次，Alice想要让最终数组的元素和尽可能大，Bob想要让数组的元素和尽可能小；
问最终的数字和为多少；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例2行
第一行，整数𝑛 , 𝑘 , and 𝑥 (1≤𝑛≤2⋅1e5 , 1≤𝑥,𝑘≤𝑛 )
第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1000)

输出：
每个样例一行，输出最终的数字和；

Examples
input
8
1 1 1
1
4 1 1
3 1 2 4
6 6 3
1 4 3 2 5 6
6 6 1
3 7 3 3 32 15
8 5 3
5 5 3 3 3 2 9 9
10 6 4
1 8 2 9 3 3 4 5 3 200
2 2 1
4 3
2 1 2
1 3

output
0
2
0
3
-5
-9
0
-1

题目解析：
由于题目有k和x两个变量，我们先考虑x=1个数字的情况；
假设题目数据已经从大到小排序，数组还是a，以4、3、2、1为例；
先考虑bob的操作（为什么是先考虑后手？因为这样思考简单）
假设Alice没有操作，那bob一定会选择-4，也就是数组最大的元素；（如果x=2，那么就是前2个）

那么Alice如果操作呢？
移除4的好处是最终消除了-4，但是增加了-3，同时移除原来正数3，总体的代价应该是4-3-3=-2，所以Alice不操作结果更佳；

由此可知道数组排序后，Alice如果移除，一定是移除前面若干个数字；Bob的负数操作，也一定是前面x个数字。
那么只需要枚举下k=0、1、2、3、、、k的情况，对应的结果。（边界情况比较容易些错，可以直接模拟，简化过程）

注意：
一些特殊case
k=2, x=2
4+3+2+1
-4-3+2+1=-4
-3-2+1=-4
-2-1=-3

k=2, x=2
6+6+3.5+1
-6-6-+4.5=-7.5
-3.5-1=-4.5

typedef long long lld;
 
class Solution {
    static const int N = 201010;
    lld a[N], sum[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k, x;
            cin >> n >> k >> x;
            for (int i = 0; i < n; ++i) cin >> a[i];
            sort(a, a + n, greater<int>());
            sum[0] = a[0];
            // [left, mid, right]
            // left是移除，mid是负数，right是剩下
            lld leftSum = 0, midSum = 0, rightSum = 0;
            for (int i = 0; i < x; ++i) midSum += a[i];
            for (int i = x; i < n; ++i) rightSum += a[i];
            lld ans = rightSum - midSum;
            for (int remove = 1; remove <= k; ++remove) {
                midSum -= a[remove - 1]; //移除当前这个数字
                if (remove + x <= n) {
                    // 右边还有剩余
                    midSum += a[remove + x - 1]; // midSum增加这个数字
                    rightSum -= a[remove + x - 1]; // rightSum移除这个数字
                }
                ans = max(ans, rightSum - midSum);
            }
            cout << ans << endl;
        }
    }
}
ac;