字符串哈希

什么是字符串哈希

字符串Hash可以通俗的理解为,把一个字符串转换为一个整数

如果我们通过某种方法,将字符串转换为一个整数,就可以便的确定某个字符串是否重复出现过,这是最简单的字符串Hash应用情景了。

当然也不难想到,如果有不同的两个字符串同时Hash到一个整数,这样就比较麻烦了。我们希望这个映射是一个单射,所以问题就是如何构造这个Hash函数,使得他们成为一个单射。

Hash方法

给定字符串 s,则 asc[s[i]] = s[i] - ‘a’ + 1.

自然溢出方法

1
2
unsigned long long Hash[n];
Hash[i] = Hash[i - 1] * p + asc[s[i]]

利用unsigned long long的范围自然溢出,相当于自动对 2^64 -1 取模。

单哈希方法

1
Hash[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD

其中 p 和 MOD 均为质数,且有 p < MOD。

对于此种Hash方法,将 p 和 MOD 尽量取大即可,这种情况下,冲突的概率是很低的。

如取 p = 13, MOD = 101, 对字符串 “abc” 进行Hash。这里注意asc[s[i]]是s[i]的ascii码加1.

Hash[0] = 1;

Hash[1] = (Hash[0] * 13 + 2) % 101 = 15; // s[i] = ‘b’, asc[s[i]] = ‘b’ - ‘a’ + 1 = 2

Hash[2] = (Hash[1] * 13 + 3) % 101 = 97;

结果是Hash[n],即Hash[2]。所以此时认为 97 就是字符串”abc”的值。

双哈希方法

将一个字符串用不同的MOD Hash两次,将这两个结果用一个二元组表示,作为Hash结果。

1
2
Hash1[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD1;
Hash2[i] = (Hash[i - 1] * p + asc[s[i]]) % MOD2;

Hash的结果为 < Hash1[n], Hash2[n] >

这种Hash很安全。

求子串公式

假设有一个∣S∣=5 的字符串,设 Si 为第 i 个字符,其中 1 ≤ i ≤ 5。

根据定义分别求出hash[i]:

hash[1] = s1;

hash[2] = s1 ∗ p + s2;

hash[3] = s1 ∗ p^2 + s2 ∗ p + s3;

hash[4] = s1 ∗ p^3 + s2 ∗ p^2 + s3 ∗ p + s4;

hash[5] = s1 ∗ p^4 + s2 ∗ p^3 + s3 ∗ p^2 + s4 ∗ p + s5;

现在要求子串 s3s4 的hash值,不难得出为s3 ∗ p + s4。
Hash[4] - Hash[2] * pow(p, 4 - 3 + 1)

所以公式如下:

Hash[l~r] = Hash[r] - Hash[l - 1] * pow(p, r - l + 1)

考虑到取模:

Hash[l~r] = ((Hash[r] - Hash[l - 1] * pow(p, r - l + 1)) % MOD + MOD) % MOD

应用

POJ2774

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define maxn 100010
#define p 131
// #define INF 0x3f3f3f3f
// #define MOD 1000000007

// Hash1和Hash2存储两个字符串的哈希值,
// po记录p的乘方(相当于转化为p进制),tmp用于比较(后面会讲解)
ull Hash1[maxn], Hash2[maxn], po[maxn], tmp[maxn];
int len1, len2; // 两字符串的长度
char s1[maxn], s2[maxn];

// 求h的子串s[l~r](包括s[l]和s[r])的Hash值
ull getHash(ull* h, int l, int r) {
return h[r] - h[l - 1] * po[r - l + 1];
}

/*
check函数用来判断是否有长度为len的相同子串
先将Hash1的长度为len的子串的Hash值依次求出,存入tmp数组中
将tmp由小到大排序(这里排序只是为了便于Hash2的二分查找)
因为二分查找要求数组有序!
*/
bool check(int len) {
int cnt = 0;
for(int i = 1; i + len - 1 <= len1; i++)
tmp[cnt ++] = getHash(Hash1, i, i + len - 1);
sort(tmp, tmp + cnt);
for(int i = 1; i + len - 1 <= len2; i++) {
ull x = getHash(Hash2, i, i + len - 1);
if(binary_search(tmp, tmp + cnt, x)) return true;
// 这里用到了<algorithm>中的binary_search函数,这是一个bool类型函数,
// 是在[tmp, tmp + cnt),即[tmp, tmp + cnt - 1]范围内
// 二分查找x,如果找到了就返回true,否则返回false
}
return false;
}

void init_po() { // 将p的乘方都算出来,打表
po[0] = 1;
for(int i = 1; i < maxn; i++)
po[i] = po[i - 1] * p;
}

int main() {
init_po();
while(~scanf("%s%s", s1 + 1, s2 + 1)) { // s1和s2都从索引1开始存储
len1 = strlen(s1 + 1);
len2 = strlen(s2 + 1);

// 计算s1和s2的Hash值
Hash1[0] = Hash2[0] = 0;
for(int i = 1; i <= len1; i++)
Hash1[i] = Hash1[i - 1] * p + (s1[i] - 'a');
for(int i = 1; i <= len2; i++)
Hash2[i] = Hash2[i - 1] * p + (s2[i] - 'a');

// 二分查找最大长度
int l = 0, r = min(len1, len2);
int ans = 0;
while(l <= r) {
int m = (l + r) >> 1; // 移位更快
if(check(m)) { // 如果m满足长度为m的子串相等
l = m + 1; // 就增大左边界l,看看有没有更大的长度
ans = m; // ans更新为当前的最大值
}
else
r = m - 1; // 没有找到,那就先减小右边界看看有没有符合的m
}
printf("%d\n", ans);
}
return 0;
}

最大公共子序列和最大公共子串

最大公共子序列

最大公共子串

动态规划(未优化)

动态规划(一级空间优化)

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
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

char s1[1000001], s2[1000001];
int dp[2][1000005];

int lcs() {
int len1 = strlen(s1), len2 = strlen(s2);
int i, j, cur = 1, pre = 0, cnt = 0;
if(len2 > len1) {
for(i = 0; i <= len2; i++) dp[0][i] = 0;
dp[1][0] = 0;
for(i = 1; i <= len1; i++) {
for(j = 1; j <= len2; j++) {
if(s1[i - 1] == s2[j - 1]) {
dp[cur][j] = dp[pre][j - 1] + 1;
cnt = max(cnt, dp[cur][j]);
}
else dp[cur][j] = 0;
}
swap(cur, pre);
}
return cnt;
}
else {
for(i = 0; i <= len1; i++) dp[0][i] = 0;
dp[1][0] = 0;
for(i = 1; i <= len2; i++) {
for(j = 1; j <= len1; j++) {
if(s2[i - 1] == s1[j - 1]) {
dp[cur][j] = dp[pre][j - 1] + 1;
cnt = max(cnt, dp[cur][j]);
}
else dp[cur][j] = 0;
}
swap(cur, pre);
}
return cnt;
}
}

int main() {
while(~scanf("%s%s", s1, s2)) {
int ans = lcs();
printf("%d\n", ans);
}
return 0;
}

动态规划(二级空间优化)

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
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

char s1[1000001], s2[1000001];
int dp[1000001];

int lcs() {
int len1 = strlen(s1), len2 = strlen(s2);
int i, j, tmp, old, cnt = 0;
if(len2 > len1) {
for(i = 0; i <= len2; i++) dp[i] = 0;
for(i = 1; i <= len1; i++) {
old = dp[0];
for(j = 1; j <= len2; j++) {
tmp = dp[j];
if(s1[i - 1] == s2[j - 1]) {
dp[j] = old + 1;
cnt = max(cnt, dp[j]);
}
else dp[j] = 0;
old = tmp;
}
}
return cnt;
}
else {
for(i = 0; i <= len1; i++) dp[i] = 0;
for(i = 1; i <= len2; i++) {
old = dp[0];
for(j = 1; j <= len1; j++) {
tmp = dp[j];
if(s2[i - 1] == s1[j - 1]) {
dp[j] = old + 1;
cnt = max(cnt, dp[j]);
}
else dp[j] = 0;
old = tmp;
}
}
return cnt;
}
}

int main() {
while(~scanf("%s%s", s1, s2)) {
int ans = lcs();
printf("%d\n", ans);
}
return 0;
}

后缀数组

桶排序

对于待排序的数组a,在排序时逐个遍历数组a,将数组a的值作为”桶数组r”的下标。当a中数据被读取时,就将桶的值加1。例如,读取到数组a[3]=5,则将r[5]的值+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
void bucket_sort(int a[], int n) {
int i, j;
int bucket[maxn]; // maxn是a[]的最大值
memset(bucket, 0, sizeof(bucket));
// 计数
for(i = 0; i < n; i++)
bucket[a[i]]++;
// 排序
for(i = 0, j = 0; i < maxn; i++) {
while((bucket[i]--) > 0)
a[j++] = i;
}
}

基数排序

桶排序的扩展。它的基本思想是:将整数按位数切割成不同的数字,然后按每个位数分别比较。
具体做法是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

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
int base(int i) {
if(i == 0) return 10;
else return 10 * base(i - 1);
}

void bucket_sort(int bit) {
int bucket[maxn];
int tmp[n];
memset(bucket, 0, sizeof(bucket));
for(int i = 0; i < n; i++)
bucket[(a[i] / base(bit)) % 10]++;
for(int i = 1; i < maxn; i++)
bucket[i] += bucket[i - 1];
for(int i = n - 1; i >= 0; i--) {
tmp[bucket[(a[i] / base(bit)) % 10] - 1] = a[i];
bucket[(a[i] / base(bit)) % 10]--;
}
for(int i = 0; i < n; i++)
a[i] = tmp[i];
}

void radix_sort() {
int bit = getbit(); //获取数组a的位数
for(int i = 0; i < bit; i++)
bucket_sort(i);
print(); //已排好序
}

后缀数组

1
2
3
4
Str: 需要处理的字符串(长度为Len)
Suffix[i]: Str下标为i~Len的连续子串(例如Str="abcdef", Suffix[3]="def")
Rank[i]: Suffix[i]在所有后缀中的排名
SA[i]: 排名为i的后缀的起始下标,即排名为i的后缀为Suffix[SA[i]],与Rank是互逆运算

后缀数组指的就是这个SA[i],有了它,我们就可以实现一些很强大的功能(如不相同子串个数、连续重复子串等)。如何快速的到它,便成为了这个算法的关键。而SARank是互逆的,只要求出任意一个,另一个就可以O(Len)得到。
现在比较主流的算法有两种,倍增DC3,在这里,就主要讲一下稍微慢一些,但比较好实现以及理解的倍增算法(虽说慢,但也是O(Len logLen))的。

倍增算法

Height数组

1
2
Height[i]: 表示Suffix[SA[i]]和Suffix[SA[i-1]]的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀
H[i]: 等于Height[Rank[i]],即Height[i]=H[SA[i]]

H[i] >= H[i-1] - 1

证明:设Suffix[k]是排在Suffix[i - 1]前一名的后缀,则它们的最长公共前缀是H[i - 1]。都去掉第一个字符,就变成Suffix[k + 1]Suffix[i]如果H[i - 1] = 0或1,那么H[i] ≥ 0显然成立。否则H[i] ≥ H[i - 1] - 1(去掉了原来的第一个,其他前缀一样相等),所以Suffix[i]和在它前一名的后缀的最长公共前缀至少是H[i - 1] - 1。

DFS

Problem 1

题目描述
给定M根小木棍,每根木棍有各自的长度,能否把它们全部用上来围成一个正方形?其中4≤M≤20,每根木棍的长度是1到10000之间的整数

输入格式
第一行是一个整数T表示测试数据的组数。 对于每组测试数据,输入一行,包含M+1个整数,第一个整数表示M,接下来M个整数表示M个木棍的长度

输出格式
对于每组数据一行,如果能够围成正方形 输出“yes” 否则输出“no”

输入输出样例

输入

1
2
3
4
3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

输出

1
2
3
yes
no
yes

Solution

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

int len[25],v[25],m,l;

bool dfs(int p,int g,int d){
if(d==3) return true;
for(int i=p; i>=0; i--){
if(!v[i]){
v[i]=1;
int t=g+len[i];
if(t<l){
if(dfs(p-1,t,d))
return true;
}
else if(t==l){
if(dfs(m-1,0,d+1))
return true;
}
else{
v[i]=0;
}
}
}
return false;
}

int main(){
int t;
scanf("%d",&t);
while(t--){
int sum=0;
scanf("%d",&m);
for(int i=0; i<m; i++){
scanf("%d",&len[i]);
sum+=len[i];
}
sort(len,len+m);
memset(v,0,sizeof(v));
l=sum/4;
if(sum%4!=0 || m<4 || l<len[m-1]) printf("no\n");
else if(dfs(m-1,0,0)) printf("yes\n");
else printf("no\n");
}
return 0;
}

Problem 2

题目描述
小埋会告诉你一盘扫雷,用一个 n*m 的矩阵表示,1 是雷 ,0 不是雷,请你告诉她这盘扫雷的 3bv 。

周围八格没有“雷”且自身不是“雷”的方格称为“空格”,周围八格有“雷”且自身不是“雷”的方格称为“数字”,由“空格”组成的八连通块称为一个“空”。3bv = 周围八格没有“空格”的“数字”个数 + “空”的个数。

输入格式
第一行有两个整数 n 和 m,代表这盘扫雷是一个 n*m 的矩阵。

后面的 n 行每行有 m 个整数,表示这个矩阵,每个数字为 0 或 1,1 代表是雷,0 代表不是雷。

输出格式
一个整数,代表这盘扫雷的 3bv 。

输入

1
2
3
4
5
6
7
8
9
8 8
0 0 0 1 1 0 0 0
1 0 0 1 0 0 0 1
1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0

输出

1
13

Solution

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

int a[1000][1000],v[1000][1000],bv3,n,m;
int x[8]={-1,-1,-1,0,0,1,1,1},y[8]={-1,0,1,-1,1,-1,0,1};

bool noBlank(int l,int r){ //周围八格没有“空格”的
for(int i=0; i<8; i++){
int ll=l+x[i]; int rr=r+y[i];
if(ll>=0 && ll<n && rr>=0 && rr<m && !a[ll][rr])
return 0;
}
return 1;
}

void incr(int l,int r){ //让“雷”周围八格中不是“雷”的都增加1
for(int i=0; i<8; i++){
int ll=l+x[i]; int rr=r+y[i];
if(ll>=0 && ll<n && rr>=0 && rr<m && a[ll][rr]!=-1)
a[ll][rr]++;
}
}

void dfs(int l,int r){
for(int i=0; i<8; i++){
int ll=l+x[i]; int rr=r+y[i];
if(ll>=0 && ll<n && rr>=0 && rr<m && !a[ll][rr] && !v[ll][rr]){ //判断是否越界,用v判重
v[ll][rr]=1;
dfs(ll,rr);
}
}
}

int main(){
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
scanf("%d",&a[i][j]);
if(a[i][j])
a[i][j]=-1;
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(a[i][j]==-1)
incr(i,j);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
if(a[i][j] && a[i][j]!=-1 && noBlank(i,j)) //周围八格没有“空格”的“数字”的个数
bv3++;
}
for(int i=0; i<n; i++)
for(int j=0; j<m; j++){
if(!a[i][j] && !v[i][j]){ //“空”的个数
bv3++;
dfs(i,j);
}
}
printf("%d\n", bv3);
return 0;
}

Problem 3

将数字 1…9 填入一个 3×3 的九宫格中,使得格子中每一横行和的值全部相等,每一竖列和的值全部相等。请你计算有多少种填数字的方案。

next_permutation

https://www.cnblogs.com/eudiwffe/p/6260699.html

https://blog.csdn.net/c18219227162/article/details/50301513

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
using namespace std;

int a[10];

int main(){
int ans = 0;
for(int i = 1; i <= 9; i++)
a[i] = i;
do{
if(a[1] + a[2] + a[3] == a[4] + a[5] + a[6]
&& a[4] + a[5] + a[6] == a[7] + a[8] + a[9]
){
if(a[1] + a[4] + a[7] == a[2] + a[5] + a[8]
&& a[2] + a[5] + a[8] == a[3] + a[6] + a[9]
)
ans++;
}
}while(next_permutation(a + 1, a + 10));
printf("%d\n", ans);
return 0;
}
//72

Problem 4

右侧代码是将 6 个整数按照任意顺序组合到一起,计算能组合出的最大数字。

例如:4123,25,66 组合到一起就是 66412325。

请阅读程序补全代码,实现这个功能

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
#include <stdio.h>
#include <algorithm>

long long test(int a[], int n) {
long long ret = 0;
for (int i = 0; i < n; ++i) {
int tp = a[i];
int j = 1;
while(tp) {
j *= 10;
tp /= 10;
}
ret = ret * j + a[i];
}
return ret;
}

long long f(int a[], int k) {
if (k == 6) {
return test(a, k);
}
long long ret = 0;
for(int i = k; i < 6; ++i) {
int t = a[k];
a[k] = a[i];
a[i] = t;
ret = std::max(ret, f(a, k + 1));
t = a[k];
a[k] = a[i];
a[i] = t;
}
return ret;
}

int main() {
int a[6] = {517, 283, 429, 65, 6566, 32};
printf("%lld\n", f(a, 0));
return 0;
}

树形dp

树形dp就是在树的结构上用动态规划,主要用DFS。

1
dp[i][j][0/1],其中i指以i为根的子树,j指在以i为根的子树中选择j个子节点,0表示不选这个节点,1表示选择这个节点。有时候j或0/1这一维可以压掉。

基本方程:

选择节点类

1
2
dp[i][0] = dp[j][1]
dp[i][1] = max/min(dp[j][0], dp[j][1])

树形背包类

1
2
dp[v][k] = dp[u][k] + val
dp[u][k] = max(dp[u][k], dp[v][k-1])

入门题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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 6005;
int n, root, r[maxn], f[maxn][2], v[maxn]; //f记录快乐指数总和;v表示visited,用于找root;r存储每个人的快乐指数
vector<int>s[maxn];
void dp(int x){
f[x][0] = 0;
f[x][1] = r[x];
for(int i = 0; i < s[x].size(); i++){
int t = s[x][i];
dp(t); //dfs
f[x][0] += max(f[t][0], f[t][1]); //上司没来,直接下属想来就来
f[x][1] += f[t][0]; //上司来了,直接下属一定不来
}
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
cin >> r[i];
int l, k;
memset(v, 0, sizeof(v));
for(int i = 1; i <= n-1; i++){
cin >> l >> k;
s[k].push_back(l);
v[l] = 1;
}
for(int i = 1; i <= n; i++)
if(!v[i]){
root = i;
break;
}
dp(root);
cout << max(f[root][0], f[root][1]) << endl;
return 0;
}

参考资料

数据结构合集

这篇文章主要记录各种数据结构的基本操作以及一些相关题目。

队列

队尾插入,队头删除。

基本操作

顺序队列

队列的类型定义:

1
2
3
4
5
#define MAXLEN 1000
struct SeqQueue{
int front, rear;
int data[MAXLEN];
};

队列的初始化:

1
2
3
void init(SeqQueue &q){
q.front = q.rear = 0;
}

判断队列是否为空:

1
2
3
bool isEmpty(SeqQueue q){
return q.front == q.rear;
}

判断是否队满:

1
2
3
bool isFull(SeqQueue q){
return q.rear == MAXLEN;
}

入队操作:

1
2
3
4
5
bool Push(SeqQueue &q, int t){
if(isFull(q)) return false;
q.data[q.rear++] = t;
return true;
}

出队操作:

1
2
3
4
5
bool Pop(SeqQueue &q, int &dt){
if(isEmpty(q)) return false;
dt = q.data[q.front++];
return true;
}

循环队列

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
#define MAXLEN 100
struct CycleQueue{
int data[MAXLEN];
int front, rear;
};
void init(CycleQueue &q){
q.front = q.rear = 0;
}
bool isEmpty(CycleQueue q){
return q.rear == q.front;
}
bool isFull(CycleQueue &q){
return (q.rear + 1) % MAXLEN == q.front;
}
bool Push(CycleQueue &q, int t){
if(isFull(q)) return false;
q.data[q.rear++] = t;
return true;
}
bool Pop(CycleQueue &q, int &dt){
if(isEmpty(q)) return false;
dt = q.data[q.front];
q.front = (q.front + 1) % MAXLEN;
return true;
}

HDU1276

方法一:(没用队列)

注意:这里是说不超过3,也就是可以小于3,所以不是只剩下3个时就停止报数,而是把那一趟报完,剩下几个就输出几个。

典型的如:输入4,输出1 3

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
#include <iostream>
using namespace std;

int n;
int d[5005];

void init(){
for(int i = 1; i <= n; i++)
d[i] = i;
}

int main(){
int N;
while(cin >> N){
while(N--){
cin >> n;
init();
int c = 0, cnt = n;
while(cnt > 3){
if(!c){
int f = 0;
for(int i = 1; i <= n; i++){
if(d[i]){
if(f){
d[i] = 0;
cnt--;
}
f ^= 1;
}
}
c ^= 1;
}
else{
int f = 2;
for(int i = 1; i <= n; i++){
if(d[i]){
if(f){
f--;
}
else{
d[i] = 0;
cnt--;
f = 2;
}
}
}
c ^= 1;
}
}
int j = 0;
for(int i = 1; i <= n; i++){
if(d[i]){
j = i;
cout << d[i];
break;
}
}
if(j){
for(int i = j + 1; i <= n; i++){
if(d[i]){
cout << " " << d[i];
}
}
}
cout << endl;
}
}
return 0;
}

方法二:(队列)

利用两个队列来模拟整个报数方式,一个队列存放初始士兵,另一个存放一次报数后剩下的士兵,两个队列循环,直到最后队列中人数小于4人时,停止报数。

1

顺序栈的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MAXLEN 100
struct Stack{
int data[MAXLEN];
int top;
};
bool isEmpty(Stack s){
return s.top == 0;
}
bool isFull(Stack s){
return s.top == MAXLEN; //栈顶指针s.top指向的是栈顶元素位置的上一个
}
bool Push(Stack &s, int t){
if(isFull(s)) return false;
s.data[s.top++] = t;
return true;
}
bool Pop(Stack &s, int &dt){ //或者干脆写个GetTop(int &dt)
if(isEmpty(s)) return false;
dt = s.data[s.top--];
return true;
}

栈的应用

表达式求值

数制转换

KM算法

KM算法解决的是带权二分图的最优匹配问题。

下面这段代码来自:click here

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
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int love[MAXN][MAXN]; // 记录每个妹子和每个男生的好感度
int ex_girl[MAXN]; // 每个妹子的期望值
int ex_boy[MAXN]; // 每个男生的期望值
bool vis_girl[MAXN]; // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN]; // 记录每一轮匹配匹配过的男生
int match[MAXN]; // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN]; // 记录每个汉子如果能被妹子倾心最少还需要多少期望值

int N;


bool dfs(int girl)
{
vis_girl[girl] = true;

for (int boy = 0; boy < N; ++boy) {

if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次

int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];

if (gap == 0) { // 如果符合要求
vis_boy[boy] = true;
if (match[boy] == -1 || dfs( match[boy] )) { // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
match[boy] = girl;
return true;
}
} else {
slack[boy] = min(slack[boy], gap); // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
}

return false;
}

int KM()
{
memset(match, -1, sizeof(match)); // 初始每个男生都没有匹配的女生
memset(ex_boy, 0, sizeof(ex_boy)); // 初始每个男生的期望值为0

// 每个女生的初始期望值是与她相连的男生最大的好感度
for (int i = 0; i < N; ++i) {
ex_girl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
ex_girl[i] = max(ex_girl[i], love[i][j]);
}
}

// 尝试为每一个女生解决归宿问题
for (int i = 0; i < N; ++i) {

fill(slack, slack + N, INF); // 因为要取最小值 初始化为无穷大

while (1) {
// 为每个女生解决归宿问题的方法是 :如果找不到就降低期望值,直到找到为止

// 记录每轮匹配中男生女生是否被尝试匹配过
memset(vis_girl, false, sizeof(vis_girl));
memset(vis_boy, false, sizeof(vis_boy));

if (dfs(i)) break; // 找到归宿 退出

// 如果不能找到 就降低期望值
// 最小可降低的期望值
int d = INF;
for (int j = 0; j < N; ++j)
if (!vis_boy[j]) d = min(d, slack[j]);

for (int j = 0; j < N; ++j) {
// 所有访问过的女生降低期望值
if (vis_girl[j]) ex_girl[j] -= d;

// 所有访问过的男生增加期望值
if (vis_boy[j]) ex_boy[j] += d;
// 没有访问过的boy 因为girl们的期望值降低,距离得到女生倾心又进了一步!
else slack[j] -= d;
}
}
}

// 匹配完成 求出所有配对的好感度的和
int res = 0;
for (int i = 0; i < N; ++i)
res += love[ match[i] ][i];

return res;
}

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

