比赛链接：https://codeforces.com/contest/1343
有一数列 x + 2x + 4x + ... + 2k-1x = n，输出 k ≥ 2 时任一满足该等式的一个 x 值。
等比数列求和得 (2k-1) x = n，枚举 k 即可。
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; for (int i = 2; i < 32; i++) { if (n % ((1 << i) - 1) == 0) { cout << n / ((1 << i) - 1) << "\n"; return; } } } int main() { int t; cin >> t; while (t--) solve(); }
构造一个数组，要求满足：
贪心，从 2 起构造前一半，从 1 起构造后一半，后一半最后一个元素特别构造。
#include <bits/stdc++.h> using ll = long long; using namespace std; void solve() { int n; cin >> n; if (n / 2 % 2 == 1) cout << "NO" << "\n"; else { ll a[n], sum = 0; for (int i = 0; i < n / 2; i++) { a[i] = (i + 1) * 2; sum += a[i]; } ll num = 1; for (int i = n / 2; i < n - 1; i++) { a[i] = num; num += 2; sum -= a[i]; } a[n - 1] = sum; cout << "YES" << "\n"; for (ll i : a) cout << i << ‘ ‘; cout << "\n"; } } int main() { int t; cin >> t; while (t--) solve(); }
在一个数组中寻找一个正负相间的最长的子序列，且该子序列元素之和为该长度所有子序列的最大值。
长度优先——贪心地取所有不同正负的元素
最大和——同正负的元素利用双指针局部排序，每次取最大值
#include <bits/stdc++.h> using ll = long long; using namespace std; void solve() { int n; cin >> n; ll a[n]; for (ll &i : a) cin >> i; ll ans = 0; for (int i = 0; i < n; ) { int j = i + 1; while (j < n and a[i] * a[j] > 0) ++j; sort(a + i, a + j); ans += a[j - 1]; i = j; } cout << ans << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
对一个长度为偶数，元素大小在 [1, k] 之间的数组元素做变换，每次可以用 [1, k] 间的一个数替换一个元素，要求最终满足，所有的 a[i] + a[n - 1 - i] 相等 (0-indexed)，求最少需要的变换次数。
a[i] + a[n - 1 - i] 的范围为 [2, 2 * k]，我们可以假设每个和一开始都需要变换所有元素，然后计算每个对称和所能变换的最小值和最大值，在此区间内的和只需变换一次即可，为了在线性时间内访问所有需要减一的区间，可以用一个差分数组记录每个需要变换区间的左右端点，线性访问一遍即可，最后对于初始时的和因为两个子元素都不用变换所以需要再减一。
#include <bits/stdc++.h> using namespace std; const int M = 2e5 + 100; int n, k; int a[M], cnt[2 * M], sub[2 * M]; void solve() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i <= 2 * k + 10; i++) cnt[i] = n, sub[i] = 0; for (int i = 0; i < n / 2; i++) { int x = a[i], y = a[n - 1 - i]; int mi = min(x, y) + 1; int mx = max(x, y) + k; --cnt[x + y]; --sub[mi]; ++sub[mx + 1]; } for (int i = 2; i <= 2 * k; i++) { sub[i] += sub[i - 1]; cnt[i] += sub[i]; } int ans = INT_MAX; for (int i = 2; i <= 2 * k; i++) ans = min(ans, cnt[i]); cout << ans << "\n"; } int main() { int t; cin >> t; while (t--) solve(); }
Codeforces Round #636 (Div. 3)
原文：https://www.cnblogs.com/Kanoon/p/12749282.html