yx - C++博客

hdu 4294 Multiple 数论 + bfs

这是前天成都网赛的题，比赛时候确实一点思路也没有。比完之后看了人家的解题报告，还是不会怎么搜出答案，太弱了。
题意是给出N,K，求M，使得M是N的正倍数，而且M用K进制表示后所需要的不同数字(0,1,2,3,...,k-1)最少，如果有多组
这样的情况，求出最小的M。
很数学的题意。用到了一个结论，就是任意数字的正倍数均可以用不超过2个不同数字的数得到。
证明如下：
任意数M % N 总共有N种结果，假如有N+1个不同的M，那么肯定有2个M对N取模后的结果是相同，这个是所谓鸽巢原理。
那么，我取a,aa,aaa,...,aaaaaaaaaa....，总共N+1个，同样满足上面的结论。那么我取那2个对N取模相同的数字相减得到
数字aaaaa...000....，这个数字肯定是N的倍数。
综合上面的证明，只能得到2个数字肯定能表示N的倍数。但是不能说形式就是aaaaa...000....。

到了这里我还是一点思路都没有，一点都不知道怎么搜索。。。
想了1个多小时，无头绪，问过了这题的同学，还是无头绪。看解题报告，他们的代码写得太牛了，完全看不懂，无头绪。
也许也是我对bfs理解太浅，才看不懂他们的搜索代码。而且，我连可以搜索的地方都没有找到，都不知道搜什么了。
想了好久，昨天吃饭的时候，终于发现可以对余数进行搜索。
对于任意的N，其余数就是范围是[0, N -1]。这个其实就可以代表状态了，或者代表bfs中的点了。从当前余数转移到其它
余数的是MOD * K + A 或者 MOD * K + B，如果要转移到得余数以前没被搜过，那就可以转移过去。这个刚好就是一个
优化了。也可以看成是子问题了。但是，dfs完全不行。刚开始用dfs，绝对的超时。
用dfs也是我对思路理解不深，侥幸认为能过。。。后面发现，这题完全和bfs吻合。[0, N -1]刚好代表N个点，我要通过
从外面的一个点，最短的遍历到点0，可以bfs或者最短路算法。这题我觉得还有个难点就是保存答案，因为答案最长的长度
可能是N(N<=10000)，所以把答案直接放到节点里面肯定不行的。但是，我还仔细看过算法导论。因此想到了可以利用bfs
搜索出来的那颗树或者最短路算法跑出来的那颗树，从目标节点逆序寻找答案，找到出发节点之后，再把答案reverse一下就行了。
这题还得注意0不能是N的倍数，所以注意bfs(0,i)这种情况的处理。

代码如下：

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 10010;
int nOut[MAX_N];
int nOLen;
int nAns[MAX_N];
int nALen;
bool bMod[MAX_N];
int nFather[MAX_N];
int nChoose[MAX_N];
int nN;
int nK;
bool bFind;

int Cmp(int* A, int nLA, int* B, int nLB)
{
    if (nLA != nLB)
    {
        return nLA - nLB;
    }
    for (int i = 0; i < nLA; ++i)
    {
        if (A[i] != B[i])
        {
            return A[i] - B[i];
        }
    }
    return 0;
}

void Bfs(int nA, int nB)
{
    memset(bMod, false, sizeof(bMod));
    queue<int> que;
    que.push(0);
    int nTemp;
    bool bFirst = true;
    bFind = false;

    if (nA > nB)swap(nA, nB);
    //printf("nA:%d, nB:%d\n", nA, nB);
    while (!que.empty())
    {
        //printf("nMod:%d\n", que.front());
        int nMod = que.front();
        que.pop();
        if (nMod == 0)
        {
            if (bFirst)bFirst = false;
            else
            {
                bFind = true;
                break;
            }
        }

        nTemp = (nMod * nK + nA) % nN;
        if (!(nMod == 0 && nA == 0) && !bMod[nTemp])
        {
            nFather[nTemp] = nMod;
            nChoose[nTemp] = nA;
            que.push(nTemp);
            bMod[nTemp] = true;
            //printf("nTemp:%d\n", nTemp);
        }
        if (nA == nB)continue;
        nTemp = (nMod * nK + nB) % nN;
        if (!bMod[nTemp])
        {
            nFather[nTemp] = nMod;
            nChoose[nTemp] = nB;
            que.push(nTemp);
            bMod[nTemp] = true;
            //printf("nTemp:%d\n", nTemp);
        }
    }

    if (bFind)
    {
        int nF = 0;
        nALen = 0;
        do
        {
            nAns[nALen++] = nChoose[nF];
            nF = nFather[nF];
        } while (nF);
        reverse(nAns, nAns + nALen);
    }
}

