动态规划(三)

SP913 Qtree2

Brief Description

给定一棵$n$个点的树,边具有边权。要求作以下操作:

  • DIST a b 询问点a至点b路径上的边权之和
  • KTH a b k 询问点a至点b有向路径上的第k个点的编号

Solution

使用树上倍增求最近公共祖先, 对于两种操作:

  1. 维护点到根节点的距离, 那么$Dis_{a,b}=Dis_{a, root}+Dis_{b,root}-2Dis_{lca_{a,b}, root}$.
  2. 若$a$到根节点路径上点的个数小于等于$k$个, 则答案为$a$的第$k - 1$个祖先;
     否则, 答案为$b$的第$dep_b+dep_a-2\cdot dep_{lca_{a,b}}-k+1$个祖先.

Code

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 10006;
struct Edge {
int v, nxt, c;
}e[N << 1];
int head[N], tot;
void Add(int u, int v, int c) {
e[++tot] = (Edge) { v, head[u], c}; head[u] = tot;
e[++tot] = (Edge) { u, head[v], c}; head[v] = tot;
}
int f[N][15], dep[N], dis[N];
int dfs(int u) {
for (int i = head[u]; i; i = e[i].nxt) {
if (e[i].v == f[u][0]) continue;
dep[e[i].v] = dep[u] + 1,
dis[e[i].v] = dis[u] + e[i].c, f[e[i].v][0] = u;
dfs(e[i].v);
}
}
void Clear() {
memset(head, false, sizeof head), tot = 0;
}
int lca(int u, int v) {
if (dep[u] < dep[v]) std:: swap(u, v);
for (int i = 14; ~i; i -= 1)
if (dep[f[u][i]] >= dep[v])
u = f[u][i];
for (int i = 14; ~i; i -= 1)
if (f[u][i] != f[v][i])
u = f[u][i], v = f[v][i];
return u == v ? u : f[u][0];
}
int Find(int u, int k) {
if (not k) return u;
for (int i = 14; ~i; i -= 1)
if (k & (1 << i))
u = f[u][i];
return u;
}
int main () {
int T; scanf("%d", &T);
while (T --) {
Clear();
int n; scanf("%d", &n);
for (int i = 1; i < n; i += 1) {
int u, v, c; scanf("%d%d%d", &u, &v, &c);
Add(u, v, c);
}
dfs(1);
for (int i = 1; i <= 14; i += 1)
for (int j = 1; j <= n; j += 1)
f[j][i] = f[f[j][i - 1]][i - 1];
std:: string str; std:: cin >> str;
while (str != "DONE") {
int u, v;
scanf("%d%d", &u, &v);
if (str == "DIST")
printf("%d\n", dis[u] + dis[v] - dis[lca(u, v)] * 2);
else {
int k; scanf("%d", &k);
int Lca = lca(u, v);
if (dep[u] - dep[Lca] < k)
printf("%d\n", Find(v, dep[v] + dep[u] + 1 - 2 * dep[Lca] - k));
else printf("%d\n", Find(u, k - 1));
}
std:: cin >> str;
}
}
return 0;
}

P2258 子矩阵

Brief Description

给出如下定义:

  • 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。
  • 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
  • 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。

本题任务:给定一个$n$行$m$列的正整数矩阵,请你从这个矩阵中选出一个$r$行$c$列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。

Solution

比较慢但是好理解的一种状压dp做法.

  • 设$f_{i,j,k}$表示每列的状态为$i$, 当前选到第$j$行一共选了$k$行的最小代价;
  • $Cost_{i,j,k}$表示每行的状态为$i$时相邻两行为$j,k$时产生的代价.
  • $Val_{i,j}$表示每行的状态为$i$时, 第$j$行产生的
    则:
    $$
    \begin{aligned}
    f_{i,j,k}=
    \begin{cases}
    \min f_{i,l,k-1}+Cost_{i,l,j}+Val_{i,j}, k>1\\
    Val_{i,j}, k = 1
    \end{cases}
    \end{aligned}
    $$

