QOJ 4211 Alice and Bob
模拟赛中链的部分分很有启发意义：注意到每一个棋子的后继确定，所以只需考虑 Alice 和 Bob 每次移动哪颗棋子。
容易发现按照颜色划分，所有结点构成若干连续段，假设我们强制钦定不能跨段移动棋子，那么胜负其实已经确定了，考虑每个结点有一个最大移动步数 \(v_i\)，那么考虑 \(i\) 的后继点 \(j\)，满足 \(i\) 和 \(j\) 颜色相同（若不存在 \(j\) 则 \(v_i = 0\)），转移是 \(v_i = v_j + 1\)，设 Alice 初始控制的有棋子的点集为 \(A\)，Bob 初始控制的有棋子的点集为 \(B\)，Alice 必胜当且仅当 \(\sum\limits_{i \in A} v_i > \sum\limits_{i \in B} v_i\)。
现在加入可以跨段移动的规则，考虑一个结点 \(i\) 有一个后继点 \(j\)，并且 \(i, j\) 颜色不同，此时若移动在 \(i\) 处的棋子可以使自己多移动一步，但会使对手可以多移动 \(j\) 步，所以 \(v_i = \max(1 - v_j, 0)\)。
我们发现这样的价值设定对不是链的情况也成立，我们只需对于多个后继点取 \(\max\) 即可。
最后讨论如何计数，先预处理每个结点的价值 \(v\)，设 \(f_{i, j}\) 表示考虑前 \(i\) 个结点，当前满足 \(\sum\limits_{x \in A} v_x - \sum\limits_{x \in B} v_x = j\)，容易发现 \(v_i \le n\)，所以直接 \(O(n^3)\) 转移就行。
Code
#include <iostream>
#include <vector>
using namespace std;
const int N = 305;
const int Mod = 998244353;
int n, m;
char col[N];
vector<int> e[N];
int sg[N], f[N][N * N * 2];
int main () {
// freopen("game.in", "r", stdin);
// freopen("game.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> col[i];
}
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
e[u].push_back(v);
}
for (int i = n; i; --i) {
for (auto j : e[i]) {
if (col[i] == col[j])
sg[i] = max(sg[i], sg[j] + 1);
else
sg[i] = max(sg[i], 1 - sg[j]);
}
}
fill(f[0], f[n] + n * n * 2 + 1, 0);
f[0][n * n] = 1;
for (int i = 1; i <= n; ++i) {
int v = (col[i] == 'W' ? sg[i] : -sg[i]), lim = (i - 1) * n;
for (int j = -lim + n * n; j <= lim + n * n; ++j) {
f[i][j] = (f[i][j] + f[i - 1][j]) % Mod;
f[i][j + v] = (f[i][j + v] + f[i - 1][j]) % Mod;
}
}
int ans = 0;
for (int i = n * n + 1; i <= n * n * 2; ++i) {
ans = (ans + f[n][i]) % Mod;
}
cout << ans << '\n';
return 0;
}
QOJ 4215 Easiest Sum
设 \(c(x)\) 表示要使得序列的最大子段和 \(\le x\)，最少需要多少次操作。
为了计算 \(c(x)\)，我们设 \(f_i\) 表示使得前缀 \([1, i]\) 中，每个子段 \(\le x\) 的最小操作数，显然有 \(f_i \ge f_{i - 1}\)，在此基础上枚举 \(j\)，为了使得 \([i, j]\) 合法，还有额外转移 \(f_i = \max\limits_{j < i} f_j + \sum\limits_{k = j + 1}^{i} a_k - x\)。注意到我们只关心 \(c(x) = f_n\)。
将 \(f\) 数组的求解转化为从 \(0\) 到 \(n\) 的最长路问题：
-
\(\forall i \in [0, n)\)，有一条由 \(i\) 连向 \(i + 1\)，边权为 \(0\) 的边。
-
\(\forall 0 \le j < i \le n\)，有一条由 \(i\) 连向 \(j\)，边权为 \(\sum\limits_{k = j + 1}^{i} a_k - x\) 的边。
将边权取反变为最短路，并加上 \(\sum\limits_{i = 1}^n a_i\) 得到：
-
\(\forall i \in [0, n)\)，有一条由 \(i\) 连向 \(i + 1\)，边权为 \(a_{i + 1}\) 的边。
-
\(\forall 0 \le j < i \le n\)，有一条由 \(i\) 连向 \(j\)，边权为 \(x\) 的边。
考虑这个最短路怎么求，我们钦定走 \(k\) 条权值为 \(x\) 的边（我们称为跳边），我们现在要最小化其余边的权值和，记为 \(t_k\)。
假设初始时没有跳边，权值和 \(t_0 = \sum\limits_{i = 1}^{n} a_i\)，多走一条跳边相当于删除了 \(a\) 中的一个子段，由于我们希望边权和最小，那么就要使得删掉的数权值和最大，那么这是最大 \(k\) 子段和问题。
假设我们已经求出 \(a\) 的最大 \(k\) 子段和 \(d_k\)，把代价带回去可以表示出 \(c(x) = \max\limits_{k} d_k - kx\)。
考虑 \(d_k\) 怎么求，这个是线段树优化最小费用最大流经典题，在线段树上每次找出最大子段，再将区间取反即可，这样相当于添加了一个反悔策略，这一部分预处理时间复杂度 \(O(n \log n)\)。
现在我们可以将答案表示为 \(ans = \sum\limits_{k = 1}^K \min\limits_{c(x) \le k} x\)，暴力计算，时间复杂度 \(O(nK \log V)\)。
观察 \(c(x)\) 的性质，设 \(f_{k}(x) = d_k - kx, c(x) = \max\limits_{k} f_k(x)\)，由于 \(d_k\) 具有凸性（考虑选出的子段越多，每多选一个子段所增加的收益越少），并且斜率每次变化 \(1\)，所以将所有点 \((x, c(x))\) 画在二维平面上构成左下凸壳。
考虑如何描述我们要求的 \(ans\)，它相当于 \(\forall y_0 \in [1, K]\)，作一条 \(y = y_0\) 的直线，与凸包相割的位置横坐标为 \(x\)，答案就是对 \(\lceil x \rceil\) 求和。
转化到这一步就非常好做了，对于每个 \(k \in [1, n)\)，求一下 \(f_k\) 和 \(f_{k + 1}\) 的交点，这些交点就是凸壳上的顶点，通过这些顶点将凸壳可以分成 \(n\) 个限制值域的一次函数，将值域与 \([1, K]\) 求交分别做即可。对于每一个一次函数的计算容易用数学方法做到 \(O(1)\)。
Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const int Mod = 998244353, Inv = (Mod + 1) / 2;
const LL Inf = 2e18;
struct D {
int pret, suft, l, r;
LL sum, pre, suf, ans;
void Invert () {
sum = -sum, pre = -pre, suf = -suf, ans = -ans;
}
};
int n, a[N];
LL k, s[N], f[N], d[N], p[N];
LL arr[N], pre[N];
namespace Seg {
#define lc (k << 1)
#define rc ((k << 1) | 1)
const int T = N * 4;
D mx[T], mi[T];
bool tag[T];
void Node_invert (int k) {
swap(mi[k], mx[k]);
mi[k].Invert(), mx[k].Invert();
tag[k] ^= 1;
}
D Merge (D a, D b, auto cmp) {
D res;
res.sum = a.sum + b.sum;
if (cmp(a.pre, a.sum + b.pre)) {
res.pre = a.pre, res.pret = a.pret;
}
else {
res.pre = a.sum + b.pre, res.pret = b.pret;
}
if (cmp(b.suf, b.sum + a.suf)) {
res.suf = b.suf, res.suft = b.suft;
}
else {
res.suf = b.sum + a.suf, res.suft = a.suft;
}
auto better = [&](LL a, LL b) -> LL {
return cmp(a, b) ? a : b;
} ;
res.ans = better(better(a.ans, b.ans), a.suf + b.pre);
if (res.ans == a.ans) {
res.l = a.l, res.r = a.r;
}
else if (res.ans == b.ans) {
res.l = b.l, res.r = b.r;
}
else if (res.ans == a.suf + b.pre) {
res.l = a.suft, res.r = b.pret;
}
return res;
}
D Merge_min (D a, D b) { return Merge(a, b, less<LL>()); }
D Merge_max (D a, D b) { return Merge(a, b, greater<LL>()); }
void Pushup (int k) {
mx[k] = Merge_max(mx[lc], mx[rc]);
mi[k] = Merge_min(mi[lc], mi[rc]);
}
void Build (int k, int L = 1, int R = n) {
if (L == R) {
mx[k].pret = mx[k].suft = mx[k].l = mx[k].r = L;
mx[k].sum = mx[k].pre = mx[k].suf = mx[k].ans = a[L];
mi[k] = mx[k];
return;
}
int mid = (L + R) >> 1;
Build(lc, L, mid);
Build(rc, mid + 1, R);
Pushup(k);
}
void Pushdown (int k) {
if (tag[k]) {
Node_invert(lc), Node_invert(rc);
tag[k] = 0;
}
}
void Invert (int k, int l, int r, int L = 1, int R = n) {
if (l <= L && r >= R) {
Node_invert(k);
return;
}
Pushdown(k);
int mid = (L + R) >> 1;
if (l <= mid) {
Invert(lc, l, r, L, mid);
}
if (r > mid) {
Invert(rc, l, r, mid + 1, R);
}
Pushup(k);
}
#undef lc
#undef rc
}
int Calc (int t, LL x) {
LL b = d[t];
LL ival = ceil(b * 1.0 / t);
ival = (ival % Mod + Mod) % Mod;
int p = b % t;
int ans = 0;
ans = (ans + 1ll * ival * min(x, 0ll + p)) % Mod;
x -= p, b -= p;
if (x <= 0) return ans;
ans = (ans - (b / t) % Mod + Mod) % Mod;
ival = b / t;
LL g = x / t;
ans = (ans + 1ll * g * t % Mod * ((ival * 2 - g + 1 + Mod * 2) % Mod) % Mod * Inv) % Mod;
x %= t;
for (int k = 0; k <= x; ++k) {
LL x = ceil((b - k) * 1.0 / t) - g;
ans = (ans + x % Mod + Mod) % Mod;
}
return ans;
}
int main () {
// freopen("seg.in", "r", stdin);
// freopen("seg.out", "w", stdout);
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i], s[i] = s[i - 1] + a[i];
}
Seg::Build(1);
int t = 0;
for (int i = 1; i <= n; ++i) {
D ret = Seg::mx[1];
if (ret.ans <= 0) break;
t = i;
d[i] = d[i - 1] + ret.ans;
Seg::Invert(1, ret.l, ret.r);
}
vector<int> v;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] >= 0) {
++cnt;
}
else {
v.push_back(a[i]);
}
}
for (int i = t + 1; i <= cnt; ++i) {
d[i] = d[i - 1];
}
sort(v.begin(), v.end());
for (int i = cnt + 1; i <= n; ++i) {
d[i] = d[i - 1] + v.back();
v.pop_back();
}
for (int i = 1; i < n; ++i) {
p[i] = (i + 1) * d[i] - i * d[i + 1];
}
p[n] = Inf;
cin >> k;
int ans = 0;
for (int i = 1; i <= n; ++i) {
LL l = p[i - 1] + 1, r = min(p[i], k);
if (l <= r)
ans = (0ll + ans + Calc(i, r) - Calc(i, l - 1) + Mod) % Mod;
}
cout << (ans + Mod) % Mod << '\n';
return 0;
}
QOJ 1263 Keep It Cool
我们考虑如何刻画 \((a, c)\) 出现在 \((a, b)\) 和 \((b, c)\) 之间的条件：构造一个 \(1 \sim n\) 的排列 \(p\)，按照所有有序数对 \((a, b)\) 出现的位置，依次对排列执行交换值为 \(a\) 和值为 \(b\) 的元素，要求 \(a\) 和 \(b\) 在 \(p\) 中相邻，且 \(a\) 出现在 \(b\) 左侧。
那么一个有序数对构成的排列合法当且仅当：
- 执行完所有交换操作后，排列由 \([1, 2, \ldots, n]\) 变为 \([n, n - 1, \ldots, 1]\)。
我们发现，\((a, c)\) 出现在 \((a, b)\) 和 \((b, c)\) 之间的条件被隐式的描述了，若 \((a, c)\) 在 \((a, b), (b, c)\) 之前，那么交换 \(a\) 和 \(b\) 时它们不可能相邻，出现在它们之后也是同理的。
现在我们证明上面所说的是充要条件：
-
必要性：若排列最终没有变为 \([n, n - 1, \ldots, 1]\)，说明它的逆序对数一定小于 \(\frac{n(n - 1)}{2}\)，由于初始时逆序对数为 \(0\)，并且恰好执行 \(\frac{n(n - 1)}{2}\) 次交换操作，所以一定存在某一次交换了一个逆序对使其变为正序，那么此时 \(a > b\)，有序数对 \((a, b)\) 显然是不合法的。
-
充分性：若排列最终变成了 \([n, n - 1, \ldots, 1]\)，它一定满足每次交换一个正序对，那么所用到的 \(\frac{n(n - 1)}{2}\) 个数对互不相同，就构成了一个排列，并且根据前面的分析，他也满足所有 \((a, c)\) 出现在 \((a, b)\) 和 \((b, c)\) 之间，那么一种交换方案恰好对应一个有序数对的合法排列。
然后形如 \((a, b)\) 出现在 \((c, d)\) 前的条件如何表示？我们发现这个条件可以使得 \((a, b)\) 出现在 \((c, d)\) 后的状态不合法。对应到我们构造的排列 \(p\) 上，它可以表示为 \(p\) 中数字 \(a\) 和 \(b\) 构成正序对，而数字 \(c\) 和 \(d\) 构成逆序对，一旦发现这样的状态就舍弃即可。
接下来我们只关心排列，它只有 \(O(n!)\) 种，我们给每一个排列赋一个编号 \(S\)，设 \(f_{S}\) 表示进行了若干次合法操作，得到的排列为 \(S\) 的方案数，注意操作次数可以用 \(S\) 的逆序对数表示。首先检查 \(S\) 是否合法，然后转移枚举相邻的两个数交换即可。事实上取逆排列代码更好写。
Code
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
const int N = 12, S = 3628800 + 5;
const int Mod = 998244353;
int n, m;
int a[N * N], b[N * N], c[N * N], d[N * N], p[N], f[S], fac[N], pos[N];
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i;
}
iota(p + 1, p + n + 1, 1);
f[1] = 1;
int id = 0;
do {
++id;
for (int i = 1; i <= n; ++i) {
pos[p[i]] = i;
}
bool fl = 1;
for (int i = 1; i <= m; ++i) {
fl &= !(p[a[i]] < p[b[i]] && p[c[i]] > p[d[i]]);
}
if (!fl) {
f[id] = 0;
continue;
}
for (int i = 1; i < n; ++i) {
if (pos[i + 1] > pos[i]) {
int t = id + fac[n - pos[i]];
f[t] = (f[t] + f[id]) % Mod;
}
}
} while (next_permutation(p + 1, p + n + 1));
cout << f[id] << '\n';
return 0;
}