题面懒得写了。
A. Stop, Yesterday Please No More
袋鼠移动相当于边界和洞移动。通过模拟可以得出：不考虑洞，移动后剩余袋鼠的矩形。以及假设洞在原点，移动后形成的轨迹形状。
枚举洞在哪个位置，多干掉的袋鼠就是两个几何图形的交。由于洞的移动轨迹较复杂，我们考虑让它不动，改为移动袋鼠的矩形，这样只需要求一个二维前缀和。时间复杂度 \(\mathcal{O}(nm + s)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 2e3 + 5, M = 1e6 + 5;
bool Mbe;
int n, m, k, len, B = 1e3, a[N][N];
char s[M];
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {1, -1, 0, 0};
int type[200];
bool chk(int x, int y) {
return x >= -n && x <= n && y >= -m && y <= m;
}
void solve() {
cin >> n >> m >> k;
cin >> s + 1;
len = strlen(s + 1);
int nx = -1, ny = -1;
a[nx + B][ny + B] = 1;
int x1 = 0, y1 = 0;
int x2 = n - 1, y2 = m - 1;
int x3 = 0, y3 = 0;
int x4 = n - 1, y4 = m - 1;
bool ok = true;
auto chk2 = [&](int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
};
for (int i = 1; i <= len; i++) {
int c = type[s[i]];
nx += dx[c];
ny += dy[c];
// cerr << "(" << nx << ", " << ny << ")\n";
x1 += dx[c ^ 1];
y1 += dy[c ^ 1];
x2 += dx[c ^ 1];
y2 += dy[c ^ 1];
if (!chk2(x1, y1) && !chk2(x2, y2)) {
ok = false;
break;
} else {
auto upd = [&](int &x, int &y, int lim) {
if (x < 0) x = 0, y++;
if (x >= lim) x = lim - 1, y--;
};
upd(x1, x3, n);
upd(y1, y3, m);
upd(x2, x4, n);
upd(y2, y4, m);
// cerr << "(" << x1 << ", " << y1 << "), (" << x2 << ", " << y2 << ")\n";
}
if (chk(nx, ny)) a[nx + B][ny + B] = 1;
}
if (!ok) {
if (k == 0) cout << n * m << "\n";
else cout << "0\n";
} else {
int cnt = (x2 - x1 + 1) * (y2 - y1 + 1);
for (int i = -n; i <= n; i++)
for (int j = -m; j <= m; j++) {
a[i + B][j + B] += a[i - 1 + B][j + B] + a[i + B][j - 1 + B] - a[i - 1 + B][j - 1 + B];
}
int ans = 0;
auto qry = [&](int x1, int y1, int x2, int y2) {
return a[x2 + B][y2 + B] - a[x2 + B][y1 - 1 + B] - a[x1 - 1 + B][y2 + B] + a[x1 - 1 + B][y1 - 1 + B];
};
for (int i = -n; i <= -1; i++)
for (int j = -m; j <= -1; j++)
ans += qry(i + x3, j + y3, i + x4, j + y4) == cnt - k;
cout << ans << "\n";
}
for (int i = -n; i <= n; i++)
for (int j = -m; j <= m; j++)
a[i + B][j + B] = 0;
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
type['L'] = 0;
type['R'] = 1;
type['D'] = 2;
type['U'] = 3;
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
1
3 18 33
UDRLR
*/
B. Ropeway
首先单调队列优化 DP 预处理出前后缀的答案。修改后有两种情况：修改的这个点选上了，直接往两边枚举前后缀合并答案即可。如果修改的这个点没有被选，那么上一个被选的离修改位置一定不超过 \(k\)，同样容易枚举前后缀合并答案。总时间复杂度 \(\mathcal{O}(n + qk)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e6 + 5;
constexpr LL inf = 1e18;
bool Mbe;
int n, m, k, a[N], nxt[N], pre[N];
char s[N];
LL f[N], g[N], ans;
int q[N], hd, tl;
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
fill(f, f + n + 2, 0);
fill(g, g + n + 2, 0);
cin >> s + 1;
int t = -1;
hd = 1, tl = 0;
q[++tl] = 0;
for (int i = 1; i <= n + 1; i++) {
while (hd <= tl && q[hd] < i - k) hd++;
f[i] = f[q[hd]] + a[i];
pre[i] = t;
if (s[i] == '1') {
hd = tl + 1;
q[++tl] = i;
t = i;
} else {
while (hd <= tl && f[q[tl]] >= f[i] && s[q[tl]] == '0') tl--;
q[++tl] = i;
}
}
t = n + 2;
hd = 1, tl = 0;
q[++tl] = n + 1;
for (int i = n; i >= 0; i--) {
while (hd <= tl && q[hd] > i + k) hd++;
g[i] = g[q[hd]] + a[i];
nxt[i] = t;
if (s[i] == '1') {
hd = tl + 1;
q[++tl] = i;
t = i;
} else {
while (hd <= tl && g[q[tl]] >= g[i] && s[q[tl]] == '0') tl--;
q[++tl] = i;
}
}
cin >> m;
while (m--) {
int p, v;
cin >> p >> v;
LL L, R;
if (pre[p] >= max(1, p - k)) {
L = f[pre[p]];
} else {
L = inf;
for (int i = max(0, p - k); i < p; i++) L = min(L, f[i]);
}
if (nxt[p] <= min(n, p + k)) {
R = g[nxt[p]];
} else {
R = inf;
for (int i = min(n + 1, p + k); i > p; i--) R = min(R, g[i]);
}
ans = L + R + v;
if (s[p] == '0') {
LL mi = inf;
for (int i = max(0, p - k + 1), j = p + 1; i < p; i++) {
while (j <= i + k) mi = min(mi, g[j]), j++;
if (nxt[i] < p) continue;
LL val;
if (nxt[p] <= min(n, i + k)) val = g[nxt[p]];
else val = mi;
ans = min(ans, f[i] + val);
}
}
cout << ans << "\n";
}
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
C. Fabulous Fungus Frenzy
一句话题解：倒着做。
考虑从目标状态撤销操作得到能匹配初始状态的矩阵。交换操作与旋转操作均可逆，对于盖章操作，逆操作相当于将一个能与要盖的章匹配上的子矩阵全变为通配符。那你发现通配符肯定越多越好，所以贪心的能撤就撤就行了。
如果保证每次盖章操作至少新增一个通配符，盖章次数就不会超过 \(nm\) 次，符合 \(400\) 次盖章操作的限制。
不妨选定矩阵左上角进行盖章。通过交换操作使得左上角矩阵与要盖的章，使用操作将其全变成通配符。接下来每次移动一个章里有的字符到左上角矩阵对应位置，再进行盖章操作就能新增一个通配符。一直重复直到无法新增通配符。这个章之后也都用不上了。接下来找到下一个能盖的章，重复以上操作。
当所有的章都已经用不上时，检查当前矩阵每种字符的数量判断是否可能经过若干次交换操作后与初始矩阵进行匹配。如果可能匹配则有解，并构造交换方案，否则无解。简单分析一下可知操作数满足限制。在模拟过程中需要用一个数组动态维护当前矩阵中每种字符的个数，以及通配符的数量，总时间复杂度 \(\mathcal{O}(n^2m^2(n+m) + (nm + k^2) V)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 30, M = 62;
bool Mbe;
struct info {
int ty, x, y;
};
int n, m, k;
vector <info> ns;
int s[N][N], t[N][N];
pi siz[N];
int pat[N][N][N];
int sc[M + 5], tc[M + 5], pc[N][M + 5];
int trans(char c) {
if ('a' <= c && c <= 'z') return c - 'a' + 1;
if ('A' <= c && c <= 'Z') return 26 + c - 'A' + 1;
return 52 + c - '0' + 1;
}
void move(int sx, int sy, int tx, int ty) {
while (sx < tx) {
ns.push_back({ -3, sx, sy });
swap(t[sx][sy], t[sx + 1][sy]);
sx++;
}
while (sy < ty) {
ns.push_back({ -1, sx, sy });
swap(t[sx][sy], t[sx][sy + 1]);
sy++;
}
while (sx > tx) {
ns.push_back({ -4, sx, sy });
swap(t[sx][sy], t[sx - 1][sy]);
sx--;
}
while (sy > ty) {
ns.push_back({ -2, sx, sy });
swap(t[sx][sy], t[sx][sy - 1]);
sy--;
}
}
bool Med;
int main() {
// fprintf(stderr, "%.9lfMb\n", 1.0 * (&Mbe - &Med) / 1048576);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
s[i][j] = trans(c);
sc[s[i][j]]++;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
t[i][j] = trans(c);
tc[t[i][j]]++;
}
for (int z = 1; z <= k; z++) {
cin >> siz[z].fi >> siz[z].se;
for (int i = 1; i <= siz[z].fi; i++)
for (int j = 1; j <= siz[z].se; j++) {
char c;
cin >> c;
pat[z][i][j] = trans(c);
pc[z][pat[z][i][j]]++;
}
}
bool ok = true;
while (ok) {
ok = false;
for (int z = 1; z <= k; z++) {
int cur = 0;
for (int i = 1; i <= M; i++) {
cur += min(pc[z][i], tc[i]);
}
if (cur == 0) continue;
if (cur + tc[0] < siz[z].fi * siz[z].se) continue;
ok = true;
for (int i = 1; i <= siz[z].fi; i++)
for (int j = 1; j <= siz[z].se; j++) {
int need = pat[z][i][j];
int nx = -1, ny = -1;
for (int x = 1; x <= n && nx == -1; x++)
for (int y = 1; y <= m && ny == -1; y++) {
if ((x < i && y <= siz[z].se) || (x == i && y < j)) continue;
if (t[x][y] == need) nx = x, ny = y;
}
if (nx == -1) {
for (int x = 1; x <= n && nx == -1; x++)
for (int y = 1; y <= m && ny == -1; y++) {
if ((x < i && y <= siz[z].se) || (x == i && y < j)) continue;
if (t[x][y] == 0) nx = x, ny = y;
}
}
move(nx, ny, i, j);
tc[t[i][j]]--;
t[i][j] = 0;
tc[t[i][j]]++;
}
ns.push_back({ z, 1, 1 });
}
}
ok = true;
for (int i = 1; i <= M; i++) ok &= sc[i] >= tc[i];
if (!ok) return cout << "-1\n", 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int need = s[i][j];
int nx = -1, ny = -1;
for (int x = 1; x <= n && nx == -1; x++)
for (int y = 1; y <= m && ny == -1; y++) {
if (x < i || (x == i && y < j)) continue;
if (t[x][y] == need) nx = x, ny = y;
}
if (nx == -1) {
for (int x = 1; x <= n && nx == -1; x++)
for (int y = 1; y <= m && ny == -1; y++) {
if (x < i || (x == i && y < j)) continue;
if (t[x][y] == 0) nx = x, ny = y;
}
}
assert(nx != -1);
move(nx, ny, i, j);
}
reverse(ns.begin(), ns.end());
cout << (int)ns.size() << "\n";
for (auto [ty, x, y] : ns) cout << ty << " " << x << " " << y << "\n";
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
4 8 4
11122222
33344444
55556666
77777777
NIxSHUOx
DExDUIxx
DANxSHIx
YUANSHEN
2 3
NIy
DEx
3 8
zzzzzzzz
DANNSH9I
YUA9SHEN
1 1
x
2 5
SHO8y
DUUI8
*/
D. Chat Program
二分第 \(k\) 大，令 \(\geq k\) 的元素为 \(1\)，\(< k\) 的元素为 \(0\)，转化为判定是否能够通过至多一次操作使得使序列中 \(1\) 的数量大于等于 \(k\)。
考虑操作对一个位置的影响，容易发现如果最后某个位置上是 \(1\)，可能的起点是一个区间，并且能够 \(\mathcal{O}(1)\) 求出。差分前缀和一下就能算出每个起点有多少个 \(1\)，时间复杂度 \(\mathcal{O}(n \log A)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e6 + 5;
constexpr LL inf = 1e18;
bool Mbe;
int n, k, m, a[N];
LL c, d, ans;
int s[N];
bool check(LL mid) {
int cnt = 0;
fill(s + 1, s + n + 1, 0);
for (int i = 1; i <= n; i++) {
if (a[i] >= mid) cnt++;
else {
LL need;
if (d == 0) {
if (mid - a[i] <= c) {
int l = max(i - m + 1, 1);
int r = i;
s[l]++, s[r + 1]--;
}
continue;
}
if (mid - a[i] <= c) need = 0;
else need = (mid - a[i] - c) / d + ((mid - a[i] - c) % d != 0);
if (need < min(m, i)) {
int l = max(i - m + 1, 1);
int r = i - need;
// if (mid == 5) cerr << l << " " << r << "\n";
s[l]++, s[r + 1]--;
}
}
}
int mx = 0;
for (int i = 1; i <= n; i++) s[i] += s[i - 1], mx = max(mx, s[i]);
cnt += mx;
return cnt >= k;
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k >> m >> c >> d;
int mx = 0;
for (int i = 1; i <= n; i++) cin >> a[i], mx = max(mx, a[i]);
LL l = 0, r = c + m * d + mx;
while (l <= r) {
LL mid = (l + r) >> 1;
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
cout << ans << "\n";
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
6 4 3 1 2
1 1 4 5 1 4
*/
E. Color the Tree
这题做的没 G 久，流汗黄豆。
注意到每一层节点是独立的。先考虑单独一层怎么做，设当前考虑的层深度为 \(D\)。显然有一个 DP，设 \(f_u\) 为 \(u\) 子树内的答案，\(d_u\) 为 \(u\) 的深度，则有 \(f_u = \min( a_{D - d_u}\ , \sum \limits_{v \in \text{son}_u} f_v )\)，即考虑在不在 \(u\) 做一次操作。
然后你发现每次可以建虚树做 DP，在一条链上做操作的最小代价只需要求一个 \(a\) 的区间 \(\min\)，预处理 ST 表即可 \(\mathcal{O}(1)\) 转移。总时间复杂度 \(\mathcal{O}(n \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 2e6 + 5;
constexpr LL inf = 1e18;
bool Mbe;
int n, a[N];
vector <int> e[N], t[N];
int f[N][20], dep[N], dfn[N], tim;
void dfs(int u, int ff) {
dfn[u] = ++tim;
dep[u] = dep[ff] + 1;
f[u][0] = ff;
for (int i = 1; i <= 19; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (auto v : e[u]) {
if (v == ff) continue;
dfs(v, u);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 19; i >= 0; i--)
if (dep[f[x][i]] >= dep[y]) x = f[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; i--)
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
return f[x][0];
}
int g[N][20];
int qry(int l, int r) {
int t = log2(r - l + 1);
return min(g[l][t], g[r - (1 << t) + 1][t]);
}
vector <int> buc[N];
int stk[N], tp, par[N]; LL dp[N];
void calc(int u, int d) {
if (t[u].empty()) {
dp[u] = qry(d - dep[u], d - dep[par[u]] - 1);
return;
}
LL val = 0;
for (auto v : t[u]) calc(v, d), val += dp[v];
dp[u] = val;
val = qry(d - dep[u], d - dep[par[u]] - 1);
dp[u] = min(dp[u], val);
}
bool cmp(int i, int j) {
return dfn[i] < dfn[j];
}
LL solve(int d) {
tp = 0;
for (auto x : buc[d]) stk[++tp] = x;
sort(stk + 1, stk + tp + 1, cmp);
for (int i = 2; i <= tp; i++) {
int r = lca(stk[i - 1], stk[i]);
if (r != stk[i - 1] && r != stk[i]) stk[++tp] = r;
}
sort(stk + 1, stk + tp + 1);
tp = unique(stk + 1, stk + tp + 1) - stk - 1;
sort(stk + 1, stk + tp + 1, cmp);
for (int i = 2; i <= tp; i++) {
int r = lca(stk[i], stk[i - 1]);
t[r].emplace_back(stk[i]);
par[stk[i]] = r;
}
par[1] = 0;
calc(1, d);
LL res = dp[1];
// cout << d << " : " << res << "\n";
for (int i = 1; i <= tp; i++) {
int x = stk[i];
t[x].clear();
dp[x] = par[x] = 0;
}
return res;
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i], g[i][0] = a[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
for (int j = 1; j <= 19; j++)
for (int i = 0; i + (1 << j) < n; i++) {
g[i][j] = min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
}
dfs(1, 0);
LL ans = 0;
int mx = 0;
for (int i = 1; i <= n; i++) {
buc[dep[i]].emplace_back(i);
mx = max(mx, dep[i]);
}
for (int i = 2; i <= mx; i++) buc[i].emplace_back(1);
for (int i = 1; i <= mx; i++) ans += solve(i);
tim = 0;
for (int i = 1; i <= n; i++) {
buc[i].clear();
e[i].clear();
dep[i] = dfn[i] = 0;
}
cout << ans << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
3
4
10 15 40 1
1 2
2 3
2 4
5
10 5 1 100 1000
1 2
2 3
2 4
4 5
4
1000 200 10 8
1 2
2 3
3 4
*/
G. Inscryption
这题做的比 E 久，流汗黄豆。
进行第一种事件后，答案的分子和分母都加 \(1\)，很不牛。进行第二种事件后，答案的分母减 \(1\)，很牛。那么显然我们要在合法的前提下，尽可能进行第二种事件。
如果确定了第一种事件的数量，那么显然越早越好，于是考虑贪心，先全都填成 \(-1\)，然后从前往后依次改成 \(1\)，如果当前所有前缀和都 \(\geq 0\) 就结束。用线段树维护前缀和的 \(\min\) 即可，时间复杂度 \(\mathcal{O}(n \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e6 + 5;
constexpr LL inf = 1e18;
bool Mbe;
int n, a[N], s[N];
struct SGT {
#define m ((l + r) >> 1)
int tr[N << 2], add[N << 2];
void push_tag(int x, int v) {
tr[x] += v, add[x] += v;
}
void push_down(int x) {
if (add[x]) push_tag(x << 1, add[x]), push_tag(x << 1 | 1, add[x]), add[x] = 0;
}
void build(int x, int l, int r) {
tr[x] = add[x] = 0;
if (l == r) return tr[x] = s[l], void();
build(x << 1, l, m), build(x << 1 | 1, m + 1, r);
tr[x] = min(tr[x << 1], tr[x << 1 | 1]);
}
void mdf(int x, int l, int r, int ql, int qr, int v) {
if (ql <= l && qr >= r) return push_tag(x, v);
push_down(x);
if (ql <= m) mdf(x << 1, l, m, ql, qr, v);
if (qr > m) mdf(x << 1 | 1, m + 1, r, ql, qr, v);
tr[x] = min(tr[x << 1], tr[x << 1 | 1]);
}
int qry(int x, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return tr[x];
push_down(x);
if (qr <= m) return qry(x << 1, l, m, ql, qr);
if (ql > m) return qry(x << 1 | 1, m + 1, r, ql, qr);
return min(qry(x << 1, l, m, ql, qr), qry(x << 1 | 1, m + 1, r, ql, qr));
}
#undef m
} sgt;
void solve() {
cin >> n;
vector <int> tmp;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (!a[i]) tmp.emplace_back(i), a[i] = -1;
}
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
sgt.build(1, 1, n);
for (auto i : tmp) {
if (sgt.tr[1] >= 0) break;
a[i] = 1;
sgt.mdf(1, 1, n, i, n, 2);
}
if (sgt.tr[1] < 0) return cout << "-1\n", void();
int p = 1, q = 1;
for (int i = 1; i <= n; i++) {
if (a[i] == 1) p += 1, q += 1;
if (a[i] == -1) q -= 1;
}
int r = __gcd(p, q);
p /= r;
q /= r;
cout << p << " " << q << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
1
9
0 1 0 -1 -1 0 -1 0 1
*/
H. Factories Once More
任选一个点为根，对于一条连接 \(u\) 和 \(fa_u\) 的权值为 \(w_u\) 的边，如果 \(u\) 的子树内选了 \(i\) 个关键点，那么这条边的贡献是 \(w_u \cdot i (k − i)\)。
据此容易写出一个 DP：设 \(f_{u,i}\) 表示以 \(u\) 为根的子树里选了 \(i\) 个关键点时子树里每条边贡献之和的最大值，每次背包合并子树即可。
注意到 \(w_u \cdot i(k-i)\) 是上凸的，因此可以归纳证明 \(f_u\) 上凸，那么我们可以启发式合并求出每个 \(f_u\) 的差分数组。由于需要全局加上函数 \(w_u \cdot i(k-i)\)，需要支持给差分数组加一个等差数列的操作，使用 FHQ-Treap 维护并启发式合并即可。时间复杂度 \(\mathcal{O}(n \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e6 + 5;
bool Mbe;
int n, k;
vector <pi> e[N];
mt19937 Rand(chrono :: system_clock :: now().time_since_epoch().count());
struct FHQ_Treap {
int lc[N], rc[N], rnd[N];
LL val[N], k[N], b[N];
int siz[N], tot;
stack <int> s;
int create(LL v) {
int p = s.empty() ? ++tot : s.top();
if (!s.empty()) s.pop();
k[p] = b[p] = lc[p] = rc[p] = 0;
val[p] = v, siz[p] = 1, rnd[p] = Rand();
return p;
}
void push_up(int p) {
siz[p] = siz[lc[p]] + siz[rc[p]] + 1;
}
void push_tag(int p, LL K, LL B) {
val[p] += K * (siz[lc[p]] + 1) + B;
k[p] += K, b[p] += B;
}
void push_down(int p) {
if (k[p] || b[p]) {
if (lc[p]) push_tag(lc[p], k[p], b[p]);
if (rc[p]) push_tag(rc[p], k[p], k[p] * (siz[lc[p]] + 1) + b[p]);
k[p] = b[p] = 0;
}
}
void split(LL v, int p, int &x, int &y) {
if (!p) x = y = 0;
else {
push_down(p);
if (v > val[p]) {
y = p;
split(v, lc[p], x, lc[p]);
} else {
x = p;
split(v, rc[p], rc[p], y);
}
push_up(p);
}
}
int merge(int x, int y) {
if (!x || !y) return x + y;
push_down(x), push_down(y);
if (rnd[x] < rnd[y]) {
rc[x] = merge(rc[x], y);
push_up(x);
return x;
} else {
lc[y] = merge(x, lc[y]);
push_up(y);
return y;
}
}
void flatten(int p, vector <LL> &v) {
s.push(p);
push_down(p);
if (lc[p]) flatten(lc[p], v);
v.push_back(val[p]);
if (rc[p]) flatten(rc[p], v);
}
void insert(int &p, LL v) {
int x, y;
split(v, p, x, y);
p = merge(merge(x, create(v)), y);
}
} t;
int root[N], siz[N];
void dfs(int u, int ff) {
siz[u] = 1;
int son = 0;
for (auto [v, w] : e[u]) {
if (v == ff) continue;
dfs(v, u);
t.push_tag(root[v], -2LL * w, 1LL * w * (k + 1));
siz[u] += siz[v];
if (siz[v] > siz[son]) son = v;
}
if (son) root[u] = root[son];
t.insert(root[u], 0);
for (auto [v, w] : e[u]) {
if (v == ff || v == son) continue;
vector <LL> val;
t.flatten(root[v], val);
for (LL z : val) t.insert(root[u], z);
}
}
bool Med;
int main() {
// fprintf(stderr, "%.9lfMb\n", 1.0 * (&Mbe - &Med) / 1048576);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
int rt = 1;
dfs(rt, 0);
LL ans = 0;
vector <LL> val;
t.flatten(root[rt], val);
for (int i = 1; i <= k; i++) {
ans += val[i - 1];
}
cout << ans << "\n";
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
6 3
1 2 3
2 3 2
2 4 1
1 5 2
5 6 3
*/
I. Perfect Palindrome
完美回文当且仅当全相同，枚举一下最后是什么字符，统计一下数量即可。时间复杂度 \(\mathcal{O}(n + c)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e5 + 5;
constexpr LL inf = 1e18;
bool Mbe;
int n, cnt[26];
char s[N];
void solve() {
cin >> s + 1;
n = strlen(s + 1);
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++) cnt[s[i] - 'a']++;
int mx = 0;
for (int i = 0; i < 26; i++) mx = max(mx, cnt[i]);
cout << n - mx << "\n";
}
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
J. Perfect Matching
感觉很牛。
当 \(i − a_i = j − a_j\) 或 \(i + a_i = j + a_j\) 时，\(i\) 和 \(j\) 有连边。构建这样一个二分图：每个 \(i\) 可以看做是一条边，这条边连接二分图左边编号为 \((i − a_i)\) 的点，以及右边编号为 \((i + a_i)\) 的点。此时 \(i\) 和 \(j\) 能匹配当且仅当它们在二分图里对应的边有公共顶点。问题转化成将一张图分解成若干条边不相交（点可以相交）的长度为 \(2\) 的链。
对于每个连通分量，如果它含有奇数条边，无解。否则求出任意一棵 DFS 树，然后从深到浅考虑每一个点。找到所有和它相连的未被匹配的边，除了它连向父亲的边（这条边显然未被匹配）。如果这些边是偶数条，两两匹配即可，连向父亲的边会在处理父亲时被匹配上。如果这些边是奇数条，就把连向父亲的边也加入匹配。
时间复杂度 \(\mathcal{O}(n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 5e5 + 5;
bool Mbe;
int n, a[N], cnt, t[N], sz[N]; pi par[N]; bool mark[N];
map <int, int> vis[2];
set <pi> e[N], g[N];
vector <pi> ns;
int find(int x) {
return x == t[x] ? x : t[x] = find(t[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
sz[y]++;
if (x != y) t[x] = y, sz[y] += sz[x];
}
int getid(int x, int c) {
if (vis[c].count(x)) return vis[c][x];
vis[c][x] = ++cnt;
t[cnt] = cnt, sz[cnt] = 0;
return cnt;
}
void dfs(int u) {
mark[u] = 1;
for (auto [v, id] : e[u]) {
if (mark[v]) continue;
par[v] = make_pair(u, id);
e[v].erase(make_pair(u, id));
g[u].insert(make_pair(v, id));
dfs(v);
}
}
void construct(int u) {
for (auto [v, id] : g[u]) {
construct(v);
}
queue <int> q;
for (auto [v, id] : e[u]) {
q.push(id);
if (v != u && e[v].find(make_pair(u, id)) != e[v].end()) {
e[v].erase(make_pair(u, id));
}
}
if (q.size() & 1) {
int v = par[u].fi;
int id = par[u].se;
q.push(id);
e[v].erase(make_pair(u, id));
}
while (!q.empty()) {
int u = q.front(); q.pop();
int v = q.front(); q.pop();
ns.emplace_back(u, v);
}
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
int u = i - a[i];
int v = i + a[i];
u = getid(u, 0);
v = getid(v, 1);
merge(u, v);
e[u].insert(make_pair(v, i));
e[v].insert(make_pair(u, i));
}
bool ok = true;
for (int i = 1; i <= cnt; i++)
if (t[i] == i) {
if (sz[i] & 1) {
ok = false;
break;
}
dfs(i);
construct(i);
}
if (ok) {
cout << "Yes\n";
for (auto [u, v] : ns) cout << u << " " << v << "\n";
} else cout << "No\n";
for (int i = 1; i <= cnt; i++) {
e[i].clear();
g[i].clear();
mark[i] = 0, par[i] = make_pair(0, 0);
}
cnt = 0;
for (int i = 0; i < 2; i++) vis[i].clear();
ns.clear();
}
bool Med;
int main() {
// fprintf(stderr, "%.9lfMb\n", 1.0 * (&Mbe - &Med) / 1048576);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7
*/
L. Proposition Composition
有几种情况：
- 存在至少一条割边。
- 一条链边，一条非链边。
- 两条链边。
第二种情况要求链边恰好被一条非链边覆盖。前两种情况容易使用线段树维护被覆盖 \(0\) 次和 \(1\) 次的链边计算答案。
考虑如何维护第三种情况。此时要求这两条边被覆盖的情况相同。我们用双向链表把所有被覆盖情况完全相同的链边串在一起。那么每次加入一条额外边时，本质是有些双向链表需要被切开。
注意到被切开的位置始终是某个边本身被覆盖，且和它的前驱（或后继）没有被覆盖的情况。我们用线段树维护区间最远前驱和最远后继，就能 \(\mathcal{O}(cnt \log n)\) 地找到所有被切开的位置，其中 \(cnt\) 是被切的位置数量。由于每次被切会增加双向链表的数量，且最多只有 \(n − 1\) 条链（每个链边单独一条），因此这里复杂度为 \(\mathcal{O}(n \log n)\)。
注意双向链表有中间某段被切出来的情况，此时两个切点都会被上述线段树找到。总时间复杂度 \(\mathcal{O}(n \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e6 + 5;
constexpr int the_answer_to_life_the_universe_and_everything = 42;
bool Mbe;
int n, m;
int pre[N], nxt[N], siz[N], root[N], bel[N], tot;
LL cnt;
struct SGT {
struct dat {
int mn, mx;
int cnt[2], tag;
} t[N << 2];
#define ls x << 1
#define rs x << 1 | 1
#define m ((l + r) >> 1)
void push_tag(int x, int v) {
if (v == 1) {
t[x].cnt[1] = t[x].cnt[0], t[x].cnt[0] = 0;
} else {
t[x].cnt[1] = t[x].cnt[0] = 0;
}
t[x].tag += v;
}
void push_down(int x) {
if (t[x].tag) {
push_tag(ls, t[x].tag);
push_tag(rs, t[x].tag);
t[x].tag = 0;
}
}
void push_up(int x) {
t[x].mn = min(t[ls].mn, t[rs].mn);
t[x].mx = max(t[ls].mx, t[rs].mx);
t[x].cnt[0] = t[ls].cnt[0] + t[rs].cnt[0];
t[x].cnt[1] = t[ls].cnt[1] + t[rs].cnt[1];
}
void build(int x, int l, int r) {
t[x].tag = 0;
if (l == r) {
t[x].cnt[0] = 1, t[x].cnt[1] = 0;
t[x].mn = pre[l], t[x].mx = nxt[l];
return;
}
build(ls, l, m);
build(rs, m + 1, r);
push_up(x);
}
void add(int x, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) {
push_tag(x, 1);
return;
}
push_down(x);
if (ql <= m) add(ls, l, m, ql, qr);
if (qr > m) add(rs, m + 1, r, ql, qr);
push_up(x);
}
void findL(int x, int l, int r, int ql, int qr, int v, vector <pi> &p) {
if (t[x].mn >= v) return;
if (l == r) {
p.emplace_back(bel[l], l);
return;
}
push_down(x);
if (ql <= m) findL(ls, l, m, ql, qr, v, p);
if (qr > m) findL(rs, m + 1, r, ql, qr, v, p);
}
void findR(int x, int l, int r, int ql, int qr, int v, vector <pi> &p) {
if (t[x].mx <= v) return;
if (l == r) {
p.emplace_back(bel[nxt[l]], nxt[l]);
return;
}
push_down(x);
if (ql <= m) findR(ls, l, m, ql, qr, v, p);
if (qr > m) findR(rs, m + 1, r, ql, qr, v, p);
}
void mdf_pre(int x, int l, int r, int p, int v) {
if (l == r) {
pre[l] = t[x].mn = v;
return;
}
push_down(x);
if (p <= m) mdf_pre(ls, l, m, p, v);
else mdf_pre(rs, m + 1, r, p, v);
push_up(x);
}
void mdf_nxt(int x, int l, int r, int p, int v) {
if (l == r) {
nxt[l] = t[x].mx = v;
return;
}
push_down(x);
if (p <= m) mdf_nxt(ls, l, m, p, v);
else mdf_nxt(rs, m + 1, r, p, v);
push_up(x);
}
#undef ls
#undef rs
#undef m
} sgt;
LL calc(int m) {
LL ans = 0;
int zero = sgt.t[1].cnt[0], one = sgt.t[1].cnt[1];
ans += 1LL * zero * (n + m - zero);
ans += one;
ans += cnt;
return ans;
}
void connect(int x, int y) {
sgt.mdf_nxt(1, 1, n, x, y);
sgt.mdf_pre(1, 1, n, y, x);
}
void split(int x) {
int y = pre[x];
sgt.mdf_pre(1, 1, n, x, x);
sgt.mdf_nxt(1, 1, n, y, y);
}
void create(vector <int> t) {
tot++;
root[tot] = t[0];
siz[tot] = t.size();
for (auto x : t) bel[x] = tot;
}
LL bin(int x) {
return 1LL * x * (x - 1) / 2;
}
void cut(int p, int l) {
cnt -= bin(siz[p]);
vector <int> v1, v2;
int p1 = root[p], p2 = l;
while (true) {
v1.push_back(p1);
v2.push_back(p2);
int np1 = nxt[p1] == l ? p1 : nxt[p1];
int np2 = nxt[p2];
if (np1 == p1) {
create(v1);
root[p] = l;
siz[p] -= v1.size();
break;
} else if (np2 == p2) {
create(v2);
siz[p] -= v2.size();
break;
} else {
p1 = np1;
p2 = np2;
}
}
split(l);
cnt += bin(siz[p]) + bin(siz[tot]);
}
void cut(int p, int l, int r) {
cnt -= bin(siz[p]);
vector <int> v1, v2;
int p1 = root[p], p2 = l;
while (true) {
v1.push_back(p1);
v2.push_back(p2);
int np1 = nxt[p1] == l ? r : nxt[p1];
int np2 = nxt[p2] == r ? p2 : nxt[p2];
if (np1 == p1) {
create(v1);
root[p] = l;
siz[p] -= v1.size();
break;
} else if (np2 == p2) {
create(v2);
siz[p] -= v2.size();
break;
} else {
p1 = np1;
p2 = np2;
}
}
int tmp = pre[l];
split(l);
split(r);
connect(tmp, r);
cnt += bin(siz[p]) + bin(siz[tot]);
}
void solve() {
cin >> n >> m;
if (n == 1) {
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
cout << "0\n";
}
return;
}
n -= 1;
tot = 1;
cnt = bin(n);
root[1] = 1;
nxt[n] = n, pre[1] = 1;
siz[1] = n;
fill(bel + 1, bel + n + 1, 1);
for (int i = 1; i < n; i++) {
nxt[i] = i + 1;
pre[i + 1] = i;
}
sgt.build(1, 1, n);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
if (u == v) {
cout << calc(i) << "\n";
continue;
}
if (u > v) swap(u, v);
v--;
sgt.add(1, 1, n, u, v);
vector <pi> pt;
sgt.findL(1, 1, n, u, v, u, pt);
sgt.findR(1, 1, n, u, v, v, pt);
sort(pt.begin(), pt.end());
for (int i = 0; i < pt.size(); i++) {
if (i + 1 < pt.size() && pt[i].fi == pt[i + 1].fi) {
cut(pt[i].fi, pt[i].se, pt[i + 1].se);
i++;
} else {
cut(pt[i].fi, pt[i].se);
}
}
cout << calc(i) << "\n";
}
}
bool Med;
int main() {
// fprintf(stderr, "%.9lfMb\n", 1.0 * (&Mbe - &Med) / 1048576);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) solve();
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
3
4 3
2 4
4 2
3 3
7 3
3 4
1 2
1 7
6 4
1 3
4 6
2 5
3 4
*/
- Universal Contest Nanjing Stage Trialuniversal contest nanjing stage universal stage the 2nd contest spring round trial universal qingdao stage the universal stage 6555 good universal okayama stage the universal shenyang stage the universal shaanxi stage 6735 universal northern stage good universal stage hefei the