for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
scanf("%d", &love[i][j]);

printf("%d\n", KM());
}
return 0;
}

模板题:HDU2255

二分图判定

二分图的判定问题比较少见,简单来说,就是对于给定的图,判断图是否为二分图。

可以把每个节点着以黑色和白色之一,使得每条边的两个端点颜色不同,不难发现,对于一个当且仅当每个连通分量都是二分图,因此我们只考虑无向连通图。

无向图 G 为二分图的充分必要条件:G 至少有两个顶点,且其所有回路的长度均为偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n;  //节点数
vector<int> G[N]; //G[i]表示i节点邻接的点
int color[N]; //color[i]=0,1,2 代表i节点不涂颜色、涂白色、涂黑色
//假设u是遍历时的第一个结点,则color[u]已经被初始化为1或2
bool bipartite(int u){ //判断无向图是否可二分
for(int i = 0; i < G[u].size(); i++){ //枚举结点
int v = G[u][i]; //相邻节点
if(color[v] == color[u]) //若两结点颜色相同,无法二分
return false;
if(!color[v]){ //若结点没涂颜色
color[v] = 3 - color[u]; //改变结点颜色,使v的颜色与u的颜色对立
if(!bipartite(v)) //若点v不满足二分图话,则无法二分
return false;
}
}
return true;
}

