這題意思很簡(jiǎn)單。求一棵樹里面的一條路徑，使得其異或權(quán)(就是將路徑里面所有邊的權(quán)值異
或起來)最大。
這個(gè)題有兩步。第一步是假定根為節(jié)點(diǎn)0，求出根到其它節(jié)點(diǎn)的異或距離，保存在數(shù)組xor里面，
這個(gè)dfs一下即可。然后，用xor[i]^xor[j]就能代表節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑。這個(gè)結(jié)論可以這么看。
如果，i和j之間的路徑經(jīng)過根節(jié)點(diǎn)，那么上面的結(jié)論肯定是正確的。如果，該路徑不經(jīng)過根，那么
xor[i]和xor[j]必定保護(hù)從根到某個(gè)節(jié)點(diǎn)的相同的一段子路徑，根據(jù)異或的性質(zhì)，這段子路徑會(huì)
被消掉，所以這個(gè)結(jié)論也是這確的。。。
第二步就是枚舉，xor[i]^xor[j]使得結(jié)果最大了。如果直接暴力，平方的算法肯定會(huì)超時(shí)的。
由于每個(gè)值可以表示成2進(jìn)制，如果把其它xor值都保存在字典樹里面，用當(dāng)前的xor[i]去字典樹
里面，一遍就可以找到異或最大值。
另外，由于樹的點(diǎn)數(shù)太多，只能用鄰接表，用vector模擬鄰接表果斷超時(shí)了。。。
改成靜態(tài)鏈表才過。。。
代碼如下：
#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;
}
這是并查集最后一題，據(jù)說也是最經(jīng)典的一題。經(jīng)常前面幾題的訓(xùn)練，這題的思路很快
就能想出來了。只需要對(duì)每個(gè)節(jié)點(diǎn)附加一個(gè)信息表示離根節(jié)點(diǎn)的距離，并且距離是模3循環(huán)的。
注意合并時(shí)候保持距離變化的正確性。而且合并有2種情況，距離相同合并和距離不同合并。
分別對(duì)應(yīng)于題目描述中的1和2操作。
關(guān)鍵還是FindSet里面對(duì)距離nDis數(shù)組里面的修改，前面一直寫錯(cuò)這個(gè)，wa了好幾次，還是
看隊(duì)友代碼才一眼發(fā)現(xiàn)我又把這里寫錯(cuò)了。。。當(dāng)前距離的更新還是等于當(dāng)前距離加上前一個(gè)
節(jié)點(diǎn)的距離再模3，類似于前面幾題的更新方法。
這種將有關(guān)系的節(jié)點(diǎn)放在一個(gè)并查集里面，再給每個(gè)節(jié)點(diǎn)附加其它信息描述其它關(guān)系的做法，
確實(shí)比較有效。。。并查集是應(yīng)用于不相交集合的數(shù)據(jù)結(jié)構(gòu)，看來某個(gè)時(shí)候卻有妙用啊。。。
代碼如下：
#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;
}
也是個(gè)題意比較奇葩的題目。有2個(gè)操作，1個(gè)是把一個(gè)元素所在的棧，放到另外1個(gè)元素所在
的棧上面。另外一個(gè)操作是統(tǒng)計(jì)某個(gè)元素下面有多少個(gè)元素(當(dāng)然是在同一個(gè)棧中）。
貌似，需要記錄每個(gè)元素下面的元素是什么了，既然要記錄這個(gè)就不能用并查集的路徑壓縮了。
不壓縮路徑的話，肯定會(huì)超時(shí)的。怎么辦了。。。
其實(shí)，可以這么考慮，以每個(gè)棧的棧底元素作為并查集的代表元素。壓縮路徑后，每個(gè)元素或者
是根元素或者其父親元素就是根元素。所以，另外對(duì)每個(gè)節(jié)點(diǎn)附加個(gè)信息代表該節(jié)點(diǎn)的高度，棧底
元素高度為0。再附加個(gè)信息代表每個(gè)并查集元素總數(shù)目，這樣就可以在合并集合時(shí)候修改信息，
并且壓縮路徑也能保證答案正確。。。
代碼如下：
#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;
}
并查集應(yīng)用的變形。題目意思是一個(gè)圖中，只有上下左右四個(gè)方向的邊。給出這樣的一些邊，
求任意指定的2個(gè)節(jié)點(diǎn)之間的距離。
有可能當(dāng)前給出的信息，沒有涉及到要求的2個(gè)節(jié)點(diǎn)，或者只涉及到了1個(gè)節(jié)點(diǎn)，那么肯定
無法確定它們的距離?；蛘吒鶕?jù)已經(jīng)給出的邊只知道這2個(gè)節(jié)點(diǎn)在不同的聯(lián)通分量里面，那么其
距離也是無法確定的，根據(jù)題目要求，輸出-1。
問題是如果能夠確定它們?cè)谝粋€(gè)聯(lián)通分量里面，如何確定它們的距離了。
這個(gè)題的關(guān)鍵在于，只有上下左右四個(gè)方向的邊，假設(shè)每個(gè)節(jié)點(diǎn)都有一個(gè)坐標(biāo)的話，那么它們
相對(duì)于代表該聯(lián)通分量節(jié)點(diǎn)的坐標(biāo)肯定是固定的，那么就不需要考慮圖里面有環(huán)之類的情況了。
這樣就可以很方便的應(yīng)用并查集來解了。
利用并查集，給每個(gè)節(jié)點(diǎn)附加其它信息，即相對(duì)于代表該并查集的節(jié)點(diǎn)的坐標(biāo)（x，y）。
在FindSet里面求出坐標(biāo)，在UnionSet里面修改合并后新加入的另外一個(gè)集合的根節(jié)點(diǎn)的坐標(biāo)即可。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
const int MAX_N = 40010;
int nN, nM;
int nSets[MAX_N];
int nX[MAX_N];
int nY[MAX_N];
char szInput[MAX_N][100];
void MakeSets(
int nNum)
{
for (
int i = 0; i < nNum; ++i)
{
nSets[i] = i;
nX[i] = nY[i] = 0;
}
}
int FindSets(
int nI)
{
if (nSets[nI] != nI)
{
int nPre = nSets[nI];
nSets[nI] = FindSets(nSets[nI]);
nX[nI] += nX[nPre];
nY[nI] += nY[nPre];
}
return nSets[nI];
}
void UnionSets(
int nBeg,
int nEnd,
int dx,
int dy)
{
int nA = FindSets(nBeg);
int nB = FindSets(nEnd);
if (nA != nB)
{
nSets[nB] = nA;
//把集合B合并到集合A中
nX[nB] = nX[nBeg] + dx - nX[nEnd];
//因?yàn)榉较蚰孢^來了,所以是減去
nY[nB] = nY[nBeg] + dy - nY[nEnd];
}
}
int main()
{
int nBeg, nEnd, nL;
char szDir[10];
while (scanf("%d%d%*c", &nN, &nM) == 2)
{
MakeSets(nN);
for (
int i = 0; i < nM; ++i)
{
fgets(szInput[i], 100, stdin);
}
int nK;
int nF1, nF2, nI;
scanf("%d", &nK);
int nCur = 0;
while (nK--)
{
scanf("%d%d%d", &nF1, &nF2, &nI);
for (
int i = nCur; i < nI; ++i)
{
sscanf(szInput[i], "%d%d%d%s", &nBeg,
&nEnd, &nL, szDir);
int dx = 0, dy = 0;
switch (szDir[0])
{
case 'N': dy += nL;
break;
case 'S': dy -= nL;
break;
case 'E': dx += nL;
break;
case 'W': dx -= nL;
break;
}
UnionSets(nBeg, nEnd, dx, dy);
}
nCur = nI;
if (FindSets(nF1) != FindSets(nF2))
{
printf("-1\n");
}
else {
printf("%d\n", abs(nX[nF1] - nX[nF2])
+ abs(nY[nF1] - nY[nF2]));
}
}
}
return 0;
}
并查集應(yīng)用的變形。
給出的是2個(gè)節(jié)點(diǎn)是敵對(duì)關(guān)系的信息，最后詢問任意2個(gè)節(jié)點(diǎn)的關(guān)系。根據(jù)這些信息，
節(jié)點(diǎn)之間可能是敵對(duì)的，也可能不是的（因?yàn)閿橙说臄橙司褪桥笥眩?，也可能給出的
信息根本描述不了它們的關(guān)系。
看起來跟原始的并查集應(yīng)用差遠(yuǎn)了。。。
有個(gè)比較直接的做法，那么就是把不在一個(gè)集合的節(jié)點(diǎn)直接用并查集合并在一起。這樣的話，
如果詢問的2個(gè)節(jié)點(diǎn)在同一個(gè)并查集里面，那么它們之間的關(guān)系是確定的，否則無法確定它們的
關(guān)系。
現(xiàn)在還有一個(gè)問題是，在同一個(gè)并查集里面的2個(gè)節(jié)點(diǎn)是敵對(duì)關(guān)系還是朋友關(guān)系。。。
可以給每個(gè)節(jié)點(diǎn)另外附加個(gè)信息，記錄其距離并查集根節(jié)點(diǎn)的距離。如果，詢問的2個(gè)節(jié)點(diǎn)距離
其根節(jié)點(diǎn)的距離都是奇數(shù)或者都是偶數(shù)，那么這2個(gè)節(jié)點(diǎn)是朋友關(guān)系，否則是敵對(duì)關(guān)系。。。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 100010;
int nSets[MAX_N];
int nDis[MAX_N];
int nN, nM;
void MakeSets(
int nNum)
{
for (
int i = 0; i < nNum; ++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[nI] + nDis[nPre]) % 2;
}
return nSets[nI];
}
void UnionSet(
int nI,
int nJ)
{
int nA = FindSet(nI);
int nB = FindSet(nJ);
if (nA != nB)
{
nSets[nA] = nB;
nDis[nA] = (nDis[nI] + nDis[nJ] + 1) % 2;
}
}
int main()
{
int nT;
scanf("%d", &nT);
while (nT--)
{
scanf("%d%d", &nN, &nM);
MakeSets(nN);
char szOper[10];
int nA, nB;
while (nM--)
{
scanf("%s%d%d", szOper, &nA, &nB);
if (szOper[0] == 'D')
{
UnionSet(nA, nB);
}
else {
int nX = FindSet(nA);
int nY = FindSet(nB);
if (nX == nY)
{
if (nDis[nA] == nDis[nB])
{
printf("In the same gang.\n");
}
else {
printf("In different gangs.\n");
}
}
else {
printf("Not sure yet.\n");
}
}
}
}
return 0;
}
此題本來模擬即可，但是注意有容易出錯(cuò)的地方。
這題主要是可以用中國(guó)剩余定理來做。
根據(jù)題意可以抽象出這樣的模型。給出三個(gè)數(shù)A,B,C分別是模23,28,33后的余數(shù)，求最小的數(shù)字
使得其模23,28,33分別為A,B,C，并且要大于給定的數(shù)字D。
中國(guó)剩余定理很好的解決了這種余數(shù)問題。令模數(shù)為Ni,余數(shù)為Ai,設(shè)Mi = N1*N2*...*Ni-1*Ni+1*...*Nn，
那么答案一定滿足形式ans =
ΣAi*Mi*(Mi對(duì)Ni的乘法逆) % N。(N為所有Ni的乘積)。
很明顯，由于ans的第i項(xiàng)有Mi因子，所以模N1-Ni-1和Ni+1-Nn肯定是0，而Ai*Mi*(Mi對(duì)Ni的乘法逆) %Ni
就是Ai。這樣就滿足了要求。
代碼如下：
#include <stdio.h>
#include <algorithm>
#include <
string.h>
#include <vector>
using namespace std;
int Egcd(
int nN,
int nM,
int& nX,
int& nY)
{
if (nM == 0)
{
nX = 1, nY = 0;
return nN;
}
int nRet = Egcd(nM, nN % nM, nX, nY);
int nT = nX;
nX = nY;
nY = nT - (nN / nM) * nY;
return nRet;
}
int main()
{
int nA, nB, nC, nD;
int nDays = 21252;
int nCase = 1;
while (scanf("%d%d%d%d", &nA, &nB, &nC, &nD),
nA != -1 || nB != -1 || nC != -1 || nD != -1)
{
int nFirst = 0;
nA %= 23;
nB %= 28;
nC %= 33;
int nM1= 28 * 33, nM2 = 23 * 33, nM3 = 23 * 28;
int nN1, nN2, nN3, nTemp;
Egcd(23, nM1, nTemp, nN1);
Egcd(28, nM2, nTemp, nN2);
Egcd(33, nM3, nTemp, nN3);
nFirst = (nA * nM1 * nN1 + nB * nM2 * nN2 + nC * nM3 * nN3) % nDays;
while (nFirst <= nD)nFirst += nDays;
printf("Case %d: the next triple peak occurs in %d days.\n",
nCase++, nFirst - nD);
}
return 0;
}
這個(gè)題是求一個(gè)字符串的最小重復(fù)單元的重復(fù)次數(shù)，那么求出最小重復(fù)單元的長(zhǎng)度即可。
這個(gè)題有3種方法，方法一：直接枚舉長(zhǎng)度為[1,len/2]內(nèi)的子串，暴力就過了。方法二：
將原串重復(fù)一次形成一個(gè)新串，用原串去匹配新串，但是得從第二個(gè)位置開始匹配，第一次
成功匹配的位置減一就代表最小重復(fù)單元的長(zhǎng)度。方法三：利用kmp的next函數(shù)，如果len
能夠整除len-next[len]，那么len-next[len]就代表最小重復(fù)單元的長(zhǎng)度。
方法一明顯是對(duì)的，數(shù)據(jù)不強(qiáng)的情況下就能水過了。方法二也不是那么容易想到的，不過
將原串?dāng)U展為2倍的做法也不是太奇葩，比如判斷2個(gè)循環(huán)串是否相等就可以用這個(gè)辦法做。
方法三就比較難理解了。
方法三的理解：
next[len]代表的是str的最長(zhǎng)前綴(使得這個(gè)前綴與同樣長(zhǎng)度的后綴相等)的長(zhǎng)度。所謂的next
數(shù)組就是長(zhǎng)度為1-len的str的滿足上述描述的最長(zhǎng)前綴的長(zhǎng)度。如果len是len-next[len]的倍數(shù)，
假設(shè)m = len-next[len] ，那么str[1-m] = str[m-2*m]，以此類推下去，m肯定是str的最小
重復(fù)單元的長(zhǎng)度。假如len不是len-next[len]的倍數(shù)， 如果前綴和后綴重疊，那么最小重復(fù)單元
肯定str本身了，如果前綴和后綴不重疊，那么str[m-2*m] != str[len-m,len]，所以str[1-m]
!= str[m-2*m] ,最終肯定可以推理出最小重復(fù)單元是str本身，因?yàn)橹灰粩噙f增m證明即可。
方法三的代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
char szStr[1000010];
int nNext[1000010];
void GetNext(
char* szStr,
int nLen,
int* nNext)
{
nNext[0] = -1;
for (
int i = 1, j = -1; i < nLen; ++i)
{
while (j > -1 && szStr[i] != szStr[j + 1])
{
j = nNext[j];
}
if (szStr[i] == szStr[j + 1])
{
++j;
}
nNext[i] = j;
}
}
int main()
{
while (scanf("%s", szStr), strcmp(szStr, "."))
{
int nLen = strlen(szStr);
GetNext(szStr, nLen, nNext);
if (nLen % (nLen - nNext[nLen - 1] - 1))
{
printf("1\n");
}
else {
printf("%d\n", nLen / (nLen - nNext[nLen - 1] - 1));
}
}
return 0;
}
裸的字符串匹配，子串最長(zhǎng)10,000，母串最長(zhǎng)
1,000,000。
求子串在母串中出現(xiàn)的次數(shù)。
如果子串長(zhǎng)度較小，那么直接RK匹配即可，hash值相同時(shí)候，直接比較字符串是否相同。
但是這個(gè)題的子串太長(zhǎng)了，還比較字符串會(huì)超時(shí)，如果不比較字符串理論上是錯(cuò)誤的，雖然
出錯(cuò)的概率很小，而且概率還是跟模數(shù)的選擇以及運(yùn)算時(shí)候是否溢出有關(guān)。
剛開始用了int，發(fā)現(xiàn)一直wa了，估計(jì)就是運(yùn)算時(shí)候就超int了，取模沒起到作用。模數(shù)的選
擇能夠提高正確率。Rabin-Karp 字符串匹配雖然比較好寫，也很容易理解，但是適用情況感
覺不是很廣，比如子串太長(zhǎng)了，處理就麻煩了，舍棄子串比較也不是很好。
但是子串不長(zhǎng)的話，Rabin-Karp 字符串匹配還是很不錯(cuò)的。
相比而言，這個(gè)題用kmp應(yīng)該會(huì)好很多。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
typedef
long long INT;
char szStrM[1000010];
char szStrS[10010];
const INT MOD = 16381 * 4733 + 1;
int main()
{
int nT;
scanf("%d", &nT);
while (nT--)
{
scanf("%s%s", szStrS, szStrM);
INT nMatch = szStrS[0] - 'A';
INT nPowN = 1;
int nSizeS = 1;
char* pszStr = szStrS + 1;
while (*pszStr)
{
nMatch = (26 * nMatch + *pszStr - 'A') % MOD;
nPowN = (nPowN * 26) % MOD;
++nSizeS;
++pszStr;
}
//prINTf("match:%d\n", nMatch);
int nSizeM = strlen(szStrM);
INT nKey = 0;
for (
int i = 0; i < nSizeS; ++i)
{
nKey = (26 * nKey + szStrM[i] - 'A') % MOD;
}
//prINTf("key:%d\n", nKey);
int nAns = 0;
for (
int i = 0; i <= nSizeM - nSizeS; ++i)
{
//prINTf("key:%d\n", nKey);
if (nKey == nMatch)
// && memcpy(szStrS, szStrM + i, nSizeS) == 0)
{
++nAns;
}
nKey = (26 * (nKey - nPowN * (szStrM[i] - 'A')) % MOD
+ szStrM[i + nSizeS] - 'A') % MOD;
nKey = (nKey + MOD) % MOD;
}
printf("%d\n", nAns);
}
return 0;
}
這個(gè)題是求一個(gè)字符串里面出現(xiàn)了多少個(gè)長(zhǎng)度為N的不同子串，同時(shí)給出了母串里面不同字符
的個(gè)數(shù)NC。
保存子串到set里面直接暴力肯定超時(shí)了。這個(gè)題有個(gè)利用字符串hash的解法，雖然理論上有
bug，但是能過這個(gè)題。
利用給出的NC，對(duì)長(zhǎng)度為N的字符串，將其當(dāng)作NC進(jìn)制的數(shù)字，求出其值，對(duì)值進(jìn)行hash，
求出不同的hash位置個(gè)數(shù)。
這個(gè)算法其實(shí)類似于Karp-Rabin字符串匹配算法。不過，Karp-Rabin算法做了點(diǎn)改進(jìn)，對(duì)
進(jìn)制為D的字符串求值的時(shí)候?yàn)榱朔乐挂绯鰰?huì)模一個(gè)素?cái)?shù)，而且不會(huì)每次都迭代求下一個(gè)子串的
值，而是從當(dāng)前子串的值直接遞推出下一個(gè)字符的值。怎么遞推了，其實(shí)很簡(jiǎn)單，就是當(dāng)前值去
掉最高位再乘以D(相當(dāng)于左移一位,不過是D進(jìn)制的，不能直接用<<符號(hào))，再加上新的最低位。
Karp-Rabin算法應(yīng)該主要在于設(shè)計(jì)出合理的hash算法，比如，用取模hash函數(shù)的話，得保
證hash表足夠大，否則沖突太多，速度就不會(huì)怎么好了。比如這個(gè)題，hash表小了就AC不了了。
代碼如下：
#include <stdio.h>
#include <string.h>
const int MAX = 13747347;
int nHash[MAX];
char szStr[17000001];
int nN, nNC;
int nW[200];
void Insert(int nKey)
{
int nPos = nKey;
while (nHash[nPos] != -1 && nHash[nPos] != nKey)
{
nPos = (nPos + 1) % MAX;
}
nHash[nPos] = nKey;
}
bool Find(int nKey)
{
int nPos = nKey;
while (nHash[nPos] != -1 && nHash[nPos] != nKey)
{
nPos = (nPos + 1) % MAX;
}
return nHash[nPos] != -1;
}
int main()
{
while (scanf("%d%d%s", &nN, &nNC, szStr) == 3)
{
memset(nW, 0, sizeof(nW));
memset(nHash, -1, sizeof(nHash));
int nNum = 0;
int nSize = 0;
for (char* pszStr = szStr; *pszStr; ++pszStr)
{
if (!nW[*pszStr])
{
nW[*pszStr] = ++nNum;
}
++nSize;
}
int nKey = 0;
int nAns = 0;
int nPowN = 1;
for (int j = 0; j < nN; ++j)
{
nKey = (nKey * nNC + nW[szStr[j]]) % MAX;
nPowN *= nNC;
}
nPowN /= nNC;
if (!Find(nKey))
{
Insert(nKey);
nAns++;
}
for (int i = nN; i < nSize; ++i)
{
nKey = (nNC * (nKey - nPowN * nW[szStr[i - nN]])
+ nW[szStr[i]]) % MAX;
nKey = (nKey + MAX) % MAX;
if (!Find(nKey))
{
Insert(nKey);
nAns++;
}
}
printf("%d\n", nAns);
}
return 0;
}
代碼如下：
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
#define MAX (5000000)
bool bPrime[MAX];
void InitPrime()
{
int nMax = sqrt((double)MAX) + 1;
bPrime[0] = bPrime[1] = true;
for (int i = 2; i <= nMax; ++i)
{
if (!bPrime[i])
{
for (int j = 2 * i; j < MAX; j += i)
{
bPrime[j] = true;
}
}
}
}
LL multAndMod(LL a, LL b, LL n)
{
LL tmp = 0;
while (b)
{
if(b & 1)
{
tmp = (tmp + a) % n;
}
a = (a << 1) % n;
b >>= 1;
}
return tmp;
}
//計(jì)算a^u%n
LL ModExp(LL a, LL u, LL n)
{
LL d = 1;
a %= n;
while (u)
{
if (u & 1)
{
d = multAndMod(d, a, n);
}
a = multAndMod(a, a, n);
u >>= 1;
}
return d % n;
}
//判斷nN是不是合數(shù)
bool Witness(LL a, LL nN)
{
LL u = nN - 1, t = 0;//將nN-1表示為u*2^t
while (u % 2 == 0)
{
t++;
u >>= 1;
}
LL x0 = ModExp(a, u, nN);//x是a^u
LL x1;
for (int i = 1; i <= t; ++i)
{
x1 = multAndMod(x0, x0, nN);
if (x1 == 1 && x0 != nN - 1 && x0 != 1)
{
return true;
}
x0 = x1;
}
if (x1 != 1)
{
return true;
}
return false;
}
//素?cái)?shù)測(cè)試
bool MillerRabin(LL nN)
{
//if (nN < MAX)return !bPrime[nN];
const int TIME = 10;
for (int i = 0; i < TIME; ++i)
{
LL a = rand() % (nN - 1) + 1;
if (Witness(a, nN))
{
return false;
}
}
return true;
}
LL gcd(LL a, LL b)
{
if (a < b)swap(a, b);
while (b)
{
LL t = a;
a = b;
b = t % b;
}
return a;
}
//啟發(fā)式尋找nN的因子
LL PollardRho(LL n, LL c)
{
LL i = 1, t = 2;
LL x, y;
LL ans;
srand(time(NULL));
y = x = rand() % n;
while(1)
{
i++;
x = (multAndMod(x, x, n) + c) % n;
ans = gcd(y - x, n);
if(ans > 1 && ans < n)
return ans;
if(x == y)
return n;
if(t == i)
{
y = x;
t <<= 1;
}
}
}
LL FindMin(LL nN, LL c)
{
//printf("nN:%I64u\n", nN);
if (MillerRabin(nN) || nN <= 1)
{
return nN;
}
LL p = nN;
while (p >= nN) p = PollardRho(p, c--);
if (p > 1)
p = FindMin(p, c);//分解p的最小因子
if (p < nN)
{
LL q = nN / p;
q = FindMin(q, c);//找到q的最小因子
p = min(p, q);
}
return p;
}
int main()
{
int nTest;
srand(time(NULL));
//InitPrime();
scanf("%d", &nTest);
while (nTest--)
{
LL nN;
scanf("%I64u", &nN);
if (nN > 2 && nN % 2 == 0)
{
printf("2\n");
}
else if (nN == 2 || MillerRabin(nN))
{
printf("Prime\n");
}
else
{
printf("%I64u\n", FindMin(nN, 181));
}
}
return 0;
}