久久久精品久久久久特色影视,久久精品人妻一区二区三区,久久久久久青草大香综合精品

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 閱讀(1372) | 評論 (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 閱讀(1370) | 評論 (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 閱讀(1315) | 評論 (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 閱讀(1276) | 評論 (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 閱讀(1560) | 評論 (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 閱讀(1394) | 評論 (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 閱讀(1507) | 評論 (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 閱讀(1690) | 評論 (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 閱讀(1373) | 評論 (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 閱讀(894) | 評論 (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

好友

同學

網友

搜索

最新評論

閱讀排行榜

評論排行榜