匈牙利算法

交替路

从一个未匹配点出发,依次经过 非匹配边、匹配边、非匹配边… 形成的路径。

增广路

定义:设 M 为二分图 G 已匹配边的集合,若 P 是图 G 中一条连通两个未匹配点的路径(起点在 X/Y 部,终点在 Y/X 部),且属 M 的边(匹配边)与不属 M 的边(非匹配边)在 P 上交替出现,则称 P 为相对 M 的一条增广路径。

由于增广路的第一条边是没有参与匹配的,第二条边参与了匹配,…,最后一条边没有参与匹配,并且起点和终点还没有被选择过,显然 P 有奇数条边。

简单来说,从一个未匹配点出发,走交替路,若途径另一未匹配点(除起点外),则这条交替路称为增广路。

如下图,左图中的一条增广路如右图所示,图中的匹配点均用红色标出:

avatar

增广路性质

  1. P 的长度必为奇数,第一条边和最后一条边都不属于 M,且两个端点分属两个集合,均未匹配。

  2. P 的非匹配边比匹配边多一条。

  3. P 经过取反操作可以得到一个更大的匹配 M’。

  4. M 为 G 的最大匹配当且仅当不存在相对于 M 的增广路径。

增广路定理

由于增广路中间的匹配节点不存在其他相连的匹配边,因此交换增广路中的匹配边与非匹配边不会破坏匹配的性质。

