ACM►DP►区间DP

URAL1183 - Brackets Sequence（区间DP）

题目链接：

http://acm.timus.ru/problem.aspx?space=1&num=1183

题目大意：

参考博客

定义正规的括号序列如下:

  1. 空序列是一个正规的括号序列
  2. 如果S是一个正规的括号序列, 那么(S) 和[S] 也都是正规的括号序列。
  3. 如果A和B是正规的括号序列, 那么AB也是一个正规的括号序列。

现给定一个括号序列A（只包含小括号和中括号，可能为空序列），求一个正规括号序列B，使得A包含于B，而且B的长度是满足条件的序列中最小的。

题目分析：

设 $dp[i][j]$ 为使得 [i, j] 这段区间括号匹配所需要的最小花费，那么根据题意，$dp[i][j]$可由两种方式转移而来：

  • 如果 i 与 j 可以匹配的话$dp[i][j] = dp[i + 1][j - 1]$
  • 不关 i 与 j 是否匹配 $dp[i][k] = dp[i][k] + dp[k + 1][j]$

最后递归的打印答案，转移的时候标记一下，当前是否分为两个子序列。

AC代码：

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
#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

char s[1123];

int dp[112][112];
int mark[112][112];

void print(int l, int r) {
    if (l > r) return;
    if (l == r) {
        if (s[l] == '(' || s[l] == ')') cout << "()";
        else cout << "[]";
        return;
    }
    if (mark[l][r] == -1) {
        if (s[l] == '(') {
            cout << "(";
            print(l + 1, r - 1);
            cout << ")";
        } else {
            cout << "[";
            print(l + 1, r - 1);
            cout << "]";
        }
    } else {
        print(l, mark[l][r]);
        print(mark[l][r] + 1, r);
    }
}

int main() {
    gets(s + 1);
    int n = strlen(s + 1);
    if (!n) {
        cout << endl;
        return 0;
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) dp[i][i] = 1;
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            dp[i][j] = INF;
            if (s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']') {
                dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
            }
            mark[i][j] = -1;
            for (int k = i; k < j; k++) {
                if (dp[i][k] + dp[k + 1][j] < dp[i][j]) {
                    dp[i][j] = dp[i][k] + dp[k + 1][j];
                    mark[i][j] = k;
                }
            }
        }
    }
    print(1, n);
    cout << endl;
}

解题过程：

这题卡了好久ORZ，之前了解过一点区间DP，结果还是不会做。

ACM►图论►网络流

HihoCoder1424 - Asa's Chess Problem（有上下流量限制的费用流）

题目链接：

https://vjudge.net/problem/HihoCoder-1424

题目大意：

参考 http://www.cnblogs.com/flipped/p/7635420.html

有个 N×N 的棋盘，告诉你每个格子黑色(1)或白色(0)，以及每对能相互交换的同行或同列格子，每个格子只在一对中，即共有N×N/2对。求最少交换次数使得每行每列的黑格子总数满足给出的上下范围：若最终第i行,第j列分别有R[i],C[j]个黑格子，那么需要让Rl[i]≤R[i]≤Rh[i],Cl[j]≤C[i]≤Ch[j]。

题目分析：

这里先介绍一种有流量下限限制的建图方式，参考这个博客。

记节点 i 所有流入的流量下限和为 in[i]，所有的流出流入和下限为 out[i]，建一个超级源点 SS，超级汇点 ST。

如果一个节点 in[i] > out[i]，那么建一条 SS 到 i 的边，流量为 in[i] - out[i]。

如果 in[i] < out[i]，那么建一条 i 到 ST 的边，流量为 out[i] - in[i]。

对于无源汇的图来说，上面从 SS 到 ST跑一个最大流，如果上面的从 SS 出发的附加边满流，当前就是一个可行流，否则无解。

对于有源汇的图来说，需要从 T 到 S 连一条流量为无穷的边，然后再从 SS 到 ST 跑最大流。

对于这个题，设每一行每一列原有的黑色棋子数量为 R[i] 和 C[i]。

  • 首先从 S 到每一行每一列建一条上下限均为 R[i] 或 C[i] 的边
  • 每一行每一列对 T 建边，容量上下限为 Rl[i]， Rh[i] 或 Cl[i]，Ch[i]
  • 然后对于可以交换的棋子，如果他们颜色相同，那么不需要建边，否则如果列相同，黑色所在的行向白色棋子所在的行建流量下限为 0 上限为 1 费用为 1 的边，列相同类似
  • 从 t 到 s 建一条流量下限为 0，上限为无穷的边。

上述所有边默认费用为 0 。

AC代码：

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <bits/stdc++.h>

using namespace std;

const int MAX = 600;

int n;
int data[112][112];

struct Edge {
    int u, v, c, w, nxt;
} edge[MAX * MAX];

int head[MAX], etot;

int in[112], out[112];

