Codeforces Round 887 (Div. 1)
A
先来个二分。注意到这样一件事：考虑是 \(a_i\) 失效的最小时间 \(t_i\)，发现 \(t\) 有单调性。所以从大到小考虑 \(a\)，每次相当于将二分的值减去一个值，复杂度 \(O(\sum n(\log n + \log k))\)。
code
const int N = 2e5 + 10;
int n; ll k;
ll a[N];
ll calc(ll x) {
ll res = 0;
for(int i = n; i >= 1; --i) {
ll d;
if(x < a[i]) d = 0;
else d = min(k, (x - a[i]) / i + 1);
x -= d; res += d;
}
return res;
}
void solve() {
cin >> n >> k;
for(int i = 1; i <= n; ++i)
cin >> a[i];
ll ans = 0;
for(ll l = 0, r = 2e14; l <= r; ) {
ll mid = (l + r) / 2;
if(calc(mid) >= mid) ans = mid + 1, l = mid + 1;
else r = mid - 1;
}
cout << ans << '\n';
}
B
不难发现所求序列的绝对值是一个 \(1\) 到 \(n\) 的排列。画个图可以发现，如果我们按照 \(b\) 的绝对值从大到小确定这个排列，那么限制是好描述的。设 \(i\) 在 \(b\) 中系数为 \(t_i \in \{1, -1\}\)。那么有 \(\sum_{i=1}^{j-1}t_i + jt_j = a\)。这样，我们发现若存在合法解，则解唯一。所以可以直接逐位确定。
code
void solve() {
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i].first, a[i].second = i;
sort(a + 1, a + n + 1);
for(int i = n, l = 1, r = n, pre = 0; i >= 1; --i) {
if(a[r].first > i) {
cout << "NO\n";
return ;
} else if(a[l].first == 0 && a[r].first == i) {
cout << "NO\n";
return ;
} else if(a[r].first == i) {
++pre, ans[a[r].second] = i;
--a[l].first;
if(l < --r) a[r].first -= pre;
} else if(a[l].first == 0) {
ans[a[l].second] = -i;
if(++l < r) a[l].first -= pre;
} else {
cout << "NO\n";
return ;
}
}
cout << "YES\n";
for(int i = 1; i <= n; ++i)
cout << ans[i] << " ";
cout << '\n';
}
C
题意转化为初始 \(c_i = 0\)，每次对 \(c\) 区间 \(+1\)，最后使得 \(c_i \equiv a_i \pmod k\)。不难发现若最终 \(c_i\) 确定，则答案为 \(\sum \max(0, c_i - c_{i - 1})\)。
设 \(d_i = c_i - c_{i - 1}\)，考虑我们可以干啥，发现我们是答案变优的手段是将若干个 \(d_i\) 增大 \(k\)，这样就会消去某些位置的贡献。发现最终 \(|d_i| < k\)，否则不调整一定不劣。考虑限制，发现类似括号序，每个前缀中 \(+k\) 的数量大于等于消去贡献位置的数量。发现这玩意不好 dp，于是考虑贪心。不难得到费用流模型：对 \(d_i < 0\) 连边 \((S, i, 1, d_i + k)\)，对 \(d_i > 0\) 连边 \((i, T, 1, -d_i)\)，任意 \(i\) 连边 \((i, i + 1, 1, 0)\)。直接使用小根堆模拟即可。
code
void solve() {
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
if(a[i] == k) a[i] = 0;
}
priority_queue<int, vector<int>, greater<int>> q;
ll sum = 0;
for(int i = 1; i <= n; ++i) {
int d = a[i] - a[i - 1];
sum += max(d, 0);
if(d < 0) {
q.push(k + d);
} else if(q.size()) {
int x = q.top();
if(x < d) {
sum += x - d;
q.pop(), q.push(d);
}
}
}
cout << sum << '\n';
}
D
暴力 dp，打表发现可以有性质，直接做就行了。
code
const int N = 2e5 + 10;
int n, k;
string s;
struct info {
int l, r, p;
info operator + (const int &x) const {
return {l + x, r + x, p == -1 ? -1 : p + x};
}
info operator + (const info &x) const {
if(r + 2 == x.l) return {l, x.r, r + 1};
if(x.r + 2 == l) return {x.l, r, x.r + 1};
if(~p && p < x.l) return {l, max(r, x.r), p};
if(~p && p > x.r) return {min(l, x.l), r, p};
if(~x.p && x.p < l) return {x.l, max(r, x.r), x.p};
if(~x.p && x.p > r) return {min(l, x.l), x.r, x.p};
return {min(l, x.l), max(r, x.r), p == x.p ? p : -1};
}
bool check(int x) {
return l <= x && x <= r && x != p;
}
}f[N][2];
string ans;
void out(int n, int c) {
k -= (s[n] - 'A' != c);
for(int nc = 0; nc < 2; ++nc) {
if(f[n - 1][nc].check(k - (c != nc))) {
k -= (c != nc);
out(n - 1, nc);
break;
}
}
ans += c + 'A';
}
void solve() {
cin >> n >> k >> s;
f[0][0] = {s[0] == 'B', s[0] == 'B', -1};
f[0][1] = {s[0] == 'A', s[0] == 'A', -1};
for(int i = 1; i < n; ++i) {
k -= (s[i] != s[i - 1]);
if(s[i] == 'A') {
f[i][0] = (f[i - 1][0] + (f[i - 1][1] + 1));
f[i][1] = ((f[i - 1][0] + 1) + f[i - 1][1]) + 1;
} else {
f[i][0] = (f[i - 1][0] + (f[i - 1][1] + 1)) + 1;
f[i][1] = ((f[i - 1][0] + 1) + f[i - 1][1]);
}
}
ans.clear();
if(f[n - 1][0].check(k)) {
cout << "YES\n";
out(n - 1, 0);
cout << ans << '\n';
return ;
} else if(f[n - 1][1].check(k)) {
cout << "YES\n";
out(n - 1, 1);
cout << ans << '\n';
} else {
cout << "NO\n";
}
}
E
不难发现，如果出现凸这种形状，那么大区间是没用的。这样可以先求出所有实际上有用的区间，那么这些区间的左右端点是不能动的，其他部分可以乱搞。
感觉一下，认为最多出现一种原序列没有的数，证明很简单，如果有两种那么把小的变成大的依然满足限制。我们考虑怎么安排新的这种数，发现需要让新区间包含一个值比他大的小区间。
考虑如果所有区间都已确定，那么接下来每个位置只需要填包含这个区间的最大的数即可，先不管新的数求一边。现在剩下的问题就是如何确定新的数的区间。我们考虑枚举包含的那个比他大的区间，不难发现会如果某一侧有比新数小的数那么会直接选了，如果没有则会选最小的。可以用依托数据结构和 vector 上二分维护做到 \(O(n \log n)\)。
写一个下午发现做法一直假，麻了。在细节上卡了整整三天才过。细节是什么呢？如果我们去掉某些区间后，一些位置直接贪得不到一个确定的数，那么我们必然需要新数，否则可以不使用新数。
code
const int N = 1e6 + 10;
int n, m, o[N], b[N];
struct info {
int l, r, x;
}a[N];
map<int, int> fl, fr;
struct BIT {
int tr[N];
int lowbit(int x) {
return x & -x;
}
void clear() {
for(int i = 1; i <= n; ++i)
tr[i] = 0;
}
void add(int x, int v) {
for(; x <= n; x += lowbit(x))
tr[x] = max(tr[x], v);
}
int query(int x) {
int res = 0;
for(; x; x -= lowbit(x))
res = max(res, tr[x]);
return res;
}
}s;
int occ[N];
vector<int> vec;
void clear() {
fl.clear(), fr.clear();
for(int i = 1; i <= n; ++i)
b[i] = occ[i] = 0;
vec.clear(), s.clear();
}
void solve() {
clear();
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> o[i];
if(!fl.count(o[i])) fl[o[i]] = i;
fr[o[i]] = i;
}
m = 0;
for(auto [x, l] : fl) {
int r = fr[x];
a[++m] = {l, r, x};
}
sort(a + 1, a + m + 1, [](info x, info y) {
return x.l == y.l ? x.r < y.r : x.l > y.l;
});
vector<int> vv;
int tmp = m; m = 0;
for(int i = 1; i <= tmp; ++i) {
int l = a[i].l, r = a[i].r, x = a[i].x;
int p = s.query(r);
if(p < x) {
a[++m] = a[i];
s.add(r, x);
occ[l] = occ[r] = m;
vv.eb(x);
}
}
sort(vv.begin(), vv.end());
int lst = 0;
for(int x : vv) {
if(lst != x - 1) vec.eb(x - 1);
lst = x;
}
set<int, greater<int>> se;
se.insert(0);
vector<pii> vb;
vector<int> vmn, vmx;
for(int i = 1; i <= n; ++i) {
if(occ[i]) {
int x = a[occ[i]].x; b[i] = x;
if(se.find(x) != se.end()) se.erase(x);
else if(a[occ[i]].r > a[occ[i]].l) se.insert(x);
} else {
b[i] = *se.begin();
vb.emplace_back(mp(b[i], i));
}
}
sort(vb.begin(), vb.end());
vmn.resize(vb.size()), vmx.resize(vb.size());
for(int i = 0, mn = n + 1, mx = 0; i < sz(vb); ++i)
vmn[i] = -(mn = min(mn, vb[i].second)), vmx[i] = mx = max(mx, vb[i].second);
auto qmn = [&](int x) {
int rk = lower_bound(vmn.begin(), vmn.end(), -x) - vmn.begin();
if(rk == sz(vb)) return -1;
return vb[rk].second;
};
auto qmx = [&](int x) {
int rk = lower_bound(vmx.begin(), vmx.end(), x) - vmx.begin();
if(rk == sz(vb)) return -1;
return vb[rk].second;
};
vec.emplace_back(-1);
sort(vec.begin(), vec.end());
auto get = [&](int x) {
return *(lower_bound(vec.begin(), vec.end(), x + 1) - 1);
};
ll ms = 0;
for(int i = 1; i <= n; ++i)
if(b[i] == 0) ms = -1e18;
int L = -1, R = -1, w = -1;
ll sum = 0; int mn = n + 1, mx = 0;
sort(a + 1, a + m + 1, [](info x, info y) {
return x.x < y.x;
});
for(int i = 1, p = 0; i <= m; ++i) {
int x = a[i].x, v = get(x);
if(v <= 0) continue;
while(p < sz(vb) && vb[p].first <= v) {
mn = min(mn, vb[p].second), mx = max(mx, vb[p].second);
sum += vb[p++].first;
}
ll t = 1ll * p * v - sum;
int lp = 0, rp = 0;
if(mn > a[i].l) {
int ql = qmn(a[i].l);
if(ql == -1) continue;
assert(b[ql] > v);
t = t - b[ql] + v, lp = ql;
}
if(mx < a[i].r) {
int qr = qmx(a[i].r);
if(qr == -1) continue;
assert(b[qr] > v);
t = t - b[qr] + v, rp = qr;
}
if(t > ms) {
ms = t, w = v;
L = lp, R = rp;
}
}
for(int i = 1; i <= n; ++i)
if(occ[i]) cout << b[i] << ' ';
else {
if(i == L || i == R) cout << w << ' ';
else cout << max(w, b[i]) << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T; cin >> T;
while(T--) solve();
}