由增广路性质可知,只要把增广路中的匹配边和非匹配边交换,交换后,图中的匹配边数目比原来多了 1 条。

故而,可以通过不停地找增广路来增加匹配中的匹配边和匹配点,找不到增广路时,即达到最大匹配,这就是增广路定理。

匈牙利树

匈牙利树一般由 DFS 构造(类似于 DFS 树),其是从一个未匹配点出发进行 DFS(必须走交替路),直到不能再扩展为止。

如下图,通过左侧的二分图,进行 DFS 可以得到右侧的树,但这棵树存在一叶结点为非匹配点(7号),而匈牙利树要求所有叶结点均为匹配点,故这棵树不是匈牙利树。

avatar

但若原图中不含 7 号结点,那么从 2 号结点出发就会得到一棵匈牙利树,如下图:

avatar

匈牙利算法流程

匈牙利算法是用增广路来求最大匹配的算法,在求最大匹配前,需要先用 DFS 或 BFS 找到增广路。

流程

  1. 从左边第 1 个点开始,挑选未匹配点进行搜索,寻找增广路
    1)若经过一个未匹配点,则寻找成功,更新路径信息,匹配边数 +1,停止搜索。
    2)若一直没有找到增广路,则不再从这个点开始搜索。事实上,此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去,而不影响结果。
  2. 由于找到增广路后需要沿着路径更新匹配,因此需要一个结构来记录路径上的点,DFS 版本通过函数调用隐式地使用一个栈,而 BFS 版本使用 pre 数组(前驱结点)。

