STEP BY STEP

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

求N个字符串最长的公共子串。这题数据比较水，暴力第一个字符串的子串也可以过。初学后缀数组，有很多不明白的东西，此题后缀数组的代码在网上也是一把抓。
说实话我确实还不懂后缀数组，但是后缀数组太强大了，只能硬着头皮照着葫芦画瓢了。贴下代码方便以后查阅吧。。。
感觉后缀数组的应用最主要的还是height数组，看懂倍增算法排序后缀已经非常困难了。然后再理解height数组怎么用也不是一件容易的事情。然后貌似height数组最关键的用法是枚举某一个长度的子串时候，比如长度为k，能够用这个k对height数组进行分组，这个罗穗骞的论文里面有个求不重叠最长重复子串的例子说明了这个height数组分组的思路，不过我现在还是不怎么理解。。。

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

const int MAX_N = 110;
const int MAX_L = MAX_N * MAX_N;
char szStr[MAX_N];
int nNum[MAX_L];
int nLoc[MAX_L];
bool bVisit[MAX_N];
int sa[MAX_L], rank[MAX_L], height[MAX_L];
int wa[MAX_L], wb[MAX_L], wv[MAX_L], wd[MAX_L];

int cmp(int* r, int a, int b, int l)
{
    return r[a] == r[b]  r[a + l] == r[b + l];
}

//倍增算法,r为待匹配数组,n为总长度,m为字符串范围
void da(int* r, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;

    for (i = 0; i < m; ++i) wd[i] = 0;
    for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;
    for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;

    for (j = 1, p = 1; p < n; j *= 2, m = p)
    {
        for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
        for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;

        for (i = 0; i < n; ++i) wv[i] = x[y[i]];
        for (i = 0; i < m; ++i) wd[i] = 0;
        for (i = 0; i < n; ++i) wd[wv[i]]++;
        for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
        for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];

        swap(x, y);
        for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
        {
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;
        }
    }
}

//求height数组
void calHeight(int* r, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; ++i) rank[sa[i]] = i;
    for (i = 0; i < n; height[rank[i++]] = k)
    {
        if (k) --k;
        for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
    }
}

bool Check(int nMid, int nLen, int nN)
{
    int nCnt = 0;

    memset(bVisit, false, sizeof(bVisit));
    for (int i = 2; i <= nLen; ++i)
    {
        if (nMid > height[i])
        {
            nCnt = 0;
            memset(bVisit, false, sizeof(bVisit));
            continue;
        }
        if (!bVisit[nLoc[sa[i - 1]]])
        {
            bVisit[nLoc[sa[i - 1]]] = true;
            ++nCnt;
        }
        if (!bVisit[nLoc[sa[i]]])
        {
            bVisit[nLoc[sa[i]]] = true;
            ++nCnt;
        }
        if (nCnt == nN) return true;
    }

    return false;
}

