Dual (Easy & Hard Version)
原题链接
C2-Dual (Hard Version) Codeforces Round 889 (Div. 2)
最喜欢这种什么算法都没有的构造题。
简明题意
给定 n 个数 ai,你可以进行不超过 k 次操作,使得最终 a 是非降序的。每次操作任选两个数使得 ai+=aj。
Easy Version:1≤n≤20,−20≤ai≤20,k=50。
Hard Version:1≤n≤20,−20≤ai≤20,k=31。
解题思路
Easy Version 的解法很多就不介绍了,我直接出的 Hard Version 的思路。
首先我们考虑使用 前缀和 操作,因为不使用前缀和会发现问题变得非常棘手,我们很难讨论序列之间的复杂状态。如果最后一步使用前缀和,我们只需要保证在最后一步之前所有数都是非负数或者非正数(对应后缀和)。前缀和的代价是 n−1。
其次我们先 考虑全部变为非负数的方式 ,因为全部变为非负和全部变为非正是相反的操作,所以先考虑一边即可。
那么问题转化为如何 在剩余代价内将所有数转化为非负数 。假设我们对于序列 a 求出最大正数的绝对值 max+,正数的个数 cnt+,最大负数的绝对值 max−,负数的个数 cnt−。那么很直观的想法就是让所有负数加上 max+ 直到变为非负数,但是当 max+=1 而 max−=20 时,这样做的代价是 20。这里需要观察到 ai 是可以做自加的,这相当于一个倍增的过程,那么首先让 max+ 倍增到大于等于 max−,再进行后面的操作。计算总代价为 n−1+⌈log2max+max−⌉+cnt− ,这样做的最大代价为 43,显然问题还没有结束。
我们之前讨论的是考虑将全部数变为非负数,那么相应的,我们还可以选择 将全部变为非正数的方式 ,然后做一次后缀和。总代价为 n−1+⌈log2max−max+⌉+cnt+。这其实也是一个很直观的想法,但是我们如何对这两种方案做出决策呢?如果卡在这里那实在是太可惜了,事实上我们可以将两个方案都进行计算,将决策交给程序进行(一个简单的 if−else 语句而已)。拿到这个方案我也并不确定是否符合题目条件,但是后面我们将 证明 。
最后还剩下一些上面的解法可能无法解决的一些小问题需要解决:如果全为 0,不需要进行任何操作;如果只有非负数,直接进行一次前缀和;如果只有非正数,直接进行一次后缀和。
正确性证明
现在我们要证明:
min(n−1+⌈log2max+max−⌉+cnt−, n−1+⌈log2max−max+⌉+cnt+)≤31
因为 max+ 与 max− 的取值与 cnt+ 与 cnt− 无关,我们分开考虑。⌈log2max+max−⌉ 和 ⌈log2max−max+⌉ 必定有一个取值为 0,另一个取值 ⌈log2A⌉,其中 A 表示值域(此处为 20)。所以,
原式 ≤ max(min(n−1+⌈log2A⌉+cnt−, n−1+cnt+), min(n−1+cnt−, n−1+⌈log2A⌉+cnt+))
将 cnt−+cnt+≤n 代入原式,然后两个线性方程求最值。
min(n−1+⌈log2A⌉+cnt−, n−1+cnt+) ≤ min(n−1+⌈log2A⌉+cnt, n−1+n−cnt) ≤ 23n−2+⌈log2A⌉min(n−1+cnt−, n−1+⌈log2A⌉+cnt+) ≤ min(n−1+cnt, n−1+⌈log2A⌉+n−cnt) ≤ 23n−2+⌈log2A⌉
原式 ≤ max(23n−2+⌈log2A⌉, 23n−2+⌈log2A⌉)≈31.5
所以最劣情况下,此方案的步数最多为 31。
代码
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
|
#ifdef ONLINE_JUDGE #define TEST 1 #else
#define LOCAL 1 #endif #ifndef LOCAL #define TEST 1 #endif #include <bits/stdc++.h> #define int int64_t #ifdef TEST #pragma GCC optimize(3, "Ofast", "inline") #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) { 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 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; }
|