vp了一场gym，我又开心地划水了。
A. Coloring Roads
题意：给定一棵树，树边一开始都是无色的，每次操作可以把一个点到根的路径染成某个颜色，每次询问当前树上出现过某个次数的颜色种数。
题解：看到操作与$Access$类似，考虑使用$lct$解决。由于一条重链的颜色一定是相同的，也就是一棵$splay$中的颜色都是相同的，所以$Access$时每次把整棵$splay$修改掉算一下变化就好了。
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + ; int n, m, nq, edg;
int fe[N], cnt[N], ccnt[N];
vector<int> g[N]; void Change(int a, int b, int z) {
--ccnt[cnt[a]];
cnt[a] -= z;
++ccnt[cnt[a]];
--ccnt[cnt[b]];
cnt[b] += z;
++ccnt[cnt[b]];
} namespace T {
const int N = ::N * ;
int fa[N], lc[N], rc[N], si[N], co[N], lzy[N]; bool Is_root(int x) {
return lc[fa[x]] != x && rc[fa[x]] != x;
} bool Is_right(int x) {
return rc[fa[x]] == x;
} void U(int x, int _c) {
co[x] = lzy[x] = _c;
} void Up(int x) {
si[x] = x > n;
if (lc[x]) si[x] += si[lc[x]];
if (rc[x]) si[x] += si[rc[x]];
} void Down(int x) {
if (lzy[x]) {
if (lc[x]) U(lc[x], lzy[x]);
if (rc[x]) U(rc[x], lzy[x]);
lzy[x] = ;
}
} void Roll(int x) {
if (!Is_root(x)) Roll(fa[x]);
Down(x);
} void Rotate(int x) {
int y = fa[x], z = fa[y];
int d = Is_right(x), s = d? lc[x] : rc[x];
if (!Is_root(y)) (Is_right(y)? rc[z] : lc[z]) = x;
fa[x] = z;
(d? rc[y] : lc[y]) = s;
if (s) fa[s] = y;
(d? lc[x] : rc[x]) = y;
fa[y] = x;
Up(y), Up(x);
} void Splay(int x) {
Roll(x);
for (int y; !Is_root(x); Rotate(x)) {
if (!Is_root(y = fa[x])) {
Rotate(Is_right(y) == Is_right(x)? y : x);
}
}
} void Access(int x, int _c) {
for (int y = ; x; y = x, x = fa[x]) {
Splay(x);
Change(co[x], _c, si[x] - si[rc[x]]);
rc[x] = y;
Up(x);
U(x, _c);
}
} } void Dfs(int x, int ft) {
for (int v : g[x]) {
if (v == ft) continue;
fe[v] = ++edg;
T::fa[n + edg] = x;
T::fa[v] = n + edg;
Dfs(v, x);
}
} int main() {
scanf("%d%d%d", &n, &m, &nq);
for (int i = , x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
} cnt[] = n - ;
ccnt[n - ] = ;
ccnt[] += m; Dfs(, );
for (int i = ; i <= n + edg; ++i) {
T::Up(i);
} for (int u, c, z; nq--; ) {
scanf("%d%d%d", &u, &c, &z);
T::Access(u, c);
printf("%d\n", ccnt[z] - (cnt[] == z));
} return ;
}
B. Dev, Please Add This!
题意：给一个网格图，一个格子是空地或墙，空地上可能有星星。有且仅有一个空地上有一个球，每次可以把球往一个方向推，直到球碰到墙或边界。球经过一个星星就可以把那个星星吃掉，问能否吃掉所有星星。
题解：我们可以考虑每一行或每一列中的一段极长的空地，由于球可以在这一个条中来回滚动，所以可以把这个条看成一个状态。一个墙边的点可以看成是一个状态向另一个状态连单向边，特殊地，我们需要一个源点，其中源点需要向起点所在的行或列的极长条连边。此时大家可以闻到一点$2-sat$的气味。我们用布尔变量表示一个状态是否被经过，然后我们的限制有三种：1，如果一个格子是星星，那么这个格子所在的行或列的极长条中至少有一个是$1$；如果一个状态不能被起点到达，那它必须是$0$；如果两个状态中没有一个能到另一个，那它们不能同时为$1$。利用这些限制跑$2-sat$就可以了，因为这是满足题目要求的充要条件。很容易发现这些限制对于判断$NO$是必要的，不容易发现的是满足这些限制后就一定能构造出可行的方案。注意我们保证了每一对为$1$的状态其中至少存在一个可以到达另一个，我们把可以相互到达的状态缩成一个点后，构造一种方案就可以转化成如下一个问题：给定一个竞赛图，要求其中一条哈密顿路径，满足起点的入度为$0$。这是一个经典问题，贪心构造即可。
#include <bits/stdc++.h> using namespace std; const int N = ;
const int M = N * N; namespace G {
const int M = ::M * ;
int n, clk, cnm;
int dfn[M], low[M], col[M], st[M];
vector<int> g[M]; void Init(int _n) {
n = _n;
clk = cnm = *st = ;
for (int i = ; i <= n; ++i) {
dfn[i] = low[i] = col[i] = ;
g[i].clear();
}
} void Ade(int a, int b) {
assert( <= a && a <= n);
assert( <= b && b <= n);
g[a].push_back(b);
} void Tarjan(int x) {
dfn[x] = low[x] = ++clk;
st[++*st] = x;
for (int v : g[x]) {
if (!dfn[v]) {
Tarjan(v);
low[x] = min(low[x], low[v]);
} else if (!col[v]) {
low[x] = min(low[x], dfn[v]);
}
}
if (dfn[x] == low[x]) {
col[x] = ++cnm;
for (; st[*st] != x; --*st) {
col[st[*st]] = cnm;
}
--*st;
}
} void Main() {
for (int i = ; i <= n; ++i) {
if (!dfn[i]) {
Tarjan(i);
}
}
} } int n, m, bar;
char mp[N][N];
int belh[N][N], bell[N][N];
vector<int> link[M];
bitset<M> reach[M]; bool Good(int i, int j) {
return mp[i][j] == '*' || mp[i][j] == '.' || mp[i][j] == 'O';
} void Set(int x, int rt) {
reach[rt].set(x);
for (int v : link[x]) {
if (!reach[rt][v]) {
Set(v, rt);
}
}
} int main() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) {
scanf("%s", mp[i] + );
for (int j = ; j <= m; ++j) {
if (!Good(i, j - ) && Good(i, j)) {
belh[i][j] = ++bar;
} else if (Good(i, j)) {
belh[i][j] = bar;
}
}
} for (int j = ; j <= m; ++j) {
for (int i = ; i <= n; ++i) {
if (!Good(i - , j) && Good(i, j)) {
bell[i][j] = ++bar;
} else if (Good(i, j)) {
bell[i][j] = bar;
}
}
} for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
if (!Good(i, j)) continue;
if (!Good(i - , j) || !Good(i + , j)) {
link[bell[i][j]].push_back(belh[i][j]);
}
if (!Good(i, j - ) || !Good(i, j + )) {
link[belh[i][j]].push_back(bell[i][j]);
}
if (mp[i][j] == 'O') {
link[].push_back(belh[i][j]);
link[].push_back(bell[i][j]);
}
}
} for (int i = ; i <= bar; ++i) {
Set(i, i);
} G::Init(bar * );
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
if (mp[i][j] == '*') {
G::Ade(belh[i][j], bell[i][j] + bar);
G::Ade(bell[i][j], belh[i][j] + bar);
}
}
}
for (int i = ; i <= bar; ++i) {
if (!reach[][i]) {
G::Ade(bar + i, i);
}
}
for (int i = ; i <= bar; ++i) {
for (int j = i + ; j <= bar; ++j) {
if (!reach[i][j] && !reach[j][i]) {
G::Ade(bar + i, j);
G::Ade(bar + j, i);
}
}
} G::Main();
for (int i = ; i <= bar; ++i) {
if (G::col[i] == G::col[i + bar]) {
printf("NO\n");
return ;
}
}
printf("YES\n"); return ;
}
C. Dstorv
题意：数轴上排列着一些左箭头和右箭头，每个箭头都会以相同速度朝着各自方向移动。当一个左箭头和一个右箭头相遇时会有一个固定的概率$p$使得其中一方消失，问在无穷多的时间后留下恰好$a$个右箭头和$b$个左箭头的概率。
题解：容易发现对于每一种存活下来的可能方案，一定存在唯一一个分界线使得分界线以左的右箭头都被干掉了，分界线以右的左箭头都被干掉了。于是我们可以设计这样一个$dp$，用$f_{i,j}$表示考虑前$i$个箭头时，如果右边有$j$个左箭头过来时，有$b$个左箭头存活，没有右箭头存活的概率。初始时有$f_{0,b} = 1$，转移时如果$i$是左箭头，那$f_{i,j} = f_{i - 1, j + 1}$；如果是右箭头，那必然需要被干掉，枚举这个右箭头死之前干掉了几个来自右边的左箭头即可转移。同样设计$g_{i,j}$来表示有关于右箭头的。最后枚举分界线算答案，$ans = \sum\limits_{i = 0}^{n} f_{i, 0} * g_{i + 1, 0}$。
#include <bits/stdc++.h>
using namespace std;
namespace {
const int MOD = 1e9 + ;
int Add(int a, int b) { return (a += b) >= MOD? a - MOD : a; }
int Sub(int a, int b) { return (a -= b) < ? a + MOD : a; }
int Mul(int a, int b) { return (long long)a * b % MOD; }
int Pow(int a, int b) {
int r = ;
for (; b; b >>= , a = Mul(a, a)) if (b & ) r = Mul(r, a);
return r;
}
}
const int N = 5e3 + ;
int n, m, pr, pl, a, b;
char s[N];
int f[N][N], g[N][N];
int main() {
scanf("%d%d%d", &n, &pr, &pl);
scanf("%s%d%d", s + , &a, &b);
int wl = Mul(pr, Pow(Add(pl, pr), MOD - ));
int wr = Sub(, wl);
f[][b] = ;
for (int i = ; i <= n; ++i) {
if (s[i] == 'R') { // kill it
for (int j = ; j <= n; ++j) {
f[i][j] = Add(Mul(f[i - ][j], wl), Mul(f[i][j - ], wr));
}
} else {
for (int j = ; j < n; ++j) {
f[i][j] = f[i - ][j + ];
}
}
}
g[n + ][a] = ;
for (int i = n; i >= ; --i) {
if (s[i] == 'H') {
for (int j = ; j <= n; ++j) {
g[i][j] = Add(Mul(g[i + ][j], wr), Mul(g[i][j - ], wl));
}
} else {
for (int j = ; j < n; ++j) {
g[i][j] = g[i + ][j + ];
}
}
}
int ans = ;
for (int i = ; i <= n; ++i) {
ans = Add(ans, Mul(f[i][], g[i + ][]));
}
printf("%d\n", ans);
return ;
}
D. Dumae
题意：$n$个人要排成一排，每个人想要站的位置都是一个区间，同时还有一些形如“$x$必须站在$y$左边”的限制，构造一组方案。
题解：建出左右关系的拓扑图，每个人的右端点更新为他能走到的点的右端点的最小值$-1$。拓扑构造答案时每次贪心地在能选的人中选择右端点最左边的即可。
#include <bits/stdc++.h> using namespace std; const int N = 3e5 + ; int n, m;
bool vis[N];
int l[N], r[N], din[N], ans[N];
vector<int> g[N]; struct No {
int l, r, id;
friend bool operator < (No a, No b) {
return a.l > b.l;
}
}; int Sear(int x) {
if (vis[x]) {
return r[x];
}
vis[x] = ;
for (int v : g[x]) {
r[x] = min(r[x], Sear(v) - );
}
return r[x];
} int main() {
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) {
scanf("%d%d", &l[i], &r[i]);
}
for (int i = , x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
g[x].push_back(y);
++din[y];
} priority_queue<pair<int, int> > pq;
priority_queue<No> ready;
for (int i = ; i <= n; ++i) {
r[i] = Sear(i);
if (!din[i]) {
ready.push({ l[i], r[i], i });
}
} int now = ;
for (int x; ; ) {
while (!ready.empty() && ready.top().l <= now) {
No top = ready.top();
ready.pop();
pq.push({ -top.r, top.id });
} if (pq.empty()) {
break;
}
x = pq.top().second;
pq.pop();
if (r[x] < now) {
printf("-1\n");
return ;
} ans[now++] = x;
for (int v : g[x]) {
if (!(--din[v])) {
ready.push({ l[v], r[v], v });
}
}
} if (now <= n) {
printf("-1\n");
return ;
} for (int i = ; i <= n; ++i) {
printf("%d%c", ans[i], " \n"[i == n]);
} return ;
}
E. Electronic Circuit
题意：给一个无向图，判断能否选定一组源与汇使得它们之间的是简单电阻网络（即仅由串并联组成）。
题解：逆向考虑问题，把一个图按规则分解即可。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + ; int n, m, cnt;
bool del[N];
set<int> g[N]; void Del(int x) {
if (g[x].size() == ) {
del[x] = ;
--cnt;
int y = *g[x].begin();
int z = *g[x].rbegin();
g[y].erase(x);
g[z].erase(x);
g[y].insert(z);
g[z].insert(y);
if (!del[y]) Del(y);
if (!del[z]) Del(z);
}
} int main() {
scanf("%d%d", &n, &m);
for (int i = , x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
g[x].insert(y);
g[y].insert(x);
} cnt = n;
for (int i = ; i <= n; ++i) {
if (!del[i]) {
Del(i);
}
} printf(cnt == ? "Yes\n" : "No\n"); return ;
}
G. Fascination Street
题意：街道上有一排一开始都是灭的灯，要点亮其中的一部分灯使得每一盏灯要么被点亮，要么左右相邻的灯中有被点亮的。点亮每一盏灯有各自的代价，你还有$k$次机会交换其中的两盏灯。问最小代价。
题解：容易发现交换的一定是一盏亮的灯和一盏灭的灯。可以$dp$，设$f_{i,x,y,a,b}$表示考察了前$i$盏灯，最后两盏灯的亮灭状态分别为$x,y$，已经有$a$盏亮的灯被换走了，已经有$b$盏灭的灯被换上了的最小代价，只有四种转移：点灯；不点灯；点亮后被换走；不点从别的地方弄个灯过来。复杂度$O(nk^2)$。
#include <bits/stdc++.h> using namespace std; const int K = ;
const int N = 2.5e5 + ;
const long long INF = 1e17; int n, k;
int w[N];
long long dp[][][][K][K]; bool Chkmin(long long &a, long long b) {
return (a > b)? (a = b, ) : ();
} int main() {
scanf("%d%d", &n, &k);
for (int i = ; i <= n; ++i) {
scanf("%d", &w[i]);
} memset(dp, 0x3f, sizeof dp);
dp[][][][][] = ;
for (int i = ; i < n; ++i) {
int nxt = ~i & , pre = i & , val = w[i + ];
memset(dp[nxt], 0x3f, sizeof dp[nxt]);
for (int a = ; a <= k; ++a) { // to help
for (int b = ; b <= k; ++b) { // usd
for (int x = ; x < ; ++x) {
for (int y = ; y < ; ++y) {
if (dp[pre][x][y][a][b] > INF) continue;
Chkmin(dp[nxt][y][][a][b], dp[pre][x][y][a][b] + val);
if (x || y)
Chkmin(dp[nxt][y][][a][b], dp[pre][x][y][a][b]);
if (b < k)
Chkmin(dp[nxt][y][][a][b + ], dp[pre][x][y][a][b]);
if (a < k && (x || y))
Chkmin(dp[nxt][y][][a + ][b], dp[pre][x][y][a][b] + val);
}
}
}
}
} long long ans = INF;
for (int i = ; i <= k; ++i) {
for (int x = ; x < ; ++x) {
for (int y = ; y < ; ++y) {
if (x || y) {
ans = min(ans, dp[n & ][x][y][i][i]);
}
}
}
} printf("%lld\n", ans); return ;
}
K. Interesting Drug
题意：一条路上按顺序有 n 瓶毒药，对于每个$i \in [1, n]$，求出如下的值：从$i$出发，每个时刻都可以向左或向右，最终可以得到一个吃毒药的排列，一个排列的伤害定义为$\sum\limits_{j = 1}^{n} d_j[p_{c_j} = j]$，求可能的排列中最大的伤害值。
题解：很容易发现已经吃到的毒药可以表示成一个区间，就能想到一个$O(n^2)$的$dp$，即$f_{i, j}$表示当前已经吃到的毒药区间是$[i,j]$，吃完剩下的毒药的最大伤害是多少。转移是$O(1)$的，第$i$个答案就是$f_{i,i}+d_i[c_i = 1]$。如果把它放到一个二维平面上考虑，就可以把状态看成一个点，把转移看成一条带权的向左或向下的有向边，第$i$个答案就是$(1,n)$到$(i,i)$的最长路径。由于带权的边只有$2*n$条，可以考虑逐层转移，一条边的转移大概就是一个前缀取$max$的过程，用树状数组优化即可。
#include <bits/stdc++.h> using namespace std; const int N = 3e5 + ; int n;
int c[N], d[N];
long long t[N];
vector<int> row[N]; void Upd(int x, long long v) {
for (; x; x -= x & -x) {
t[x] = max(t[x], v);
}
} long long Ask(int x) {
long long r = ;
for (; x <= n; x += x & -x) {
r = max(r, t[x]);
}
return r;
} int main() {
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%d", &c[i]);
}
for (int i = ; i <= n; ++i) {
scanf("%d", &d[i]);
if (i >= c[i] && c[i] != ) {
row[i - c[i] + ].push_back(i);
}
} for (int i = ; i <= n; ++i) {
for (int j = row[i].size() - ; ~j; --j) {
int x = row[i][j];
Upd(x - , Ask(x) + d[x]);
}
printf("%lld%c", Ask(i) + (c[i] == ? d[i] : ), " \n"[i == n]);
if (i + c[i] - <= n) {
Upd(i + c[i] - , Ask(i + c[i] - ) + d[i]);
}
} return ;
}