小鸟游六花

vanishment this world

发表于 更新于

今天在写堆结构的时候，突然怀疑两种方式构建堆的正确性了，还是记录下思考过程比较好。

一、算法实现

我们知道，在堆排序的过程中有两种方式构建堆，从后往前依次下沉插入$O(n)$，从前往后依次上升插入$O(nlogn)$。这里都可以用数学归纳法证明其构建的正确性，具体我写在注释里了。

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
#define _CRT_SECURE_NO_WARNINGS
#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
void heapInsert(int* arr, int i) {
    // 不要用 (i - 1) >> 1, 当i=0时会有问题
    while (arr[(i - 1) / 2] < arr[i]) {
        swap(arr[(i - 1) / 2], arr[i]);
        i = (i - 1) / 2;
    }
}
// 大顶堆 下调堆
void heapify(int *arr, int i, int n) {
    int left = (i << 1) + 1, right = left + 1;
    while (left <= n) {
        int largest = i;
        if (arr[largest] < arr[left]) largest = left;
        if (right <= n && arr[largest] < arr[right]) largest = right;
        if (largest == i) break;
        swap(arr[largest], arr[i]);
        i = largest;
        left = (i << 1) + 1, right = left + 1;
    }
}


int main()
{
    int arr[] = { 1,3,5,7,9,2,4,6,10,8 };
    int n = sizeof(arr) / sizeof(int);

    // 可以用数学归纳法证明O(nlogn) 这样构建的是一个大根堆
    // i = 0 显然成立
    // i = n + 1 时：假设不是大根堆，只会是 n+1 的父节点严格小于 n+1的兄弟节点，这显然是不可能的
    for (int i = 0; i < n; ++i) heapInsert(arr, i);
    // 同理也可以证明 这也是一个大根堆 O(n)
    /*for (int i = n - 1; i >= 0; --i) {
        heapify(arr, i, n - 1);
    }*/
    for (int i = 1; i < n; ++i) {
        swap(arr[0], arr[n - i]);
        heapify(arr, 0, n - 1 - i);
    }



    for (int i = 0; i < n; ++i) printf("%d  ", arr[i]);
    return 0;
}

发表于 更新于

一、算法模板

参考 OI Wiki： https://oi-wiki.org/string/hash/

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
const int maxn = 2010;
int prefix_hash[maxn];
int suffix_hash[maxn];
int base_power[maxn];
const int M = 1e9 + 7;
const int B = 233;
using ll = long long;

void init_hash(string &str, int n){
    for(int i = 0, val = 1; i < maxn; ++i){
        base_power[i] = val, val = ((ll)val * B) % M;
    }
    for(int i = 0, val = 0; i < n; ++i){
        prefix_hash[i] = val = ((ll)val * B + str[i]) % M;
    }
    for(int i = n-1, val = 0; i >=0; --i){
        suffix_hash[i] = val = ((ll)val * B + str[i]) % M;
    }
}
int segment_prefix_hash(int i, int j){
    int ans = prefix_hash[j];
    if(i != 0) ans = (ans - (ll)prefix_hash[i - 1] * base_power[j-i+1]) % M;
    if(ans < 0) ans += M;
    return ans;
}
int segment_suffix_hash(int i, int j, int n){
    int ans = suffix_hash[i];
    if(j != n-1) ans = (ans - (ll)suffix_hash[j + 1] * base_power[j-i+1]) % M;
    if(ans < 0) ans += M;
    return ans;
}