性能比较

无论是使用 DFS 还是 BFS,两个版本的时间复杂度均为 O(V*E)。

DFS 的优点是思路清晰,代码量少,但性能不如 BFS;BFS 的优点是速度较快,但代码量大。

对于稀疏图,BFS 版本明显快于 DFS 版本,对于稠密图,两者不相上下,因而当图为稀疏图时,常选用 DFS 版本,当图为稠密图时,常选用 BFS 版本。

koning定理及推论

基本概念

k-正则图:各顶点的度均为 k 的无向简单图

最大匹配数:最大匹配的匹配边的数目

最大独立集数:选取最多的点集,使点集中任意两点均不相连

最小点覆盖数:选取最少的点集,使任意一条边都至少有一个端点在点集中

内容

  • 最大匹配数 = 最小点覆盖数
  • 最大独立集数 = 顶点数 - 最大匹配数

实现

1.最大匹配数/最小点覆盖数

DFS 版本

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
int n, m;  //x、y中结点个数,下标从0开始
bool vis[N]; //vis[i]表示是否在交替路中
int link[N]; //存储连接点
vector<int> G[N]; //存边

bool dfs(int x){
for(int i = 0; i < G[x].size(); i++){ //对x的每个邻接点
int y = G[x][i];
if(!vis[y]){ //不在交替路中
vis[y] = true; //放入交替路
if(link[y] == -1 || dfs(link[y])){ //如果是未匹配点,说明交替路是增广路
link[y] = x; //交换路径
return true; //返回成功
}
}
}
return false; //不存在增广路,返回失败
}