void add_edge(int u, int v, int low, int up, int w) {
    edge[etot].u = u;
    edge[etot].v = v;
    edge[etot].c = up - low;
    edge[etot].w = w;
    edge[etot].nxt = head[u];
    head[u] = etot++;

    out[u] += low;

    edge[etot].u = v;
    edge[etot].v = u;
    edge[etot].c = 0;
    edge[etot].w = -w;
    edge[etot].nxt = head[v];
    head[v] = etot++;

    in[v] += low;
}

int dist[MAX], vis[MAX], pre[MAX], flow[MAX];

void spfa(int s) {
    memset(dist, 0x3f, sizeof(dist));
    queue<int> q;
    q.push(s);
    flow[s] = 1e9;
    vis[s] = 1;
    dist[s] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            Edge &e = edge[i];
            if (edge[i].c > 0 && dist[e.v] > dist[e.u] + e.w) {
                dist[e.v] = dist[e.u] + e.w;
                pre[e.v] = i;
                flow[e.v] = min(flow[e.u], e.c);
                if (!vis[e.v]) {
                    vis[e.v] = true;
                    q.push(e.v);
                }
            }
        }
        vis[u] = false;
    }
}

pair<int, int> min_cost_flow(int s, int e) {
    int rst = 0, total = 0;
    while (true) {
        spfa(s);
        if (dist[e] == 0x3f3f3f3f) break;
        int d = flow[e], u = e;
        total += d;
        rst += dist[e] * d;
        while (u != s) {
            int last = pre[u];
            edge[last].c -= d;
            edge[last ^ 1].c += d;
            u = edge[last].u;
        }
    }
    return make_pair(total, rst);
}


int Rl[112], Rh[112], Cl[112], Ch[112];

int row[112], col[112];

int main() {
    while (~scanf("%d", &n)) {

        etot = 0;
        memset(head, -1, sizeof(head));
        memset(col, 0, sizeof(col));
        memset(row, 0, sizeof(row));
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));


        //源点，汇点，超级源点，超级汇点
        int s = 0;
        int e = n * 2 + 1;
        int ss = e + 1;
        int se = ss + 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &data[i][j]);
                row[i] += data[i][j];
                col[j] += data[i][j];
            }
        }

        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &Rl[i], &Rh[i]);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &Cl[i], &Ch[i]);
        }

        for (int i = 1; i <= n; i++) {
            add_edge(s, i, row[i], row[i], 0);
            add_edge(s, i + n, col[i], col[i], 0);
            add_edge(i, e, Rl[i], Rh[i], 0);
            add_edge(i + n, e, Cl[i], Ch[i], 0);
        }

        int sum = 0;

        for (int i = 1; i <= n * n / 2; i++) {
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            if (data[x1][y1] == data[x2][y2]) continue;
            if (data[x1][y1] == 0) swap(x1, x2), swap(y1, y2);
            if (x1 == x2) {
                add_edge(n + y1, n + y2, 0, 1, 1);
            } else if (y1 == y2) {
                add_edge(x1, x2, 0, 1, 1);
            }
        }

        add_edge(e, s, 0, 1e9, 0);

        //对超级源点，超级汇点建边
        for (int i = 0; i <= n + n + 1; i++) {
            int t = in[i] - out[i];
            if (t < 0) {
                t = -t;
                add_edge(i, se, 0, t, 0);
            } else {
                sum += t;
                add_edge(ss, i, 0, t, 0);
            }
        }


        pair<int, int> ans = min_cost_flow(ss, se);

        if (ans.first != sum) {
            printf("-1\n");
        } else {
            printf("%d\n", ans.second);
        }
    }
}

解题过程：

这个题感觉也不是很难，感觉应该做出来的，关键是比赛的时候漏看了一个条件，只有列或行相同时才可以交换，如果没有这个条件建图就复杂了，当时也想麻烦了。

ACM►图论►连通性

CodeForces732F - Tourist Reform（边双连通 + DFS）

题目链接：

http://codeforces.com/contest/732/problem/F

题目大意：

给出一张 n 个顶点， m 条边的无向图，保证图连通，没有重边，现在给每个边加上方向，记从点 i 出发可以访问到的点的数量为 $r_i$，求一种分配方向的方式，使得最小的 $r_i$ 尽量的大。

$2 \le n \le 400000, 1 \le m \le 400000$

题目分析：

这里就引用下 dalao的博客:

我们考虑如何将边定向，定向成 DAG 肯定是极不好的，因为 DAG 里边存在没有出度的点，而这样的话，答案就必然为 1 了。也就是说，不能出去的点，最好要形成一个环，这样答案就是环的大小了。

将图分解为若干边-双连通分量，将每个边-双连通分量看作一个点，那么此时形成了一棵缩点树。对于每个边-双连通分量，我们可以将里边的边定向，使之成为强联通分量。再将缩点后的树边定向，成为一个边指向根的树形图，这样答案就是根代表的边-双连通分量的答案，由于任意点都可以做树形图的根，所以答案就是最大的边-双连通分量的大小。

