Dual (Easy & Hard Version)

前往 算竞题解 分类 || 前往 算竞模板 分类

原题链接

C2-Dual (Hard Version) Codeforces Round 889 (Div. 2)

最喜欢这种什么算法都没有的构造题。

简明题意

给定 nn 个数 aia_i，你可以进行不超过 kk 次操作，使得最终 aa 是非降序的。每次操作任选两个数使得 ai+=aja_i += a_j。

Easy Version：1≤n≤201 \le n \le 20，−20≤ai≤20-20 \le a_i \le 20，k=50k = 50。

Hard Version：1≤n≤201 \le n \le 20，−20≤ai≤20-20 \le a_i \le 20，k=31k = 31。

解题思路

Easy Version 的解法很多就不介绍了，我直接出的 Hard Version 的思路。

首先我们考虑使用 前缀和 操作，因为不使用前缀和会发现问题变得非常棘手，我们很难讨论序列之间的复杂状态。如果最后一步使用前缀和，我们只需要保证在最后一步之前所有数都是非负数或者非正数（对应后缀和）。前缀和的代价是 n−1n-1。

其次我们先 考虑全部变为非负数的方式 ，因为全部变为非负和全部变为非正是相反的操作，所以先考虑一边即可。

那么问题转化为如何 在剩余代价内将所有数转化为非负数 。假设我们对于序列 aa 求出最大正数的绝对值 max+max_+，正数的个数 cnt+cnt_+，最大负数的绝对值 max−max_-，负数的个数 cnt−cnt_-。那么很直观的想法就是让所有负数加上 max+max_+ 直到变为非负数，但是当 max+=1max_+=1 而 max−=20max_-=20 时，这样做的代价是 2020。这里需要观察到 aia_i 是可以做自加的，这相当于一个倍增的过程，那么首先让 max+max_+ 倍增到大于等于 max−max_-，再进行后面的操作。计算总代价为 n−1+⌈log⁡2max−max+⌉+cnt−n-1 + \lceil\log_2{\frac{max_-}{max_+}}\rceil + cnt_- ，这样做的最大代价为 4343，显然问题还没有结束。

我们之前讨论的是考虑将全部数变为非负数，那么相应的，我们还可以选择 将全部变为非正数的方式 ，然后做一次后缀和。总代价为 n−1+⌈log⁡2max+max−⌉+cnt+n-1 + \lceil\log_2{\frac{max_+}{max_-}}\rceil + cnt_+。这其实也是一个很直观的想法，但是我们如何对这两种方案做出决策呢？如果卡在这里那实在是太可惜了，事实上我们可以将两个方案都进行计算，将决策交给程序进行（一个简单的 if−elseif-else 语句而已）。拿到这个方案我也并不确定是否符合题目条件，但是后面我们将 证明 。

最后还剩下一些上面的解法可能无法解决的一些小问题需要解决：如果全为 00，不需要进行任何操作；如果只有非负数，直接进行一次前缀和；如果只有非正数，直接进行一次后缀和。

正确性证明

现在我们要证明：

min(n−1+⌈log⁡2max−max+⌉+cnt−,    n−1+⌈log⁡2max+max−⌉+cnt+)≤31min(n-1 + \lceil\log_2{\frac{max_-}{max_+}}\rceil + cnt_-,~~~~n-1 + \lceil\log_2{\frac{max_+}{max_-}}\rceil + cnt_+) \le 31

因为 max+max_+ 与 max−max_- 的取值与 cnt+cnt_+ 与 cnt−cnt_- 无关，我们分开考虑。⌈log⁡2max−max+⌉\lceil\log_2{\frac{max_-}{max_+}}\rceil 和 ⌈log⁡2max+max−⌉\lceil\log_2{\frac{max_+}{max_-}}\rceil 必定有一个取值为 00，另一个取值 ⌈log⁡2A⌉\lceil\log_2{A}\rceil，其中 AA 表示值域（此处为 2020）。所以，

原式  ≤  max(min(n−1+⌈log⁡2A⌉+cnt−,    n−1+cnt+),    min(n−1+cnt−,    n−1+⌈log⁡2A⌉+cnt+))原式 ~~\le~~ max(min(n-1 + \lceil\log_2{A}\rceil + cnt_-,~~~~n-1 + cnt_+),~~~~min(n-1 + cnt_-,~~~~n-1 + \lceil\log_2{A}\rceil + cnt_+))

将 cnt−+cnt+≤ncnt_- + cnt_+ \le n 代入原式，然后两个线性方程求最值。