int main()
{
    while (scanf("%d%d", &nN, &nK) == 2)
    {
        bool bOk = false;
        nOLen = 0;
        for (int i = 1; i < nK; ++i)
        {
            Bfs(i, i);
            if (bFind)
            {
                if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
                {
                    nOLen = nALen;
                    memcpy(nOut, nAns, sizeof(int) * nALen);
                }
                bOk = true;
            }
        }
        if (!bOk)
            for (int i = 0; i < nK; ++i)
            {
                for (int j = i + 1; j < nK; ++j)
                {
                    Bfs(i, j);
                    if (bFind)
                    {
                        if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
                        {
                            nOLen = nALen;
                            memcpy(nOut, nAns, sizeof(int) * nALen);
                        }
                    }
                }
            }
        for (int k = 0; k < nOLen; ++k)
        {
            printf("%d", nOut[k]);
        }
        printf("\n");
    }

    return 0;
}

posted @ 2012-09-18 13:27 yx 阅读(1367) | 评论 (0) | 编辑收藏

poj 3468 A Simple Problem with Integers 线段树成段延迟更新

用线段树成段更新不能立即全部更新，必须搞延迟操作。其实，就是针对每个节点，另外搞一个域表示延迟
更新的数目。然后，在更新操作和查找操作的时候都把父亲节点的延迟域往2个儿子走。
这个题是要成段增加值，所以在写PushDown函数的时候要注意，只能给儿子节点加上父亲节点压过来的值
乘以儿子区间的长度。这题貌似用树状数组也可以做，不过解法肯定意思不是那么直白的。不过速度肯定会快。
树状数组解法：http://kenby.iteye.com/blog/962159
线段树网上流行的解法都是开最多节点数目4倍的数组。以位置1作为根，每个位置其实代表的是一个区间。
某人位置1代表1-N或者0-(N-1)区间，具体看题目了。那么2就代表区间1-(1+N)/2，3就代表区间(1+N)/2+1 - N了。
至于lazy标记还是搞个大数组，意义和线段树数组一样，搞清楚之后写起来都比较简单，最重要的是变形来
解决一些要求奇怪的题目。

#include <stdio.h>

#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;

const INT MAX_N = 100010;
const INT INF = 0x7ffffffffffffffLL;
INT nTree[MAX_N << 2];
INT nAdd[MAX_N << 2];
INT nN, nQ;

void PushUp(INT nRt)
{
    nTree[nRt] = nTree[nRt << 1] + nTree[nRt << 1 | 1];
}

void BuildTree(INT nL, INT nR, INT nRt)
{
    nAdd[nRt] = 0;
    if (nL == nR)
    {
        scanf("%I64d", &nTree[nRt]);
        return;
    }

    INT nMid = (nL + nR) >> 1;
    BuildTree(nL, nMid, nRt << 1);
    BuildTree(nMid + 1, nR, nRt << 1 | 1);
    PushUp(nRt);
}

void PushDown(INT nL, INT nR, INT nRt)
{
    INT nMid = (nL + nR) >> 1;
    INT nLs = nRt << 1;
    INT nRs = nLs | 1;

    if (nAdd[nRt])
    {
        nAdd[nLs] += nAdd[nRt];
        nAdd[nRs] += nAdd[nRt];
        nTree[nLs] += (nMid - nL + 1) * nAdd[nRt];
        nTree[nRs] += (nR - nMid) * nAdd[nRt];
        nAdd[nRt] = 0;
    }
}

void Update(INT nL, INT nR, INT nRt, INT nX, INT nY, INT nV)
{
    if (nL >= nX && nR <= nY)
    {
        nTree[nRt] += nV * (nR - nL + 1);
        nAdd[nRt] += nV;
        return;
    }

    PushDown(nL, nR, nRt);
    INT nMid = (nL + nR) >> 1;
    if (nX <= nMid) Update(nL, nMid, nRt << 1, nX, nY, nV);
    if (nY > nMid) Update(nMid + 1, nR, nRt << 1 | 1, nX, nY, nV);
    PushUp(nRt);
}

INT Query(INT nL, INT nR, INT nRt, INT nX, INT nY)
{
    if (nL >= nX && nR <= nY)
    {
        return nTree[nRt];
    }
    PushDown(nL, nR, nRt);
    INT nAns = 0;
    INT nMid = (nL + nR) >> 1;
    if (nX <= nMid) nAns += Query(nL, nMid, nRt << 1, nX, nY);
    if (nY > nMid) nAns += Query(nMid + 1, nR, nRt << 1 | 1, nX, nY);
    return nAns;
}

int main()
{
    INT nTemp;
    while (scanf("%I64d%I64d", &nN, &nQ) == 2)
    {
        BuildTree(1, nN, 1);

        while (nQ--)
        {
            char szCmd[10];
            INT nX, nY, nV;
            scanf("%s", szCmd);
            if (szCmd[0] == 'Q')
            {
                scanf("%I64d%I64d", &nX, &nY);
                printf("%I64d\n", Query(1, nN, 1, nX, nY));
            }
            else
            {
                scanf("%I64d%I64d%I64d", &nX, &nY, &nV);
                Update(1, nN, 1, nX, nY, nV);
            }
        }
    }

    return 0;
}