定理：答案就是是最大的边-双连通分量的大小。
证明：前面已经证明了，最大的边-双连通分量的大小是一个合法答案。现在只需证明，最大的答案不会大于最大的边-双连通分量的大小：考虑定向后的图，将其强联通缩点，答案就是没有出度的强联通分量中最小的那个，如果这个值比最大的边-双连通分量的大小更大，那么考虑将这个强联通分量中的边改为无向边，这就能形成一个边-双连通分量，而且比原图中最大的边-双连通分量的大小还要大，这就产生了矛盾。

考虑输出方案，树边是很好定向的，DFS 一下缩点树就行了。如何将边-双连通分量中的边定向，使得形成一个强联通分量呢？我们考虑直接使用 DFS 中第一次访问边的顺序，为什么？因为利用这个顺序，肯定能保证联通。我们再考虑 DFS 树，在 DFS 树中，每个点一定能通过 DFS 返祖边和非返祖边的结合，走到自己上方的点（否则存在桥，与边-双连通的定义违背），所以每个点都可以通过定向后的边走到根，自然证明这个原先的边-双连通分量通过这种定向方法后强联通。

AC代码：

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>

using namespace std;

const int MAX = 4112345;

struct Edge {
    int u, v, nxt;
} edge[MAX << 1];

int n, m;

int head[MAX], ecnt;

int dfs_clock, scc_cnt;
int low[MAX], pre[MAX], mark[MAX];
stack<int> S;

int num[MAX], ans, id;
int data[MAX][2];

void add_edge(int u, int v) {
    edge[ecnt].u = u;
    edge[ecnt].v = v;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}

void init() {
    dfs_clock = scc_cnt = ecnt = 0;
    memset(head, -1, sizeof(head));
    memset(mark, 0, sizeof(mark));

    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &data[i][0], &data[i][1]);
        add_edge(data[i][0], data[i][1]);
        add_edge(data[i][1], data[i][0]);
    }
}

void tarjan(int u, int fa) {
    low[u] = pre[u] = ++dfs_clock;
    S.push(u);

    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (v == fa) continue;
        if (!pre[v]) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        if (!mark[v]) {
            low[u] = min(low[u], pre[v]);
        }
    }
    if (pre[u] == low[u]) {
        scc_cnt++;
        int x;
        do {
            x = S.top();
            S.pop();
            mark[x] = scc_cnt;
            num[scc_cnt]++;
            if (num[scc_cnt] > ans) {
                ans = num[scc_cnt];
                id = u;
            }
        } while (x != u);
    }
}

bool vis[MAX];
int fa[MAX];

void dfs1(int u) {
    fa[u] = true;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (vis[i / 2]) continue;
        if (mark[v] != mark[u]) continue;
        vis[i / 2] = true;
        data[i / 2][0] = u;
        data[i / 2][1] = v;
        if (fa[v]) continue;
        dfs1(v);
    }
}

void dfs2(int u) {
    vis[u] = true;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        //这里类似 DFS 一棵树的过程，如果当前双连通分量已经访问过了，那么不应该通过其他强连通分量去访问了
        if (mark[v] != mark[u]) {
            if (fa[mark[v]] == 0 || fa[mark[v]] == mark[u]) {
                fa[mark[v]] = mark[u];
                data[i/2][0] = v;
                data[i/2][1] = u;
            }
        }
        if (vis[v]) continue;
        dfs2(v);
    }
}

void solve() {
    tarjan(1, -1);

    //第一次 DFS 为双连通分量里面的边分配方向
    for (int i = 1; i <= n; i++) {
        dfs1(i);
    }

    //第二次为连接不同的双连通分量的边分配方向
    memset(vis, 0, sizeof(vis));
    memset(fa, 0, sizeof(fa));
    fa[mark[id]] = -1;
    dfs2(id);

    printf("%d\n", ans);
    for (int i = 0; i < m; i++) {
        printf("%d %d\n", data[i][0], data[i][1]);
    }
}

int main() {
    init();
    solve();
}

解题过程：

这题卡了好久，主要是为缩点后的图重新建边后会爆内存，然后只能用第一次建的边去 DFS，然后就写的有点恶心了…

ACM►DP

URAL1167 - Bicolored Horses（DP）

题目链接：

http://acm.timus.ru/problem.aspx?space=1&num=1167

题目大意：

给出一段 0 和 1 的串，要求将其划分成 k 个连续的部分（一定要划分成 k 个连续的部分，并且某一部分不能为 0，任一 0 或 1 一定要分到一分组里），记某一分组有 i 个 0 和 j 个 1，那么这一组的值为 $i \cdot j$ ，现在要求划分 k 组，使得这 k 组的值和最小，输出最小值。

$1 \le N \le 500, 1\le K \le N$

解题过程：

先是从四维降到了三维，然后还是 MLE，最后类比了一下 M 子段和的题，还是不对，然后翻的别人博客，看到状态转移方程后感觉好像也不是太难…

题目分析：

设 $dp[i][j]$ 的含义是划分了前 i 组以第 j 个元素为结尾的最小值。

那么状态转移方程是:

$$dp[i][j] = min(dp[i - 1][k] + v | k = 0 \dots j - 1)$$

含义是，因为分组是连续的第 i 组以 j 结尾可以枚举第 i - 1 组以谁结尾来转移。

