poj 3764 The xor-longest Path 字典树 + Xor

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

   代码如下:
#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, falsesizeof(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;
}

posted @ 2012-10-12 20:12 yx 阅读(1008) | 评论 (0)编辑 收藏

poj 1182 食物链 并查集

   这是并查集最后一题,据说也是最经典的一题。经常前面几题的训练,这题的思路很快
就能想出来了。只需要对每个节点附加一个信息表示离根节点的距离,并且距离是模3循环的。
   注意合并时候保持距离变化的正确性。而且合并有2种情况,距离相同合并和距离不同合并。
分别对应于题目描述中的1和2操作。
   关键还是FindSet里面对距离nDis数组里面的修改,前面一直写错这个,wa了好几次,还是
看队友代码才一眼发现我又把这里写错了。。。当前距离的更新还是等于当前距离加上前一个
节点的距离再模3,类似于前面几题的更新方法。
   这种将有关系的节点放在一个并查集里面,再给每个节点附加其它信息描述其它关系的做法,
确实比较有效。。。并查集是应用于不相交集合的数据结构,看来某个时候却有妙用啊。。。

   代码如下:
#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;
}

   

posted @ 2012-10-10 20:51 yx 阅读(1256) | 评论 (0)编辑 收藏

poj 1988 Cube Stacking 并查集

   也是个题意比较奇葩的题目。有2个操作,1个是把一个元素所在的栈,放到另外1个元素所在
的栈上面。另外一个操作是统计某个元素下面有多少个元素(当然是在同一个栈中)。
   貌似,需要记录每个元素下面的元素是什么了,既然要记录这个就不能用并查集的路径压缩了。
 不压缩路径的话,肯定会超时的。怎么办了。。。
   其实,可以这么考虑,以每个栈的栈底元素作为并查集的代表元素。压缩路径后,每个元素或者
是根元素或者其父亲元素就是根元素。所以,另外对每个节点附加个信息代表该节点的高度,栈底
元素高度为0。再附加个信息代表每个并查集元素总数目,这样就可以在合并集合时候修改信息,
并且压缩路径也能保证答案正确。。。

   代码如下:
#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;
}

posted @ 2012-10-10 12:15 yx 阅读(956) | 评论 (0)编辑 收藏

poj 1984 Navigation Nightmare 并查集

   并查集应用的变形。题目意思是一个图中,只有上下左右四个方向的边。给出这样的一些边,
求任意指定的2个节点之间的距离。
   有可能当前给出的信息,没有涉及到要求的2个节点,或者只涉及到了1个节点,那么肯定
无法确定它们的距离。或者根据已经给出的边只知道这2个节点在不同的联通分量里面,那么其
距离也是无法确定的,根据题目要求,输出-1。
   问题是如果能够确定它们在一个联通分量里面,如何确定它们的距离了。
   这个题的关键在于,只有上下左右四个方向的边,假设每个节点都有一个坐标的话,那么它们
相对于代表该联通分量节点的坐标肯定是固定的,那么就不需要考虑图里面有环之类的情况了。
这样就可以很方便的应用并查集来解了。
   利用并查集,给每个节点附加其它信息,即相对于代表该并查集的节点的坐标(x,y)。
在FindSet里面求出坐标,在UnionSet里面修改合并后新加入的另外一个集合的根节点的坐标即可。
   代码如下:

#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];//因为方向逆过来了,所以是减去
        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;
}

posted @ 2012-10-09 21:25 yx 阅读(932) | 评论 (0)编辑 收藏

poj 1703 Find them, Catch them 并查集

   并查集应用的变形。
   给出的是2个节点是敌对关系的信息,最后询问任意2个节点的关系。根据这些信息,
节点之间可能是敌对的,也可能不是的(因为敌人的敌人就是朋友),也可能给出的
信息根本描述不了它们的关系。
   看起来跟原始的并查集应用差远了。。。
   有个比较直接的做法,那么就是把不在一个集合的节点直接用并查集合并在一起。这样的话,
如果询问的2个节点在同一个并查集里面,那么它们之间的关系是确定的,否则无法确定它们的
关系。
   现在还有一个问题是,在同一个并查集里面的2个节点是敌对关系还是朋友关系。。。
   可以给每个节点另外附加个信息,记录其距离并查集根节点的距离。如果,询问的2个节点距离
其根节点的距离都是奇数或者都是偶数,那么这2个节点是朋友关系,否则是敌对关系。。。

   代码如下:
#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;
}

posted @ 2012-10-08 22:33 yx 阅读(1091) | 评论 (0)编辑 收藏

poj 1006 Biorhythms 中国剩余定理

   此题本来模拟即可,但是注意有容易出错的地方。
   这题主要是可以用中国剩余定理来做。
   根据题意可以抽象出这样的模型。给出三个数A,B,C分别是模23,28,33后的余数,求最小的数字
使得其模23,28,33分别为A,B,C,并且要大于给定的数字D。
   中国剩余定理很好的解决了这种余数问题。令模数为Ni,余数为Ai,设Mi = N1*N2*...*Ni-1*Ni+1*...*Nn,