posted @ 2012-09-16 20:42 yx 阅读(1364) | 评论 (0) | 编辑收藏

poj 2886 Who Gets the Most Candies? 约瑟夫环和反素数

直接模拟约瑟夫环是N^2，况且这题每次移动的距离和方向都是不确定的，只能模拟，如果加快查找和移动的话，
可以提高速度，果断用线段树维护当前位置前面有多少个人。
至于反素数指的是求一个小于等于N的数字，使得其因子个数在1-N中是最大的。这个利用一个必要条件暴力搜索即可。

其实就是利用下面这2个性质搜索的。
性质一:一个反素数的质因子必然是从2开始连续的质数。性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....。

代码如下：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

int nPrime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int nAns;
int nCN;
const int MAX_N = 500010;
//nPow不会超过20
void InitBest(int nCur, int nI, int nMax, int nN, int nNum)
{
    if (nCur > nN) return;
    if (nNum > nCN){nAns = nCur;nCN = nNum;}
    if (nNum == nCN){nAns = min(nAns, nCur);}
    for (int i = 1; i <= nMax; ++i)
    {
        nCur *= nPrime[nI];
        if (nCur > nN)return;//不加这句优化会超时
        if (nI < 15)
        InitBest(nCur, nI + 1, i, nN, nNum * (i + 1));
    }
}

char szNames[MAX_N][10];
int nValue[MAX_N];
int nTree[MAX_N << 2];
void PushUp(int nRt)
{
    nTree[nRt] = nTree[nRt << 1] + nTree[nRt << 1 | 1];
}

void BuildTree(int nL, int nR, int nRt, int nV)
{
    if (nL == nR)
    {
        nTree[nRt] = nV;
        return;
    }
    int nMid = (nL + nR) >> 1;
    BuildTree(nL, nMid, nRt << 1, nV);
    BuildTree(nMid + 1, nR, nRt << 1 | 1, nV);
    PushUp(nRt);
}

void Add(int nL, int nR, int nRt, int nP, int nV)
{
    if (nL == nR)
    {
        nTree[nRt] += nV;
    }
    else
    {
        int nMid = (nL + nR) >> 1;
        if (nP <= nMid)Add(nL, nMid, nRt << 1, nP, nV);
        else Add(nMid + 1, nR, nRt << 1 | 1, nP, nV);
        PushUp(nRt);
    }
}

int Query(int nL, int nR, int nRt, int nSum)
{
    if (nL == nR)
    {
        return nL;
    }
    int nMid = (nL + nR) >> 1;
    int nLs = nRt << 1;
    int nRs = nLs | 1;
    if (nTree[nLs] >= nSum) return Query(nL, nMid, nLs, nSum);
    else return Query(nMid + 1, nR, nRs, nSum - nTree[nLs]);
}

int main()
{
    //InitBest(1, 0, 15);
    int nN, nK;

    while (scanf("%d%d", &nN, &nK) == 2)
    {
        nK--;
        nAns = 2;
        nCN = 0;
        InitBest(1, 0, 20, nN, 1);
        //printf("ans:%d cn:%d\n", nAns, nCN);
        for (int i = 0; i < nN; ++i)
        {
            scanf("%s%d", szNames[i], &nValue[i]);
        }

        BuildTree(0, nN - 1, 1, 1);
        int nTotal = nN;
        int nPos;
        for (int i = 0; i < nAns; ++i)
        {
            nPos = Query(0, nN - 1, 1, nK + 1);
            //printf("nK:%d %s %d\n", nK, szNames[nPos], nValue[nPos]);
            nTotal--;
            Add(0, nN - 1, 1, nPos, -1);
            if (!nTotal)break;
            if (nValue[nPos] >= 0)
            {
                nK = (nK - 1 + nValue[nPos] + nTotal) % nTotal;
            }
            else
            {
                nK = ((nK + nValue[nPos]) % nTotal + nTotal) % nTotal;
            }
        }
        printf("%s %d\n", szNames[nPos], nCN);
    }

    return 0;
}

posted @ 2012-09-14 20:53 yx 阅读(1306) | 评论 (0) | 编辑收藏

hdu 2492 Ping pong 树状数组

此题是求一个数字序列中，长度为3的子序列(a,b,c)，且满足条件a<=b<=c或者c<=b<=a的子序列的个数。
明显枚举每个b，求每个b左边的a的个数和右边c的个数，以及左边c的个数和右边a的个数，然后累加左右乘积求和即可。
刚开始只求了满足条件a<=b<=c的部分，而且忘记用64位了。wa了几次。求左边a的个数其实就是求小于等于b的数字
的个数，这个刚好可以用树状数组或者线段树求。具体见代码。