int main()
{
    int nT;

    scanf("%d", &nT);
    while (nT--)
    {
        int nN;
        int nEnd = 300;
        int nP = 0;
        scanf("%d", nN);
        for (int i = 1; i <= nN; ++i)
        {
            scanf("%s", szStr);
            char* pszStr;
            for (pszStr = szStr; *pszStr; ++pszStr)
            {
                nLoc[nP] = i;
                nNum[nP++] = *pszStr;
            }
            nLoc[nP] = nEnd;
            nNum[nP++] = nEnd++;

            reverse(szStr, szStr + strlen(szStr));
            for (pszStr = szStr; *pszStr; ++pszStr)
            {
                nLoc[nP] = i;
                nNum[nP++] = *pszStr;
            }
            nLoc[nP] = nEnd;
            nNum[nP++] = nEnd++;
        }
        nNum[nP] = 0;

        da(nNum, nP + 1, nEnd);
        calHeight(nNum, nP);

        int nLeft = 1, nRight = strlen(szStr), nMid;
        int nAns = 0;
        while (nLeft <= nRight)
        {
            nMid = (nLeft + nRight) / 2;
            if (Check(nMid, nP, nN))
            {
                nLeft = nMid + 1;
                nAns = nMid;
            }
            else nRight = nMid - 1;
        }
        printf("%d\n", nAns);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3k 阅读时长 ≈ 3 分钟

题意是给定一系列模式串。然后给出一个文本串，问至少改变文本串里面多少个字符可以使文本串不包含任何一个模式串。
还是先建立Trie图，然后在Trie图上面进行dp。dp的思路也不是很复杂。dp[i][j]的意思是长度为i的文本串需要改变dp[i][j]个字符顺利到达状态j。需要注意的是长度为i的时候，对应的字符串中的第i-1个字符。刚开始一直没发现这个bug。而且注意中途不能转移到匹配成功的状态上去，多加几个条件控制即可了。。。转移方程，dp[i][j] = min(dp[i][j], dp[i-1][nNext] + szText[i-1] != k)，其中nNext是从状态j可以转移到的非匹配成功的状态，k代表的当前边的权。

代码如下：

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

const int MAX_N = 61;
const int MAX_L = 31;
const int MAX_D = 4;
const int INF = 1110;
char chHash[256];
char szPat[MAX_L];

void InitHash()
{
    chHash['A'] = 0;
    chHash['G'] = 1;
    chHash['C'] = 2;
    chHash['T'] = 3;
}

struct Trie
{
    Trie* fail;
    Trie* next[MAX_D];
    bool flag;
    int no;
};
int nP;
Trie* pRoot;
Trie tries[MAX_N * MAX_L];

Trie* NewNode()
{
    memset(tries[nP], 0, sizeof(Trie));
    tries[nP].no = nP;
    return tries[nP++];
}

void InitTrie(Trie* pRoot)
{
    nP = 0;
    pRoot = NewNode();
}

void Insert(Trie* pRoot, char* pszPat)
{
    Trie* pNode = pRoot;
    while (*pszPat)
    {
        int idx = chHash[*pszPat];
        if (pNode->next[idx] == NULL)
        {
            pNode->next[idx] = NewNode();
        }
        pNode = pNode->next[idx];
        ++pszPat;
    }
    pNode->flag = true;
}

void BuildAC(Trie* pRoot)
{
    pRoot->fail = NULL;
    queue<Trie*> qt;
    qt.push(pRoot);

    while (!qt.empty())
    {
        Trie* front = qt.front();
        qt.pop();

        for (int i = 0; i < MAX_D; ++i)
        {
            if (front->next[i])
            {
                Trie* pNode = front->fail;
                while (pNode && pNode->next[i] == NULL)
                {
                    pNode = pNode->fail;
                }
                front->next[i]->fail = pNode? pNode->next[i] : pRoot;
                front->next[i]->flag |= front->next[i]->fail->flag;
                qt.push(front->next[i]);
            }
            else
            {
                front->next[i] = front == pRoot? pRoot : front->fail->next[i];
            }
        }
    }
}

int nChange[INF][INF];
char szText[INF];

int Solve()
{
    int nLen = strlen(szText);
    for (int i = 0; i <= nLen; ++i)
    {
        for (int j = 0; j < nP; ++j)
        {
            nChange[i][j] = INF;
        }
    }

    int i, j, k;
    nChange[0][0] = 0;
    for (i = 1; i <= nLen; ++i)
    {
        for (j = 0; j < nP; ++j)
        {
            if (tries[j].flag) continue;
            if (nChange[i - 1][j] == INF) continue;
            for (k = 0; k < MAX_D; ++k)
            {
                int nNext = tries[j].next[k] - tries;
                if (tries[nNext].flag) continue;
                //trie是边权树,所以i是从1到len,而且当前字符是szText[i-1]
                int nTemp = nChange[i - 1][j] + (k != chHash[szText[i - 1]]);
                nChange[i][nNext] = min(nChange[i][nNext], nTemp);
            }
        }
    }

    int nAns = INF;
    for (i = 0; i < nP; ++i)
    {
        if (!tries[i].flag)
            nAns = min(nAns, nChange[nLen][i]);
    }
    return nAns == INF? -1 : nAns;
}

int main()
{
    int nN;
    int nCase = 1;

    InitHash();
    while (scanf("%d", &nN), nN)
    {
        InitTrie(pRoot);
        while (nN--)
        {
            scanf("%s", szPat);
            Insert(pRoot, szPat);
        }
        BuildAC(pRoot);
        scanf("%s", szText);
        printf("Case %d: %d\n", nCase++, Solve());
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 4.1k 阅读时长 ≈ 4 分钟

这个题与poj2778dna sequence解法基本一致。只是这个题的答案没有取模，而且文本串不太长。问题是不取模的话就只能输出实际的答案了，就只能用大数了。
而且用大数的话，再用矩阵冥可能就会超时之类的。
这类题还可以用除矩阵冥外的另外一种解法，就是直接dp即可。二维状态，第一维代表文本串长度，第二维代表在AC自动机中的状态。比如dp[i][j]代表长度为i的文本串，转移到Trie图中节点j时候满足不包含任何模式串的答案。剩下的是如何转移状态。转移的话也是考虑next指针数组，设next = tries[j].next[k]，那么有dp[i+1][next] =dp[i+1][next] + dp[i][j]，从0到字母集合大小N枚举k即可。
这个题有一个易错的地方，就是字母集合可能是ascii码在128到256的范围内。而char的范围可能是-128到127或者0到255，这个是根据编译器不同的。所以，直接用字符串数组读入数据后需要再处理下。可以直接将每个字符加128后再处理。
另外，getchar返回的是int，但是与gets之类的函数获得的值的差别也不是那么确定的了。觉得getchar除了对eof之外其余都返回正值。但是，如果char是有符号的话，scanf或者gets之类得到的char数组里面可能就包含负值了。。。
这个可以生成随机文件，再用getchar读入并用%d输出其返回值验证下。验证程序如下：注释掉的部分是生成随机文件的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char ch;
    freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    int nNum = 100;
    int nCh;
    do
    {
        printf("%d\n", nCh = getchar());
    }
    while (nCh != EOF);
    /*while (nNum--)
    {
        putchar(rand() % 256);
    }*/

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

const int MAX_D = 256;
const int MAX_N = 51;
const int MAX_M = 51;
const int MAX_P = 11;
struct Trie
{
    Trie* fail;
    Trie* next[MAX_D];
    int no;
    bool flag;
};
Trie tries[MAX_P * MAX_P];
int nP;
int nN, nM;
Trie* pRoot;
int nHash[MAX_D];
char szPat[MAX_M];

Trie* NewNode()
{
    memset(tries[nP], 0, sizeof(Trie));
    tries[nP].no = nP;
    return tries[nP++];
}

void InitTrie(Trie* pRoot)
{
    nP = 0;
    pRoot = NewNode();
}

void Insert(Trie* pRoot, char* pszPat)
{
    Trie* pNode = pRoot;
    while (*pszPat)
    {
        int idx = nHash[*pszPat];
        if (pNode->next[idx] == NULL)
        {
            pNode->next[idx] = NewNode();
        }
        pNode = pNode->next[idx];
        ++pszPat;
    }
    pNode->flag = true;
}

void BuildAC(Trie* pRoot)
{
    pRoot->fail = NULL;
    queue<Trie*> qt;
    qt.push(pRoot);

    while (!qt.empty())
    {
        Trie* front = qt.front();
        qt.pop();

        for (int i = 0; i < nN; ++i)
        {
            if (front->next[i])
            {
                Trie* pNode = front;
                while (pNode && pNode->next[i] == NULL)
                {
                    pNode = pNode->fail;
                }
                front->next[i]->fail = pNode? pNode->next[i] : pRoot;
                front->next[i]->flag |= front->next[i]->fail->flag;
                qt.push(front->next[i]);
            }
            else
            {
                front->next[i] = front->fail->next[i];
            }
        }
    }
}

const int MAX_L = 200;
struct BigInt
{
    int nD[MAX_L];
    BigInt()
    {
        Clear();
    }
    void Clear()
    {
        memset(nD, 0, sizeof(nD));
    }

    void Print()
    {
        int i = MAX_L - 1;
        while (!nD[i] && i)--i;
        while (i >= 0)
        {
            putchar(nD[i] + '0');
            --i;
        }
    }
    int operator[](int idx) const
    {
        return nD[idx];
    }

    int operator[](int idx)
    {
        return nD[idx];
    }
};
BigInt bi[MAX_M][MAX_D];

BigInt operator+(const BigInt one, const BigInt two)
{
    BigInt ret;

    for (int i = 0, nAdd = 0; i < MAX_L; ++i)
    {
        ret[i] = one[i] + two[i] + nAdd;
        nAdd = ret[i] / 10;
        ret[i] %= 10;
    }

    return ret;
}

void Solve()
{
    BigInt ans;
    for (int i = 0; i <= nM; ++i)
    {
        for (int j = 0; j < nP; ++j)
        {
            bi[i][j].Clear();
        }
    }
    bi[0][0][0] = 1;

    for (int i = 1; i <= nM; ++i)
    {
        for (int j = 0; j < nP; ++j)
        {
            if (tries[j].flag) continue;
            for (int k = 0; k < nN; ++k)
            {
                int nNext = tries[j].next[k] - tries;
                if (tries[nNext].flag == false)
                {
                    bi[i][nNext] = bi[i][nNext] + bi[i - 1][j];
                }
            }
        }
    }

    for (int i = 0; i < nP; ++i)
    {
        ans = ans + bi[nM][i];
    }
    ans.Print();
    printf("\n");
}

int main()
{
    int nT;

    while (scanf("%d%d%d%*c", &nN, &nM, &nT) == 3)
    {
        int nCh;
        int nTmp = 0;
        memset(nHash, 0, sizeof(nHash));
        while (nCh = getchar(), nCh != '\n')
        {
            if (!nHash[nCh])
            {
                nHash[nCh] = nTmp++;
            }
        }
        InitTrie(pRoot);
        while (nT--)
        {
            gets(szPat);
            Insert(pRoot, szPat);
        }
        printf("1");
        BuildAC(pRoot);
        printf("2");
        Solve();
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

赤裸裸的字符串最小表示题。所谓字符串最小表示指的是给定一个字符串，假设其可以循环移位，问循环左移多少位能够得到最小的字符串。
算法即是周源的最小表示法，搜索可以找到相关论文和ppt。
该算法其实也不是太复杂，思路可以这样理解。假设原字符串为s，设s1 = s + s; s2 = s1循环左移1位;现在处理s1和s2，实际写程序的时候可以通过下标偏移和取模得到s1和s2，而并不需要生成。
处理过程是这样的，设i和j分别指向s1和s2的开头。我们的目的是找到这样的i和j，假设k是s的长度，满足条件s1[i,i+k-1] = s2[j,j+k-1] 并且s1[i,i+k-1] 是所有满足条件的字符串中最小的字符串，如果有多个这样的s1[i,i+k-1] 那么我们希望i最小。
其实这个算法主要是做了一个优化，从而把时间搞成线性的。比如，对于当前的i和j，我们一直进行匹配，也就是s1[i,i+k] = s2[j,j+k] 一直满足，突然到了一个位置s1[i+k] != s2[j+k]了，现在我们需要改变i和j了。但是，我们不能只是++i或者++j。而是根据s1[i+k]>s2[j+k]的话i =i + k + 1，否则j = j + k + 1。这样的瞬移i或者j就能够保证复杂度是线性的了。
问题是如何证明可以这样的瞬移。其实，说穿了也很简单。因为s1[i,i+k - 1] = s2[j,j+k -1]是满足的，只是到了s1[i+k]和s2[j+k]才出现问题了。假如s1[i+k]>s2[j+k]，那么我们改变i为区间[i+1,i+k]中任何一个值m都不可能得到我们想要的答案，这是因为我们总可以在s2中找到相应的比s1[m,m+k-1]小的字符串s2[j+m-i,j+m-i+k-1]，因为有s1[i+k]>s2[j+k]。同样对于s1[i+k]<s2[j+k]的情况。
文字可能描述的不是很清楚。看PPT能够根据图进行分析。

代码如下：

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

int GetMin(string str)
{
    int nSize = str.size();
    int i = 0, j = 1, k = 0;

    while (i < nSize && j < nSize && k < nSize)
    {
        char chDif = str[(i + k) % nSize]
                     - str[(j + k) % nSize];
        if (!chDif) ++k;
        else
        {
            if (chDif > 0) i = i + k + 1;
            else j = j + k + 1;
            if (i == j) ++j;
            k = 0;
        }
    }
    return min(i, j);
}

int main()
{
    string str;
    int nN;

    scanf("%d", &nN);
    while (nN--)
    {
        cin >> str;
        printf("%d\n", GetMin(str) + 1);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 4.1k 阅读时长 ≈ 4 分钟

这个题目更奇葩。据说是上一个题的加强版。题意是给定M个模式串，然后给定长度L，问不超过L的文本至少含有一个模式的情况的总种数。
还是用模式串建立Trie图，根据Trie图建立起路径长度为1的矩阵M。
总情况数目为26^1+26^2+…+26^L。不含模式串的情况总数为矩阵N = M^1+M^2+M^3+…+M^L的第一行之和。总情况数目减去不含模式串的情况就是答案。
这里用到了矩阵的一些算法，比如快速冥，还有快速冥求和。但是，我用了操作符重载，最悲剧的是重载后的操作符没有优先级，而我还当作有优先级的在用，所以悲剧了。。。一直样例都过不去。。。唉，最后才发现了这个问题。。。写了260行左右的代码，前面的一部分代码可以当作矩阵操作的模板了。。。Trie图的也不错，过几天估计得打印下来用了。。。

代码如下：

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

typedef unsigned long long INT;
const int MAX_D = 26;
const int MAX_L = 10;
const int MAX_N = 10;
char szPat[MAX_L];

const int MAX_S = 31;
struct Matrix
{
    int nSize;
    INT nD[MAX_S][MAX_S];
    Matrix(int nS)
    {
        Clear(nS);
    }

    Matrix operator = (const Matrix m)
    {
        nSize = m.nSize;
        for (int i = 0; i < nSize; ++i)
        {
            for (int j = 0; j < nSize; ++j)
            {
                nD[i][j] = m.nD[i][j];
            }
        }
        return *this;
    }
    void Clear(int nS)
    {
        nSize = nS;
        memset(nD, 0, sizeof(nD));
    }
    void Unit()
    {
        for (int i = 0; i < nSize; ++i)
        {
            for (int j = 0; j < nSize; ++j)
            {
                nD[i][j] = (i == j ? 1 : 0);
            }
        }
    }
};

Matrix operator+(const Matrix A, const Matrix B)
{
    Matrix C(A.nSize);

    for (int i = 0; i < A.nSize; ++i)
    {
        for (int j = 0; j < A.nSize; ++j)
        {
            C.nD[i][j] = A.nD[i][j] + B.nD[i][j];
        }
    }
    return C;
}

Matrix operator*(const Matrix nA, const Matrix nB)
{
    Matrix nC(nB.nSize);
    for (int i = 0; i < nA.nSize; ++i)
    {
        for (int j = 0; j < nA.nSize; ++j)
        {
            for (int k = 0; k < nA.nSize; ++k)
            {
                nC.nD[i][j] += nA.nD[i][k] * nB.nD[k][j];
            }
        }
    }
    return nC;
}

Matrix operator^(Matrix B, INT nExp)
{
    Matrix ans(B.nSize);

    ans.Unit();
    while (nExp)
    {
        if (nExp % 2)
        {
            ans = ans * B;
        }
        B = B * B;
        nExp >>= 1;
    }
    return ans;
}

//求base^1+base^2++base^N
Matrix SumPowMatrix(Matrix base, INT nN)
{
    if (nN == 1)
    {
        return base;
    }

    Matrix ans = SumPowMatrix(base, nN / 2);
    ans = ans + ((base^(nN / 2)) * ans);//重载运算符保证不了优先级
    if (nN % 2)
    {
        ans = ans + (base^nN);//没优先级啊,必须加括号,查错2个小时了
    }
    return ans;
}

struct Trie
{
    Trie* next[MAX_D];
    Trie* fail;
    int no;
    bool flag;
};
Trie tries[MAX_L * MAX_N];
int nP;
Trie* pRoot;

Trie* NewNode()
{
    memset(tries[nP], 0, sizeof(Trie));
    tries[nP].no = nP;
    return tries[nP++];
}

void InitTrie(Trie* pRoot)
{
    nP = 0;
    pRoot = NewNode();
}

void Insert(Trie* pRoot, char* pszPat)
{
    Trie* pNode = pRoot;
    while (*pszPat)
    {
        int idx = *pszPat - 'a';
        if (pNode->next[idx] == NULL)
        {
            pNode->next[idx] = NewNode();
        }
        pNode = pNode->next[idx];
        ++pszPat;
    }
    pNode->flag = true;
}

void BuildAC(Trie* pRoot, Matrix M)
{
    pRoot->fail = NULL;
    queue<Trie*> qt;
    qt.push(pRoot);

    M.Clear(nP);
    while (!qt.empty())
    {
        Trie* front = qt.front();
        qt.pop();
        for (int i = 0; i < MAX_D; ++i)
        {
            if (front->next[i])
            {
                Trie* pNode = front->fail;
                while (pNode && pNode->next[i] == NULL)
                {
                    pNode = pNode->fail;
                }
                front->next[i]->fail = pNode? pNode->next[i] : pRoot;
                if (front->next[i]->fail->flag)
                {
                    front->next[i]->flag = true;
                }
                qt.push(front->next[i]);
            }
            else
            {
                front->next[i] = front == pRoot? pRoot : front->fail->next[i];
            }

            //这里必须要加上front->flag为false的判断么?加不加会生成不同的矩阵
            if (!front->next[i]->flag)
            {
                ++M.nD[front->no][front->next[i]->no];
            }
        }
    }
}

int main()
{
    int nN;
    INT nL;
    Matrix M(0);

    while (scanf("%d%I64u", &nN, &nL) == 2)
    {
        InitTrie(pRoot);
        while (nN--)
        {
            scanf("%s", szPat);
            Insert(pRoot, szPat);
        }
        BuildAC(pRoot, M);

        Matrix tmp(1);
        tmp.nD[0][0] = 26;
        tmp = SumPowMatrix(tmp, nL);
        INT nAns = tmp.nD[0][0];
        Matrix msum = SumPowMatrix(M, nL);
        for (int i = 0; i < msum.nSize; ++i)
        {
            nAns -= msum.nD[0][i];
        }
        printf("%I64u\n", nAns);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.4k 阅读时长 ≈ 3 分钟

题意很简单，假定文本集就是A,C,T,G，给定M个模式串，问你长度为N的文本不出现这些模式串的可能性到底有多少种。。。
确实非常不直观的样子。。。
解法是先学学AC自动机，建立起Trie图，根据trie图可以得到长度为1的路径矩阵，然后再快速冥得到长度为N的路径矩阵。
说起来都非常纠结，没学过AC自动机更加无法理解。学AC自动机之前据说得先学Trie树和KMP才好理解。学AC自动机搞Trie图就花费了近2天了，然后弄懂这个题又是一天，好在基本明白了。马上快比赛了，从长春换到金华也不知道是好是坏。。。还是弱菜啊。。。
贴下我的Trie图+快速冥(直接二分了,没有写成数论里面那种算法)…

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

typedef long long INT;
const int MOD = 100000;
const int MAX_P = 100;
const int MAX_D = 4;
int nIdx[256];
char szPat[MAX_P];
INT nMatrix[MAX_P][MAX_P];
INT B[MAX_P][MAX_P];
INT A[MAX_P][MAX_P];

void InitIdx()
{
    nIdx['A'] = 0;
    nIdx['C'] = 1;
    nIdx['T'] = 2;
    nIdx['G'] = 3;
}

struct Trie
{
    Trie* fail;
    Trie* next[MAX_D];
    int no;
    bool flag;
    Trie()
    {
        fail = NULL;
        memset(next, 0, sizeof(next));
        no = 0;
        flag = false;
    }
};
Trie tries[MAX_D * MAX_P];
int nP;
Trie* pRoot;

Trie* NewNode()
{
    memset(tries[nP], 0, sizeof(Trie));
    tries[nP].no = nP;
    return tries[nP++];
}

void InitTrie(Trie* pRoot)
{
    nP = 0;
    pRoot = NewNode();
}

void Insert(char* pszPat)
{
    Trie* pNode = pRoot;

    while (*pszPat)
    {
        if (pNode->next[nIdx[*pszPat]] == NULL)
        {
            pNode->next[nIdx[*pszPat]] = NewNode();
        }
        pNode = pNode->next[nIdx[*pszPat]];
        ++pszPat;
    }
    pNode->flag = true;
}

int BuildAC(Trie* pRoot)
{
    memset(nMatrix, 0, sizeof(nMatrix));

    pRoot->fail = NULL;
    queue<Trie*> qt;
    qt.push(pRoot);
    while (!qt.empty())
    {
        Trie* front = qt.front();
        qt.pop();

        for (int i = 0; i < MAX_D; ++i)
        {
            if (front->next[i])
            {
                Trie* pNode = front->fail;
                while (pNode && pNode->next[i] == NULL)
                {
                    pNode = pNode->fail;
                }
                front->next[i]->fail = pNode? pNode->next[i] : pRoot;
                if (front->next[i]->fail->flag == true)
                {
                    front->next[i]->flag = true;
                }

                qt.push(front->next[i]);
            }
            else
            {
                front->next[i] = front == pRoot? pRoot : front->fail->next[i];
            }

            if (front->next[i]->flag == false)
            {
                nMatrix[front->no][front->next[i]->no]++;
            }
        }
    }

    return nP;//节点总个数
}

void MultyMatrix(INT A[][MAX_P], INT B[][MAX_P], INT C[][MAX_P], int nSize)
{
    for (int i = 0; i < nSize; ++i)
    {
        for (int j = 0; j < nSize; ++j)
        {
            INT nSum = 0;
            for (int k = 0; k < nSize; ++k)
            {
                nSum = (nSum + A[i][k] * B[k][j]) % MOD;
            }
            C[i][j] = nSum;
        }
    }
}

void CopyMatrix(INT A[][MAX_P], INT B[][MAX_P], int nSize)
{
    for (int i = 0; i < nSize; ++i)
    {
        for (int j = 0; j < nSize; ++j)
        {
            A[i][j] = B[i][j];
        }
    }
}

void MatrixPower(INT M[][MAX_P], int nSize, INT nP)
{
    if (nP == 1)
    {
        CopyMatrix(A, M, nSize);
        return;
    }

    MatrixPower(M, nSize, nP / 2);
    MultyMatrix(A, A, B, nSize);
    if (nP % 2)
    {
        MultyMatrix(B, M, A, nSize);
    }
    else
    {
        CopyMatrix(A, B, nSize);
    }
}

int main()
{
    INT nM, nN;

    InitIdx();
    while (scanf("%I64d%I64d", &nM, &nN) == 2)
    {
        InitTrie(pRoot);
        while (nM--)
        {
            scanf("%s", szPat);
            Insert(szPat);
        }
        int nSize = BuildAC(pRoot);

        MatrixPower(nMatrix, nSize, nN);
        INT nAns = 0;
        for (int i = 0; i < nSize; ++i)
        {
            nAns = (nAns + A[0][i]) % MOD;
        }
        printf("%I64d\n", nAns % MOD);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

句子的语法匹配。这个用DFA确实可以很方便做出来，用递归判断之类的应该也可以。感觉用dfa只需要保证状态转换图对了，基本上就不会出bug了，但是其它的方法去匹配这种类似正则表达式的字符串就容易出错多了。

百度百科的DFA定义如下：
英文全称：Deterministic Finite Automaton, 简写：DFA
DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中
① K是一个有穷集，它的每个元素称为一个状态；
② Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；
③ f是转换函数，是K×Σ→K上的映射，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，
当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；
④ S ∈ K是唯一的一个初态；
⑤ Z⊂K是一个终态集，终态也称可接受状态或结束状态。
该题的状态转换图：

现在再根据状态转换图，写一个模拟转换关系的匹配就非常方便了。。。
代码如下：

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

string strNouns[8] =
{
    "tom", "jerry", "goofy", "mickey",
    "jimmy", "dog", "cat", "mouse"
};

bool IsNoun(string str)
{
    for (int i = 0; i < 8; ++i)
    {
        if (str == strNouns[i])
        {
            return true;
        }
    }
    return false;
}

bool IsVerb(string str)
{
    return str == "hate" || str == "love"
           || str == "know" || str == "like"
           || str == "hates" || str == "loves"
           || str == "knows" || str == "likes";
}

bool IsArticle(string str)
{
    return str == "a" || str == "the";
}

bool CheckState(vector<string> vs)
{
    if (vs.empty()) return false;

    int nState = 0;
    for (int i = 0; i < vs.size(); ++i)
    {
        //printf("nState:%d, str:%s\n", nState, vs[i].c_str());
        switch (nState)
        {
        case 0:
            if (IsArticle(vs[i]))
            {
                nState = 1;
                break;
            }
            else if (IsNoun(vs[i]))
            {
                nState = 2;
                break;
            }
            else
            {
                return false;
            }

        case 1:
            if (IsNoun(vs[i]))
            {
                nState = 2;
                break;
            }
            else
            {
                return false;
            }

        case 2:
            if (vs[i] == "and")
            {
                nState = 0;
                break;
            }
            else if (IsVerb(vs[i]))
            {
                nState = 3;
                break;
            }
            else
            {
                return false;
            }

        case 3:
            if (IsArticle(vs[i]))
            {
                nState = 4;
                break;
            }
            else if (IsNoun(vs[i]))
            {
                nState = 5;
                break;
            }
            else
            {
                return false;
            }

        case 4:
            if (IsNoun(vs[i]))
            {
                nState = 5;
                break;
            }
            else
            {
                return false;
            }

        case 5:
            if (vs[i] == "and")
            {
                nState = 3;
                break;
            }
            else if (vs[i] == ",")
            {
                nState = 0;
                break;
            }
            else
            {
                return false;
            }
        }
    }

    return nState == 5;
}

int main()
{
    int nT;

    scanf("%d%*c", &nT);
    while (nT--)
    {
        vector<string> vs;
        string line, str;

        getline(cin, line);
        stringstream ss(line);
        while (ss >> str)
        {
            vs.push_back(str);
        }
        printf("%s\n", CheckState(vs) ? "YES I WILL" : "NO I WON'T");
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.7k 阅读时长 ≈ 2 分钟

这题意思很简单。求一棵树里面的一条路径，使得其异或权(就是将路径里面所有边的权值异或起来)最大。
这个题有两步。第一步是假定根为节点0，求出根到其它节点的异或距离，保存在数组xor里面，这个dfs一下即可。然后，用xor[i]^xor[j]就能代表节点i到节点j的路径。这个结论可以这么看。如果，i和j之间的路径经过根节点，那么上面的结论肯定是正确的。如果，该路径不经过根，那么xor[i]和xor[j]必定保护从根到某个节点的相同的一段子路径，根据异或的性质，这段子路径会被消掉，所以这个结论也是这确的。。。
第二步就是枚举，xor[i]^xor[j]使得结果最大了。如果直接暴力，平方的算法肯定会超时的。
由于每个值可以表示成2进制，如果把其它xor值都保存在字典树里面，用当前的xor[i]去字典树
里面，一遍就可以找到异或最大值。
另外，由于树的点数太多，只能用邻接表，用vector模拟邻接表果断超时了。。。改成静态链表才过。。。

代码如下：

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

const int MAX = 100010;
int nXor[MAX];
bool bVis[MAX];
int nFirst[MAX];
struct Edge
{
    int nE;
    int nW;
    int nNext;
};
Edge egs[MAX * 2];

struct Node
{
    Node* pSons[2];
};
Node nodes[MAX * 32];
Node* pRoot = nodes[0];
int nNew;

void GetBCode(int nL, int* nBCode, int nLen)
{
    nLen = 0;
    while (nLen <= 30)
    {
        nBCode[nLen++] = nL % 2;
        nL >>= 1;
    }
    reverse(nBCode, nBCode + nLen);
}

void Insert(int nL)
{
    int nLen = 0;
    int i = 0;
    int nBCode[32];

    GetBCode(nL, nBCode, nLen);
    Node* pNode = pRoot;

    while (i < nLen)
    {
        if (pNode->pSons[nBCode[i]])
        {
            pNode = pNode->pSons[nBCode[i]];
        }
        else
        {
            memset(nodes + nNew, 0, sizeof(nodes[nNew]));
            pNode->pSons[nBCode[i]] = nodes + nNew;
            pNode = nodes + nNew;
            ++nNew;
        }
        ++i;
    }
}

int FindMax(int nL)
{
    int nLen = 0;
    int nAns = 0;
    int i = 0;
    int nBCode[32];
    Node* pNode = pRoot;

    GetBCode(nL, nBCode, nLen);
    while (i < nLen)
    {
        int nBest = (nBCode[i] == 0 ? 1 : 0);
        int nBad = (nBCode[i] == 0 ? 0 : 1);
        if (pNode->pSons[nBest])
        {
            nAns = 2 * nAns + nBest;
            pNode = pNode->pSons[nBest];
        }
        else if (pNode->pSons[nBad])
        {
            nAns = 2 * nAns + nBad;
            pNode = pNode->pSons[nBad];
        }
        else break;
        ++i;
    }

    return nAns ^ nL;
}

void Dfs(int nV, int nL)
{
    nXor[nV] = nL;
    bVis[nV] = true;
    for (int e = nFirst[nV]; e != -1; e = egs[e].nNext)
    {
        if (!bVis[egs[e].nE])
        {
            Dfs(egs[e].nE, nL ^ egs[e].nW);
        }
    }
}

int main()
{
    int nN;
    int nU, nV, nW;

    while (scanf("%d", &nN) == 1)
    {
        for (int i = 0; i < nN; ++i) nFirst[i] = -1;
        for (int i = 1, j = 0; i < nN; ++i)
        {
            scanf("%d%d%d", &nU, &nV, &nW);
            egs[j].nE = nV;
            egs[j].nW = nW;
            egs[j].nNext = nFirst[nU];
            nFirst[nU] = j++;
            egs[j].nE = nU;
            egs[j].nW = nW;
            egs[j].nNext = nFirst[nV];
            nFirst[nV] = j++;
        }

        memset(bVis, false, sizeof(bool) * nN);
        Dfs(0, 0);

        memset(nodes[0], 0, sizeof(Node));
        nNew = 1;
        int nAns = 0;

        for (int i = 0; i < nN; ++i)
        {
            nAns = max(nAns, FindMax(nXor[i]));
            Insert(nXor[i]);
        }
        printf("%d\n", nAns);
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

这是并查集最后一题，据说也是最经典的一题。经常前面几题的训练，这题的思路很快就能想出来了.只需要对每个节点附加一个信息表示离根节点的距离，并且距离是模3循环的。注意合并时候保持距离变化的正确性。而且合并有2种情况，距离相同合并和距离不同合并。分别对应于题目描述中的1和2操作。
关键还是FindSet里面对距离nDis数组里面的修改，前面一直写错这个，wa了好几次，还是看队友代码才一眼发现我又把这里写错了。。。当前距离的更新还是等于当前距离加上前一个节点的距离再模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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX = 50010;
int nN, nK;
int nSets[MAX];
int nDis[MAX];

void MakeSets(int nN)
{
    for (int i = 1; i <= nN; ++i)
    {
        nSets[i] = i;
        nDis[i] = 0;
    }
}

int FindSet(int nI)
{
    if (nSets[nI] != nI)
    {
        int nPre = nSets[nI];
        nSets[nI] = FindSet(nSets[nI]);
        nDis[nI] = (nDis[nPre] + nDis[nI]) % 3;
    }
    return nSets[nI];
}

int main()
{
    int nAns = 0;
    int nOper, nX, nY;

    scanf("%d%d", &nN, &nK);
    MakeSets(nN);
    while (nK--)
    {
        scanf("%d%d%d", &nOper, &nX, &nY);
        if (nX > nN || nY > nN || nOper == 2  nX == nY)
        {
            ++nAns;
        }
        else
        {
            if (nOper == 1)
            {
                int nA = FindSet(nX);
                int nB = FindSet(nY);
                if (nA == nB)
                {
                    if (nDis[nX] != nDis[nY])
                    {
                        ++nAns;
                    }
                }
                else
                {
                    nSets[nB] = nA;
                    nDis[nB] = (nDis[nX] - nDis[nY] + 3) % 3;
                }
            }
            else
            {
                int nA = FindSet(nX);
                int nB = FindSet(nY);
                if (nA == nB)
                {
                    if ((nDis[nX] + 1) % 3 != nDis[nY])
                    {
                        ++nAns;
                    }
                }
                else
                {
                    nSets[nB] = nA;
                    nDis[nB] = (nDis[nX] + 1 - nDis[nY] + 3) % 3;
                }
            }
        }
    }
    printf("%d\n", nAns);

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.4k 阅读时长 ≈ 1 分钟

也是个题意比较奇葩的题目。有2个操作，1个是把一个元素所在的栈，放到另外1个元素所在的栈面。另外一个操作是统计某个元素下面有多少个元素(当然是在同一个栈中）。貌似，需要记录每个元素下面的元素是什了，既然要记录这个就不能用并查集的路径压缩了。不压缩路径的话，肯定会超时的。怎么办了。。。
其实，可以这么考虑，以每个栈的栈底元素作为并查集的代表元素。压缩路径后，每个元素或者是根元素或者其父亲元素就是根元素。所以，另外对每个节点附加个信息代表该节点的高度，栈底元素高度为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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX = 30010;
int nSets[MAX];
int nNum[MAX];
int nRank[MAX];

void MakeSets(int nN)
{
    for (int i = 0; i < nN; ++i)
    {
        nSets[i] = i;
        nNum[i] = 1;
        nRank[i] = 0;
    }
}

int FindSet(int nI)
{
    if (nSets[nI] != nI)
    {
        int nPre = nSets[nI];
        nSets[nI] = FindSet(nSets[nI]);
        nRank[nI] += nRank[nPre];
    }

    return nSets[nI];
}

void Move(int nX, int nY)
{
    int nA = FindSet(nX);
    int nB = FindSet(nY);
    //printf("nA:%d,nB:%d\n", nA, nB);
    if (nA != nB)
    {
        nSets[nA] = nB;
        nRank[nA] += nNum[nB];
        nNum[nB] += nNum[nA];
    }
}

int main()
{
    int nP;
    char szOper[10];
    int nX, nY;

    scanf("%d", &nP);
    MakeSets(MAX);
    while (nP--)
    {
        scanf("%s", szOper);
        if (szOper[0] == 'M')
        {
            scanf("%d%d", &nX, &nY);
            Move(nX, nY);
        }
        else
        {
            scanf("%d", &nX);
            FindSet(nX);
            printf("%d\n", nRank[nX]);
        }
    }

    return 0;
}