Codeforces Round 889 (Div. 2) （C1~C2）-Toy模板网

这篇具有很好参考价值的文章主要介绍了Codeforces Round 889 (Div. 2) （C1~C2）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

掉大分，C1被sb错误困扰。
提示如果C1会了但不会C2,也应该先将C1解法看一遍

C1 Dual (Easy Version)

题意

给定长度为 $n$ 的数组 $a$ ，（ $n<=20，-20<=a_i<=20$ ），每次操作可以任选 $i, j$ ，使得 $a_i = a_i + a_j$ （ $i$ 可以等于 $j$ ）。问最多 $50$ 次操作以内如何将给定数组变成非降序。

思路

以下出现的 c1,c2等都代表执行操作的次数 c1代表执行一次，以此类推。
简单版本给了 $50$ 次操作机会理应是好想的，假如现在告诉你数组数字全都是非负数或者都是负数，是否能在 $19$ 次操作以内将其变成非降序。方法是很好想到的，如果全是正数就从前往后累加一遍，负数就从后往前累加一遍即可。

for(int i = 2; i <= n; i ++){ // 全是非负数累加一次 c19  c10 + c19 = c29
    ans.push_back({i, i - 1});
}
for(int i = n - 1; i >= 1; i --){ // 累加 c19   c12 + c19 = c31
    ans.push_back({i, i + 1});
}

那么现在问题变成如何将数组变成全部非负或全负，这个问题也很好实现，如果最小负数 $+$ 最大正数 $>= 0$ ，那么我们将所有负数加上最大正数不就可以了吗，反之亦然。这个操作的次数同样不会超过 $20$ 次。
$19 + 19 = 38 < 50$ 解法成立。
~~博主写题的时候犯蠢没想到这个，写了个有点麻烦的写法，还写错了找了一小时bug，真逆天。~~

解法较为简单，代码就不放了，想看的可以参考一下C2的代码。

C2 Dual (Hard Version)

题意

和C1唯一的区别是，要求操作数在 $31$ 次以内。

思路

思路继承自C1解法，使用了分类的讨论的方法，码量虽然有点大，但较为容易理解都是判断语句，并且在代码中有详细注释，直接看代码即可。文章来源地址https://www.toymoban.com/news/detail-617352.html

代码

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

#define ll long long
// const int N = 2e5 + 10;

int a[100];
struct node{
    int b, id;
    bool operator < (const node &A)const{
        return b < A.b; // 按大小排序
    }
}s[100];
void solve(){
    int n;
    cin >> n;
    int sum1 = 0, sum2 = 0; // 记录负数和正数的数量
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(a[i] < 0) sum1 ++;
        else sum2 ++;
        s[i] = {a[i], i};
    }
    sort(s + 1, s + 1 + n);
    

    if(sum1 == 0 && sum2 == 0){ // 全0
        cout << "0\n";
        return ;
    }   

    vector<pair<int, int>> ans;
    
    // 以下出现的 c1,c2等都代表执行操作的次数 c1代表执行一次，以此类推
    if(sum2 >= sum1){ // 正数数量 >= 负数
        if(s[1].b + s[n].b >= 0){ // 最小负数 + 最大正数 >= 0 那么先将负数变成非负 <= c10 
            for(int i = 1; i <= n; i ++){
                if(a[i] < 0) ans.push_back({i, s[n].id});
            }
            for(int i = 2; i <= n; i ++){ // 全是非负数累加一次 c19  c10 + c19 = c29
                ans.push_back({i, i - 1});
            }
        }
        else { // 最小负数 + 最大正数 < 0
            if(sum2 <= 12){
                for(int i = 1; i <= n; i ++){ // 将所有正数变成负数 <= c12
                    if(a[i] > 0) ans.push_back({i, s[1].id});
                }
                for(int i = n - 1; i >= 1; i --){ // 累加 c19   c12 + c19 = c31
                    ans.push_back({i, i + 1});
                }
            }
            else{ // 正数数量 >= 13 负数数量 <= 7
                for(int i = 1; i <= 5; i ++){ // 将最大的正数翻倍c5次 就算是1 5次后也等于 32  最小负数-20 相加为正数
                    ans.push_back({s[n].id, s[n].id});
                }
                for(int i = 1; i <= n; i ++){ // 将所有负数变成正数 <= c7
                    if(a[i] < 0) ans.push_back({i, s[n].id});
                }
                for(int i = 2; i <= n; i ++){
                    ans.push_back({i, i - 1}); // 累加 c19  c5 + c7 + c19 = c31
                }
            }
        }
    }
    else{ // 一样的思路
        if(s[1].b + s[n].b <= 0){ // 最小负数 + 最大正数 <= 0 那么先将正数变非正 <= c10 
            for(int i = 1; i <= n; i ++){
                if(a[i] > 0) ans.push_back({i, s[1].id});
            }
            for(int i = n - 1; i >= 1; i --){ // 全是非正数累加一次 c19  c10 + c19 = c29
                ans.push_back({i, i + 1});
            }
        }
        else { // 最小负数 + 最大正数 > 0
            if(sum1 <= 12){
                for(int i = 1; i <= n; i ++){ // 将所有负数变成正数 <= c12
                    if(a[i] < 0) ans.push_back({i, s[n].id});
                }
                for(int i = 2; i <= n; i ++){ // 累加 c19   c12 + c19 = c31
                    ans.push_back({i, i - 1});
                }
            }
            else{ // 负数数量 >= 13 正数数量 <= 7
                for(int i = 1; i <= 5; i ++){ // 将最小的负数翻倍c5次 就算是-1 5次后也等于 -32  最大正数20 相加为负数
                    ans.push_back({s[1].id, s[1].id});
                }
                for(int i = 1; i <= n; i ++){ // 将所有正数变成负数 <= c7
                    if(a[i] > 0) ans.push_back({i, s[1].id});
                }
                for(int i = n - 1; i >= 1; i --){
                    ans.push_back({i, i + 1}); // 累加 c19  c5 + c7 + c19 = c31
                }
            }
        }
    }
    
    cout << (int)ans.size() << "\n";
    for(auto [i, j] : ans){
        cout << i << " " << j << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}