Code

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
#include <vector>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 19;
const int Max = 65537;
const int inf = 0x3f3f3f3f;
int matrix[N][N];
int R[N][Max];
std:: vector<int> status;
void dfs(int sta, int s, int end, int n, int m, int c) {
if (s == c) status.push_back(sta);
for (int i = end + 1; i < m; i += 1) {
if (~end)
for (int k = 0; k < n; k += 1)
R[k][sta + (1 << i)] = R[k][sta] + abs(matrix[k][i] - matrix[k][end]);
dfs(sta + (1 << i), s + 1, i, n, m, c);
}
}
int f[N][N];
int Cost[Max][N][N];
int main () {
int n, m, r, c;
scanf("%d%d%d%d", &n, &m, &r, &c);
for (int i = 0; i < n; i += 1)
for (int j = 0; j < m; j += 1)
scanf("%d", &matrix[i][j]);
int Max = 1 << m, MM = 1 << n;
bool flag = true;
dfs(0, 0, -1, n, m, c);
for (int z = 0; z < status.size(); z += 1) {
int Status = status[z];
for (int i = 0; i < m; i += 1)
if (Status & (1 << i)) {
for (int j = 0; j < n; j += 1)
for (int k = j + 1; k < n; k += 1)
Cost[Status][j][k] += abs(matrix[j][i] - matrix[k][i]),
Cost[Status][k][j] += abs(matrix[j][i] - matrix[k][i]);
}
}
int res = inf;
for (int i = 0; i < status.size(); i += 1) {
int Res = inf;
int Status = status[i];
memset(f, 0x3f, sizeof f);
for (int j = 0; j < n; j += 1)
f[j][1] = R[j][Status];
for (int j = 1; j < n; j += 1)
for (int k = 2; k <= std:: min(j + 1, r); k += 1) {
for (int l = 0; l < j; l += 1)
f[j][k] = std:: min(f[j][k],
f[l][k - 1] + Cost[Status][j][l] + R[j][Status]);
if (k == r) Res = std:: min(Res, f[j][k]);
}
res = std:: min(res, Res);
if (Status == 13) {
}
}
printf("%d\n", res);
return 0;
}

MIoj94 能让你快回来的诗篇

Brief Description

用一个字符集中的字符写出长度为$n$ 且不出现某个字符串$S$的所有字符串, 求方案总数
模 $10^9 +7$ 的结果. 其中字符集中的字符最多只包含 $26$ 个小写字母, $n<10^9$ , S 的长度小于 $50$.

Solution

有一道很类似的题目, 如果将它的情况加以延伸, 就可以得到这道题的做法.

考虑动态规划, $f_{i,j}$表示$i$位的字符串最后面$j$个字符是妹子不喜欢字符串的前$j$个字符时的方案数.那么如何转移呢?

  • $f_{i,j}\rightarrow f_{i+1,j+1}$;表示加一个不喜欢字符串中的字符;
  • $f_{i,j}\rightarrow f_{i+1,k}$表示构成的字符串的一个后缀是妹子不喜欢字符串的一个前缀$k$.

可以很明显的发现后面那个转移需要用kmp来求, 暴力当然可以就是比较naive.

因为n略大, 需要用矩阵快速幂优化.

Code

PythonC++各写了一份, 因为一开始写的Python超时了, 不仅仅是因为Python效率低, 而且我的Py代码质量也低的吓人.

所有用Python写这道题的人都超时了

Python

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
def Mul(a, b, r, c, l):
res = []
for i in range(r):
res.append([])
for j in range(c):
res[i].append(0)
for k in range(l):
res[i][j] += a[i][k] * b[k][j]
if res[i][j] > 1000000000:
res[i][j] %= 1000000007
return res
def Pow(a, b, n):
res = []
for i in range(n):
res.append([])
for j in range(n):
res[i].append(1 if i == j else 0)
base = a
while b:
if b & 1:
res = Mul(base, res, n, n, n)
base = Mul(base, base, n, n, n)
b /= 2
return res
def get_next(string, ch):
next = [0]
nxt = []
Len = len(string)
n = len(ch)
for i in range(n):
nxt.append([0])
j = 0
for i in range(1, Len):
while j and string[i] != string[j]:
j = next[j - 1]
if string[j] == string[i]:
j += 1
next.append(j)
for i in range(Len - 1):
for j in range(n):
if ch[j] == string[i + 1]:
nxt[j].append(0)
continue
k = next[i]
while k and ch[j] != string[k]:
k = next[k - 1]
if ch[j] == string[k]:
k += 1
nxt[j].append(k)
return nxt
def solution(line):
tmp = line.split(';')
n = int(tmp[0])
ch = tmp[1]
string = tmp[2]
Len = len(string)
lenn = len(ch)
nxt = get_next(string, ch)
# Output(nxt)
f = []
for i in range(Len):
f.append([])
for j in range(Len):
f[i].append(0)
for i in range(Len):
for j in range(lenn):
if ch[j] == string[i]:
continue
if nxt[j][i] != 0:
f[i][nxt[j][i]] += 1
else:
f[i][0] += 1
if i < Len - 1:
f[i][i + 1] += 1
f = Pow(f, n - 1, Len)
g = [[lenn - 1, 1]]
for i in range(2, Len):
g[0].append(0)
res = Mul(g, f, 1, Len, Len)
reslut = 0
for i in range(Len):
reslut += res[0][i]
return reslut % 1000000007