那么答案一定满足形式ans = ΣAi*Mi*(Mi对Ni的乘法逆) % N。(N为所有Ni的乘积)。
   很明显,由于ans的第i项有Mi因子,所以模N1-Ni-1和Ni+1-Nn肯定是0,而Ai*Mi*(Mi对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;
}

posted @ 2012-10-03 23:11 yx 阅读(844) | 评论 (0)编辑 收藏

poj 2406 Power Strings kmp的妙用

   这个题是求一个字符串的最小重复单元的重复次数,那么求出最小重复单元的长度即可。
   这个题有3种方法,方法一:直接枚举长度为[1,len/2]内的子串,暴力就过了。方法二:
将原串重复一次形成一个新串,用原串去匹配新串,但是得从第二个位置开始匹配,第一次
成功匹配的位置减一就代表最小重复单元的长度。方法三:利用kmp的next函数,如果len
能够整除len-next[len],那么len-next[len]就代表最小重复单元的长度。
   方法一明显是对的,数据不强的情况下就能水过了。方法二也不是那么容易想到的,不过
将原串扩展为2倍的做法也不是太奇葩,比如判断2个循环串是否相等就可以用这个办法做。
方法三就比较难理解了。
   方法三的理解:
   next[len]代表的是str的最长前缀(使得这个前缀与同样长度的后缀相等)的长度。所谓的next
数组就是长度为1-len的str的满足上述描述的最长前缀的长度。如果len是len-next[len]的倍数,
假设m = len-next[len] ,那么str[1-m] = str[m-2*m],以此类推下去,m肯定是str的最小
重复单元的长度。假如len不是len-next[len]的倍数, 如果前缀和后缀重叠,那么最小重复单元
肯定str本身了,如果前缀和后缀不重叠,那么str[m-2*m] != str[len-m,len],所以str[1-m]
!= str[m-2*m] ,最终肯定可以推理出最小重复单元是str本身,因为只要不断递增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;
}

   
   

posted @ 2012-09-30 15:25 yx 阅读(1223) | 评论 (1)编辑 收藏

poj 3461 Oulipo Rabin-Karp 字符串匹配

   裸的字符串匹配,子串最长10,000,母串最长1,000,000。
   求子串在母串中出现的次数。
   如果子串长度较小,那么直接RK匹配即可,hash值相同时候,直接比较字符串是否相同。
但是这个题的子串太长了,还比较字符串会超时,如果不比较字符串理论上是错误的,虽然
出错的概率很小,而且概率还是跟模数的选择以及运算时候是否溢出有关。
   刚开始用了int,发现一直wa了,估计就是运算时候就超int了,取模没起到作用。模数的选
择能够提高正确率。Rabin-Karp 字符串匹配虽然比较好写,也很容易理解,但是适用情况感
觉不是很广,比如子串太长了,处理就麻烦了,舍弃子串比较也不是很好。
   但是子串不长的话,Rabin-Karp 字符串匹配还是很不错的。
   相比而言,这个题用kmp应该会好很多。

   代码如下:
#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;
}

posted @ 2012-09-28 12:01 yx 阅读(1094) | 评论 (0)编辑 收藏

poj 1200 Crazy Search 字符串hash

   这个题是求一个字符串里面出现了多少个长度为N的不同子串,同时给出了母串里面不同字符
的个数NC。
   保存子串到set里面直接暴力肯定超时了。这个题有个利用字符串hash的解法,虽然理论上有
bug,但是能过这个题。
   利用给出的NC,对长度为N的字符串,将其当作NC进制的数字,求出其值,对值进行hash,
求出不同的hash位置个数。
   这个算法其实类似于Karp-Rabin字符串匹配算法。不过,Karp-Rabin算法做了点改进,对
进制为D的字符串求值的时候为了防止溢出会模一个素数,而且不会每次都迭代求下一个子串的
值,而是从当前子串的值直接递推出下一个字符的值。怎么递推了,其实很简单,就是当前值去
掉最高位再乘以D(相当于左移一位,不过是D进制的,不能直接用<<符号),再加上新的最低位。
   Karp-Rabin算法应该主要在于设计出合理的hash算法,比如,用取模hash函数的话,得保
证hash表足够大,否则冲突太多,速度就不会怎么好了。比如这个题,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;
}

posted @ 2012-09-27 22:07 yx 阅读(1013) | 评论 (0)编辑 收藏

poj 1811 Prime Test 数论 素数测试

 代码如下:
#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;
}
//计算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是不是合数
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;
}
//素数测试
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;
}
//启发式寻找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;
}

posted @ 2012-09-24 12:56 yx 阅读(175) | 评论 (0)编辑 收藏

仅列出标题
共10页: 1 2 3 4 5 6 7 8 9 Last 
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

常用链接

留言簿(3)

随笔分类

随笔档案

me

好友

同学

网友

搜索

最新评论

阅读排行榜

评论排行榜