这里的 v 是前缀和，含义是 $[k + 1 , j]$ 这段区间的值。

AC代码：

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
#include <bits/stdc++.h>

using namespace std;

const int MAX = 500 + 5;

int dp[MAX][MAX];
int data[MAX];
int one[MAX];
int zero[MAX];

int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        memset(zero, 0, sizeof(zero));
        memset(one, 0, sizeof(one));
        for (int i = 1; i <= n; i++) {
            scanf("%d", data + i);
            if (data[i]) one[i] += 1;
            else zero[i] += 1;
            one[i] += one[i - 1];
            zero[i] += zero[i - 1];
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = i; j <= n; j++) {
                for (int k = i - 1; k < j; k++) {
                    int v;
                    v = zero[j] - zero[k];
                    v *= one[j] - one[k];
                    dp[i][j] = min(dp[i - 1][k] + v, dp[i][j]);
                }
            }
        }
        printf("%d\n", dp[m][n]);
    }
}
ACM►DP

URAL1260 - Nudnik Photographer（DP+递推）

题目链接：

http://acm.timus.ru/problem.aspx?space=1&num=1260

题目大意：

给出 1 ～ N 的 N 个数，进行排列，要求 1 一定要为第一个元素，并且任意两个相邻的元素之间的差不能超过 2，输出有多少种这样的排列。

$1\le N \le 55$

解题过程：

感觉是和程设课上的递推题差不多，然后卡了我了两个小时也没想出来…看来数据结构刷多了真的能刷傻。

题目分析：

$dp[i]$的含义是，i 个数有多少个符合上述要求排列。那么状态转移方程是：

$$dp[i] = dp[i - 3] + dp[i - 1] + 1$$

这样分情况考虑：

首先第一个位置肯定是要放 1 的（因为题目要求），然后

  • 第二个位置放 2，那么现在的排列的个数等价于 $dp[i - 1]$，你可以当做把 1 扔掉，然后剩下的数都减一
  • 第二个位置放 3
    • 第三个位置放 2，那么第四个位置一定是要放 4，那么当前情况的排列总数是等价于$dp[i - 3]$的
    • 如果第三个位置不放 2，那么只有一种情况，假设 n = 8， 那么是1 3 5 7 8 6 4 2

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll dp[60];

int main() {
    int n;
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    for (int i = 4; i <= 55; i++) {
        dp[i] = dp[i - 1] + dp[i - 3] + 1;
    }
    while (~scanf("%d", &n)) {
        printf("%lld\n", dp[n]);
    }
}
ACM►数据结构►Splay

BZOJ1500 - 维修数列(Splay)

题目链接：

http://www.lydsy.com/JudgeOnline/problem.php?id=1500

题目大意：

给出 N 个数字和 M 次操作。

分为下面六种操作：

$M \le 2\times 10^4$，保证序列中的数字不会超过 $5 \times 10^5$，并且插入数字的总数不超过$4 \times 10^6$

解题过程：

调了一晚上才 A 掉，最后还是对照金桔的代码改的。

题目分析：

裸的 Splay 题，Splay的操作基本上都用上了，但是有好多坑点，下面列举一下：

  • GET-SUM 有可能 y = 0，这是计算区间时有可能右区间大于左区间。
  • 总共可能用到 $4 \times 10^6$ 个节点，这样会超内存，但是同时在序列的节点最多只有$5 \times 10^5$，所以要自己写内存回收。
  • 求最大子列和需要维护的信息是不对称的，当节点翻转时，对应维护的信息也需要翻转。
  • 当进行插入和删除操作的时候，需要维护一下根节点和插入到的父亲节点，主要是为了维护 size 这个值，因为 getid 需要用这个值二分，否则会 TLE。
  • 区间修改时需要两个变量，一个是 lazy 值，另一个是判断是否进行了修改。

AC代码：

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
#include <cstdio>
#include <cstring>
#include <stack>

typedef long long ll;

using namespace std;

const int maxn = 552345 + 10;

int n, m;

struct Info {
    int size;
    ll sum;
    ll lma, rma, tma;

    Info(ll v = 0) {
        size = 1;
        sum = v;
        lma = rma = tma = v;
    }

    void addIt(ll v) {
        sum = v * size;
        lma = rma = tma = max(sum, v);
    }

    //翻转区间信息
    void revIt() {
        swap(lma, rma);
    }
};

//进行区间信息合并
Info operator+(const struct Info &a, const struct Info &b) {
    Info rst(a.sum + b.sum);
    rst.size = a.size + b.size;

    rst.lma = max(a.lma, a.sum + b.lma);
    rst.rma = max(b.rma, b.sum + a.rma);
    rst.tma = max(max(a.tma, b.tma), a.rma + b.lma);

    return rst;
}

struct Node {
    int son[2], fa;
    ll val, lazy;
    Info info;
    bool change;
    bool flip;

    int &l() { return son[0]; }

    int &r() { return son[1]; }

    Node(ll v = 0) {
        l() = r() = fa = -1;
        val = v;
        change = false;
        info = Info(v);
        lazy = 0;
        flip = false;
    }