bool is_palindrome(int i, int j, int n){
    return segment_prefix_hash(i, j) == segment_suffix_hash(i, j, 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
// https://leetcode.cn/problems/longest-palindromic-substring/submissions/468447762/
// hash相等的时候需要判断一次，这里没做也能过
const int maxn = 1010;
int PHash[maxn];
int SHash[maxn];
int BP[maxn];
const int M = 1e9 + 7;
const int B = 233;
typedef long long ll;

void initHash(string &str, int n){
    for(int i = 0, val = 1; i < maxn; ++i){
        BP[i] = val, val = ((ll)val * B) % M;
    }
    for(int i = 0, val = 0; i < n; ++i){
        PHash[i] = val = ((ll)val * B + str[i]) % M;
    }
    for(int i = n-1, val = 0; i >=0; --i){
        SHash[i] = val = ((ll)val * B + str[i]) % M;
    }
}
int segPHash(int i, int j){
    int ans = PHash[j];
    if(i != 0) ans = (ans - (ll)PHash[i - 1] * BP[j-i+1]) % M;
    if(ans < 0) ans += M; 
    return ans;
}
int segSHash(int i, int j, int n){
    int ans = SHash[i];
    if(j != n-1) ans = (ans - (ll)SHash[j + 1] * BP[j-i+1]) % M;
    if(ans < 0) ans += M; 
    return ans;
}

class Solution {
public:
    string longestPalindrome(string& s) {

        if(!s.size()) return s;
        int n = s.size(), maxLen = 1, pos = 0, lastLen = 1;
        initHash(s, n);
        //cout << segPHash(0,0) << endl;
        //cout << segPHash(1,1) << endl;
        //cout << segSHash(1,1,n) << endl;
        for(int i = 1; i < n; ++i){
            //最大回文长度
            int k = min(i + 1, lastLen + 2);
            lastLen = 1;
            while(k>1){
                // 回文半径长度
                int len = (k >> 1) + (k & 1);
                int lh = segPHash(i-k+1, i-k+len);
                int rh = segSHash(i-len+1, i,n);
                //printf(" %d %d %d %d %d %d =>>>>>>>>      ", i-k+1, i-k+len, i-len+1, i, lh,rh);
                //cout << s.substr(i-k+1, len) << " : " << s.substr(i-len+1, len) << endl;
                if(lh == rh){
                    if(k > maxLen) maxLen = k, pos = i;
                    lastLen = k;break;
                }
                --k;
            }
        }
        return s.substr(pos-maxLen+1,maxLen);
    }
};

发表于 更新于

一、常用模板

1、用邻接矩阵表示(耗费内存，速度快)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int maxn = 400005;
int pos = 0;
int trie[maxn][26];
bool trieExists[maxn];
void insert(char *s){
    int p = 0;
    while(*s) {
        int c = *s++ - 'a';
        if(!trie[p][c]) trie[p][c] = ++pos;
        p = trie[p][c];
    }
    trieExists[p] = 1;
}
int find(char *s){
    int p = 0;
    while(*s){
        int c = *s++ - 'a';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return trieExists[p];
}

2、用邻接表表示(节约内存，数据分散时遍历快)

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
int tHeads[maxn];
int tNode[maxn]; int ncnt = 0;
int tNodeVal[maxn];

int trieExistsCount[maxn];
int trieJoinCount[maxn];
void insert(char *s) {
    int p = 0;
    while (*s) {
        ++trieJoinCount[p];
        int c = *s++;
        int nex = tHeads[p];
        while(nex && tNodeVal[nex] != c) nex = tNode[nex];
        if (!nex) {
            int bf = tHeads[p];
            tHeads[p] = ++ncnt;
            tNode[ncnt] = bf;
            tNodeVal[ncnt]  = c;
            p = ncnt;
        }
        else p = nex;
    }
    ++trieExistsCount[p];
    ++trieJoinCount[p];
}

二、相关习题

1、UVA1401

直接套用模板：

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

#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
const int maxn = 400005;
int pos = 0;
int trie[maxn][26];
bool trieExists[maxn];
void insert(char *s){
    int p = 0;
    while(*s) {
        int c = *s++ - 'a';
        if(!trie[p][c]) trie[p][c] = ++pos;
        p = trie[p][c];
    }
    trieExists[p] = 1;
}
int find(char *s){
    int p = 0;
    while(*s){
        int c = *s++ - 'a';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return trieExists[p];
}

char W[300005];
char S[105];
int DP[300005];
int main()
{
    int kase = 0;
    while(~scanf("%s",W)){
        memset(DP,0,sizeof(DP));
        memset(trie,0,sizeof(trie));
        memset(trieExists,0,sizeof(trieExists));
        int n = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; ++i) scanf("%s", S), insert(S);
        int wl = strlen(W);DP[0]=1;
        for(int i = 0; i < wl; ++i){
            int j = i, p = 0,c;
            while(j < wl){
                c = W[j] - 'a';
                p = trie[p][c];
                if(!p) break;
                if(trieExists[p]) DP[j+1] = (DP[j+1] + DP[i])%20071027;
                ++j;
            }
        }
        //for(int i = 0; i <= wl; ++i) printf("%d ", DP[i]);puts("");
        printf("Case %d: %d\n",++kase, DP[wl]);
    }
    return 0;
}

2、⭐UVA11732

用邻接矩阵会TLE，需要用邻接表：

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
#define _CRT_SECURE_NO_WARNINGS
#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
const int maxn = 4002205;


int tHeads[maxn];
int tNode[maxn]; int ncnt = 0;
int tNodeVal[maxn];

int trieExistsCount[maxn];
int trieJoinCount[maxn];
int codeMap[] = {-61,-60,-59,-58,-57,-56,-55,-54,-53,-52,-51,-50,-49,-48,-47,-46,-45,-44,-43,-42,-41,-40,-39,-38,-37,-36,-35,-34,-33,-32,-31,-30,-29,-28,-27,-26,-25,-24,-23,-22,-21,-20,-19,-18,-17,-16,-15,-14,0,1,2,3,4,5,6,7,8,9,-3,-2,-1,0,1,2,3,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,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,-189,-188,-187};
void insert() {
    int p = 0;
    while (1) {
        char ch = getchar();
        if (ch == '\n') break;
        ++trieJoinCount[p];
        int c = codeMap[ch];
        
        int nex = tHeads[p];
        while(nex && tNodeVal[nex] != c) nex = tNode[nex];
        if (!nex) {
            int bf = tHeads[p];
            tHeads[p] = ++ncnt;
            tNode[ncnt] = bf;
            tNodeVal[ncnt]  = c;
            p = ncnt;
        }
        else p = nex;
    }
    ++trieExistsCount[p];
    ++trieJoinCount[p];
}
long long int ans = 0;
long long int dc = 0;
void dfs(int p,int last) {
    int f = trieExistsCount[p];
    int j = trieJoinCount[p];
    if (j && last) {
        // 计算与兄弟节点的比较次数，这里会计算两次
        dc += (last - j) * j;
        //cout << "dc" << (last - j) * j << endl;
        // 计算当前节点相等值比较次数，a,a,a,ac,ac,ac 需要计算5*4次
        ans += j * (j - 1);
        //cout << "self:" << j * (j - 1) << endl;
        // 计算当前节点的终止节点与非终止比较次数，a,a,a,ac,ac,ac 需要计算3*3次
        ans += f * (j - f);
        //cout << "diff:" << f * (j - f) << endl;
        // 计算当前节点的终止节点比较次数，a,a,a,ac,ac,ac 需要计算3*2/2*2次
        ans += f * (f - 1);
        //cout << "end:" << f * (f - 1)  << endl;
    }
    int t = j - f;
    int nex = tHeads[p];
    while(nex){
        dfs(nex, t);
        nex = tNode[nex];
    }
}
char S[1005];
int main()
{
    //freopen("1.txt", "r", stdin);
    int kase = 0; int n;
    while (~scanf("%d", &n) && n) {
        ans = 0, dc = 0, ncnt = 0;
        memset(trieExistsCount, 0, sizeof(trieExistsCount));
        memset(trieJoinCount, 0, sizeof(trieJoinCount));
        memset(tHeads, 0, sizeof(tHeads));
        getchar();
        for (int i = 0; i < n; ++i) {
            insert();
        }
        dfs(0, 0);

        //for(int i = 0; i <= wl; ++i) printf("%d ", DP[i]);puts("");
        printf("Case %d: %lld\n", ++kase, ans + dc/2);

    }
    return 0;
}
0%