min(n−1+⌈log⁡2A⌉+cnt−,    n−1+cnt+)  ≤  min(n−1+⌈log⁡2A⌉+cnt,    n−1+n−cnt)  ≤  3n−2+⌈log⁡2A⌉2min(n−1+cnt−,    n−1+⌈log⁡2A⌉+cnt+)  ≤  min(n−1+cnt,    n−1+⌈log⁡2A⌉+n−cnt)  ≤  3n−2+⌈log⁡2A⌉2\begin{array}{} min(n-1 + \lceil\log_2{A}\rceil + cnt_-,~~~~n-1 + cnt_+) ~~\le~~ min(n-1 + \lceil\log_2{A}\rceil + cnt,~~~~n-1 + n - cnt) ~~\le~~ \frac{3n-2+\lceil\log_2{A}\rceil }{2}\\ min(n-1 + cnt_-,~~~~n-1 + \lceil\log_2{A}\rceil + cnt_+) ~~\le~~ min(n-1 + cnt,~~~~n-1 + \lceil\log_2{A}\rceil + n - cnt) ~~\le~~ \frac{3n-2+\lceil\log_2{A}\rceil}{2} \\ \end{array}

原式  ≤  max(3n−2+⌈log⁡2A⌉2,    3n−2+⌈log⁡2A⌉2)≈31.5原式 ~~\le~~ max\left(\frac{3n-2+\lceil\log_2{A}\rceil}{2},~~~~\frac{3n-2+\lceil\log_2{A}\rceil}{2}\right) \approx 31.5

所以最劣情况下，此方案的步数最多为 3131。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// Dual (Easy Version)
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1 // Test Switch
#else
// #define TEST 1
#define LOCAL 1 // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
#pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 105;
#else
#ifdef LOCAL
const int MAX = 105;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

int a[MAX];

void solve() {
    int n;
    cin >> n;
    int max_pos = 0, imax_pos = 0, cnt_pos = 0;
    int max_neg = 0, imax_neg = 0, cnt_neg = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > 0) {
            if (max_pos < a[i]) {
                max_pos = a[i];  // 最大正数
                imax_pos = i;    // 最大正数的索引
            }
            cnt_pos++;  // 正数个数
        } else if (a[i] < 0) {
            if (max_neg < -a[i]) {
                max_neg = -a[i]; // (绝对值)最大负数
                imax_neg = i;    // (绝对值)最大负数的索引
            }
            tomax(max_neg, -a[i]);
            cnt_neg++;  // 负数个数
        }
    }
    if (cnt_pos == 0 and cnt_neg == 0) {  // 全 0
        cout << 0 << endl;
    } else if (cnt_pos == 0) {  // 只有非正数, 一遍后缀和 
        cout << n - 1 << endl;
        for (int i = n - 2; i >= 0; i--) {
            cout << i + 1 << ' ' << i + 2<< endl;
        }
    } else if (cnt_neg == 0) {  // 只有非负数, 一遍前缀和
        cout << n - 1 << endl;
        for (int i = 1; i < n; i++) {
            cout << i + 1 << ' ' << i << endl;
        }
    } else {
        int tmp;
        vector<pair<int, int>> out_pos;
        tmp = max_pos;
        while (tmp < max_neg) {
            tmp *= 2;
            out_pos.push_back({imax_pos, imax_pos});  // 倍增
        }
        for (int i = 0; i < n; i++) {
            if (a[i] < 0) {
                out_pos.push_back({i, imax_pos});  // 变负为非负
            }
        }
        for (int i = 1; i < n; i++) {
            out_pos.push_back({i, i - 1});  // 前缀和
        }

           // 略
        vector<pair<int, int>> out_neg;
        tmp = max_neg;
        while (tmp < max_pos) {
            tmp *= 2;
            out_neg.push_back({imax_neg, imax_neg});
        }
        for (int i = 0; i < n; i++) {
            if (a[i] > 0) {
                out_neg.push_back({i, imax_neg});
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            out_neg.push_back({i, i + 1});
        }

        // 决策
        if (out_pos.size() <= out_neg.size()) {
            cout << out_pos.size() << endl;
            for (pair<int, int> p : out_pos) {
                cout << p.first + 1 << ' ' << p.second + 1 << endl;
            }
        } else {
            cout << out_neg.size() << endl;
            for (pair<int, int> p : out_neg) {
                cout << p.first + 1 << ' ' << p.second + 1 << endl;
            }
        }
    }
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false); 
#endif
#ifdef LOCAL
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);


    int t = 1;
    cin >> t;
    while (t--)
        solve();


#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif 
    return 0;
}