C++

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 51;
const long long mod = 1e9 + 7;
int ReadInt (char *line) {
int f = 1;
while (not isdigit(line[0])) {
if (line[0] == '\0') return -1;
line = line + 1;
}
int s = 0;
while (isdigit(line[0])) {
s = s * 10 + line[0] - '0';
line = line + 1;
}
return s * f;
}
struct Matrix {
long long m[N][N];
int r, c;
Matrix () { memset(m, false, sizeof m); }
Matrix (int n) {
r = c = n;
memset(m, false, sizeof m);
for (int i = 0; i < n; i += 1) m[i][i] = 1;
}
Matrix (int _, int __) : r(_), c(__) { memset(m, false, sizeof m); }
Matrix (int _, int __, long long (*ha)[N]) {
r = _, c = __;
for (int i = 0; i < r; i += 1)
for (int j = 0; j < c; j += 1)
m[i][j] = ha[i][j];
}
Matrix operator * (const Matrix& o) const {
Matrix res = Matrix(r, o.c);
for (int i = 0; i < r; i += 1)
for (int j = 0; j < o.c; j += 1)
for (int k = 0; k < c; k += 1) {
res.m[i][j] += this->m[i][k] * o.m[k][j] % mod,
res.m[i][j] %= mod;
}
return res;
}
Matrix operator ^ (int pow) const {
Matrix res = Matrix(r), base = *this;
while (pow) {
if (pow & 1)
res = res * base;
base = base * base;
pow >>= 1;
}
return res;
}
};
int nxt[N][N];
int cnt[N];
void getNext(char *string, char *ch) {
int *next = new int[N];
int Len = strlen(string);
int n = strlen(ch);
memset(next, false, sizeof next);
memset(nxt , false, sizeof nxt );
memset(cnt , false, sizeof cnt );
int j = 0;
for (int i = 1; i < Len; i += 1) {
while (j and string[i] != string[j])
j = next[j - 1];
if (string[j] == string[i])
j += 1;
next[i] = j;
}
for (int i = 0; i < Len - 1; i += 1) {
for (auto j = 0; j < n; j += 1) {
if (ch[j] == string[i + 1]) {
nxt[j][++cnt[j]] = 0;
continue;
}
int k = next[i];
while (k and ch[j] != string[k])
k = next[k - 1];
if (ch[j] == string[k])
k += 1;
nxt[j][++cnt[j]] = k;
}
}
}
long long solution(char*, char*, int);
char ch[10005];
int main () {
while (std:: cin.getline(ch, 10005)) {
int n = ReadInt(ch);
if (n == -1) break;
char *l1 = strstr(ch, ";") + 1, *l2 = strstr(l1, ";") + 1;
*(l2 - 1) = '\0';
printf("%d\n", solution(l2, l1, n));
}
return 0;
}
long long f[N][N];
long long solution(char *string, char *ch, int n) {
int Len = strlen(string), lenn = strlen(ch);
getNext(string, ch);
memset(f, false, sizeof f);
for (auto i = 0; i < Len; i += 1) {
for (auto j = 0; j < lenn; j += 1) {
if (ch[j] == string[i])
continue;
if (nxt[j][i])
f[i][nxt[j][i]] += 1;
else f[i][0] += 1;
}
if (i < Len - 1)
f[i][i + 1] += 1;
}
Matrix A = Matrix(Len, Len, f);
A = A ^ (n - 1);
Matrix B = Matrix(1, Len);
B.m[0][0] = lenn - 1, B.m[0][1] = 1;
Matrix Res = B * A;
long long res = 0;
for (auto i = 0; i < Len; i += 1)
res = (res + Res.m[0][i]) % mod;
return res % mod;
}
-------------本文结束感谢您的阅读-------------