代码如下：

#include <stdio.h>

#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;
const INT MAX_N =  100010;
const INT N = 20010;
INT nN;
INT nNum[N];
INT nTree[MAX_N + 10];
INT nLeft[2][N], nRight[2][N];

INT LowBit(INT nI)
{
    return nI & (-nI);
}

void Add(INT nI, INT nAdd)
{
    while (nI <= MAX_N)
    {
        nTree[nI] += nAdd;
        nI += LowBit(nI);
    }
}

INT Query(INT nPos)
{
    INT nAns = 0;
    while (nPos > 0)
    {
        nAns += nTree[nPos];
        nPos -= LowBit(nPos);
    }
    return nAns;
}

int main()
{
    INT nT;

    scanf("%I64d", &nT);
    while (nT--)
    {
        scanf("%I64d", &nN);
        memset(nTree, 0, sizeof(nTree));
        for (INT i = 1; i <= nN; ++i)
        {
            scanf("%I64d", &nNum[i]);
            nLeft[0][i] = Query(nNum[i]);
            nLeft[1][i] = Query(MAX_N) - Query(nNum[i] - 1);
            Add(nNum[i], 1);
        }
        memset(nTree, 0, sizeof(nTree));
        for (INT i = nN; i >= 1; --i)
        {
            nRight[0][i] = Query(MAX_N) - Query(nNum[i] - 1);
            nRight[1][i] = Query(nNum[i]);
            Add(nNum[i], 1);
        }
        INT nAns = 0;
        for (INT i = 1; i <= nN; ++i)
        {
            nAns += nLeft[0][i] * nRight[0][i] + nLeft[1][i] * nRight[1][i];
        }
        printf("%I64d\n", nAns);
    }

    return 0;
}

posted @ 2012-09-12 21:11 yx 阅读(1270) | 评论 (0) | 编辑收藏

hdu 3584 Cube 三维树状数组

这个题意思是翻转一个01立方体。翻转多次后再查询某个点的值。
还是利用上一篇文章的思想，把翻转操作转换为单点更新操作。把查询操作转换为利用树状数组查询和的方式。
这样每次操作的复杂度都是logN的3次。而直接翻转立方体的复杂度是N的3次。
这个题最麻烦的地方是空间想象能力。因为要翻转8个点才能完成一次立方体翻转。比如，翻转(x,y,z)相当于
以该点作为左上角做一个无限立方体，把该立方体翻转。这样就会翻转多余的部分，那么需要把多翻转的部分翻转
回来。最后的思考结果发现，只要对每个顶点翻转一次即可。至于为什么这样，自己去计算重复翻转的部分就会明白
了。刚好确实是把每个点翻转了一次。

代码如下：

#include <stdio.h>

#include <string.h>
#include <algorithm>
using namespace std;

const int MAX_N = 110;
int nSum[MAX_N + 10][MAX_N + 10][MAX_N + 10];
int nN, nM;

int LowBit(int nPos)
{
    return nPos & (-nPos);
}

void Add(int nX, int nY, int nZ)
{
    for (int i = nX; i <= nN; i += LowBit(i))
    {
        for (int j = nY; j <= nN; j += LowBit(j))
        {
            for (int k = nZ; k <= nN; k += LowBit(k))
            {
                nSum[i][j][k]++;
            }
        }
    }
}

int Query(int nX, int nY, int nZ)
{
    int nAns = 0;

    for (int i = nX; i > 0; i -= LowBit(i))
    {
        for (int j = nY; j > 0; j -= LowBit(j))
        {
            for (int k = nZ; k > 0; k -= LowBit(k))
            {
                nAns += nSum[i][j][k];
            }
        }
    }
    return nAns;
}

int main()
{
    int nCmd;
    int nX, nY, nZ;
    int nX1, nY1, nZ1;
    int nX2, nY2, nZ2;

    while (scanf("%d%d", &nN, &nM) == 2)
    {
        memset(nSum, 0, sizeof(nSum));
        while (nM--)
        {
            scanf("%d", &nCmd);
            if (nCmd == 0)
            {
                scanf("%d%d%d", &nX, &nY, &nZ);
                printf("%d\n", Query(nX, nY, nZ) % 2);
            }
            else
            {
                scanf("%d%d%d%d%d%d", &nX1, &nY1, &nZ1, &nX2, &nY2, &nZ2);
                if (nX1 > nX2)swap(nX1, nX2);
                if (nY1 > nY2)swap(nY1, nY2);
                if (nZ1 > nZ2)swap(nZ1, nZ2);
                Add(nX1, nY1, nZ1);

                Add(nX2 + 1, nY1, nZ1);
                Add(nX1, nY2 + 1, nZ1);
                Add(nX1, nY1, nZ2 + 1);

                Add(nX1, nY2 + 1, nZ2 + 1);
                Add(nX2 + 1, nY1, nZ2 + 1);
                Add(nX2 + 1, nY2 + 1, nZ1);

                Add(nX2 + 1, nY2 + 1, nZ2 + 1);
            }
        }
    }

    return 0;
}

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