int hungarian(){
int ans = 0; //记录最大匹配数
memset(vis, -1, sizeof(vis));
for(int i = 1; i <= n; i++){ //从左侧开始每个结点找一次增广路
memset(vis, false, sizeof(vis));
if(dfs(i)) //找到一条增广路,形成一个新匹配
ans++;
}
return ans;
}

int main(){
while(~scanf("%d%d", &n, &m)){
memset(link, -1, sizeof(link)); //全部初始化为未匹配点
for(int i = 0; i < N; i++)
G[i].clear();
while(m--){
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
printf("%d\n", hungarian()); //输出最大匹配数
}
return 0;
}

BFS 版本

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
int n,m;//左边点数,右边点数
int vis[N];//vis[i]表示是否在交替路中
int link[N];//存连接点
int pre[N];//存前驱结点
vector<int> G[N];//存边
queue<int> Q;
int hungarian(){
memset(vis,-1,sizeof(vis));
memset(pre,-1,sizeof(pre));
memset(link,-1,sizeof(link));

int ans=0;//记录最大匹配数
for(int i=1;i<=n;i++){
if(link[i]==-1){//若点未匹配
pre[i]=-1;//没有前驱
while(!Q.empty())//清空队列
Q.pop();

Q.push(i);
bool flag=false;
while(!Q.empty() && !flag){
int x=Q.front();
for(int j=0;j<G[x].size();j++){//对x的每个邻接点
if(!flag)//如果falg为真,则说明找到一未匹配点,不必继续下去
break;

int y=G[x][j];
if(vis[y]!=i){//不在交替路中
vis[y]=i;//存入交替路
Q.push(link[y]);//交换路径
if(link[y]>=0)//在已匹配点中
pre[link[y]]=x;
else {//找到未匹配点,交替路变增广路
flag=true;
int d=x;
int e=y;
while(d!=-1){//找到一个未匹配点,无法构成匈牙利树,让所有点不断的往回更新,重选下一个
int temp=link[d];
link[d]=e;
link[e]=d;
d=pre[d];
e=temp;
}
}
}
}
Q.pop();
}
if(link[i]!=-1)//统计最大匹配数
ans++;
}
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
while(m--){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
printf("%d\n", hungarian());//输出最大匹配数
}
return 0;
}

最大独立集

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
int n,m;
bool vis[N];
int link[N];
bool G[N][N];
bool dfs(int x){
for(int y=1;y<=m;y++){
if(G[x][y]&&!vis[y]){
vis[y]=true;
if(link[y]==-1 || dfs(link[y])){
link[y]=x;
return true;
}
}
}
return false;
}
int hungarian(){
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i))
ans++;
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){
memset(link,-1,sizeof(link));
memset(G,true,sizeof(G));

while(m--){
int x,y;
scanf("%d%d",&x,&y);
G[x][y]=false;//不满足条件则连一条边
}

int mate=hungarian();//最大匹配数
int res=n-mate;//最大独立集

printf("%d\n",res);
}
return 0;
}

