题意：给你一棵树，每个点被染成了k种颜色之一或者没有颜色。你要切断恰k - 1条边使得不存在两个异色点在同一连通块内。求方案数。
解：对每颜色构建最小斯坦纳树并判交。我用的树上差分实现。
然后把同一颜色的点缩成一个点，在新树上树形DP，fx表示x子树内，x所在连通块内有一个关键点的方案数。hx表示x所在连通块内没有关键点的方案数。
#include <bits/stdc++.h>
const int N = , MO = ;
struct Edge {
int nex, v, len;
};
int n, m, col[N], pw[N << ], fr[N], imp[N], K, stk[N], top, f[N], h[N];
std::vector<int> v[N];
inline void ERR() {
puts("");
exit();
return;
}
struct G {
Edge edge[N << ]; int tp;
int e[N], d[N], fa[N], pos[N], num, ST[N << ][];
G(){}
inline void add(int x, int y, int z = ) {
edge[++tp].v = y;
edge[tp].len = z;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void DFS_1(int x, int f) {
d[x] = d[f] + ;
fa[x] = f;
pos[x] = ++num;
ST[num][] = x;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) continue;
DFS_1(y, x);
ST[++num][] = x;
}
return;
}
inline void pre1(int x = ) {
DFS_1(x, );
return;
}
inline void lcapre() {
for(int j = ; j <= pw[num]; j++) {
for(int i = ; i + ( << j) - <= num; i++) {
if(d[ST[i][j - ]] < d[ST[i + ( << (j - ))][j - ]]) {
ST[i][j] = ST[i][j - ];
}
else {
ST[i][j] = ST[i + ( << (j - ))][j - ];
}
}
}
return;
}
inline int lca(int x, int y) {
x = pos[x];
y = pos[y];
if(x > y) std::swap(x, y);
int t = pw[y - x + ];
if(d[ST[x][t]] < d[ST[y - ( << t) + ][t]]) {
return ST[x][t];
}
else {
return ST[y - ( << t) + ][t];
}
}
int recol(int x) {
int Col = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa[x]) {
continue;
}
int c = recol(y);
if(c && Col && c != Col) {
ERR();
}
if(c && !Col) {
Col = c;
}
}
if(col[x]) {
if(Col && col[x] != Col) {
ERR();
}
else {
Col = col[x];
}
}
col[x] = Col;
if(fr[x]) {
Col = ;
}
return Col;
}
inline int build_t(G &gr) {
/*printf("build virtue tree \n");
for(int i = 1; i <= K; i++) printf("%d ", imp[i]);
puts("\n");*/
stk[top = ] = imp[];
for(int i = ; i <= K; i++) {
int x = imp[i], y = lca(x, stk[top]);
while(top > && pos[y] <= pos[stk[top - ]]) {
gr.add(stk[top - ], stk[top], d[stk[top]] - d[stk[top - ]]);
top--;
}
if(y != stk[top]) {
gr.add(y, stk[top], d[stk[top]] - d[y]);
stk[top] = y;
}
stk[++top] = x;
}
while(top > ) {
gr.add(stk[top - ], stk[top], d[stk[top]] - d[stk[top - ]]);
top--;
}
return stk[top];
}
int cal(int x) {
int ans = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
int t = cal(y);
ans = 1ll * ans * t % MO * edge[i].len % MO;
}
return ans;
}
void DP(int x, int father) {
f[x] = col[x] ? : ;
h[x] = col[x] ? : ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == father) continue;
DP(y, x);
///
int t, t2;
t = 1ll * f[x] * (f[y] + h[y]) % MO + 1ll * f[y] * h[x] % MO;
t2 = 1ll * h[x] * (h[y] + f[y]) % MO;
f[x] = t % MO;
h[x] = t2;
}
//printf("x = %d f[x] = %d h[x] = %d \n", x, f[x], h[x]);
return;
}
}g[];
inline bool cmp(const int &a, const int &b) {
return g[].pos[a] < g[].pos[b];
}
void out(int x, G &gr) {
for(int i = gr.e[x]; i; i = gr.edge[i].nex) {
int y = gr.edge[i].v;
if(y == gr.fa[x]) continue;
//printf("%d -> %d len = %d \n", x, y, gr.edge[i].len);
out(y, gr);
}
return;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= n * ; i++) pw[i] = pw[i >> ] + ;
for(int i = ; i <= n; i++) {
scanf("%d", &col[i]);
if(col[i]) {
v[col[i]].push_back(i);
}
}
for(int i = ; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
g[].add(x, y);
g[].add(y, x);
}
g[].pre1();
g[].lcapre();
for(int i = ; i <= m; i++) {
//std::sort(v[i].begin(), v[i].end());
int len = v[i].size(), x = v[i][];
for(int j = ; j < len; j++) {
x = g[].lca(x, v[i][j]);
}
fr[x] = i;
}
g[].recol();
/*for(int i = 1; i <= n; i++) {
printf("i = %d col = %d \n", i, col[i]);
}
puts("");*/
for(int x = ; x <= n; x++) {
//printf("x = %d \n", x);
for(int i = g[].e[x]; i; i = g[].edge[i].nex) {
int y = g[].edge[i].v;
//printf("%d -> %d \n", x, y);
if(!col[x] && !col[y]) {
g[].add(x, y);
//printf("g1 : add %d %d \n", x, y);
}
else if(!col[x]) {
g[].add(x, v[col[y]][]);
//printf("g1 : add %d %d \n", x, v[col[y]][0]);
}
else if(!col[y]) {
g[].add(v[col[x]][], y);
//printf("g1 : add %d %d \n", v[col[x]][0], y);
}
else if(col[x] != col[y]) {
g[].add(v[col[x]][], v[col[y]][]);
//printf("g1 : add %d %d \n", v[col[x]][0], v[col[y]][0]);
}
}
}
g[].DP(v[][], );
printf("%d\n", f[v[][]]);
return ;
g[].pre1(v[][]);
g[].lcapre();
/*printf("out G1 : \n");
out(v[1][0], g[1]);
puts("");*/
for(int i = ; i <= m; i++) {
imp[++K] = v[i][];
}
/*for(int i = 1; i <= n; i++) {
if(!col[i]) {
imp[++K] = i;
}
}*/
std::sort(imp + , imp + K + , cmp);
int rt = g[].build_t(g[]);
//printf("out G2 : \n");
//out(rt, g[2]);
int ans = g[].cal(rt);
printf("%d\n", ans);
return ;
}
AC代码
代码中有一些冗余部分....
CF1144G - Two Merged Sequences
题意：给你一个序列，你要把它拆成一个单增和一个单减序列。n <= 200000, 空间256M。
解：我一开始想到了一个2-sat + 主席树优化连边的做法，但是因为过高的空间复杂度导致MLE/RE.....
正解是DP，我们可以设fi表示第i个元素在上升序列中，下降序列的结尾最大值。gi反之。有4种转移。
#include <bits/stdc++.h>
const int N = ;
int a[N], f[N], g[N], fr[N], gr[N], vis[N];
int main() {
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
}
memset(g, 0x3f, sizeof(g));
memset(f, -, sizeof(f));
f[] = N, g[] = -;
for(int i = ; i <= n; i++) {
if(a[i - ] < a[i] && f[i] <= f[i - ]) {
f[i] = f[i - ];
fr[i] = ;
}
if(g[i - ] < a[i] && f[i] <= a[i - ]) {
f[i] = a[i - ];
fr[i] = ;
}
if(a[i - ] > a[i] && g[i] >= g[i - ]) {
g[i] = g[i - ];
gr[i] = ;
}
if(f[i - ] > a[i] && g[i] >= a[i - ]) {
g[i] = a[i - ];
gr[i] = ;
}
//printf("i = %d f = %d g = %d \n", i, f[i], g[i]);
}
if(f[n] != -) {
printf("YES\n");
int t = ;
for(int i = n; i >= ; i--) {
vis[i] = t;
if(t == ) t = fr[i];
else t = gr[i];
}
for(int i = ; i <= n; i++) {
printf("%d ", vis[i] - );
}
return ;
}
if(g[n] != 0x3f3f3f3f) {
printf("YES\n");
int t = ;
for(int i = n; i >= ; i--) {
vis[i] = t;
if(t == ) t = fr[i];
else t = gr[i];
}
for(int i = ; i <= n; i++) {
printf("%d ", vis[i] - );
}
return ;
}
printf("NO\n");
return ;
}
AC代码
#include <bits/stdc++.h>
const int N = , lm = ;
struct Edge {
int nex, v;
}edge[N]; int tp;
int n, tot, e[N], ls[N], rs[N], dfn[N], low[N], num, a[], rt[], rt2[], rt3[], rt4[];
int fr[N], scc_cnt;
std::stack<int> S;
inline void add(int x, int y) {
edge[++tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void tarjan(int x) {
low[x] = dfn[x] = ++num;
S.push(x);
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!dfn[y]) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
}
else if(!fr[y]) {
low[x] = std::min(low[x], dfn[y]);
}
}
if(low[x] == dfn[x]) {
int y;
++scc_cnt;
do {
y = S.top();
S.pop();
fr[y] = scc_cnt;
} while(x != y);
}
return;
}
void insert(int &x, int y, int p, int id, int l, int r) {
if(!x || x == y) {
x = ++tot;
ls[x] = ls[y];
rs[x] = rs[y];
}
if(l == r) {
add(x, id);
if(y) add(x, y);
return;
}
int mid = (l + r) >> ;
if(p <= mid) {
insert(ls[x], ls[y], p, id, l, mid);
}
else {
insert(rs[x], rs[y], p, id, mid + , r);
}
if(ls[x]) {
add(x, ls[x]);
}
if(rs[x]) {
add(x, rs[x]);
}
return;
}
void Add(int id, int L, int R, int l, int r, int o) {
if(!o) return;
if(L <= l && r <= R) {
add(id, o);
return;
}
int mid = (l + r) >> ;
if(L <= mid) {
Add(id, L, R, l, mid, ls[o]);
}
if(mid < R) {
Add(id, L, R, mid + , r, rs[o]);
}
return;
}
int main() {
printf("%d\n", (sizeof(e) * + sizeof(a) * ) / );
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
a[i]++;
}
/// build
tot = n * ;
for(int i = ; i <= n; i++) {
if(i < n) {
insert(rt[i], rt[i - ], a[i], i + n, , lm);
}
if(i > ) {
Add(i, a[i], lm, , lm, rt[i - ]);
}
}
for(int i = ; i <= n; i++) {
if(i < n) {
insert(rt2[i], rt2[i - ], a[i], i, , lm);
}
if(i > ) {
Add(i + n, , a[i], , lm, rt2[i - ]);
}
}
for(int i = n; i >= ; i--) {
if(i > ) {
insert(rt3[i], rt3[i + ], a[i], i + n, , lm);
}
if(i < n) {
Add(i, , a[i], , lm, rt3[i + ]);
}
}
for(int i = n; i >= ; i--) {
if(i > ) {
insert(rt4[i], rt4[i + ], a[i], i, , lm);
}
if(i < n) {
Add(i + n, a[i], lm, , lm, rt4[i + ]);
}
}
for(int i = ; i <= tot; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
for(int i = ; i <= n; i++) {
if(fr[i] == fr[i + n]) {
puts("NO");
return ;
}
}
puts("YES");
for(int i = ; i <= n; i++) {
if(fr[i] < fr[i + n]) {
printf("0 ");
}
else {
printf("1 ");
}
}
puts("");
return ;
}
2-sat代码，仅供参考，不保证正确
CF1132E Knapsack
题意：给定8e16个物体，每个物体的体积在1 ~ 8中。求不超过W体积的情况下最接近W能得到多少体积。
解：考虑到答案要么是sum，要么不会小于W - 7,，而且由于物品体积都非常小所以随便调整几下就能得到解。
于是先贪心到W - 8以上，然后用bitset做正反两个背包，然后枚举答案判定即可。
#include <bits/stdc++.h> typedef long long LL; const int N = ; std::bitset<N> f, g, h;
LL W, a[], b[]; int main() {
LL sum = ;
scanf("%lld", &W);
for(int i = ; i <= ; i++) {
scanf("%lld", &a[i]);
sum += a[i] * i;
}
if(sum <= W) {
printf("%lld\n", sum);
return ;
} sum = ;
for(int i = ; i <= ; i++) {
if(sum + a[i] * i <= W) {
sum += a[i] * i;
std::swap(a[i], b[i]);
}
else {
LL cnt = (W - sum) / i;
sum += cnt * i;
b[i] = cnt;
a[i] -= cnt;
break;
}
} f.set();
g.set();
for(int i = ; i <= ; i++) {
int lm = std::min(a[i], 100ll);
for(int j = ; j <= lm; j++) {
f |= f << i;
}
}
for(int i = ; i <= ; i++) {
int lm = std::min(b[i], 100ll);
for(int j = ; j <= lm; j++) {
g |= g << i;
}
} int delta = W - sum;
for(int i = delta; i >= ; i--) {
/// check if f-g = i
h = (g << i) & f;
if(h.any()) {
printf("%lld\n", i + sum);
return ;
}
} return ;
}
AC代码
CF