hdu 1556 Color the ball 树状数组

这个题的意思是给定一个长为N的区间。不断的给某个子区间[A,B]中的每个点涂一次色。最后问每个点的涂色次数。
这个题貌似可以扩展到多维的情况，但是多维的情况下必须用树状数组求和以加快速度，一维的情况直接求和即可。
假如，第一次涂色是对区间[A,B]涂色一次，可以让nNum[nA]++,nNum[nB+1]--即可。因为这样对于区间[0,nA-1]的任意值i有
都要nNum[1]+nNum[2]+...+nNum[i] = 0。而对于区间[nA,nB]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。
对于区间[nB+1, nN]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。
那么重复多次了。如果上述求和nNum[1]+nNum[2]+...+nNum[i] 刚好代表每个结点i的涂色次数，那么这个题就可解了。
用例子验证一下，发现肯定是这样的。证明略了。
至于树状数组网上一大堆资料。树状数组模板单一，敲代码太方便了。

代码如下：

#include <stdio.h>

#include <string.h>
#include <algorithm>
using namespace std;

int nNum[100000 + 10];
int nN;
int LowBit(int nI)
{
    return nI & (-nI);
}

void Add(int nI, int nAdd)
{
    while (nI <= nN)
    {
        nNum[nI] += nAdd;
        nI += LowBit(nI);
    }
}

int GetSum(int nI)
{
    int nAns = 0;

    while (nI > 0)
    {
        nAns += nNum[nI];
        nI -= LowBit(nI);
    }
    return nAns;
}

int main()
{
    int nA, nB;

    while (scanf("%d", &nN), nN)
    {
        memset(nNum, 0, sizeof(nNum));

        for (int i = 1; i <= nN; ++i)
        {
            scanf("%d%d", &nA, &nB);
            Add(nA, 1);
            Add(nB + 1, -1);
        }
        for (int i = 1; i <= nN; ++i)
        {
            printf("%d%s", GetSum(i), i == nN ? "\n" : " ");
        }
    }

    return 0;
}

posted @ 2012-09-06 20:51 yx 阅读(1380) | 评论 (1) | 编辑收藏

poj 3255 Roadblocks 次短路

这个题是求次短路。有个不错的解法，是根据一个结论，替换调最短路里面的一条边肯定能得到次短路。
那么，只要枚举所有边就可以了。比如，假设开始点为s，目标点是d，设最短路为dis(s,d)。对于边(u,v)，
dis(s, u) + w(u, v) + dis(v, d) 大于dis(s, d)，则该路径就可能是次短路。求出最小的大于dis(s,d)的值就可以了。
方式是从s开始和从d开始进行2次单源多终点最短路径算法。然后枚举边即可。

该算法可以这样理解。因为替换最短路径里面的边，路径的长度只会变大或者不变。如果存在让更短路径变小的边，
这本身就与最短路径是矛盾的。所以替换2条或者更多的边只会让路径变得更大。因此，只需考虑替换一条边的情况
即可。

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int MAX_N = 5000 + 10;
struct Edge
{
    int nE;
    int nDis;
    Edge(int e, int d):nE(e), nDis(d) {}
};
vector<Edge> graph[MAX_N];
bool bVisit[MAX_N];
int nSDis[MAX_N];
int nEDis[MAX_N];

struct Node
{
    int nN;
    int nDis;

    bool operator < (const Node& node) const
    {
        return nDis > node.nDis;
    }
};

int ShortestPath(int nS, int nE, int* nDis, int nN)
{
    priority_queue<Node> pq;
    memset(bVisit, false, sizeof(bVisit));
    for (int i = 1; i <= nN; i++)
    {
        nDis[i] = 0x7fffffff;
    }
    nDis[nS] = 0;
    Node head;
    head.nDis = 0, head.nN = nS;
    pq.push(head);

    while (pq.empty() == false)
    {
        Node head = pq.top();
        pq.pop();
        int nU = head.nN;
        if (bVisit[nU]) continue;
        bVisit[nU] = true;

        for (int i = 0; i < graph[nU].size(); ++i)
        {
            int nV = graph[nU][i].nE;
            int nLen = head.nDis + graph[nU][i].nDis;
            if (nLen < nDis[nV])
            {
                nDis[nV] = nLen;
                Node node;
                node.nDis = nLen;
                node.nN = nV;
                pq.push(node);
            }
        }
    }

    return nDis[nE];
}