    void maintain();

    void push_down();

    //翻转和修改操作
    void addIt(ll v) {
        val = v;
        lazy = v;
        change = true;
        info.addIt(v);
    }

    void revIt() {
        flip ^= 1;
        swap(l(), r());
        info.revIt();
    }
} node[maxn];

void Node::push_down() {
    if (change) {
        if (l() != -1) node[l()].addIt(lazy);
        if (r() != -1) node[r()].addIt(lazy);
        lazy = 0;
        change = false;
    }
    if (flip) {
        if (l() != -1) node[l()].revIt();
        if (r() != -1) node[r()].revIt();
        flip = false;
    }
}

void Node::maintain() {
    info = Info(val);
    if (l() != -1) info = node[l()].info + info;
    if (r() != -1) info = info + node[r()].info;
}

int ori(int st) {
    int fa = node[st].fa;
    if (fa == -1) return -1;
    return st == node[fa].r();
}

void setc(int st, int sn, int d) {
    if (st != -1) {
        node[st].son[d] = sn;
        node[st].maintain();
    }
    if (sn != -1) node[sn].fa = st;
}

void zg(int x) {
    int st = node[x].fa, p = -1;

    node[st].push_down();
    node[x].push_down();

    int d = ori(x), dst = ori(st);
    if (st != -1) p = node[st].fa;
    setc(st, node[x].son[d ^ 1], d);
    setc(x, st, d ^ 1);
    setc(p, x, dst);
}

int root;

#define f(x) (node[x].fa)

void splay(int x, int fa = -1) {
    while (f(x) != fa) {
        if (f(f(x)) == fa) zg(x);
        else {
            if (ori(x) == ori(f(x))) zg(f(x));
            else zg(x);
            zg(x);
        }
    }
    if (fa == -1) root = x;
}

int getid(int v, int st) {
    node[st].push_down();
    int l = node[st].l();
    int lsize = 1 + (l == -1 ? 0 : node[l].info.size);
    if (v == lsize) return st;
    int d = v > lsize;
    if (d) v -= lsize;
    return getid(v, node[st].son[d]);
}

int getseg(int l, int r) {
    l--, r++;
    l = getid(l + 1, root), r = getid(r + 1, root);
    splay(r);
    splay(l, r);
    return node[l].r();
}


//进行插入和删除操作需要维护一下根节点和根节点的左儿子的区间信息
void segMaintain() {
    node[node[root].l()].maintain();
    node[root].maintain();
}

//进行内存回收
int head, tail;
int value[maxn], nxt[maxn];

int new_node(int v) {
    int rst = head;
    head = nxt[head];
    node[rst] = Node(v);
    return rst;
}

void recycle(int st) {
    if (st == -1) return;
    recycle(node[st].l());
    recycle(node[st].r());
    nxt[tail] = st;
    tail = st;
}

void del(int l, int r) {
    int pos = getseg(l, r);
    setc(node[pos].fa, -1, 1);
    recycle(pos);
    segMaintain();
}

int build(int l, int r) {
    int m = (l + r) >> 1;
    int st = new_node(value[m]);

    if (l < m) setc(st, build(l, m - 1), 0);
    if (m < r) setc(st, build(m + 1, r), 1);
    return st;
}

//初始化Splay
int build(int n) {
    head = 0;
    for (int i = 0; i < maxn; i++) {
        nxt[i] = i + 1;
    }
    tail = maxn - 1;
    nxt[tail] = -1;
    return build(0, n + 1);
}

void add(int l, int r, int v) {
    int pos = getseg(l, r);
    node[pos].addIt(v);
}

void insert(int pos, int p) {
    int l = pos;
    int r = pos + 1;
    l = getid(l + 1, root);
    r = getid(r + 1, root);
    splay(r);
    splay(l, r);
    setc(l, p, 1);
    segMaintain();
}

Info query(int l, int r) {
    return node[getseg(l, r)].info;
}

void flip(int l, int r) {
    int pos = getseg(l, r);
    node[pos].revIt();
}

int main() {
    char op[11];
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", value + i);
        }
        value[n + 1] = 0;
        root = build(n);
        while (m--) {
            int x, y, z;
            scanf("%s", op);
            if (strcmp(op, "GET-SUM") == 0) {
                scanf("%d %d", &x, &y);
                if (y == 0) {
                    puts("0");
                    continue;
                }
                printf("%lld\n", query(x, x + y - 1).sum);
            } else if (strcmp(op, "MAX-SUM") == 0) {
                //因为插入了两个虚拟节点，所以要减二才是总共的节点数
                printf("%lld\n", query(1, node[root].info.size - 2).tma);
            } else if (strcmp(op, "INSERT") == 0) {
                scanf("%d %d", &x, &y);
                if (y == 0) continue;
                for (int i = 1; i <= y; i++) {
                    scanf("%d", value + i);
                }
                //用 build 根据刚刚输入的值生成一个 Splay 再与主 Splay 合并
                insert(x, build(1, y));
            } else if (strcmp(op, "DELETE") == 0) {
                scanf("%d %d", &x, &y);
                if (y == 0) continue;
                del(x, x + y - 1);
            } else if (strcmp(op, "REVERSE") == 0) {
                scanf("%d %d", &x, &y);
                if (y == 0) continue;
                flip(x, x + y - 1);
            } else if (strcmp(op, "MAKE-SAME") == 0) {
                scanf("%d %d %d", &x, &y, &z);
                if (y == 0) continue;
                add(x, x + y - 1, z);
            }
        }
    }
}
ACM►数据结构►Splay

