模拟赛的密度正在威胁其他文章的生存环境。
A. 排序
https://www.luogu.com.cn/problem/P14352
对于一个长度为 \(n\) 的排列 \(p\)，定义一轮冒泡：
for i in range(1, n): if p[i] > p[i + 1]: swap(p[i], p[i + 1])给定 \(n,k\)，问在所有长度为 \(n\) 的排列中，可以在 \(k\) 轮冒泡后单增的排列数量。对 \(998244353\) 取模。
\(n\le 10^{18},k\le 2\times 10^7\)。
反序表。令 \(a_i\) 表示 \(i\) 结尾的逆序对数，那么限制相当于说 \(\max\{a\}\le k\)。
也即限制一个元素之前大于之的元素数不超过 \(k\)，可以直接计数。想象把 \(1\sim n\) 依次填入排列的过程：
对于 \(1\sim n-k\)，只能填在剩余空位的左 \(k+1\) 个（因为填完它后，剩下的空位都比它大）；
对于 \(n-k+1\sim n\)，可以填在剩余任意一个空位。
故答案为 \((k+1)^{n-k}\cdot k!\)。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("sorting.in", "r", stdin);
std::freopen("sorting.out", "w", stdout);
auto stime = std::chrono::steady_clock::now();
long long n;
int k;
std::cin >> n >> k, k = std::min((long long)k, n);
auto qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
auto res = qkp(k + 1, (n - k) % (mod - 1));
for (int i = 1; i <= k; ++i)
(res *= i) %= mod;
std::cout << res << '\n';
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double>(std::chrono::steady_clock::now() - stime).count() << "s \n";
return 0;
}B. 重排
https://www.luogu.com.cn/problem/P14353
给定一个初始为空的数组 \(a\)，再给出 \(n\) 次加数操作，每次加数后输出：
任意排列 \(a\)，得到的 \(\sum\limits_{i=2}^n |a_{i+1}-a_{i}|\) 的最大值。
\(n\le 3\times 10^6\)。
显然从小到大排列，答案是后 \(\left\lfloor \dfrac n2\right\rfloor\) 个数的和减去前 \(\left\lfloor \dfrac n2\right\rfloor\) 的和的差的二倍，再减去位于中间 2 / 3 个数中，相邻两个差的最小值。
这家伙在说什么呢.jpg
用大根堆 + 小根堆维护即可，因为 pbds 过不去
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("rearrange.in", "r", stdin);
std::freopen("rearrange.out", "w", stdout);
auto stime = std::chrono::steady_clock::now();
int n, T;
std::cin >> n >> T;
auto res = 0ll, la = 0ll, sL = 0ll, sR = 0ll;
std::priority_queue<int> L;
std::priority_queue<int, std::vector<int>, std::greater<int> > R;
for (int i = 1, mid = 0; i <= n; ++i) {
long long x;
std::cin >> x;
int b = T ? x ^ la : x;
if (i == 1)
mid = b, la = 0ll;
else if (i & 1) {
if (b < L.top()) {
mid = L.top(), sL -= mid;
L.pop();
sL += b, L.push(b);
}
else if (b > R.top()) {
mid = R.top(), sR -= mid;
R.pop();
sR += b, R.push(b);
}
else
mid = b;
la = 2 * (sR - sL) - std::min(R.top() - mid, mid - L.top());
}
else {
if (b <= mid) {
sL += b, sR += mid;
L.push(b), R.push(mid);
}
else {
sL += mid, sR += b;
L.push(mid), R.push(b);
}
la = 2 * (sR - sL) - (R.top() - L.top());
}
res ^= la;
}
printf("%lld\n", res);
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double>(std::chrono::steady_clock::now() - stime).count() << "s \n";
return 0;
}C. 整式比较 / qoj#10506. Waga
https://www.becoder.com.cn/contest/6685/problem/3 / https://qoj.ac/problem/10506
给定 \(a_{1\cdots n}\)，和一个称，如下操作称为一次『称重』：
- 选中 \(a\) 的一个子集，输入给称。记它们的和为 \(s\)，那么称会返回 \(\min(k,\left\lfloor \dfrac sc \right\rfloor)\)，其中，\(c\) 为给定常数。
现在对于每个无序对 \((i,j)\)（\(i\ne j\)），你需要判断：
- 在已知 \(a\) 中除 \(a_i,a_j\) 外所有元素值，且 \(a_i,a_j\) 数值未知的前提下，是否可以通过若干次称重确定 \(a_i,a_j\) 的大小关系。
\(n,c\le 8000,k\le 10^5,1\le a_i< kc\)。
显然，\(a_i\) 和 \(a_j\) 能区分，当且仅当 \(\left\lfloor\dfrac {a_i}c\right\rfloor\ne \left\lfloor\dfrac {a_j}c\right\rfloor\)，或者存在一个其他元素的子集 \(s\)，使得 \(\left\lfloor\dfrac {a_i+s}c\right\rfloor\ne \left\lfloor\dfrac {a_j + s}c\right\rfloor\)。
反过来，如果 \(a_i\) 和 \(a_j\) 不能区分，一个前提是 \(\left\lfloor\dfrac {a_i}c\right\rfloor =\left\lfloor\dfrac {a_j}c\right\rfloor\)。
下意识猜要排序，排序后打表发现使 \(i\) 不合法的 \(j\) 总是连续的。
证明
需要证：对于 \(x<y<z\)，若 \(x,y\) 不可区分，且 \(y,z\) 不可区分，那么 \(x,z\) 不可区分。
记 \(\left\lfloor\dfrac {x}c\right\rfloor=\left\lfloor\dfrac {y}c\right\rfloor=\left\lfloor\dfrac {z}c\right\rfloor=w\)，不存在 \(s\le c\cdot (k-w)\)，使得 \(y\) 可以进位但 \(x\) 不可，也不存在这样的 \(s\) 使得 \(z\) 可以进位但 \(y\) 不可。
合并不等式容易得到不存在这样的 \(x\) 使得 \(z\) 可以进位但 \(x\) 不可。
需要证：对于 \(x<y<z\)，若 \(x,y\) 可区分或 \(y,z\) 可区分，则 \(x,z\) 可区分。
调整法易得。
故发现只需要讨论相邻两个元素是否可区分。需要知道所有可能的子集和用于 check，可以用分治预处理『只有某相邻两个元素不选』时的前后缀背包数组（到达某个余数时需要的最小整倍数），就可以 \(O(nc\log n)\) 解决问题。
考虑在做什么：删点在 \([l,mid]\)，那么 \([mid+1,r]\) 的 DP 数组不会受到影响；删点在 \([mid + 1, r]\)，那么 \([l,mid]\) 的 DP 数组不会受到影响。背包的物品是无顺序的，所以有正确性。
也就是说大部分信息是可继承的。为什么题解管这个叫 CDQ？是因为普通分治总会被叫 CDQ 吗？
做一个类似 01 背包滚动数组的东西，维护每个点前 / 后可以凑出来的背包值，在最后下传到单点时统计答案即可。
相邻两个的处理略显烧脑，但意外地简洁。
>= 不要写成除，不然会慢成唐诗
#include <bits/stdc++.h>
const int maxn = 8e3 + 5;
char nec(void) {
static char buf[1 << 20], *p = buf, *e = buf;
if (p == e) {
e = buf + fread(buf, 1, 1 << 20, stdin);
p = buf;
}
return *p++;
}
int read(void) {
auto x = 0ll;
char t = nec();
for (; t < '0' || t > '9'; t = nec());
for (; t >= '0' && t <= '9'; t = nec())
x = x * 10 + t - '0';
return x;
}
int ok[maxn], m, k;
std::pair<int, int> a[maxn];
void calc(int l, int r, const std::vector<int> f) {
if (l > r)
return;
if (l == r) {
if (a[l].first == a[l + 1].first)
ok[l] = 1;
else if (a[l].first / m == a[l + 1].first / m)
ok[l] = (*std::min_element(f.begin() + m - a[l + 1].first % m, f.begin() + m - a[l].first % m) + a[l].first / m >= k);
return;
}
int mid = (l + r) >> 1;
auto g = f;
for (int i = mid + 2; i <= r + 1; ++i) {
auto h = g;
for (int j = 0, k; j < m; ++j) {
k = (j + m - a[i].first % m) % m;
h[j] = std::min(h[j], g[k] + a[i].first / m + (k + a[i].first % m >= m));
}
h.swap(g);
}
calc(l, mid, g);
g = f;
for (int i = l; i <= mid; ++i) {
auto h = g;
for (int j = 0, k; j < m; ++j) {
k = (j + m - a[i].first % m) % m;
h[j] = std::min(h[j], g[k] + a[i].first / m + (k + a[i].first % m >= m));
}
h.swap(g);
}
calc(mid + 1, r, g);
return;
};
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("intcmp.in", "r", stdin);
std::freopen("intcmp.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n = read();
m = read(), k = read();
for (int i = 1; i <= n; ++i)
a[i].first = read(), a[i].second = i;
std::sort(a + 1, a + n + 1);
std::vector<int> f(m, 0x3f3f3f3f);
f[0] = 0;
calc(1, n - 1, f);
std::vector<int> resL(n + 1), resR(n + 1);
int now = 0;
for (int i = 1; i <= n; ++i) {
resR[a[i].second] = i - 1 - now;
if (i != n && ok[i])
++now;
else
now = 0;
}
now = 0;
for (int i = n; i; --i) {
resL[a[i].second] = n - i - now;
if (ok[i - 1])
++now;
else
now = 0;
}
for (int i = 1; i <= n; ++i)
printf("%d %d \n", resL[i], resR[i]);
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B. 字符串转换
https://www.becoder.com.cn/problem/52055
给定等长 01 串 \(S,T\)，维护 \(Q\) 次操作：
- 修改：Flip \(S\) 的某个字符。
- 修改：Flip \(T\) 的某个字符。
每次操作后，问 \(S\) 能否通过若干次下列操作变为 \(T\)：
- 选择 \(S\) 中的一个
00，变为10。- 选择 \(S\) 中的一个
11，变为01。\(|S|,Q\le 3\times 10^5\)。
连续 00 / 11 操作，考虑奇数位取反。取反之后发现原操作等价于 \(a_i\gets a_{i+1}\)。
这个操作只会使连续段的数量减少，故要求每一个后缀，\(S\) 的连续段个数不少于 \(T\) 的连续段个数，而且二者结尾相同。
线段树维护即可。
#include <bits/stdc++.h>
const int maxn = 3e5 + 5;
struct { int l, r, mn, d; } t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
t[p].mn = t[p].d = 0;
if (l == r)
return;
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
return;
}
void pushdown(int p) {
if (t[p].d) {
t[lt].mn += t[p].d, t[lt].d += t[p].d;
t[rt].mn += t[p].d, t[rt].d += t[p].d;
t[p].d = 0;
}
return;
}
void add(int p, int l, int r, int v) {
if (l <= t[p].l && t[p].r <= r) {
t[p].mn += v, t[p].d += v;
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
t[p].mn = std::min(t[lt].mn, t[rt].mn);
return;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("string.in", "r", stdin);
std::freopen("string.out", "w", stdout);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, q;
std::cin >> n >> q;
std::vector<int> a(n + 1), b(n + 1);
bld(1, 1, n);
for (int i = 1; i <= n; ++i) {
char t;
std::cin >> t, a[i] = (t == 'B');
if (i & 1)
a[i] ^= 1;
}
for (int i = 1; i <= n; ++i) {
char t;
std::cin >> t, b[i] = (t == 'B');
if (i & 1)
b[i] ^= 1;
}
for (int i = 1; i <= n; ++i) {
int v = 0;
v += (i == n || a[i] != a[i + 1]);
v -= (i == n || b[i] != b[i + 1]);
if (v)
add(1, 1, i, v);
}
for (char op; q--; ) {
int i;
std::cin >> op >> i;
if (op == 'X') {
int v = 0, v1 = 0;
v -= (i == n || a[i] != a[i + 1]);
v1 -= (i != 1 && a[i] != a[i - 1]);
a[i] ^= 1;
v += (i == n || a[i] != a[i + 1]);
v1 += (i != 1 && a[i] != a[i - 1]);
if (v)
add(1, 1, i, v);
if (v1)
add(1, 1, i - 1, v1);
}
else {
int v = 0, v1 = 0;
v += (i == n || b[i] != b[i + 1]);
v1 += (i != 1 && b[i] != b[i - 1]);
b[i] ^= 1;
v -= (i == n || b[i] != b[i + 1]);
v1 -= (i != 1 && b[i] != b[i - 1]);
if (v)
add(1, 1, i, v);
if (v1)
add(1, 1, i - 1, v1);
}
std::cout << ((a[n] == b[n] && t[1].mn >= 0) ? "YES" : "NO") << '\n';
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C. 监控
https://www.becoder.com.cn/problem/52057
给定 \(n\) 个怪，每个怪有 \(B_i\) 滴血，也就是说每个怪能被打 \(\le B_i\) 次。
要求每个怪必须被打 \(\ge A_i\) 次，并认为被打恰好 \(A_i\) 次时这个怪是好的。
对于每个 \(1\le x\le \sum B_i\)，求：在攻击次数只能为 \(x\) 的倍数的前提下，不好的怪的最小值。你只需要输出答案的和。
\(N\le 10^5,1\le A_i< B_i\le 10^5\)。
记 \(c_i=B_i-A_i\)，把 \(c_i\) 降序排列，记 \(s=\sum A_i\)，那么一个 \(x\) 的答案为：
\[ \min\left\{i\mid{\left\lceil \frac{s}x \right\rceil\cdot x - s\ge c_i}\right\} \]
容易想到整除分块，枚举 \(\left\lceil \dfrac{s}x \right\rceil\) 的值 \(k\)，那么相当于想要找到 \([L_i,R_i]\) 中的每个 \(x\)，\(x\cdot k-s\) 会落在哪个 \(c\) 的管辖范围里。
不妨记 \(c_i\) 的管辖范围为 \([cL_i,cR_i]\)，那么转化为 \(x\cdot k-s\in [cL_i,cR_i]\)，枚举 \(c\) 解不等式即可。
但发现一个严重的问题：外层整除分块复杂度是 \(\sqrt(s)\) 的，最劣 \(10^5\) 级别，很坏了。
发现枚举商数劣的原因是使 \(\left\lceil \dfrac{s}x \right\rceil\) 很大的 \(x\) 并不多，却占用了很多枚举次数
如果做经典的整除分块同样会发现到后期块内元素远远少于 \(n\)，却要花费 \(n\) 次操作来处理它们。所以对于这部分数我们直接朴素二分。
取阈值为 1500 即可。
#include <bits/stdc++.h>
const int B = 1500;
const long long inf = 1e18;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
std::cin >> n;
std::vector<long long> c(n + 1);
auto sa = 0ll, sb = 0ll;
for (int i = 1, a, b; i <= n; ++i) {
std::cin >> a >> b;
sa += a, sb += b, c[i] = b - a;
}
std::sort(c.begin() + 1, c.end(), std::greater<int> ());
std::partial_sum(c.begin() + 1, c.end(), c.begin() + 1);
auto L = sb + 1;
std::stack<std::pair<long long, int> > st;
for (int k = 1; k <= 1500; ++k) {
auto l = (sa + k - 1) / k, r = L - 1;
if (l > r)
continue;
L = l;
st.emplace(r, n + 1);
for (int i = n; ~i; --i)
st.emplace(std::min(r, (c[i] + sa) / k), i);
}
for (int i = L - 1; i; --i)
st.emplace(i, std::lower_bound(c.begin(), c.end(), ((sa + i - 1) / i) * i - sa) - c.begin());
auto res = 0ll;
for (auto l = 1ll; !st.empty(); ) {
auto [r, v] = st.top();
st.pop();
if (l > r)
continue;
if (v == n + 1)
v = 0;
res += (r - l + 1) * v;
l = r + 1;
}
std::cout << res << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}G - Range Set Modifying Query
https://atcoder.jp/contests/abc430/tasks/abc430_g
发现开 60 个线段树非常合理
接着发现是 beats 板子题。看似需要三只 log，其实只有两只。
参见 abc426，最近 abc 都喜欢 beats 板子题吗？