int Second(int nS, int nE, int nN)
{
    int nShortest = ShortestPath(nS, nE, nSDis, nN);
    ShortestPath(nE, nS, nEDis, nN);

    int nAns = 0x7fffffff;

    for (int i = 1; i <= nN; ++i)
    {
        for (int j = 0; j < graph[i].size(); ++j)
        {
            int nU = i;
            int nV = graph[i][j].nE;
            int nLen = nSDis[i] + graph[i][j].nDis + nEDis[nV];
            if (nLen != nShortest)
            {
                nAns = min(nAns, nLen);
            }
        }
    }

    return nAns;
}

int main()
{
    int nN, nR;
    int nA, nB, nD;

    while (scanf("%d%d", &nN, &nR) == 2)
    {
        for (int i = 1; i <= nN; ++i)
        {
            graph[i].clear();
        }

        while (nR--)
        {
            scanf("%d%d%d", &nA, &nB, &nD);
            graph[nA].push_back(Edge(nB, nD));
            graph[nB].push_back(Edge(nA, nD));
        }
        printf("%d\n", Second(1, nN, nN));
    }

    return 0;
}

posted @ 2012-09-03 22:39 yx 阅读(1426) | 评论 (0) | 编辑收藏

poj 2823 Sliding Window 单调队列

这道题的意思是给定一个长N的整数序列，用一个大小为K的窗口从头开始覆盖，问第1-第N-K次窗口里面最大的数字和最小的数字。
刚开始还以为优先级队列可以做，发现无法删除最前面的元素。估计用线段树这个题也是可以解得。用这个题学了下单调队列。