经典应用——行列拆点建图

转载自:

https://blog.csdn.net/u011815404/article/details/87829705

图论-二分图

二分图

是图论中的一种特殊模型。若能将无向图G=(V,E)的顶点V划分为两个交集为空的顶点集,并且任意边的两个端点都分属于两个集合,则称图G为一个为二分图。

其充要条件是:图中至少存在两个点,且图中所有回路的长度均为偶数。

avatar

当图中的顶点分为两个集合,使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连时,此时是一特殊的二分图,称为完全二分图。

匹配

一个匹配即一个包含若干条边的集合,且其中任意两条边没有公共端点。如下图,图3的红边即为图2的一个匹配。

avatar

定义匹配点、匹配边、未匹配点、非匹配边,它们的含义非常显然。例如上图中 1、4、5、7 为匹配点,其他顶点为未匹配点;1-5、4-7为匹配边,其他边为非匹配边。

最大匹配

在G的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数。如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配(即一个图的某个匹配中,所有的顶点都是匹配点,就是一个完全匹配)。如果在左右两边加上源汇点后,图G等价于一个网络流,最大匹配问题可以转为最大流的问题。解决此问的匈牙利算法的本质就是寻找最大流的增广路径。

上图中,{1-7,2-5,3-6,4-8}就是一个最大匹配,也是一个完全匹配。