HDU3487 - Play with Chain(Splay + 模板详解)

题目链接：

https://vjudge.net/problem/HDU-3487

题目大意：

给出一个 1 ~ n 的序列，有 m 次操作，分为以下两种：

  • CUT a, b, c 将区间 a ~ b 剪下来，放到剩下的序列中第 c 个元素后面。
  • FLIP a, b 将区间 a ~ b 翻转。

输出执行完全部操作后的序列。

$1 \le n, m \le 3 \times 100000$

解题过程：

模板题，对着板子敲的，理解了下 Splay 的细节。

题目分析：

区间翻转和区间删除插入都是 Splay 树的经典操作，然后会 Splay 后这就是一个模板题。

AC代码：

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#include <bits/stdc++.h>

using namespace std;


//用来处理区间询问，每个节点维护的是一个子树的信息
//Splay可以将一段连续区间内的节点放到一颗子树内，所以这样可以维护一段区间的信息
struct Info {
    int size;
    int ma;

    Info() {};

    Info(int x) {
        size = 1;
        ma = x;
    }

    void addIt(int x) {
        ma += x;
    }
};

//区间（子树）信息的合并
Info operator+(const Info &l, const Info &r) {
    Info ret;
    ret.size = l.size + r.size;
    ret.ma = max(l.ma, r.ma);
    return ret;
}

const int maxn = 3 * 100000 + 10;

int root;

//Splay的节点
struct Node {
    //son[0]是左儿子，son[1]是右儿子
    int son[2], fa;
    int val, lazy;
    bool flp;
    Info info;

    int &l() { return son[0]; }

    int &r() { return son[1]; }

    Node(int v = 0) {
        l() = r() = fa = -1;
        val = v;
        info = Info(v);
        lazy = 0;
        flp = false;
    }

    //修改Splay上的节点后，也需要对 info 的信息进行维护
    void addIt(int v) {
        val += v;
        lazy += v;
        info.addIt(v);
    }

    void maintain();

    void push_down();
} node[maxn];


//进行 pushdown 操作，类似线段树
void Node::push_down() {
    if (lazy != 0) {
        if (l() != -1) node[l()].addIt(lazy);
        if (r() != -1) node[r()].addIt(lazy);
        lazy = 0;
    }
    if (flp) {
        swap(l(), r());
        if (l() != -1) node[l()].flp ^= 1;
        if (r() != -1) node[r()].flp ^= 1;
        flp = false;
    }
}

//Splay 进行旋转操作时，子树发生了改变，需要重新维护区间（子树）信息
void Node::maintain() {
    info = Info(val);
    if (l() != -1) info = node[l()].info + info;
    if (r() != -1) info = info + node[r()].info;
}


//查询当前节点是父亲的左儿子还是右儿子，左儿子返回0，右儿子返回1，如果无父亲返回-1
int ori(int st) {
    int fa = node[st].fa;
    if (fa == -1) return -1;
    return st == node[fa].r();
}


//把 sn 变成 st 的儿子节点，如果 d 是 0 是左儿子，否则是右儿子
//这里子树发生了改变，需要重新维护 info 信息
void setc(int st, int sn, int d) {
    if (st != -1) {
        node[st].son[d] = sn;
        node[st].maintain();
    }
    if (sn != -1) node[sn].fa = st;
}

//进行旋转操作，这里需要自己画图理解一下
void zg(int x) {
    int st = node[x].fa, p = -1;
    node[st].push_down();
    node[x].push_down();

    int d = ori(x), dst = ori(st);
    if (st != -1) p = node[st].fa;
    setc(st, node[x].son[d ^ 1], d);
    setc(x, st, d ^ 1);
    setc(p, x, dst);
}

#define f(x) (node[x].fa)

//将 x 旋转成 fa 的儿子，如果将 x 旋转成 根节点的话则不填 fa
void splay(int x, int fa = -1) {
    //循环直到 x 是 fa 的儿子
    while (f(x) != fa) {
        //如果 fa 是 x 的爷爷，那么只需要一次旋转
        if (f(f(x)) == fa) zg(x);
        else {
            //双旋！

            //说明进行 zig zig 或者 zag zag 旋转
            if (ori(x) == ori(f(x))) zg(f(x));
            else zg(x);
            zg(x);
        }
    }
    //更新根节点
    if (fa == -1) root = x;
}

int value[maxn];
int pos;

