一共4道题目，2个小时。
题目1 - 圆桌座位
$N$ 个人围坐一圈，有 $M$ 对朋友关系。
第 $i$ 对朋友关系是指，编号是 $a_i$ 的人和编号是 $b_i$ 的人是朋友。
现在要给他们安排座位，要求所有相邻的人不能是朋友。问共有多少种方案？
如果两个方案只有旋转角度不同，则我们将其视为一种方案。
数据范围
- $3 \le N \le 10$
- $0 \le M \le N(N-1)/2$
- $1 \le a_i \lt b_i \le N$
- $(a_i, b_i) \neq (a_j, b_j)$
- 所有输入均是整数
输入格式
$N \ M$
$a_1 \ b_1$
…
$a_M \ b_M$
输出格式
输出一个数，表示总方案数
样例1
输入：
4 1
1 2
输出：
2
样例2
输入：
10 5
1 2
3 4
5 6
7 8
9 10
输出：
112512
算法
(DFS) $O(n!)$
首先，为了避免旋转造成的重复计数问题，我们将编号是1的人固定在1号位置。
然后从2号位置开始，依次枚举每个位置放哪个人，注意只能放跟上一个人没有朋友关系的人。
枚举到最后一个人时，如果他跟编号是1的人不是朋友，说明方案合法，我们将方案数加一。
时间复杂度分析：第一个人位置固定，那么剩下的人总共有 $(N-1)!$ 种放法，所以时间复杂度是 $O(N!)$。$N$最大是10，所以方案最多有 326880种，计算量可以接受。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 11;
int n, m, ans;
bool g[N][N], st[N];
void dfs(int u, int last_id)
{
if (u == n)
{
ans += !g[last_id][1];
return;
}
for (int i = 1; i <= n; i ++ )
if (!st[i] && !g[i][last_id])
{
st[i] = true;
dfs(u + 1, i);
st[i] = false;
}
}
int main()
{
cin >> n >> m;
for (int i = 0, a, b; i < m; i ++ )
{
cin >> a >> b;
g[a][b] = g[b][a] = true;
}
st[1] = true;
dfs(1, 1);
cout << ans << endl;
return 0;
}
题目2 - 求区间和
给定 $N$ 个整数 $a_1, a_2, … a_N$。
然后给出 $Q$ 个询问，第 $j$ 个询问给出两个整数 $x_j, y_j$，请计算所有 $|a_k|$ 的和，满足 $x_j \le k \le y_j$。
数据范围
- $1 \le N \le 10^5$
- $-10^9 \le a_i \le 10^9(1 \le i \le N)$
- $1 \le Q \le 10^5$
- $1 \le x_j \le y_j \le N(1 \le j \le Q)$
- 所有输入均是整数
输入格式
$N$
$a_1$
…
$a_N$
$Q$
$x_1 \ y_1$
…
$x_Q \ y_Q$
输出格式
输出 $Q$ 个数，分别表示每个询问的答案。
样例
输入：
6
1
-2
3
-4
5
6
3
1 2
2 4
3 6
输出：
3
9
18
算法
(前缀和) $O(N + Q)$
因为所有询问都是求绝对值的和，所以我们先将所有数取绝对值。
然后预处理出原数组的前缀和，使得 $S_i = \sum_{k=1}^ia_k$。
则 $\sum_{k=x}^ya_k = S_y - S_{x-1}$。
所以对于每个询问，我们可以直接用两个前缀和做差得到区间和。
时间复杂度分析：初始化复杂度是 $O(N)$，每个询问的复杂度是 $O(1)$，共有 $Q$ 个询问，所以总时间复杂度是 $O(N + Q)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
int a[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i], a[i] = abs(a[i]);
cin >> m;
for (int i = 1; i <= n; i ++ ) a[i] += a[i - 1];
for (int i = 0; i < m; i ++ )
{
int x, y;
cin >> x >> y;
cout << a[y] - a[x - 1] << endl;
}
return 0;
}
题目3 - 最短距离
有 $N$ 个村庄，编号1到 $N$。村庄之间有 $M$ 条无向道路，第 $i$ 条道路连接村庄 $a_i$ 和村庄 $b_i$，长度是 $c_i$。
所有村庄都是连通的。
共有 $K$ 个村庄有商店，第 $j$ 个有商店的村庄编号是 $x_j$。
然后给出 $Q$ 个询问，第 $k$ 个询问给出一个村庄的编号 $y_k$，问该村庄距离最近的商店有多远？
数据范围
- $2 \le N \le 10^5$
- $N-1 \le M \le min(N(N-1)/2, 10^5)$
- $1 \le Q \le 10^5$
输入格式
$N \ M$
$a_1 \ b_1 \ c_1$
…
$a_M \ b_M \ c_M$
$K$
$x_1$
…
$x_K$
$Q$
$y_1$
…
$y_Q$
输出格式
对于每个询问，输出该询问的结果。
样例
输入：
7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7
输出：
3
1
3
0
0
6
0
算法
(最短路) $O(km)$
由于 $N$ 和 $Q$ 都是 $10^5$ 级别的，所以我们不可能对每个询问，都求一遍单源最短路，会超时。
我们可以建立一个虚拟起点 $S$，然后从 $S$ 向每个有商店的村庄连一条长度是0的边。
然后求一遍以 $S$ 为起点的单源最短路。
此时，对于每个询问 $y_k$，$y_k$ 到 $S$ 的最短距离，就是 $y_k$ 到所有商店的最短距离。
这是因为从 $S$ 到 $y_k$ 的每条路径，都必然先走到某个商店，且走过的路程是0，然后再走向 $y_k$，所以 $S$ 到 $y_k$ 的最短路，就是所有商店到 $y_k$ 的最短路。
时间复杂度分析：我们用 $SPFA$ 算法求单源最短路经，它的时间复杂度期望是 $O(km)$，其中 $k$ 是常数，最坏是 $O(nm)$，最坏情况很难达到。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 300010, INF = 1000000000;
int n, m;
int h[N], e[M], ne[M], v[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, v[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa()
{
queue<int> que;
for (int i = 1; i <= n; i ++ ) dist[i] = INF;
st[0] = true;
que.push(0);
while (que.size())
{
int t = que.front();
que.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
if (dist[e[i]] > dist[t] + v[i])
{
dist[e[i]] = dist[t] + v[i];
if (!st[e[i]])
{
que.push(e[i]);
st[e[i]] = true;
}
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
int K;
cin >> K;
for (int i = 0; i < K; i ++ )
{
int id;
cin >> id;
add(0, id, 0);
}
spfa();
int Q;
cin >> Q;
for (int i = 0; i < Q; i ++ )
{
int id;
cin >> id;
cout << dist[id] << endl;
}
return 0;
}
题目4 - 设计密码
你现在需要设计一个密码 $S$，$S$ 需要满足：
- $S$ 的长度是 $N$；
- $S$ 只包含小写英文字母；
- $S$ 不包含子串 $T$；
例如：abc和abcde是abcde的子串，abd不是abcde的子串。
请问共有多少种不同的密码满足要求？
由于答案会非常大，请输出答案模 $10^9+7$ 的余数。
数据范围
- $1 \le N \le 50$
- $1 \le |T| \le N, |T| 是 T 的长度$
- $T$ 只包含小写英文字母
输入格式
$N$
$T$
输出格式
一个数，表示总方案数模 $10^9+7$。
样例1
输入：
2
a
输出：
625
样例2
输入：
4
cbc
输出：
456924
样例3
输入：
3
xy
输出：
17524
样例4
输入：
50
password
输出：
448890425
算法1
(动态规划+KMP) $O(N^3)$
首先我们用KMP求出 $T$ 的 $next$ 数组。
然后我们回忆利用 $next$ 数组在长文本中匹配模板串 $T$ 的过程：如果下一个字母不匹配，需要一直沿着next指针找：j = next[j]，直到下一个字符匹配或者next指针指向开头为止。
然后我们会发现，假设我们已经匹配完长文本的前 $i$ 个字母，则剩下部分的匹配过程，只跟next指针的位置有关，因此我们可以用二维数组来表示当前状态的方案数：
f[i][j]表示匹配完前 $i$ 个字母时，next指针在 $j$ 时的方案总数。
状态转移也很自然：对于每个状态f[i][j]，我们从'a'-'z'枚举下一个字母，然后求出对应的next指针，假设是 $u$，则将f[i][j]的方案总数累加到f[i+1][u]。
转移过程中需要注意，因为密码中不能存在 $T$，所以next指针要避免转移到 $T$ 的最后一个字母。
时间复杂度分析：用KMP求next数组的时间复杂度是 $O(N)$，动态规划的状态有 $N^2$ 个，状态转移的计算量是 $25N$，所以总时间复杂度是 $O(25N^3) = O(N^3)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
const int N = 55, MOD = 1000000007;
int n, m;
string T;
int f[N][N];
int nxt[N];
void kmp()
{
m = T.size();
T = ' ' + T;
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && T[j + 1] != T[i]) j = nxt[j];
if (T[j + 1] == T[i]) j ++ ;
nxt[i] = j;
}
}
int main()
{
cin >> n >> T;
kmp();
f[0][0] = 1;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
for (char k = 'a'; k <= 'z'; k ++ )
{
int u = j;
while (u && k != T[u + 1]) u = nxt[u];
if (k == T[u + 1]) u ++;
if (u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
}
}
int res = 0;
for (int i = 0; i < m; i ++ ) res = (res + f[n][i]) % MOD;
cout << res << endl;
return 0;
}
算法2
(动态规划)$O(N^2)$
感谢评论区同学提供的一个很优秀的做法！时间复杂度与字符集大小无关，只有 $O(N^2)$。
我们从后往前不断添加新字符。
状态表示：$f[i][j]$ 表示长度为 $i$，以 $T$ 的末尾 $j$ 个字符开头，且包含 $T$ 的字符串个数。
注意：$f[i][j]$ 并不以最大后缀分类，所以 $f[i][j]$ 和 $f[i][k], (j \neq k)$ 可能包含相同字符串。
所以所有包含 $T$ 的字符串都在 $f[n][0]$中，所以答案就是 $26^n - f[n][0]$。
状态转移：
令 $m$ 表示 $T$ 的长度。
- 如果 $i \lt m$，则 $f[i][j] = 0$；
-
如果 $i \ge m$：
当 $j = 0$ 时，$f[i][j] = 26^{i - m} - f[i - 1][m - 1] + 26 \times f[i - 1][0]$。- $S_1$ 表示以 $T$ 开头，总长度为 $m$ 的字符串集合，$|S_1| = 26^{m-l}$;
- $S_2$ 表示在 $f[m-1][0]$ 所对应字符串的开头拼上任意字母组成的集合，$|S_2| = 26 \times f[m-1][0]$;
- $S_3$ 表示以 $T$ 开头，且除了开头，在其它地方也出现过 $T$ 的字符串集合，$|S_3| = f[m-1][l-1]$；
- $S$ 表示 $f[m][0]$ 对应的字符串集合;
则 $S_1 - S_3$ 表示以 $T$ 开头，且 $T$ 不出现在其它地方的字符串集合。$S_2$ 表示在其它地方出现 $T$ 的字符串集合，所以 $S = S_1 - S_3 + S_2$。
当 $j \neq 0$ 时，- 首先 $f[i][j]$ 可以从 $f[i - 1][j - 1]$ 转移过来，直接在字符串前面加上 $T[-j]$ 即可；
- 当 $T$ 的前 $j$ 个字符和后 $j$ 个字符匹配时，$f[i][j]$ 同时要加上以 $T$ 开头，但其它地方不包含 $T$ 的字符串数量。
时间复杂度分析：总共 $N^2$ 个状态，状态转移的复杂度是 $O(1)$，所以总共时间复杂度是 $O(N^2)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55, MOD = 1000000007;
int n, m;
int f[N][N];
bool ismatch[N];
int pow26[N];
string T;
int pow26f(int k)
{
long long res = 1;
while (k -- ) res = res * 26 % MOD;
return (int)res;
}
bool match(int k)
{
for (int i = 0, j = m - k; i < k; i ++ )
if (T[i] != T[j])
return false;
return true;
}
int main()
{
cin >> n >> T;
m = T.size();
for (int i = 0; i <= n; i ++ ) pow26[i] = pow26f(i);
for (int i = 0; i <= n; i ++ ) ismatch[i] = match(i);
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < m; j ++ )
{
if (i < m) f[i][j] = 0;
else
{
if (!j) f[i][j] = (int)((pow26[i - m] - f[i - 1][m - 1] + 26ll * f[i - 1][0]) % MOD);
else
{
f[i][j] = f[i - 1][j - 1];
if (ismatch[j])
f[i][j] = (pow26[i - m] - f[i - 1][j - 1]) % MOD;
}
}
}
cout << pow26[n] - f[n][0] << endl;
return 0;
}
用f[m][n]表示满足下列三点的字符串的个数:
1 总长度为m
2 以T的末尾n个字符串开头
3 包含T
那么要求的就是26^N - f[N][0]
感觉这题有点难啊，不知道上面写的对不对(
同学你的思路很有趣诶，我验证了一下没有问题！
如上文所示，已经采纳进了题解里hh
总觉得最后求转移那里复杂度可以优化
假设我预处理对每个字符k算出最后的u，那么状态转移可否从O（25N）变为O（25），从而整个时间复杂度降到N^2？
可以的，由于给定字符k，以及next指针j以后，我们转移时计算得到的u是确定的，所以可以预处理出所有k和j对应的u，从而把时间复杂度降到$O(N^2)$。
由于这道题目的N最大是50，所以当时就没再进行优化hh