Codeforces Round 924 (Div. 2) 题解 A~D

本文主要是介绍Codeforces Round 924 (Div. 2) 题解 A~D | JorbanS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - Recovering a Small String

string solve() {cin >> n >> m;if (n < m) swap(n, m);if (n & 1 && m & 1) return no;if (m & 1 && n == m << 1) return no;return yes;
}

B - Make Equal

由于排列 $1\sim n$ 均不一样，故先对原数组排序并去重

所给数组范围明显大于 $n$ ，容易想到用区间长度为 $n$ 的去匹配数组 $a$ ，故而用二分确定端点，故只要对每个左端点 $l$ ，二分出 $r$ ，取最大值即可

int solve() {cin >> n;set<int> s;for (int i = 0; i < n; i ++) {int x; cin >> x;s.insert(x);}vector<int> a;for (auto i : s) a.emplace_back(i);int res = 0;for (int i = 0; i < a.size(); i ++) {int t = upper_bound(a.begin() + i, a.end(), a[i] + n - 1) - a.begin() - i;res = max(res, t);}return res;
}

C - Make Equal Again

易得 $2 k - 2∣ n - x$ 或 $2 k - 2∣ n + x - 2$ ，直接暴力求约数即可

set<int> s;void cal(int n) {if (n & 1) return;n >>= 1;for (int i = 1; i <= n / i; i ++)if (n % i == 0) {int a = i, b = n / i;if (a + 1 >= x) s.insert(a);if (b + 1 >= x) s.insert(b);}
}int solve() {cin >> n >> x;s.clear();cal(n - x);cal(n + x - 2);return s.size();
}

D - Divisible Pairs

结果具备单峰性，三分即可，赛时漏了个 $b$ ，小丑了（

ll cal(int t) {ll res = -(ll)(t - 1) * x;for (int i = 0; i < n; i ++) {int p = a[i] / t, q = (a[i] + t - 1) / t;int nq = a[i] % t, np = t - nq;res += (ll)p * np * (a[i] - p) / 2 * b;res += (ll)q * nq * (a[i] - q) / 2 * b;}return res;
}ll solve() {cin >> n >> b >> x;for (int i = 0; i < n; i ++) cin >> a[i];int l = 1, r = 2e5;while (l + 2 < r) {int L = (l * 2 + r) / 3;int R = (l + r * 2) / 3;if (cal(L) >= cal(R)) r = R;else l = L;}return max(cal(l), max(cal(r), cal(l + 1)));
}