//要保证 value 有序，类似线段树建树，这样树高是 log(n) 的
int build(int l, int r) {
    int st = pos++;
    int m = (l + r) >> 1;
    node[st] = Node(value[m]);
    if (l < m) setc(st, build(l, m - 1), 0);
    if (m < r) setc(st, build(m + 1, r), 1);
    return st;
}

int build(int n) {
    pos = 0;
    //添加 0 和 n + 1 两个虚拟节点，方便 cut 操作
    return build(0, n + 1);
}

//获得以 st 为根节点，中序遍历的第 v 个节点
int getid(int v, int st) {
    //在树上进行二分
    node[st].push_down();
    int l = node[st].l();
    int lsize = 1 + (l == -1 ? 0 : node[l].info.size);
    if (v == lsize) return st;
    int d = v > lsize;
    if (d) v -= lsize;
    return getid(v, node[st].son[d]);
}

int getseg(int l, int r) {
    l--, r++;
    l = getid(l + 1, root), r = getid(r + 1, root);
    //现在 r+1 是 l-1 的父亲，那么 l-r 这一段子树肯定是 l-1 的右儿子
    splay(r);
    splay(l, r);
    return node[l].r();
}

void flip(int l, int r) {
    int pos = getseg(l, r);
    node[pos].flp ^= 1;
}

void cut(int l, int r, int idx) {
    //切下来 l - r 这段区间
    int rootson1 = getseg(l, r);
    int father = node[rootson1].fa;
    setc(father, -1, 1);
    l = idx, r = idx + 1;
    //因为这里是虚拟节点，所以要多加一个 1
    l = getid(l + 1, root);
    r = getid(r + 1, root);
    //将 idx+1 成为 idx 的父亲，那么上面切下来的区间放到idx的右边即可
    splay(r);
    splay(l, r);
    setc(l, rootson1, 1);
}

int n, m;
int ans[maxn], cnt;

//中序遍历
void dfs(int now) {
    node[now].push_down();
    if (node[now].son[0] != -1) dfs(node[now].son[0]);
    ans[cnt++] = node[now].val;
    if (node[now].son[1] != -1) dfs(node[now].son[1]);
}

int main() {
    char op[10];
    int L, R, idx;
    while (~scanf("%d %d", &n, &m)) {
        if (n == -1 && m == -1) break;
        for (int i = 1; i <= n; i++) value[i] = i;
        root = build(n);
        while (m--) {
            scanf("%s %d %d", op, &L, &R);
            if (op[0] == 'F') flip(L, R);
            else {
                scanf("%d", &idx);
                cut(L, R, idx);
            }
        }
        cnt = 0;
        memset(ans, 0, sizeof(ans));
        dfs(root);
        for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
    }
}

CodeForces868C - Qualification Rounds(思维+二进制)

题目链接：

http://codeforces.com/contest/868/problem/C

题目大意：

现在有 n 个长度为 k 二进制串，现在要从中选出 m 个二进制串，使得每一位的 1 的数量不能大于 0 的数量。

$1 \le n \le 10^5, 1 \le k \le 4$

解题过程：

比赛的时候一直没思路，于是乱写了一个假算法，对每个串分配权重并贪心，不过居然能过，不过还是被 Hack 掉了。

题目分析：

首先，这里 K 非常小，所以最多也就是有 16 种不同的串，考虑用桶来统计。

然后假设有一个解，那么可以证明，至多只需要选两个串就可以满足题目要求（如果存在 0000 的串，那么只需这一个串就可以满足题目要求了）。

那么这时候我们暴力枚举这如果串就可以了，复杂度$O(16\times 16)$

AC代码：

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
#include <bits/stdc++.h>

using namespace std;

//统计每个串的出现次数
int data[1123];

int main() {
    int n, k;
    cin >> n >> k;
    while (n--) {
        int temp = 0, cnt = 1;
        for (int i = 1; i <= k; i++) {
            int t;
            cin >> t;
            temp += t * cnt;
            cnt *= 2;
        }
        data[temp]++;
    }
    //如果存在 0000 这样的串，那么只选这一个串就可以了
    if (data[0]) {
        printf("YES\n");
        return 0;
    } else {
        //枚举如果串
        for (int i = 0; i < (1 << k); i++) {
            if (!data[i]) continue;
            data[i]--;
            for (int j = 0; j < (1 << k); j++) {
                //这里要保证两个串的每一位至少有一个是 0，那么他们 and 操作结果是 0
                if ((i & j) == 0 && data[j]) {
                    printf("YES\n");
                    return 0;
                }
            }
            data[i]++;
        }
    }
    printf("NO\n");
}
音乐►乐理

口琴用简谱简易教程

简介

音乐的构成主要由以下四个要素：

  • 音的高低
  • 音的长短
  • 音的强弱
  • 音的音质

这里主要说下简谱对于音的高低和音的长短是怎么表示的。

音高

在简谱中最基本的符号就是音符，音符用 1 - 7 的数字来表示，分别代表音的高低，对应读法依次是 do re mi fa so la si。所以说一个音符的写法就代表了这个音的高低。

但是只用 7 个数字来表示所有音的高低未免太少了些，而且人们发现声音的高低之间也是有规律的，所以可以把音的高低分为七个一组。于是有了低音，中音，高音之分，对于口琴来说了解这些已经够用了。

