每周日练习

URAL2118

给定前 \(k\) 个字母的 \(01\) 前缀编码(不存在一个编码是另一个编码的前缀)。

给定字符串 \(s\),设其解码后的 \(01\) 串为 \(S\),求最多能将 \(S\) 划分为多少段使得每一段都无法解码,无解输出 \(-1\)

\(k \le 52, n\le 10^6\)

首先考虑两种特殊情况:

  • 编码中既有 \(0\),也有 \(1\),那 \(S\) 无论怎么划分都可以解码。
  • 编码中既没 \(0\),也没 \(1\),那么答案为 \(|S|\)

剩下的情况为:有 \(0\)\(1\) 和有 \(1\)\(0\),由于对称性,只考虑有 \(0\)\(1\)

首先答案的上界为 \(1\) 的个数,因为全 \(0\) 的一段是可以被解码的。

如果最后一位为 \(1\),那么在每个 \(1\) 后面断开,就可以取到这个上界。

如果最后一位为 \(0\),假设最后一段 \(T\),可以说明存在最优解满足 \(T\) 前面是 \(1\):假设 \(T\) 前面有 连续\(x\)\(0\),前面总共有 \(y\)\(1\)。那么答案的上界为 \(y+1\),把这 \(x\)\(0\) 加入 \(T\),然后在 \(T\) 前面的每个 \(1\) 后面断开就可以到达这个上界。

如果 \(T\) 前面有 \(y\)\(1\),最大段数就是 \(y+1\),问题就是求最大的 \(y\),假设 \(T'\) 是最短的无法被解码的后缀,可以说明最大的 \(y\) 等于 \(T'\) 前面 \(1\) 的个数:由于 \(|T|\ge |T'|\),所以 \(y\) 不会超过 \(T'\) 前面 \(1\) 的个数,另外,令 \(T=T'前面极长的一段0+T'\)\(y\) 就可以取到这个上界。