完全匹配一定是最大匹配,但是并非每个图都存在完全匹配。

简单来说,对于一个二分图,左点集中的每一个点都与右点集的一个点匹配,或者右点集中的每一个点都与左点集的一个点匹配。

完美匹配

对于一个二分图,左点集与右点集的点数相同,若存在一个匹配,包含左点集、右点集的所有顶点,则称为完美匹配。

简单来说,对于一个二分图,左点集中的每一个点都与右点集的一个点匹配,并且右点集中的每一个点都与左点集的一个点匹配。

{1-7,2-5,3-6,4-8}也是一个完美匹配。

最大匹配问题

举例来说,若存在某一对男孩和女孩之间存在相连的边,就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对,使得每对都互相喜欢?这就是完全匹配问题。而最多有多少互相喜欢的男孩/女孩可以配对?这就是最大匹配问题。

最优匹配

最优匹配又称为带权最大匹配,是指在带有权值边的二分图中,求一个匹配使得匹配边上的权值和最大。一般X和Y集合顶点个数相同,最优匹配也是一个完备匹配,即每个顶点都被匹配。如果个数不相等,可以通过补点加0边实现转化。一般使用KM算法解决该问题。

带权二分图的权值最大的完全匹配称为最佳匹配,要注意的是,二分图的最优匹配不一定是二分图的最大权匹配

实质上最优匹配问题就是求边权和最大的最大匹配问题

求解技巧:可以添加一些权值为 0 的边,使得最优匹配和最大权匹配统一起来。

最小覆盖

二分图的最小覆盖分为最小顶点覆盖和最小路径覆盖:

①最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联,二分图的最小顶点覆盖数=二分图的最大匹配数

②最小路径覆盖也称为最小边覆盖,是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数=|V|-二分图的最大匹配数

最大独立集

最大独立集是指寻找一个点集,使得其中任意两点在图中无对应边。对于一般图来说,最大独立集是一个NP完全问题,对于二分图来说 最大独立集=|V|-二分图的最大匹配数

匈牙利算法—基本概念

交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。

最大匹配与最小点覆盖

最小点覆盖:假如选了一个点就相当于覆盖了以它为端点的所有边,你需要选择最少的点来覆盖所有的边。

最小割定理:一个二分图中的最大匹配数等于这个图中的最小点覆盖数。

最小点集覆盖==最大匹配:在这里解释一下原因,首先,最小点集覆盖一定>=最大匹配,因为假设最大匹配为n,那么我们就得到了n条互不相邻的边,光覆盖这些边就要用到n个点。现在我们来思考为什么最小点集覆盖一定<=最大匹配。任何一种n个点的最小点集覆盖,一定可以转化成一个n的最大匹配。因为最小点集覆盖中的每个点都能找到至少一条只有一个端点在点集中的边(如果找不到则说明该点所有的边的另外一个端点都被覆盖,所以该点则没必要被覆盖,和它在最小点集覆盖中相矛盾),只要每个端点都选择一个这样的边,就必然能转化为一个匹配数与点集覆盖的点数相等的匹配方案。所以最大匹配至少为最小点集覆盖数,即最小点集覆盖一定<=最大匹配。综上,二者相等。

匈牙利算法

由增广路的性质,增广路中的匹配边总是比未匹配边多一条,所以如果我们放弃一条增广路中的匹配边,选取未匹配边作为匹配边,则匹配的数量就会增加。匈牙利算法就是在不断寻找增广路,如果找不到增广路,就说明达到了最大匹配。

参考资料:

https://www.cnblogs.com/shenben/p/5573788.html

https://blog.csdn.net/u011815404/article/details/84260940