中音就是直接用 1 - 7 来表示，高音是给数字上面加一个点从 $\dot{1} $ - $\dot{7}$，低音同理不过点是画在下面的。

上图对应半音阶的孔位布局，还是比较容易理解的，每个孔对应两个音高，左边的是吹音，右边的是吸音。口琴是包括吹和吸的（所以不像网上别人说的那样，“这个人口琴好厉害呀，肺活量一定很大吧”之类的）。

这里需要注意的是，半音阶是有一个半音的，加音符前面加一个 #，例如 #1，这个半音就是指一个介于 1 与 2 之间的音。

所以半音阶对比其他孔数相同的口琴，多了一倍的音。比如 12 孔的半音阶，吹吸分别是两个音，然后按下推键之后又是两个音，所以是 $12 \times 2 \times 2 = 48$ 个音。

音长

很多谱子上面有一个 $\frac{4}{4}$的符号，对于$\frac{a}{b}$ 的含义是，以 b 分音符为一拍，每小节有 a 拍。

至于一拍有多长时间，这个就见仁见智了，所以说每一拍的时长都是相对的，但是节奏是有序的。

音符分为

  • 全音符 1———
  • 二分音符1—
  • 四分音符1
  • 八分音符$\underline{1}$

（其实还有十六分音符，三十二分音符，对应的把下划线多划几道就是了）

乐谱中基本上以四分音符为主，确定号四分音符的时长，其他的都是根据四分音符得来的。

比如，一个四分音符吹 1 s 那么对应的一个八分音符需要吹 0.5 s 。

另外还有一种经常见到的是连音线。这里无法用数学公式打出，只好复制图片了。

最后，乐谱中常见的那一个竖线，是小节线，表示一小结的结束。

常见的纯数字谱

好多人为了在网上记谱方便，用 1 代表中音 1，(1) 代表低音 1，[1] 代表高音1。

但是这并不是硬性规定，也可以用 1 代表低音，[1]，至于这点，一般会给出说明的，如果没有的话试一下就好了。

例如下面的天空之城谱子 [] 表示高音，不加任何括号是低音。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
7[#1] [2][#1][2][#4][#1]
#4#4767[2]6
#4#45#45[2]#4
[2] [2] [2][#1]#5#5[#1][#1]
7[#1] [2][#1][2][#4][#1]
#4#4767[2]6
#45[2][#1][#1][2][3][3][#4][2]
[2][#1]77[#1]#67
[2][3][#4][3][#4][6][3]
66[2][#1][2][#4][#4]
7[#1][2][#1][3][3][2]66
[5][#4][3][2][#4]
[#4][7][6] [6][#4][3][2]
[2][3][2][3][3][6][#4]
[#4][7][6][#4][3][2]
[2][3][2][3][3][#1]7

不过这样完全看不出来音长了，只能凭感觉，所以建议找铺子的时候去找规范的简谱，这种谱子到时比较普及就是了。

ACM►数据结构►主席树

主席树（模板）

感谢&资料：

感谢 bLue 学长的讲堂（虽然之前就差不多学会了），和卿学姐的视频。

简介：

只是刚入门，这里当做存一个模板，主席树的功能是可以存储历史版本的线段树，然后可以干很多神奇的事情。

代码：

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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 112345;

struct Node {
    int sum, l, r;
} tree[MAX * 40];

int root[MAX], cnt;
int data[MAX];
vector<int> sorted;

//离散化获得ID
int get_id(int x) {
    return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
}

void init() {
    cnt = 0;
    root[0] = 0;
}

//根据旧版本的线段树创建新线段树的节点
int create_node(int po) {
    int idx = ++cnt;
    tree[idx].sum = tree[po].sum + 1;
    tree[idx].l = tree[po].l;
    tree[idx].r = tree[po].r;
    return idx;
}

void updata(int &o, int po, int l, int r, int pos) {
    o = create_node(po);
    if (l == r) return;
    int m = (l + r) >> 1;
    if (pos <= m) updata(tree[o].l, tree[po].l, l, m, pos);
    else updata(tree[o].r, tree[po].r, m + 1, r, pos);
}

//二分查询
int query(int s, int e, int l, int r, int k) {
    if (l == r) return l;
    int m = (l + r) >> 1;
    int sum = tree[tree[e].l].sum - tree[tree[s].l].sum;
    if (k <= sum) return query(tree[s].l, tree[e].l, l, m, k);
    else return query(tree[s].r, tree[e].r, m + 1, r, k - sum);
}

int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &data[i]);
            sorted.push_back(data[i]);
        }
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        int num = sorted.size();
        for (int i = 1; i <= n; i++) {
            updata(root[i], root[i - 1], 1, num, get_id(data[i]));
        }
        for (int i = 1; i <= m; i++) {
            int x, y, k;
            scanf("%d %d %d", &x, &y, &k);
            printf("%d\n", sorted[query(root[x - 1], root[y], 1, num, k) - 1]);
        }
    }
}