问题转化成了求 \(T'\),那么 \(T'\) 的任何前缀都无法解码,否则 \(T'\) 不是最短的,记 \(suffix(i)\) 表示 \(S\) 长度为 \(i\) 的后缀,问题就是依次判断 \(suffix(1),suffix(2),suffix(3),\cdots\) 是否有前缀可以被解码,AC 自动机即可。

复杂度 \(O(nk)\)

Graph Subpaths

没有提交地址。

给定一张 \(n\) 个点 \(m\) 条边的有向无环图,再给定 \(k\) 条路径,每条路径长度为 \(l_i\),一条合法路径不包含这 \(k\) 条路径。

对于 \(i \in [2,n]\),求 \(1\rightarrow i\) 的合法路径条数。

\(n,m,\sum_{i=1}^kl_i \le 10^5\)

Sol 1

首先把所有边反向,就转化成了求 \(i\rightarrow 1\) 的合法路径条数。

对于边 \((u,v)\),标记它的权值为 \(v\),设 \(T_i\) 表示 \(i\rightarrow 1\) 所有合法路径组成的 trie,考虑怎么按拓扑序求出每一个 \(T_u\),对于边 \((u,v)\)\(T_v\) 是已经求过了,把 \(T_v\) 复制到根的儿子,但这样会有一些以 \(u\) 为起点的不合法路径,需要删除这些路径:从 \(T_u\) 的根出发沿着不合法路径走,把以终点为根的子树删除即可。\(u\) 的答案就是 \(T_u\) 的叶子个数。

由于 \(T_u\) 非常大,当然不能直接存下来,可行的方法是用可持久化的 trie,对于边 \((u,v)\),只需要从 \(T_u\) 的根向 \(T_v\) 连一条边就行了,而不用复制整棵 \(T_v\),删除子树也只需要对路径上的结点建新版本。

一个问题是儿子列表的维护,如果用链表维护的话,删除子树时新建的结点需要从原版本复制整个链表,复杂度可能达到 \(O(n^2)\)

用主席树维护儿子列表就可以 \(O(n\log n)\) 地新建结点。

复杂度 \(O(n\log n)\)

Sol 2

对所有路径建 AC 自动机,不难想到一个 \(O(n^2)\) 状态的 DP,设 \(f_{i,u}\) 表示在原图中走到 \(i\)AC 自动机上走到 u,且没有经过 AC 自动机上终止结点的路径条数。

由于 AC 自动机上的点对应唯一原图中的点的,所以 DP 状态定义成 \(f_u\) 就可以转移了。

由于建 AC 自动机需要主席树,复杂度 \(O(n\log n)\)

ZOJ3390

对于两棵树 \(T_1,T_2\),定义 \(T_1+T_2\) 表示把根合并,\(T_1\cdot T_2\) 表示把 \(T_1\) 中每个结点换成 \(T_2\)\(T_1=T_2\) 表示树同构。

给定树 \(A,B,C\),求 \(X,Y\) 满足 \(AX+BY=C\)

\(|A|,|B|,|C| \le 10^5\)

\(height(T)\) 表示 \(T\) 的树高(最深叶子到根的距离)。

可以发现 \(height(T_1+T_2)=\max(height(T_1),height(T_2)),height(T_1\cdot T_2)=height(T_1)+height(T_2)\)

那么 \(\max(height(A)+height(X),height(B)+height(Y))=height(C)\),假设 \(height(A)+height(X)=height(C)\)(另一种情况是一样的)。

这样就知道了 \(height(X)\),考虑怎么求 \(X\),很简单,假设 \(u\)\(C\) 中最深叶子的 \(height(X)\) 级祖先,以 \(u\) 为根的子树就是 \(X\),这样就知道了 \(AX\),然后就可以求出 \(BY\),再用类似的方法就可以求出 \(Y\) 了。

虽然思路很简单,但是有一定实现难度,求 \(BY\) 时树的“减法“,以及判定答案是否合法都需要用到树哈希。

树哈希公式: \[ f_u=1+\sum_{v\in son(u)}f_v\cdot \text{prime}(size_v) \] 其中 \(\text{prime}(i)\) 表示第 \(i\) 个质数。

注:对于两棵大小不同的树 \(T_1,T_2\)\(f_{T_1}=f_{T_2}\) 是可能的,因此哈希应当和子树大小捆绑在一起。

Generator :参数 \(T,A,B,C,D\) 可调,分别表示数据组数和树 \(A,X,B,Y\) 的大小。

查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define SZ(x) int((x).size())
#define mid ((l + r) / 2)
#define lc o * 2
#define rc o * 2 + 1
#define lch l, mid, lc
#define rch mid + 1, r, rc
#define cmi(a, b) (a = min(a, b))
#define cma(a, b) (a = max(a, b))
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pop __builtin_popcount
#define llpop __builtin_popcountll
#define ctz __builtin_ctz
#define llctz __builtin_ctzll
#define clz __builtin_clz
#define llclz __builtin_clzll
#define par __builtin_parity
#define llpar __builtin_parityll

using namespace std;
using ll = long long;
using lf = double;
// using P = pair<int, int>;
using V = vector<int>;
// using cmp = complex<lf>;

ll gen(ll x) {
const ll k = 0x9ddfea08eb382d69ull;
rep(i, 1, 3) x *= k, x ^= x >> 47;
return x * k;
}
int rnd() {
static ll s = time(0) + (ll)new char;
return (s += gen(s)) & INT_MAX;
}
V tmul(V a, V b) {
int n = a.size() - 1, m = b.size() - 1, su = n;
rep(i, 1, n) {
rep(j, 2, m) a.pb(b[j] == 1 ? i : b[j] + su - 1);
su += m - 1;
}
return a;
}
V tplus(V a, V b) {
int n = a.size() - 1, m = b.size() - 1;
rep(j, 2, m) a.pb(b[j] == 1 ? 1 : b[j] + n - 1);
return a;
}
const int N = 5, A = 5, B = 5, C = 5, D = 5;
int main() {
const int T = 100000;
printf("%d\n", T);
rep(kase, 1, T) {
int a = rnd() % A + 1, b = rnd() % B + 1, c = rnd() % C + 1, d = rnd() % D + 1;
V t1{0}, t2{0}, t3{0}, t4{0};
auto get = [](V& t, int n) { rep(i, 1, n) t.pb(i > 1 ? rnd() % (i - 1) + 1 : 0); };
get(t1, a), get(t2, b), get(t3, c), get(t4, d);
V t5 = tplus(tmul(t1, t2), tmul(t3, t4));
printf("%d %d %llu\n", a, c, t5.size() - 1);
auto prt = [](V& v) { For(i, 1, v.size()) printf("%d ", v[i]); puts(""); };
prt(t1), prt(t3), prt(t5);
}
}

Special judge:假设保存为 checker.cpp,编译后在命令行中使用:checker <input-file> <output-file>,答案正确返回值为 \(0\),否则返回值为 \(1\),输出为第一组出错的数据。

查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define SZ(x) int((x).size())
#define mid ((l + r) / 2)
#define lc o * 2
#define rc o * 2 + 1
#define lch l, mid, lc
#define rch mid + 1, r, rc
#define cmi(a, b) (a = min(a, b))
#define cma(a, b) (a = max(a, b))
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pop __builtin_popcount
#define llpop __builtin_popcountll
#define ctz __builtin_ctz
#define llctz __builtin_ctzll
#define clz __builtin_clz
#define llclz __builtin_clzll
#define par __builtin_parity
#define llpar __builtin_parityll

using namespace std;
using ll = long long;
using lf = double;
using P = pair<int, int>;
using V = vector<int>;
// using cmp = complex<lf>;

const int N = 1e5 + 5, M = 1299709;
int f[M + 5], pid, prm[N];

V tmul(V a, V b) {
int n = a.size() - 1, m = b.size() - 1, su = n;
rep(i, 1, n) {
rep(j, 2, m) a.pb(b[j] == 1 ? i : b[j] + su - 1);
su += m - 1;
}
return a;
}
V tplus(V a, V b) {
int n = a.size() - 1, m = b.size() - 1;
rep(j, 2, m) a.pb(b[j] == 1 ? 1 : b[j] + n - 1);
return a;
}

P dfs(int u, const V G[]) {
P re(1, 1);
for(int v : G[u]) {
auto [h, sz] = dfs(v, G);
re.fi = (re.fi + (ll)h * prm[sz]) % 999999937;
re.se += sz;
}
return re;
}
int Hash(const V& t) {
vector<int> G[N];
For(i, 1, t.size()) G[t[i]].pb(i);
return dfs(1, G).fi;
}
int read(FILE* f) { int x; return fscanf(f, "%d", &x) == 1 ? x : -1; }

int main(int argc, char* argv[]) {
rep(i, 2, M) {
if(!f[i]) prm[++pid] = i;
for(int j = 1; i * prm[j] <= M; j++) {
f[i * prm[j]] = 1;
if(i % prm[j] == 0) break;
}
}
FILE *in = fopen(argv[1], "r"), *out = fopen(argv[2], "r");
for(int T = read(in); T--;) {
V t1{0}, t2{0}, t3{0}, t4{0}, t5{0};
auto get = [](FILE* f, V& t, int n) { rep(i, 1, n) t.pb(read(f)); };
int a = read(in), b = read(in), c = read(in);
get(in, t1, a), get(in, t3, b), get(in, t5, c);
int d = read(out), e = read(out);
auto err = [&]() {
printf("1\n%d %d %d\n", a, b, c);
rep(i, 1, a) printf("%d ", t1[i]); puts("");
rep(i, 1, b) printf("%d ", t3[i]); puts("");
rep(i, 1, c) printf("%d ", t5[i]);
exit(1);
};
if(!~d) err();
get(out, t2, d), get(out, t4, e);
if((ll)a * d + (ll)b * e != c && Hash(tplus(tmul(t1, t2), tmul(t3, t4))) != Hash(t5)) err();
}
}

IZhO 2020 D1T3

题目链接

给定长度为 \(n\) 的序列 \(A\),问有多少三元组 \((i,j,k)\) 满足 \(i\le j<k\)\([i,j]\)\([j+1,k]\) 两个区间中数的集合相同。

\(n \le 2\cdot 10^5\)

\(prev_i\) 表示 \(A_i\) 上一次出现的位置,\(next_i\) 表示 \(A_i\) 下一次出现的位置。

三元组 \((i,j,k)\) 合法的充要条件为:

  • 区间 \([j+1,k]\) 中的数都在 \([i,j]\) 中出现,即 \(i \le \min prev_{j+1\cdots i}\),相当于 \(i\) 有个上界 \(R_{j,k}=\min prev_{j+1\cdots k}\)
  • 区间 \([i,j]\) 中的数都在 \([j+1,k]\) 中出现,即 \(\max next_{i\cdots j}\le k\),相当于 \(i\) 有个下界 \(L_{j,k}\),其中 \(L_{j,k}\) 是最小的 \(i\) 满足 \(\max next_{i\cdots j}\le k\)

那么 \((j,k)\) 的贡献就是 \(\max(R_{j,k}-L_{j,k}+1,0)\),考虑只枚举 \(k\),用数据结构动态维护 \(\sum_{j=1}^{k-1}\max(R_{j,k}-L_{j,k}+1,0)\)

先考虑 \(L_{j,k}\)\(R_{j,k}\) 分别怎么维护。

对于 \(R_{j,k}=\min prev_{j+1\cdots k}\),这是 \(prev\) 数组上的后缀 \(\min\),当 \(k\rightarrow k+1\) 时,\(R_{j,k}\) 发生的改变是一个后缀变成了 \(prev_{k+1}\),具体可以用单调栈求出这个后缀,然后区间赋值。

对于 \(L_{j,k}\),直接分析 \(k\rightarrow k+1\) 不太行,换一个角度考虑对于一个 \(j\)\(L_{j,k}\)\(k\) 的关系,\(\max next_{i\cdots j}\)\(next\) 数组上的后缀 \(\max\),将 \(next_{1\cdots j}\) 依次插入单调栈,设单调栈中元素分别为 \(next_{i_1},next_{i_2},next_{i_3},\cdots,next_{i_k}\)

  • \(k\in[j+1,next_{i_k}-1]\) 时,\(L_{j,k}=\infty\)
  • \(k\in [next_{i_k},next_{i_{k-1}-1}]\)\(L_{j,k}=i_{k-1}+1\)
  • \(\cdots\)
  • \(k\in [next_{i_1},n]\)\(L_{j,k}=1\)

综上,单调栈元素 \(i_x\) 意味着当 \(k\in [next_{i_x},next_{i_{x-1}}-1]\)\(L_{j,k}=i_{x-1}+1\),假设插入 \(next_y\)\(next_{i_x}\) 被弹掉了,那么当 \(j\in [i_x,y-1],k\in [next_{i_x},next_{i_{x-1}}-1]\) 时,\(L_{j,k}=i_{x-1}+1\),相当于 \(k\)\(next_{i_x}-1\rightarrow next_{i_x}\) 时,对 \(L_{i_x\cdots y-1,k}\) 进行区间赋值为 \(i_x+1\)。每个单调栈元素意味着一次区间赋值,所以只需要 \(n\) 次区间赋值就可以维护 \(L_{j,k}\)

但维护的是 \(\sum_{j=1}^{k-1}\max(R_{j,k}-L_{j,k}+1,0)\),相当于夹在两条递增折线之间的面积。由于 \(L_{j,k}\)\(R_{j,k}\) 都是随着 \(k\) 增大而减小的,所以每次赋值都是减小。比如将 \(R_{l\cdots r,k}\) 改为 \(v\),如果 \(v \le \min L_{l\cdots r,k}\),这一段的面积就是 \(0\),如果 \(v \ge \max L_{l\cdots r,k}\),这一段的面积就是 \(\sum_{j=l}^rR_{j,k}-\sum_{j=l}^rL_{j,k}+(r-l+1)\),否则可以二分一个分界点 \(x\),使得 \(\forall j \in[l,x], v\ge L_{j,k},\forall j\in[x+1,r],v\le L_{j,k}\),分界点左右两段分别对应上述两种情况。所以只要维护了 \(L_{j,k},R_{j,k}\) 的区间 \(\min,\max\)\(sum\) 就可以维护 \(\sum_{j=1}^{k-1}\max(R_{j,k}-L_{j,k}+1,0)\) 了。

在实现上并不需要求 \(x\),假设当前要将 \(L_{ql\cdots qr,k}\) 赋值为 \(v\),当前线段树结点区间为 \([l,r]\),一般区间赋值是在 \(ql\le l\land r \le qr\) 时停止递归,这里把条件改成 \(ql\le l\land r \le qr \land (v \le \min L_{l\cdots r,k}\lor v \ge \max L_{l\cdots r,k})\) 才可以方便地维护 \(\sum_{j=1}^{k-1}\max(R_{j,k}-L_{j,k}+1,0)\),由于只有一个分界点,所以复杂度不变。

复杂度 \(O(n\log n)\),实现难度较大,附上代码:

查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back
#define mid ((l + r) / 2)
#define lc o * 2
#define rc o * 2 + 1
#define lch l, mid, lc
#define rch mid + 1, r, rc

using namespace std;
using ll = long long;

const int N = 2e5 + 5;

int n, a[N], pre[N], nxt[N], L[N];
vector<tuple<int, int, int>> vl[N], vr[N];
int tagL[N * 4], minL[N * 4], maxL[N * 4];
int tagR[N * 4], minR[N * 4], maxR[N * 4];
ll sum[N * 4], sumL[N * 4], sumR[N * 4], as;

void pushUp(int o) {
sum[o] = sum[lc] + sum[rc];
sumL[o] = sumL[lc] + sumL[rc];
sumR[o] = sumR[lc] + sumR[rc];
minL[o] = min(minL[lc], minL[rc]);
minR[o] = min(minR[lc], minR[rc]);
maxL[o] = max(maxL[lc], maxL[rc]);
maxR[o] = max(maxR[lc], maxR[rc]);
}
void pushL(int v, int l, int r, int o) {
tagL[o] = minL[o] = maxL[o] = v, sumL[o] = v * (r - l + 1ll);
sum[o] = max(sumR[o] - sumL[o], 0ll);
}
void pushR(int v, int l, int r, int o) {
tagR[o] = minR[o] = maxR[o] = v, sumR[o] = v * (r - l + 1ll);
sum[o] = max(sumR[o] - sumL[o], 0ll);
}
void pushDown(int l, int r, int o) {
if(~tagL[o]) pushL(tagL[o], lch), pushL(tagL[o], rch), tagL[o] = -1;
if(~tagR[o]) pushR(tagR[o], lch), pushR(tagR[o], rch), tagR[o] = -1;
}
void updL(int L, int R, int v, int l, int r, int o) {
if(L <= l && r <= R && (v <= minR[o] || v >= maxR[o])) return pushL(v, l, r, o);
pushDown(l, r, o);
if(L <= mid) updL(L, R, v, lch);
if(R > mid) updL(L, R, v, rch);
pushUp(o);
}
void updR(int L, int R, int v, int l, int r, int o) {
if(L <= l && r <= R && (v >= maxL[o] || v <= minL[o])) return pushR(v, l, r, o);
pushDown(l, r, o);
if(L <= mid) updR(L, R, v, lch);
if(R > mid) updR(L, R, v, rch);
pushUp(o);
}
int main() {
cin >> n;
rep(i, 1, n) scanf("%d", &a[i]);
rep(i, 1, n) L[i] = 0;
rep(i, 1, n) pre[i] = L[a[i]], L[a[i]] = i;
rep(i, 1, n) L[i] = n + 1;
per(i, n, 1) nxt[i] = L[a[i]], L[a[i]] = i;
rep(i, 2, n) {
int& j = L[i] = i - 1;
for(; j && pre[j] >= pre[i]; j = L[j]);
vr[i].eb(max(j, 1), i - 1, pre[i]);
}
rep(i, 2, n) {
int& j = L[i] = i - 1;
for(; j && nxt[j] <= nxt[i]; j = L[j])
vl[nxt[j]].eb(max(j, 1), i - 1, L[j]);
}
mem(tagL, 63), mem(tagR, -1);
rep(i, 1, n) {
for(auto [l, r, v] : vl[i]) updL(l, r, v, 1, n, 1);
for(auto [l, r, v] : vr[i]) updR(l, r, v, 1, n, 1);
as += sum[1];
}
cout << as;
}

BaekjoonOJ18733

给定 \(n\) 个数 \(a_i\),要把它们放进 \(k\) 个有标号的盒子中,要求每个盒子非空。

每个盒子的价值为盒内所有数的按位与,要最大化所有数的价值,同时求达到最大值的方案数。

\(k \le n \le 10^5,0\le a_i \le 10^9\)

如果所有 \(a_i=0\),那么方案数为 \(k!{n\brace k}\)

假设所有 \(a_i\) 在二进制下最高位为 \(b\),可以证明最优的策略一定会最大化价值在第 \(b\) 位为 \(1\) 的盒子数量,分以下几种情况考虑:

  • 所有 \(a_i\) 在第 \(b\) 位为 \(1\),那么所有方案都会有 \(k\cdot 2^k\) 的贡献,把所有 \(a_i\) 减去 \(2^b\) 继续做。
  • \(x\)\(a_i\) 在第 \(b\) 位为 \(1\)。如果 \(x<k\),那么这 \(x\)\(a_i\) 会一对一地放进 \(x\) 个盒子中,其他的 \(a_i\) 放进剩余的 \(k-x\) 个盒子中,所有方案都会有 \(x\cdot 2^k\) 的贡献,方案数乘上 \(\binom kx\)
  • 如果 \(x\ge k\),那么其他的 \(a_i\) 一定放在同一个盒子中,所有方案都会有 \((k-1)\cdot 2^k\) 的贡献,把第 \(b\) 位为 \(1\)\(a_i\) 减去 \(2^b\),把所有第 \(b\) 位为 \(0\)\(a_i\) 替换成它们的按位与。

这样递归做下去,即可 \(O(n\log V)\) 地求出答案。

OpenCup

题目链接 提交记录

维护一个长度为 \(2^p\) 的数组 \(A\)(下标从 \(0\) 开始),支持五种操作:

  • \(A_v\) 增加 \(\delta\)

  • 查询 \(\sum_{i=l}^rA_i\)

  • 给定 \(k\)\(\forall i \in [0,2^p)\),满足 \(i\text{ and } k\ne i\),将 \(A_{i\text{ and }k}\) 加上 \(A_i\),然后令 \(A_i=0\)

  • 给定 \(k\)\(\forall i \in [0,2^p)\),满足 \(i\text{ or } k\ne i\),将 \(A_{i\text{ or }k}\) 加上 \(A_i\),然后令 \(A_i=0\)

  • 给定 \(k\)\(\forall i \in [0,2^p)\),满足 \(i\text{ xor } k\ne i\),将 \(A_{i\text{ xor }k}\) 加上 \(A_i\),然后令 \(A_i=0\)

\(p\le 19,v,k< 2^p,A_i,\delta \le 10^9\)

先分析反复进行后三种操作后对 \(A\) 的影响是怎样的,对于一个 \(A_i\),假如它最终加到了 \(A_j\) 上(\(A_i\) 不变认为 \(i=j\)),那么 \(j\) 是把 \(i\) 的某些位赋为 \(0\),某些位赋为 \(1\),某些位 \(01\) 翻转得到的,不难用 \(tag_0,tag_1,tag_f\) 三个状压标记来表示后三种操作的影响。

考虑用 0-1 trie 维护这个序列,每个结点维护 \(tag_0(u),tag_1(u),tag_f(u)\) 三个懒标记,问题是怎么下放标记,假设当前要将结点 \(u\) 上的标记下放。

首先需要将标记传给左右儿子,对于儿子 \(v\),它按如下方式接受 \(tag_0(u),tag_1(u),tag_f(u)\) 对它的影响:

  • \(tag_0(v)=tag_0(v)\cup tag_0(u),tag_1(v)=tag_1(v)\setminus tag_0(u),tag_f(v)=tag_f(v)\setminus tag_0(u)\)

  • \(tag_1(u)\) 类似。

  • \(x=tag_0(v)\cap tag_f(u),y=tag_1(v)\cap tag_f(u)\),那么 \(tag_0(v)=(tag_0(v)\setminus x)\cap y,tag_1(v)=(tag_1(v)\setminus y)\cap x,tag_f(v)=(tag_f(v)\cap tag_f(u))\setminus x\setminus y\)

用位运算可以做到 \(O(1)\)

另外还要考虑标记对点 \(u\) 自己的影响,设点 \(u\) 对应第 \(d\) 位,分三种情况:

  • 如果 \(tag_0(u)\) 包含第 \(d\) 位,需要将 \(u\) 的右子树合并到左子树去。
  • 如果 \(tag_1(u)\) 包含第 \(d\) 位,需要将 \(u\) 的左子树合并到右子树去。
  • 如果 \(tag_f(u)\) 包含第 \(d\) 位,需要将 \(u\) 的左右子树交换。

交换左右子树是容易的,将以 \(v\) 为根的子树合并到以 \(u\) 为根的子树可以像线段树合并一样做:

  • 如果 \(u,v\) 中有一个是空的,就返回。

  • 否则下放 \(u,v\) 的标记,然后分别合并 \(u,v\) 的左右儿子,并删除 \(v\)

由于第二种情况每发生一次就会删一个结点,所以复杂度均摊是 \(O(p)\) 的。

对于单点加和区间查询,像普通线段树一样做就行了,注意由于子树合并会删除结点,所以单点加的时候如果遇到了不存在的结点时需要动态开点。

复杂度 \(O(p2^p)\)

BaekjoonOJ19394

给定一张 \(n\) 个点 \(m\) 条边的无向图,定义一个边的子集是好的当且仅当仅保留这些边时,每个点的度数为偶数。

问所有好的边集的边数平方和。

\(n,m\le 2\cdot 10^5\)

下面称合法边集为欧拉子图。

首先欧拉子图的数量是多少?答案是 \(2^{m-n+c}\),其中 \(c\) 是连通块数。考虑求出图的一个生成森林,那么有 \(m-n+c\) 条非树边,每条非树边和它两个端点的树上路径构成一个基环,从这些基环中选若干个异或起来就能得到一张欧拉子图,同时任意一张欧拉子图一定是若干基环异或起来的。

假设一张欧拉子图有 \(x\) 条边,它的贡献 \(x^2=2\binom x2+x\)\(x\) 可以考虑每条边的贡献,\(\binom x2\) 可以考虑每对边的贡献。

  • 一条边 \(e\) 的贡献。如果 \(e\) 是割边,那么它没有贡献,否则贡献等于删掉它后的欧拉子图数量 \(2^{m-1-n+c}\)
  • 一对边 \(e_1,e_2\) 的贡献。如果 \(e_1,e_2\) 中有割边,那么没有贡献,否则贡献等于删掉它们后的欧拉子图数量,如果 \(e_1,e_2\) 是割集,贡献为 \(2^{m-1-n+c}\),否则为 \(2^{m-2-n+c}\)

因此问题是数有多少对非割边是割集,用数据结构当然是可以做的,但有一个优秀做法。

判断 \(k\) 条边是否组成割集有如下算法:

  • 求出生成树,给每非树边随机一个 \([0,2^{64})\) 内的权值。
  • 每条树边的权值等于所有覆盖它的非树边的权值的异或和,割边权值为 \(0\)
  • \(k\) 条边组成割集当前仅当其中一些边的异或和为 \(0\)

这个条件是割集的充分条件,有 \(2^{k-64}\) 的概率误判成割集,但用来数两条边的割集是很难出错的,可以认为两条非割边组成割集当且仅当两条边权值相等。

直接统计有多少对边权值相等就行了,复杂度 \(O(n\log n)\)\(O(n)\)(哈希表)。

OpenCup

题目链接 提交记录

给定字符串 \(s,t\),每次可以删除 \(s\) 中一个字符 \(c\) 的第一次出现或最后一次出现,删除代价取决于删除字符的初始位置。

\(|s|,|t| \le 2\cdot 10^5\)

先考虑一个 \(O(n^2)\)DP,设 \(f_{i,j}\) 表示使 \(s_{1\cdot i}\)\(t_{1\cdots j}\) 相等的最小代价,转移为:

  • \(f_{i,j}\leftarrow f_{i-1,j-1}(s_i=t_j)\)
  • \(f_{i,j}\leftarrow f_{i-1,j}(t_{1\cdots j} 或 t_{j+1\cdots |t|} 中没有字符s_i)\)

\(first(c)\) 表示字符 \(c\)\(t\) 中第一次出现的位置,\(last(c)\) 表示最后一次出现的位置,那么转移二的条件可以改写为 \(j<first(s_i)\lor j\ge last(s_i)\)

\(j\ne first(s_i)\land j\ne last(s_i)\) 时两种转移只能选择一种,考虑从这里优化。

把所有的 \(first(c),last(c)\) 标记为关键值,那么最多有 \(52\) 个关键值,考虑只计算 \(j\) 为关键值的 \(f_{i,j}\),设 \(j\) 之后的一个关键值为 \(j'\),先从 \(f_{*,j}\) 转移到 \(f_{*,j'-1}\),在这一过程,\(s\) 中一些字符必须进行转移一,其他字符必须进行转移二,因此一个 \(f_{i,j}\) 最多能转移到一个的 \(f_{i',j'-1}\),具体转移到哪一个 \(i'\) 可以通过 KMP 算出,然后再从 \(f_{*,j'-1}\) 转移到 \(f_{*,j'}\)

复杂度 \(O(26n)\)

OpenCup

题目链接 提交记录

给定两个长度为 \(n\) 的 01 串 \(s,t\),可以对 \(s\) 进行以下三种操作任意次:

  • \(s_i=0\),代价为 \(t_0\)
  • \(s_i=1\),代价为 \(t_1\)
  • 交换 \(s_i,s_{i+1}\),代价为 \(t_s\)

\(n \le 4\cdot 10^6\)

可以把所有交换操作调整到最前面,即先用交换操作把 \(s\) 变成 \(s'\),再用修改操作把 \(s'\) 变成 \(t\)

考虑 \(s\) 变成 \(s'\) 的最小代价,假设 \(s_i\) 交换后的位置为 \(s'_{p_i}\),可以证明最优的 \(p\) 满足:\(p_{p_i}=i\)。可以认为交换位置 \(i,j\) 的代价是 \(t_s|i-j|\),任何位置最多参与一次交换。

对于满足 \(s_i=t_i\)\(i\),它们没有必要参与交换,删除这些位置后满足两个性质:

  • 任何交换 \((i_1,j_1),(i_2,j_2)\) 都是不相交的,即区间 \([i_1,j_1]\) 和区间 \([i_2,j_2]\) 不相交。
  • 对于任何交换 \((i,j)\),区间 \((i,j)\) 中所有位置都参与交换。

综上,对于所有的极大交换 \((i,j)\),不妨假设 \(s_i=0,s_j=1\),把 \(0\) 变成 '(',\(1\) 变成 ')',区间 \([i,j]\) 是一个合法括号串,并且 \(i\)\(j\) 是匹配的。这意味着如果 \(s_i\) 要和 \(s_j(j<i)\) 交换,那么 \(j\) 是唯一的(或者没有,当所有的 \([j,i]\) 都不是合法括号串时)。

然后就可以 DP 了,设 \(f_i\) 表示把 \(s[1\cdots i] \rightarrow t[1\cdots i]\) 的最小代价,转移为:

\[ f_i=\min(f_{i-1}+t_{1-s_i},f_{j-1}+\text{cost}(j,i)) \]

其中 \(j\) 是和 \(i\) 匹配的位置,\(\text{cost}(j,i)\) 是区间 \([j,i]\) 中所有匹配的位置 \(x,y\)\(t_s|x-y|\) 之和,可以用栈维护。

另一个正确的转移为:

\[ f_i=\min(f_{i-1}+t_{1-s_i},f_{j-1}+f_{i-1}-f_j) \]

正确的原因是 \(f_{j-1}+f_{i-1}-f_j \le f_{j-1}+\text{cost}(j,i)\),并且 \(f_{j-1}+f_{i-1}-f_j \le f_{j-1}\) 是一个合法方案的代价(那个方案的描述有点复杂,略)。

复杂度 \(O(n)\)