单调队列正如其名，是一个从小到大排序的队列，而且能够保证所有的元素入队列一次出队列一次，所以平摊到每个元素的复杂度
就是O(1)。
对于这个题单调队列的使用。以序列1 3 -1 -3 5 3 6 7举例。
1）元素类型：一个结构体，包含数字大小和位置，比如(1，1），（3，2）。
2）插入操作：从队尾开始查找，把队尾小于待插入元素的元素全部删除，再加入待插入的元素。这个操作最坏的
情况下是O(n)，但是我们采用聚集分析的方法，知道每个元素最多删除一次，那么N个元素删除N次，平摊到每一次
操作的复杂度就是O(1)了。
3）删除队首元素：比如本文给的那个题，窗口一直往后移动，每一次移动都会删除一个元素，所以很可能队首会是要
删除的元素，那么每次移动窗口的元素要进行一次检查，如果队首元素失效的话，就删掉队首元素。

代码的实现，我是包装deque实现了一个模版类。速度很不好，居然跑了11s多才过，幸亏给了12s的时间，看status又500多ms
就过了的。估计数组实现会快很多。

代码如下：

#include <stdio.h>
#include <deque>
#include <algorithm>
using namespace std;
#define MAX_N (1000000 + 100)
int nNum[MAX_N];
int nN, nK;

struct Small
{
    int nValue;
    int nIndex;
    Small(int nV, int index):nValue(nV), nIndex(index) {}
    bool operator < (const Small& a) const
    {
        return nValue < a.nValue;
    }
};

struct Big
{
    int nValue;
    int nIndex;
    Big(int nV, int index):nValue(nV), nIndex(index) {}
    bool operator < (const Big& a) const
    {
        return nValue > a.nValue;
    }
};

//单调队列
template <typename T> class Monoque
{
    deque<T> dn;

public:
    void Insert(T node)
    {
        int nPos = dn.size() - 1;
        while (nPos >=0 && node < dn[nPos])
        {
            --nPos;
            dn.pop_back();
        }
        dn.push_back(node);
    }

    int Top()
    {
        return dn.front().nValue;
    }

    void Del(int nBeg, int nEnd)
    {
        if (dn.size() > 0)
        {
            if (dn.front().nIndex < nBeg || dn.front().nIndex > nEnd)
            {
                dn.pop_front();
            }
        }
    }
};

int main()
{
    while (scanf("%d%d", &nN, &nK) == 2)
    {
        int i;
        for (i = 0; i < nN; ++i)
        {
            scanf("%d", &nNum[i]);
        }
        Monoque<Small> minQ;
        Monoque<Big> maxQ;

        for (i = 0; i < nK; ++i)
        {
            minQ.Insert(Small(nNum[i], i));
        }

        for (i = 0; i < nN - nK; ++i)
        {
            printf("%d ", minQ.Top());
            minQ.Insert(Small(nNum[i + nK], i + nK));
            minQ.Del(i + 1, i + nK);
        }
        printf("%d\n", minQ.Top());

        for (i = 0; i < nK; ++i)
        {
            maxQ.Insert(Big(nNum[i], i));
        }

        for (i = 0; i < nN - nK; ++i)
        {
            printf("%d ", maxQ.Top());
            maxQ.Insert(Big(nNum[i + nK], i + nK));
            maxQ.Del(i + 1, i + nK);
        }
        printf("%d\n", maxQ.Top());
    }

    return 0;
}

posted @ 2012-09-02 14:25 yx 阅读(1677) | 评论 (2) | 编辑收藏

poj 3093 Margaritas on the River Walk

这是一个动态规划题，据说是背包问题的变形。我动态规划做得很少，解法一直按照算法导论的思想分解重叠子问题。
题意是用钱尽可能多的买物品，每种物品买一个，问有多少种买法。
我也想不出这是什么背包问题的变形，没做过几个背包问题，也没看过背包九讲。还是坚持认为正确的用状态描述成子问题
就一定能解题的。今天和队友在做专题时候做到这个题，我一直做了一上午都没出来。
后面发现了个性质就可以直接转换为类似最简单的背包问题了。排序物品价值，从最大物品开始分解子问题，用剩余物品数
和钱描述问题的状态。当前物品是否必须取，是根据当前的钱把剩下的物品全买了之后剩下的钱还是否大于当前物品的价值，
如果大于就必须买，否则可以买或者不买。
为了正确描述问题的状态，必须事先排序价值数组，因为排序之后可以保证不能买当前物品的时候一定不能买前面的物品，
那么我们对前面物品的处理就是正确的了。至此可以进行最简单的子问题分解了。到最后物品处理完之后（物品数为0），如果钱
一点都没减少，那么(0, M) = 0，否则(0, M) = 1。注意这个边界处理，否则会wa。
所以，需要先对价值数组排序，并计算出表示前N个物品价值和的数组。
做不出来的时候，翻了下别人的解法，一头雾水。看来还是算法导论的思想指导意义大多了。。。

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long INT;
INT nAns[40][1010];
INT nValue[100];
INT nSum[100];
INT nN, nM;

INT GetAns(INT nNum, INT nMoney)
{
    if (nAns[nNum][nMoney] == -1)
    {
        if (nNum == 0)
        {
            nAns[nNum][nMoney] = 1;
            if (nMoney == nM)
            {
                nAns[nNum][nMoney] = 0;
            }
        }
        else
        {
            INT nRet = 0;

            if (nMoney - nSum[nNum - 1] >= nValue[nNum])
            {
                nRet = GetAns(nNum - 1, nMoney - nValue[nNum]);
            }
            else
            {
                if (nMoney >= nValue[nNum])
                {
                    nRet += GetAns(nNum - 1, nMoney - nValue[nNum]);
                }
                nRet += GetAns(nNum - 1, nMoney);
            }

            nAns[nNum][nMoney] = nRet;
        }
    }
    return nAns[nNum][nMoney];
}

int main()
{
    INT nT;

    scanf("%I64d", &nT);
    for (INT i = 1; i <= nT; ++i)
    {
        scanf("%I64d%I64d", &nN, &nM);
        for (INT j = 1; j <= nN; ++j)
        {
            scanf("%I64d", &nValue[j]);
        }
        memset(nAns, -1, sizeof(nAns));
        sort(nValue + 1, nValue + nN + 1);
        nSum[0] = 0;
        for (INT j = 1; j <= nN; ++j)
        {
            nSum[j] = nSum[j - 1] + nValue[j];
        }
        printf("%I64d %I64d\n", i, GetAns(nN, nM));
    }

    return 0;
}

posted @ 2012-08-30 14:11 yx 阅读(1367) | 评论 (0) | 编辑收藏

poj 2065 SETI

题意比较纠结，搜索了把题意。

给你一个素数P(P<=30000)和一串长为n的字符串str[]。字母'*'代表0，字母a-z分别代表1-26，这n个字符所代表的数字分别代表
f(1)、f(2)....f(n)。定义: f (k) = ∑_0<=i<=n-1a_ikⁱ (mod p) (1<=k<=n,0<=ai<P)，求a0、a1.....an-1。题目保证肯定有唯一解。
解题思路：高斯消元。根据上面的公式显然可以列出有n个未知数的n个方程式：

a0*1^0 + a1*1^1+a2*1^2+........+an-1*1^(n-1) = f(1)

a0*2^0 + a1*2^1+a2*2^2+........+an-1*2^(n-1) = f(2)

..............

a0*n^0 + a1*n^1+a2*n^2+........+an-1*n^(n-1) = f(n)

然后采用高斯消元法来解上面的方程组即可。
典型的高斯消元题，只是多了个modP，因此计算过程中可能需要扩展欧几里德算法。

说下所谓的高斯消元的思路，其实可以参看维基百科，

http://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF%E6%B6%88%E5%8E%BB%E6%B3%95，大致过程是一直消变量。
比如刚开始，消第一个变量，消完之后只让第一个方程含有第一个变量，然后消第二个变量，消完之后只让第二个方程含第二个变量，以此
下去让最后的方程含最后一个变量，而且最后一个方程中对于前N-1个变量的系数都是0，这样就能解出这N个变量了。
关于自由元指的是这个变量可以取任何值，得出这样的结论是在消变量的过程中发现该变量的在第row个方程到第N方程中的系数都是0了，
所以可以取任何值。判断无解的方式是，第row+1到第N个方程在高斯消元之后所有的系数必定是0，所以方程的值也必须是0。
求方程的解得过程是从N个解开始逆推，第N-1个方程也就包含2个变量了，第N个变量和第N-1个变量，以此下去，就可以解出方程组了。
具体的可以参照维基百科和代码仔细分析。还有演算法笔记上也有高斯消元的解释。

代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX (70 + 10)

int nMatrix[MAX][MAX];
int nAns[MAX];
void InitMatrix(char* szStr, int nN, int nP)
{
    memset(nMatrix, 0, sizeof(nMatrix));
    for (int i = 0; i < nN; ++i)
    {
        nMatrix[i][nN] = (szStr[i] == '*' ? 0 : szStr[i] - 'a' + 1);
    }
    for (int i = 0; i < nN; ++i)
    {
        int nTemp = 1;
        for (int j = 0; j < nN; ++j)
        {
            nMatrix[i][j] = nTemp;
            nTemp = (nTemp * (i + 1)) % nP;
        }
    }
}

int egcd(int nA, int nB, int& nX, int& nY)
{
    if (nA < nB)swap(nA, nB);
    if (nB == 0)
    {
        nX = 1, nY = 0;
        return nA;
    }
    int nRet = egcd(nB, nA % nB, nX, nY);
    int nT = nX;
    nX = nY;
    nY = nT - (nA / nB) * nY;
    return nRet;
}

int Gauss(int nN, int nP)
{
    int nR, nC;
    for (nR = nC = 0; nR < nN && nC < nN; ++nR, ++nC)
    {
        if (nMatrix[nR][nC] == 0)
        {
            for (int i = nR + 1; i < nN; ++i)
            {
                if (nMatrix[i][nC])
                {
                    for (int j = nC; j <= nN; ++j)
                    {
                        swap(nMatrix[nR][j], nMatrix[i][j]);
                    }
                    break;
                }
            }
        }

        if (nMatrix[nR][nC] == 0)
        {
            nR--;    //自由元
            continue;
        }
        int nA = nMatrix[nR][nC];
        for (int i = nR + 1; i < nN; ++i)
        {
            if (nMatrix[i][nC])
            {
                int nB = nMatrix[i][nC];
                for (int j = nC; j <= nN; ++j)
                {
                    nMatrix[i][j] = (nMatrix[i][j] * nA - nMatrix[nR][j] * nB) % nP;
                }
            }
        }
    }
    for (int i = nR; i < nN; ++i)
    {
        if (nMatrix[i][nN])
        {
            return -1;//无解
        }
    }

    int nX, nY;
    for (int i = nN - 1; i >= 0; i--)
    {
        int nSum = 0;
        for (int j = i + 1; j < nN; ++j)
        {
            nSum = (nSum + nMatrix[i][j] * nAns[j]) % nP;
        }

        nSum = (nMatrix[i][nN] - nSum + nP * nP) % nP;

        egcd(nP, (nMatrix[i][i] + nP) % nP, nX, nY);
        nY = (nY + nP) % nP;
        nAns[i] = (nY * nSum + nP) % nP;//第i个解
    }
    return 1 << (nN - nR);//返回解的个数,本题有唯一解
}

int main()
{
    int nT;

    scanf("%d", &nT);
    while (nT--)
    {
        int nP;
        int nN;
        char szStr[MAX];
        scanf("%d%s", &nP, szStr);
        nN = strlen(szStr);
        InitMatrix(szStr, nN, nP);
        Gauss(nN, nP);
        for (int i = 0; i < nN; ++i)
        {
            printf("%d%s", nAns[i], i == nN - 1 ? "\n" : " ");
        }
    }

    return 0;
}

posted @ 2012-08-06 16:01 yx 阅读(890) | 评论 (0) | 编辑收藏

hdu 4294 Multiple 数论 + bfs

poj 3468 A Simple Problem with Integers 线段树成段延迟更新

poj 2886 Who Gets the Most Candies? 约瑟夫环和反素数

hdu 2492 Ping pong 树状数组

hdu 3584 Cube 三维树状数组

hdu 1556 Color the ball 树状数组

poj 3255 Roadblocks 次短路

poj 2823 Sliding Window 单调队列

poj 3093 Margaritas on the River Walk

poj 2065 SETI

导航

统计

公告

常用链接

留言簿(3)

随笔分类

随笔档案

me

好友

同学

网友

搜索

最新评论

阅读排行榜

评论排行榜