锘??xml version="1.0" encoding="utf-8" standalone="yes"?>久久久久久久综合狠狠综合,国产精品gz久久久,怡红院日本一道日本久久http://www.shnenglu.com/csu-yx-2013/Algorithm Study And So Onzh-cnTue, 06 May 2025 22:52:41 GMTTue, 06 May 2025 22:52:41 GMT60poj 3264 Balanced Lineup St綆楁硶寤虹珛Rmqhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/25/193854.htmlyxyxThu, 25 Oct 2012 11:29:00 GMThttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/25/193854.htmlhttp://www.shnenglu.com/csu-yx-2013/comments/193854.htmlhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/25/193854.html#Feedback0http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193854.htmlhttp://www.shnenglu.com/csu-yx-2013/services/trackbacks/193854.html   
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

const int MAX_I = 50010;
const int MAX_J = 20;

int nMax[MAX_I][MAX_J];
int nMin[MAX_I][MAX_J];
int nArr[MAX_I];
int nN, nQ;

void InitRmq(int nN)
{
    for (int i = 1; i <= nN; ++i)
    {
        nMax[i][0] = nMin[i][0] = nArr[i];
    }
    
    for (int j = 1; (1 << j) <= nN; ++j)
    {
        for (int i = 1; i + (1 << j) - 1 <= nN; ++i)
        {
            nMax[i][j] = max(nMax[i][j - 1],
                             nMax[i + (1 << (j - 1))][j - 1]);
            nMin[i][j] = min(nMin[i][j - 1],
                             nMin[i + (1 << (j - 1))][j - 1]);                
        }
    }
}

int Query(int nA, int nB)
{
    int k = (int)(log(1.0 * nB - nA + 1) / log(2.0));
    int nBig = max(nMax[nA][k], nMax[nB - (1 << k) + 1][k]);
    int nSml = min(nMin[nA][k], nMin[nB - (1 << k) + 1][k]);
    return nBig - nSml;
}

int main()
{
    while (scanf("%d%d", &nN, &nQ) == 2)
    {
        for (int i = 1; i <= nN; ++i)
        {
            scanf("%d", &nArr[i]);
        }
        InitRmq(nN);
        for (int i = 0; i < nQ; ++i)
        {
            int nA, nB;
            scanf("%d%d", &nA, &nB);
            printf("%d\n", Query(nA, nB));
        }
    }
    
    return 0;
}


yx 2012-10-25 19:29 鍙戣〃璇勮
]]>hdu 3068 鏈闀垮洖鏂?Manacher綆楁硶http://www.shnenglu.com/csu-yx-2013/archive/2012/10/24/193807.htmlyxyxWed, 24 Oct 2012 12:55:00 GMThttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/24/193807.htmlhttp://www.shnenglu.com/csu-yx-2013/comments/193807.htmlhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/24/193807.html#Feedback0http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193807.htmlhttp://www.shnenglu.com/csu-yx-2013/services/trackbacks/193807.html   璇ラ璨屼技鍙互鐢ㄥ悗緙鏁扮粍鍜屾墿灞昸mp鍋氾紝浣嗘槸濂藉儚鍚庣紑鏁扮粍璨屼技浼歵le錛屾敼瀛︿簡涓?br />涓涓笓闂ㄧ殑鍙玀anacher綆楁硶鐨勪笢瑗褲傘傘?br />   榪欏張鏄竴涓嚎鎬ф敼鑹畻娉曘傛壘鍒版湁綃囨枃绔犲啓鐨勪笉閿欙紝閾炬帴濡備笅錛?br />http://www.felix021.com/blog/read.php?2040銆?br />   璇ョ畻娉曡璧鋒潵涔熶笉鏄お澶嶆潅錛屾瘮杈冨鏄撶湅鎳傜殑閭ｇ錛屽綋鐒舵槸鎺ヨЕ榪囧叾瀹冨瓧絎︿覆綆楁硶
鐨勫墠鎻愪笅浜嗐傝寰椾互鍓嶅氨鐪嬩簡鐪嬶紝紜槸娌＄湅鎳傦紝鎯充笉鍒扮幇鍦ㄨ繖涔堝揩灝辨槑鐧戒簡銆?br />   璇ョ畻娉曢渶瑕侀澶栫殑O(N)絀洪棿銆傝璧鋒潵鏄┖闂存崲鏃墮棿鍚с?br />   澶ф鐨勬濊礬鏄厛棰勫鐞嗗瓧絎︿覆錛屼嬌鍏舵垚涓轟竴涓暱搴︿竴瀹氫負鍋舵暟鐨勪覆銆傝屼笖絎竴涓瓧絎?br />鏄?$'錛屽亣璁?$'娌℃湁鍦ㄥ師涓插嚭鐜拌繃銆傜劧鍚庡啀鍦ㄥ師鏉ョ殑姣忎釜瀛楃鍓嶉潰鍔犱笂'#'錛屾渶鍚庡啀鍔犱釜
'#'銆傛瘮濡傦紝abc灝卞彉鎴愪簡$#a#b#c#銆傜幇鍦ㄥ啀瀵規柊鐨勫瓧絎︿覆榪涜澶勭悊銆?br />   寮涓涓柊鐨勬暟緇刵Rad[MAX]錛宯Rad[i]琛ㄧず鏂頒覆涓i涓綅緗悜宸﹁竟鍜屽悜鍙寵竟鍚屾椂鎵╁睍
騫朵笖淇濇寔瀵圭О鐨勬渶澶ц窛紱匯傚鏋滄眰鍑轟簡nRad鏁扮粍鍚庯紝鏈変竴涓粨璁猴紝nRad[i]-1鎭板ソ琛ㄧず鍘熶覆
瀵瑰簲鐨勪綅緗兘澶熸墿灞曠殑鍥炴枃瀛愪覆闀垮害銆傝繖涓殑璇佹槑錛屽簲璇ユ瘮杈冪畝鍗曪紝鍥犱負鏂頒覆鍩烘湰涓婃槸鍘熶覆
鐨?鍊嶄簡錛岃屼笖鏂頒覆姣忎竴涓湁鏁堝瓧絎︿袱渚ч兘鏈夋彃鍏ョ殑#錛岃繖涓壘涓緥瀛愮湅涓嬪氨鐭ラ亾鏄繖鏍蜂簡銆?br />   鏈閲嶈鐨勬槸濡備綍姹傚嚭nRad鏁扮粍銆?br />   姹傝繖涓暟緇勭殑綆楁硶涔熶富瑕佹槸鍒╃敤浜嗕竴浜涢棿鎺ョ殑緇撹浼樺寲浜唍Rad[i]鐨勫垵濮嬪寲鍊箋傛瘮濡傛垜浠眰
nRad[i]鐨勬椂鍊欙紝濡傛灉鐭ラ亾浜唅浠ュ墠鐨刵Rad鍊鹼紝鑰屼笖鐭ラ亾浜嗗墠闈㈡湁涓涓綅緗甶d錛岃兘澶熸渶澶х殑鍚?br />涓よ竟鎵╁睍璺濈max銆傞偅涔堟湁涓涓粨璁猴紝nRad[i] 鑳藉鍒濆鍖栦負min(nRad[2*id - i], max - i)錛?br />鐒跺悗鍐嶈繘琛岄掑銆傚叧閿槸濡備綍璇佹槑榪欎釜錛岃繖涓殑璇佹槑錛屽鐓у浘鐗囧氨寰堟竻妤氫簡銆?br />   璇佹槑濡備笅錛?br />   褰?mx - i > P[j] 鐨勬椂鍊欙紝浠[j]涓轟腑蹇冪殑鍥炴枃瀛愪覆鍖呭惈鍦ㄤ互S[id]涓轟腑蹇冪殑鍥炴枃瀛愪覆涓紝鐢變簬 i 鍜?j 瀵圭О錛?br />浠[i]涓轟腑蹇冪殑鍥炴枃瀛愪覆蹇呯劧鍖呭惈鍦ㄤ互S[id]涓轟腑蹇冪殑鍥炴枃瀛愪覆涓紝鎵浠ュ繀鏈?P[i] = P[j]錛岃涓嬪浘銆?br />    
   
   褰?P[j] > mx - i 鐨勬椂鍊欙紝浠[j]涓轟腑蹇冪殑鍥炴枃瀛愪覆涓嶅畬鍏ㄥ寘鍚簬浠[id]涓轟腑蹇冪殑鍥炴枃瀛愪覆涓紝浣嗘槸鍩轟簬
瀵圭О鎬у彲鐭ワ紝涓嬪浘涓袱涓豢妗嗘墍鍖呭洿鐨勯儴鍒嗘槸鐩稿悓鐨勶紝涔熷氨鏄浠[i]涓轟腑蹇冪殑鍥炴枃瀛愪覆錛屽叾鍚戝彸鑷沖皯浼?br />鎵╁紶鍒癿x鐨勪綅緗紝涔熷氨鏄 P[i] >= mx - i銆傝嚦浜巑x涔嬪悗鐨勯儴鍒嗘槸鍚﹀縐幫紝灝卞彧鑳借佽佸疄瀹炲幓鍖歸厤浜嗐?br />   
      榪欎釜灝辮鏄庡緱寰堟竻妤氫簡銆傘傘?br />
      浠ｇ爜濡備笅錛?br />
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAX = 110010 * 2;
char szIn[MAX];
char szOut[MAX];
int nRad[MAX];

int Proc(char* pszIn, char* pszOut)
{
    int nLen = 1;
    
    *pszOut++ = '$';
    while (*pszIn)
    {
        *pszOut++ = '#';
        nLen++;
        *pszOut++ = *pszIn++;
        nLen++;
    }
    *pszOut++ = '#';
    *pszOut = '\0';
    
    return nLen + 1;
}

void Manacher(int* pnRad, char* pszStr, int nN)
{
    int nId = 0, nMax = 0;
    
    //pnRad[0] = 1;
    for (int i = 0; i < nN; ++i)
    {
        if (nMax > i)
        {
            pnRad[i] = min(pnRad[2 * nId - i], nMax - i);
        }
        else pnRad[i] = 1;
        
        while (pszStr[i + pnRad[i]] == pszStr[i - pnRad[i]])
        {
            ++pnRad[i];
        }
        if (pnRad[i] + i > nMax)
        {
            nMax = pnRad[i] + i;
            nId = i;
        }
    }
}

int main()
{
    while (scanf("%s", szIn) == 1)
    {
        int nLen = Proc(szIn, szOut);
        Manacher(nRad, szOut, nLen);
        int nAns = 1;
        for (int i = 0; i < nLen; ++i)
        {
            nAns = max(nRad[i], nAns);
        }
        printf("%d\n", nAns - 1);
    }
    
    return 0;
}


yx 2012-10-24 20:55 鍙戣〃璇勮
]]>poj 3294 Life Forms 鍚庣紑鏁扮粍姹傝嚦灝戝嚭鐜板湪K涓瓧絎︿覆涓殑鏈闀垮叕鍏卞瓙涓?/title><link>http://www.shnenglu.com/csu-yx-2013/archive/2012/10/24/193783.html</link><dc:creator>yx</dc:creator><author>yx</author><pubDate>Wed, 24 Oct 2012 07:57:00 GMT</pubDate><guid>http://www.shnenglu.com/csu-yx-2013/archive/2012/10/24/193783.html</guid><wfw:comment>http://www.shnenglu.com/csu-yx-2013/comments/193783.html</wfw:comment><comments>http://www.shnenglu.com/csu-yx-2013/archive/2012/10/24/193783.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193783.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/csu-yx-2013/services/trackbacks/193783.html</trackback:ping><description><![CDATA[   姝ら灝辨槸緇欏嚭N涓瓧絎︿覆錛岀劧鍚庢眰涓涓渶闀跨殑瀛愪覆錛屽畠鑷沖皯鍑虹幇鍦∟/2+1涓瓧絎︿覆涓紝<br />濡傛灉鏈夊涓繖鏍風殑瀛愪覆錛屾寜瀛楀吀搴忚緭鍑猴紝濡傛灉娌℃湁榪欐牱鐨勫瓙涓詫紝杈撳嚭?銆?br />   姝ら鏄綏絀楅獮璁烘枃閲岄潰鐨勪緥11錛屼粬鏈夎榪板叿浣撶殑瑙ｆ硶銆傝鐢ㄥ悗緙鏁扮粍鍋氳繖鏍風殑棰樼湡涓?br />瀹規槗錛岀敤鍚庣紑鏁扮粍灝辨劅瑙夋槸涓浠墮潪甯哥籂緇撶殑浜嬫儏浜嗐?br />   榪欎釜棰樼殑瑙ｆ硶榪樻槸閭ｇ妯″紡鍖栫殑鎬濊礬銆傛妸N涓瓧絎︿覆榪炴帴鎴愪竴涓紝娉ㄦ剰涓棿鍔犱笉鍑虹幇鍦?br />浠諱綍涓涓瓧絎︿覆涓殑鍒嗛殧絎︼紝鐒跺悗寤虹珛sa鏁扮粍鍜宧eight鏁扮粍絳夈?br />   鏈鍚庝簩鍒嗙瓟妗堬紝鏍規嵁絳旀錛屽嵆瀛愪覆鐨勯暱搴﹀height鏁扮粍榪涜鍒嗙粍錛屽垎緇勭殑鎬濊礬榪樻槸緗楃<br />楠炶鏂囬噷闈緥3鐨勬濊礬錛屽嵆浠庡埌鍚庢灇涓緃eight鏁扮粍錛屾妸榪炵畫澶т簬絳変簬絳旀鐨勫兼斁鍋氫竴緇勶紝<br />涓鏃﹀皬浜庣瓟妗堥偅涔堝氨鏄柊鐨勫垎緇勩傝繖涓闇瑕佹壘鍒頒竴浜涘垎緇勶紝鍏朵腑鐨勫悗緙鏄兘澶熷嚭鐜板湪N涓師<br />涓蹭腑錛岃繖涓垎緇勭殑鍏叡鍓嶇紑灝辨槸sa[i]寮濮嬬殑nMid涓瓧絎︿簡(nMid鏄簩鍒嗘椂鍊欒幏寰楃殑瀛愪覆闀垮害)銆?br />   鐢變簬榪欎釜棰橀渶瑕佹寜瀛楀吀搴忚緭鍑哄涓弧瓚寵姹傜殑瀛愪覆錛屾墍浠ラ夯鐑︿簡鐐廣傞渶瑕佸湪Check鍑芥暟閲岄潰<br />璁板綍榪欎簺瀛愪覆錛岃屼笖杈撳嚭絳旀鐨勬椂鍊欓渶瑕佹帓搴忥紝鍐島nique錛岀敱浜庢槸鎸塰eight鏁扮粍鐨勯『搴忔煡鎵劇殑錛?br />鑰宻a[i]宸茬粡鎺掑ソ搴忎簡錛屾墍浠ユ帓搴忕瓟妗堢殑榪囩▼鍙互鐪佺暐錛屼絾鏄繀欏籾nique銆傛兂涓婥heck鍑芥暟閲岄潰<br />閬嶅巻height鏁扮粍鐨勮繃紼嬪氨鐭ラ亾鍙兘鍑虹幇閲嶅鐨勫瓙涓層傘傘?br /><br />   浠ｇ爜濡備笅錛?br /><div style="background-color: #eeeeee; border: 1px solid #cccccc; padding: 4px 5px 4px 4px; width: 98%; word-break: break-all; "><div>#include <stdio.h></div><div>#include <string.h></div><div>#include <algorithm></div><div>using namespace std;</div><div></div><div>const int MAX_N = 110;</div><div>const int MAX_L = 1010;</div><div>const int MAX = MAX_N * MAX_L;</div><div></div><div>int nAns;</div><div>char szStr[MAX_L];</div><div>char szAns[MAX][MAX_L];</div><div>char* pszAns[MAX];</div><div>int nNum[MAX];</div><div>int nLoc[MAX];</div><div>bool bVis[MAX_N];</div><div>int sa[MAX], rank[MAX], height[MAX];</div><div>int wa[MAX], wb[MAX], wv[MAX], wd[MAX];</div><div></div><div>bool CmpStr(const char* pszOne, const char* pszTwo)</div><div>{</div><div>    return strcmp(pszOne, pszTwo) < 0;</div><div>}</div><div></div><div>bool EqualStr(const char* pszOne, const char* pszTwo)</div><div>{</div><div>    return strcmp(pszOne, pszTwo) == 0;</div><div>}</div><div></div><div>int cmp(int* r, int a, int b, int l)</div><div>{</div><div>    return r[a] == r[b] && r[a + l] == r[b + l];</div><div>}</div><div></div><div>//鍊嶅綆楁硶,r涓哄緟鍖歸厤鏁扮粍,n涓烘婚暱搴?m涓哄瓧絎︿覆鑼冨洿</div><div>void da(int* r, int n, int m)</div><div>{</div><div>    int i, j, p, *x = wa, *y = wb;</div><div>    </div><div>    for (i = 0; i < m; ++i) wd[i] = 0;</div><div>    for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;</div><div>    for (i = 1; i < m; ++i) wd[i] += wd[i - 1];</div><div>    for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;</div><div>    </div><div>    for (j = 1, p = 1; p < n; j *= 2, m = p)</div><div>    {</div><div>        for (p = 0, i = n - j; i < n; ++i) y[p++] = i;</div><div>        for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;</div><div>        </div><div>        for (i = 0; i < n; ++i) wv[i] = x[y[i]];</div><div>        for (i = 0; i < m; ++i) wd[i] = 0;</div><div>        for (i = 0; i < n; ++i) wd[wv[i]]++;</div><div>        for (i = 1; i < m; ++i) wd[i] += wd[i - 1];</div><div>        for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];</div><div>        </div><div>        swap(x, y);</div><div>        for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)</div><div>        {</div><div>            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;</div><div>        }</div><div>    }</div><div>}</div><div></div><div>//姹俬eight鏁扮粍</div><div>void calHeight(int* r, int n)</div><div>{</div><div>    int i, j, k = 0;</div><div>    for (i = 1; i <= n; ++i) rank[sa[i]] = i;</div><div>    for (i = 0; i < n; height[rank[i++]] = k)</div><div>    {</div><div>        if (k) --k;</div><div>        for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);</div><div>    }</div><div>}</div><div></div><div>bool Check(int nMid, int nN, int nK)</div><div>{</div><div>    int nCnt = 0;</div><div>    int nNo = 0;</div><div>    </div><div>    memset(bVis, false, sizeof(bVis));</div><div>    for (int i = 1; i <= nN; ++i)</div><div>    {</div><div>        if (height[i] < nMid)</div><div>        {</div><div>            nCnt = 0;</div><div>            memset(bVis, false, sizeof(bVis));</div><div>        }</div><div>        else</div><div>        {</div><div>            if (!bVis[nLoc[sa[i - 1]]])</div><div>            {</div><div>                ++nCnt;</div><div>                bVis[nLoc[sa[i - 1]]] = true;</div><div>            }</div><div>            if (!bVis[nLoc[sa[i]]])</div><div>            {</div><div>                ++nCnt;</div><div>                bVis[nLoc[sa[i]]] = true;</div><div>            }</div><div>            if (nCnt == nK)</div><div>            {</div><div>                for (int j = 0; j < nMid; ++j)</div><div>                {</div><div>                    szAns[nNo][j] = nNum[sa[i] + j];</div><div>                }</div><div>                szAns[nNo][nMid] = 0;</div><div>                ++nNo;</div><div>                nCnt = 0;</div><div>            }</div><div>        }</div><div>    }</div><div>    </div><div>    if (nNo > 0) nAns = nNo;</div><div>    return nNo > 0;</div><div>}</div><div></div><div>int main()</div><div>{</div><div>    int nN;</div><div>    bool bFirst = true;</div><div>    </div><div>    while (scanf("%d", &nN), nN)</div><div>    {</div><div>        if (bFirst) bFirst = false;</div><div>        else putchar('\n');</div><div>        </div><div>        int nEnd = 300;</div><div>        int nP = 0;</div><div>        for (int i = 0; i < nN; ++i)</div><div>        {</div><div>            scanf("%s", szStr);</div><div>            int nLen = strlen(szStr);</div><div>            for (int j = 0; j < nLen; ++j)</div><div>            {</div><div>                nNum[nP] = szStr[j];</div><div>                nLoc[nP++] = i;</div><div>            }</div><div>            nNum[nP] = nEnd;</div><div>            nLoc[nP++] = nEnd++;</div><div>        }</div><div>        nNum[nP] = 0;</div><div>        </div><div>        if (nN == 1)</div><div>        {</div><div>            printf("%s\n\n", szStr);</div><div>            continue;</div><div>        }</div><div>        da(nNum, nP + 1, 500);//500鏄及璁＄殑瀛楃闆嗗ぇ灝?/div><div>        calHeight(nNum, nP);</div><div>        </div><div>        int nLeft = 1, nRight = strlen(szStr);</div><div>        int nTemp = 0, nMid;</div><div>        int nK = nN / 2 + 1;</div><div>        nAns = 0;</div><div>        while (nLeft <= nRight)</div><div>        {</div><div>            nMid = (nLeft + nRight) >> 1;</div><div>            if (Check(nMid, nP, nK))</div><div>            {</div><div>                nTemp = nMid;</div><div>                nLeft = nMid + 1;</div><div>            }</div><div>            else nRight = nMid - 1;</div><div>        }</div><div>        if (nTemp == 0)</div><div>        {</div><div>            printf("?\n");</div><div>        }</div><div>        else</div><div>        {</div><div>            for (int i = 0; i < nAns; ++i)</div><div>            {</div><div>                pszAns[i] = szAns[i];</div><div>            }</div><div>            //sort(pszAns, pszAns + nAns, CmpStr);</div><div>            nAns = unique(pszAns, pszAns + nAns, EqualStr) - pszAns;</div><div>            for (int i = 0; i < nAns; ++i)</div><div>            {</div><div>                printf("%s\n", pszAns[i]);</div><div>            }</div><div>        }</div><div>    }</div><div>    </div><div>    return 0;</div><div>}</div><div style="font-size: 13px; "></div></div><img src ="http://www.shnenglu.com/csu-yx-2013/aggbug/193783.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/csu-yx-2013/" target="_blank">yx</a> 2012-10-24 15:57 <a href="http://www.shnenglu.com/csu-yx-2013/archive/2012/10/24/193783.html#Feedback" target="_blank" style="text-decoration:none;">鍙戣〃璇勮</a></div>]]></description></item><item><title>poj 1226 Substrings 鍚庣紑鏁扮粍http://www.shnenglu.com/csu-yx-2013/archive/2012/10/23/193741.htmlyxyxTue, 23 Oct 2012 13:11:00 GMThttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/23/193741.htmlhttp://www.shnenglu.com/csu-yx-2013/comments/193741.htmlhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/23/193741.html#Feedback0http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193741.htmlhttp://www.shnenglu.com/csu-yx-2013/services/trackbacks/193741.html鍒濆鍚庣紑鏁扮粍錛屾湁寰堝涓嶆槑鐧界殑涓滆タ錛屾棰樺悗緙鏁扮粍鐨勪唬鐮佸湪緗戜笂涔熸槸涓鎶婃姄銆?br />   璇村疄璇濇垜紜疄榪樹笉鎳傚悗緙鏁扮粍錛屼絾鏄悗緙鏁扮粍澶己澶т簡錛屽彧鑳界‖鐫澶寸毊鐓х潃钁姦鐢葷摙浜嗐?br />璐翠笅浠ｇ爜鏂逛究浠ュ悗鏌ラ槄鍚с傘傘?br />   鎰熻鍚庣紑鏁扮粍鐨勫簲鐢ㄦ渶涓昏鐨勮繕鏄痟eight鏁扮粍錛岀湅鎳傚嶅綆楁硶鎺掑簭鍚庣紑宸茬粡闈炲父鍥伴毦浜嗐?br />鐒跺悗鍐嶇悊瑙eight鏁扮粍鎬庝箞鐢ㄤ篃涓嶆槸涓浠跺鏄撶殑浜嬫儏銆傜劧鍚庤矊浼糷eight鏁扮粍鏈鍏抽敭鐨勭敤娉曟槸
鏋氫婦鏌愪竴涓暱搴︾殑瀛愪覆鏃跺欙紝姣斿闀垮害涓簁錛岃兘澶熺敤榪欎釜k瀵筯eight鏁扮粍榪涜鍒嗙粍錛岃繖涓綏絀楅獮
鐨勮鏂囬噷闈㈡湁涓眰涓嶉噸鍙犳渶闀塊噸澶嶅瓙涓茬殑渚嬪瓙璇存槑浜嗚繖涓猦eight鏁扮粍鍒嗙粍鐨勬濊礬錛屼笉榪囨垜鐜板湪
榪樻槸涓嶆庝箞鐞嗚В銆傘傘?br />  
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

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

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

//鍊嶅綆楁硶,r涓哄緟鍖歸厤鏁扮粍,n涓烘婚暱搴?m涓哄瓧絎︿覆鑼冨洿
void da(int* r, int n, int m)
{
    int i, j, p, *x = wa, *y = wb;
    
    for (i = 0; i < m; ++i) wd[i] = 0;
    for (i = 0; i < n; ++i) wd[x[i] = r[i]]++;
    for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
    for (i = n - 1; i >= 0; --i) sa[--wd[x[i]]] = i;
    
    for (j = 1, p = 1; p < n; j *= 2, m = p)
    {
        for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
        for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
        
        for (i = 0; i < n; ++i) wv[i] = x[y[i]];
        for (i = 0; i < m; ++i) wd[i] = 0;
        for (i = 0; i < n; ++i) wd[wv[i]]++;
        for (i = 1; i < m; ++i) wd[i] += wd[i - 1];
        for (i = n - 1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];
        
        swap(x, y);
        for (p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
        {
            x[sa[i]] = cmp(y, sa[i - 1], sa[i], j)? p - 1 : p++;
        }
    }
}

//姹俬eight鏁扮粍
void calHeight(int* r, int n)
{
    int i, j, k = 0;
    for (i = 1; i <= n; ++i) rank[sa[i]] = i;
    for (i = 0; i < n; height[rank[i++]] = k)
    {
        if (k) --k;
        for(j = sa[rank[i] - 1]; r[i + k] == r[j + k]; k++);
    }
}

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

int main()
{
    int nT;
    
    scanf("%d", &nT);
    while (nT--)
    {
        int nN;
        int nEnd = 300;
        int nP = 0;
        scanf("%d", &nN);
        for (int i = 1; i <= nN; ++i)
        {
            scanf("%s", szStr);
            char* pszStr;
            for (pszStr = szStr; *pszStr; ++pszStr)
            {
                nLoc[nP] = i;
                nNum[nP++] = *pszStr;
            }
            nLoc[nP] = nEnd;
            nNum[nP++] = nEnd++;
            
            reverse(szStr, szStr + strlen(szStr));
            for (pszStr = szStr; *pszStr; ++pszStr)
            {
                nLoc[nP] = i;
                nNum[nP++] = *pszStr;
            }
            nLoc[nP] = nEnd;
            nNum[nP++] = nEnd++;
        }
        nNum[nP] = 0;
        
        da(nNum, nP + 1, nEnd);
        calHeight(nNum, nP);
        
        int nLeft = 1, nRight = strlen(szStr), nMid;
        int nAns = 0;
        while (nLeft <= nRight)
        {
            nMid = (nLeft + nRight) / 2;
            if (Check(nMid, nP, nN))
            {
                nLeft = nMid + 1;
                nAns = nMid;
            }
            else nRight = nMid - 1;
        }
        printf("%d\n", nAns);
    }
    
    return 0;
}


yx 2012-10-23 21:11 鍙戣〃璇勮
]]>poj 3691 DNA repair AC鑷姩鏈?+ dphttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/21/193619.htmlyxyxSun, 21 Oct 2012 08:53:00 GMThttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/21/193619.htmlhttp://www.shnenglu.com/csu-yx-2013/comments/193619.htmlhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/21/193619.html#Feedback0http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193619.htmlhttp://www.shnenglu.com/csu-yx-2013/services/trackbacks/193619.html鍙互浣挎枃鏈覆涓嶅寘鍚換浣曚竴涓ā寮忎覆銆?br />   榪樻槸鍏堝緩绔婽rie鍥撅紝鐒跺悗鍦═rie鍥句笂闈㈣繘琛宒p銆俤p鐨勬濊礬涔熶笉鏄緢澶嶆潅銆俤p[i][j]鐨勬剰鎬?br />鏄暱搴︿負i鐨勬枃鏈覆闇瑕佹敼鍙榙p[i][j]涓瓧絎﹂『鍒╁埌杈劇姸鎬乯銆傞渶瑕佹敞鎰忕殑鏄暱搴︿負i鐨勬椂鍊欙紝
瀵瑰簲鐨勫瓧絎︿覆涓殑絎琲-1涓瓧絎︺傚垰寮濮嬩竴鐩存病鍙戠幇榪欎釜bug銆傝屼笖娉ㄦ剰涓斾笉鑳借漿縐誨埌
鍖歸厤鎴愬姛鐨勭姸鎬佷笂鍘伙紝澶氬姞鍑犱釜鏉′歡鎺у埗鍗沖彲浜嗐傘傘?br />   杞Щ鏂圭▼錛宒p[i][j] = min(dp[i][j], dp[i-1][nNext] + szText[i-1] != k)錛屽叾涓璶Next
鏄粠鐘舵乯鍙互杞Щ鍒扮殑闈炲尮閰嶆垚鍔熺殑鐘舵侊紝k浠ｈ〃鐨勫綋鍓嶈竟鐨勬潈銆?br />   
   浠ｇ爜濡備笅錛?br />
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

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

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

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

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

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

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

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

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

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

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

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

    int i, j, k;
    nChange[0][0] = 0;
    for (i = 1; i <= nLen; ++i)
    {
        for (j = 0; j < nP; ++j)
        {
            if (tries[j].flag) continue;
            if (nChange[i - 1][j] == INF) continue;
            for (k = 0; k < MAX_D; ++k)
            {
                int nNext = tries[j].next[k] - tries;
                if (tries[nNext].flag) continue;
                //trie鏄竟鏉冩爲,鎵浠鏄粠1鍒發en,鑰屼笖褰撳墠瀛楃鏄痵zText[i-1]
                int nTemp = nChange[i - 1][j] + (k != chHash[szText[i - 1]]);
                nChange[i][nNext] = min(nChange[i][nNext], nTemp);
            }
        }
    }

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

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

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

    return 0;
}


yx 2012-10-21 16:53 鍙戣〃璇勮
]]>poj 1625 Censored! AC鑷姩鏈?+ DP + 澶ф暟鍔犳硶http://www.shnenglu.com/csu-yx-2013/archive/2012/10/20/193579.htmlyxyxSat, 20 Oct 2012 13:01:00 GMThttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/20/193579.htmlhttp://www.shnenglu.com/csu-yx-2013/comments/193579.htmlhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/20/193579.html#Feedback0http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193579.htmlhttp://www.shnenglu.com/csu-yx-2013/services/trackbacks/193579.html鑰屼笖鏂囨湰涓蹭笉澶暱銆傞棶棰樻槸涓嶅彇妯＄殑璇濆氨鍙兘杈撳嚭瀹為檯鐨勭瓟妗堜簡錛屽氨鍙兘鐢ㄥぇ鏁頒簡銆?br />   鑰屼笖鐢ㄥぇ鏁扮殑璇濓紝鍐嶇敤鐭╅樀鍐ュ彲鑳藉氨浼氳秴鏃朵箣綾葷殑銆?br />   榪欑被棰樿繕鍙互鐢ㄩ櫎鐭╅樀鍐ュ鐨勫彟澶栦竴縐嶈В娉曪紝灝辨槸鐩存帴dp鍗沖彲銆?br />   浜岀淮鐘舵侊紝絎竴緇翠唬琛ㄦ枃鏈覆闀垮害錛岀浜岀淮浠ｈ〃鍦ˋC鑷姩鏈轟腑鐨勭姸鎬併?br />   姣斿dp[i][j]浠ｈ〃闀垮害涓篿鐨勬枃鏈覆錛岃漿縐誨埌Trie鍥句腑鑺傜偣j鏃跺欐弧瓚充笉鍖呭惈浠諱綍妯″紡涓茬殑絳旀銆?br />鍓╀笅鐨勬槸濡備綍杞Щ鐘舵併傝漿縐葷殑璇濅篃鏄冭檻next鎸囬拡鏁扮粍錛岃next = tries[j].next[k]錛?br />閭ｄ箞鏈塪p[i+1][next] = dp[i+1][next] + dp[i][j]錛屼粠0鍒板瓧姣嶉泦鍚堝ぇ灝廚鏋氫婦k鍗沖彲銆?br />   榪欎釜棰樻湁涓涓槗閿欑殑鍦版柟錛屽氨鏄瓧姣嶉泦鍚堝彲鑳芥槸ascii鐮佸湪128鍒?56鐨勮寖鍥村唴銆傝宑har
鐨勮寖鍥村彲鑳芥槸-128鍒?27鎴栬?鍒?55錛岃繖涓槸鏍規嵁緙栬瘧鍣ㄤ笉鍚岀殑銆傛墍浠ワ紝鐩存帴鐢ㄥ瓧絎︿覆
鏁扮粍璇誨叆鏁版嵁鍚庨渶瑕佸啀澶勭悊涓嬨傚彲浠ョ洿鎺ュ皢姣忎釜瀛楃鍔?28鍚庡啀澶勭悊銆?br />   鍙﹀錛実etchar榪斿洖鐨勬槸int錛屼絾鏄笌gets涔嬬被鐨勫嚱鏁拌幏寰楃殑鍊肩殑宸埆涔熶笉鏄偅涔堢‘瀹氱殑浜嗐?br />鎴戣寰梘etchar闄や簡瀵筫of涔嬪鍏朵綑閮借繑鍥炴鍊箋備絾鏄紝濡傛灉char鏄湁絎﹀彿鐨勮瘽錛宻canf鎴栬?br />gets涔嬬被寰楀埌鐨刢har鏁扮粍閲岄潰鍙兘灝卞寘鍚礋鍊間簡銆傘傘?br />   榪欎釜鍙互鐢熸垚闅忔満鏂囦歡錛屽啀鐢╣etchar璇誨叆騫剁敤%d杈撳嚭鍏惰繑鍥炲奸獙璇佷笅銆傞獙璇佺▼搴忓涓嬶細
娉ㄩ噴鎺夌殑閮ㄥ垎鏄敓鎴愰殢鏈烘枃浠剁殑閮ㄥ垎銆?br />
#include <stdio.h>
#include <stdlib.h>

int main()
{
    char ch;
    freopen("in.txt", "r", stdin);
    //freopen("in.txt", "w", stdout);
    int nNum = 100;
    int nCh;
    do
    {
        printf("%d\n", nCh = getchar());
    }while (nCh != EOF);
    /*while (nNum--)
    {
        putchar(rand() % 256);
    }*/
    
    return 0;
}
   
   璇ラ鐨勪唬鐮佸涓嬶細
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

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

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

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

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

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

const int MAX_L = 200;
struct BigInt
{
    int nD[MAX_L];
    BigInt()
    {
        Clear();
    }
    void Clear()
    {
        memset(nD, 0, sizeof(nD));
    }
    
    void Print()
    {
        int i = MAX_L - 1;
        while (!nD[i] && i)--i;
        while (i >= 0)
        {
            putchar(nD[i] + '0');
            --i;
        }
    }
    int operator[](int idx) const
    {
        return nD[idx];
    }
    
    int& operator[](int idx)
    {
        return nD[idx];
    }
};
BigInt bi[MAX_M][MAX_D];

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

void Solve()
{
    BigInt ans;
    for (int i = 0; i <= nM; ++i)
    {
        for (int j = 0; j < nP; ++j)
        {
            bi[i][j].Clear();
        }
    }
    bi[0][0][0] = 1;
    
    for (int i = 1; i <= nM; ++i)
    {
        for (int j = 0; j < nP; ++j)
        {
            if (tries[j].flag) continue;
            for (int k = 0; k < nN; ++k)
            {
                int nNext = tries[j].next[k] - tries;
                if (tries[nNext].flag == false)
                {
                    bi[i][nNext] = bi[i][nNext] + bi[i - 1][j];
                }
            }
        }
    }
    
    for (int i = 0; i < nP; ++i)
    {
        ans = ans + bi[nM][i];
    }
    ans.Print();
    printf("\n");
}

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


yx 2012-10-20 21:01 鍙戣〃璇勮
]]>poj 1509 Glass Beads 瀛楃涓叉渶灝忚〃紺?/title><link>http://www.shnenglu.com/csu-yx-2013/archive/2012/10/19/193541.html</link><dc:creator>yx</dc:creator><author>yx</author><pubDate>Fri, 19 Oct 2012 11:44:00 GMT</pubDate><guid>http://www.shnenglu.com/csu-yx-2013/archive/2012/10/19/193541.html</guid><wfw:comment>http://www.shnenglu.com/csu-yx-2013/comments/193541.html</wfw:comment><comments>http://www.shnenglu.com/csu-yx-2013/archive/2012/10/19/193541.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193541.html</wfw:commentRss><trackback:ping>http://www.shnenglu.com/csu-yx-2013/services/trackbacks/193541.html</trackback:ping><description><![CDATA[   璧よ８瑁哥殑瀛楃涓叉渶灝忚〃紺洪銆傛墍璋撳瓧絎︿覆鏈灝忚〃紺烘寚鐨勬槸緇欏畾涓涓瓧絎︿覆錛屽亣璁懼叾鍙互寰幆縐?br />浣嶏紝闂驚鐜乏縐誨灝戜綅鑳藉寰楀埌鏈灝忕殑瀛楃涓層?br />   綆楁硶鍗蟲槸鍛ㄦ簮鐨勬渶灝忚〃紺烘硶錛屾悳绱㈠彲浠ユ壘鍒扮浉鍏寵鏂囧拰ppt銆?br />   璇ョ畻娉曞叾瀹炰篃涓嶆槸澶鏉傦紝鎬濊礬鍙互榪欐牱鐞嗚В銆傚亣璁懼師瀛楃涓蹭負s錛岃s1 = s + s; s2 = s1寰?br />鐜乏縐?浣?鐜板湪澶勭悊s1鍜宻2錛屽疄闄呭啓紼嬪簭鐨勬椂鍊欏彲浠ラ氳繃涓嬫爣鍋忕Щ鍜屽彇妯″緱鍒皊1鍜宻2錛岃屽茍涓嶉渶<br />瑕佺敓鎴愩?br />   澶勭悊榪囩▼鏄繖鏍風殑錛岃i鍜宩鍒嗗埆鎸囧悜s1鍜宻2鐨勫紑澶淬傛垜浠殑鐩殑鏄壘鍒拌繖鏍風殑i鍜宩錛屽亣璁緆鏄痵鐨?br />闀垮害錛屾弧瓚蟲潯浠秙1[i,i+k-1] = s2[j,j+k-1] 騫朵笖s1[i,i+k-1] 鏄墍鏈夋弧瓚蟲潯浠剁殑瀛楃涓蹭腑鏈灝忕殑<br />瀛楃涓詫紝濡傛灉鏈夊涓繖鏍風殑s1[i,i+k-1] 閭ｄ箞鎴戜滑甯屾湜i鏈灝忋?br />   鍏跺疄榪欎釜綆楁硶涓昏鏄仛浜嗕竴涓紭鍖栵紝浠庤屾妸鏃墮棿鎼炴垚綰挎х殑銆傛瘮濡傦紝瀵逛簬褰撳墠鐨刬鍜宩錛屾垜浠竴鐩?br />榪涜鍖歸厤錛屼篃灝辨槸s1[i,i+k] = s2[j,j+k] 涓鐩存弧瓚籌紝紿佺劧鍒頒簡涓涓綅緗畇1[i+k]  != s2[j+k]浜嗭紝<br />鐜板湪鎴戜滑闇瑕佹敼鍙榠鍜宩浜嗐備絾鏄紝鎴戜滑涓嶈兘鍙槸++i鎴栬?+j銆傝屾槸鏍規嵁s1[i+k]>s2[j+k]鐨勮瘽i = <br />i + k + 1錛屽惁鍒檍 = j + k + 1銆傝繖鏍風殑鐬Щi鎴栬卝灝辮兘澶熶繚璇佸鏉傚害鏄嚎鎬х殑浜嗐?br />   闂鏄浣曡瘉鏄庡彲浠ヨ繖鏍風殑鐬Щ銆傚叾瀹烇紝璇寸┛浜嗕篃寰堢畝鍗曘傚洜涓簊1[i,i+k - 1] = s2[j,j+k -1]<br />鏄弧瓚崇殑錛屽彧鏄埌浜唖1[i+k]鍜宻2[j+k]鎵嶅嚭鐜伴棶棰樹簡銆傚亣濡俿1[i+k]>s2[j+k]錛岄偅涔堟垜浠敼鍙榠涓?br />鍖洪棿[i+1,i+k]涓換浣曚竴涓糾閮戒笉鍙兘寰楀埌鎴戜滑鎯寵鐨勭瓟妗堬紝榪欐槸鍥犱負鎴戜滑鎬誨彲浠ュ湪s2涓壘鍒扮浉搴?br />鐨勬瘮s1[m,m+k-1]灝忕殑瀛楃涓瞫2[j+m-i,j+m-i+k-1]錛屽洜涓烘湁s1[i+k]>s2[j+k]銆?br />   鍚屾牱瀵逛簬s1[i+k]<s2[j+k]鐨勬儏鍐點?br />   鏂囧瓧鍙兘鎻忚堪鐨勪笉鏄緢娓呮銆傜湅PPT鑳藉鏍規嵁鍥捐繘琛屽垎鏋愩?br /><br />   浠ｇ爜濡備笅錛?br /><div style="background-color:#eeeeee;font-size:13px;border:1px solid #CCCCCC;padding-right: 5px;padding-bottom: 4px;padding-left: 4px;padding-top: 4px;width: 98%;word-break:break-all"><!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->#include <stdio.h><br />#include <stdlib.h><br />#include <<span style="color: #0000FF; ">string</span>.h><br />#include <algorithm><br />#include <<span style="color: #0000FF; ">string</span>><br />#include <iostream><br /><span style="color: #0000FF; ">using</span> <span style="color: #0000FF; ">namespace</span> std;<br /><br /><span style="color: #0000FF; ">int</span> GetMin(<span style="color: #0000FF; ">string</span>& str)<br />{<br />    <span style="color: #0000FF; ">int</span> nSize = str.size();<br />    <span style="color: #0000FF; ">int</span> i = 0, j = 1, k = 0;<br />    <br />    <span style="color: #0000FF; ">while</span> (i < nSize && j < nSize && k < nSize)<br />    {<br />        <span style="color: #0000FF; ">char</span> chDif = str[(i + k) % nSize]<br />                    - str[(j + k) % nSize];<br />        <span style="color: #0000FF; ">if</span> (!chDif) ++k;<br />        <span style="color: #0000FF; ">else</span><br />        {<br />            <span style="color: #0000FF; ">if</span> (chDif > 0) i = i + k + 1;<br />            <span style="color: #0000FF; ">else</span> j = j + k + 1;<br />            <span style="color: #0000FF; ">if</span> (i == j) ++j;<br />            k = 0;<br />        }<br />    }<br />    <span style="color: #0000FF; ">return</span> min(i, j);<br />}<br /><br /><span style="color: #0000FF; ">int</span> main()<br />{<br />    <span style="color: #0000FF; ">string</span> str;<br />    <span style="color: #0000FF; ">int</span> nN;<br />    <br />    scanf("%d", &nN);<br />    <span style="color: #0000FF; ">while</span> (nN--)<br />    {<br />        cin >> str;<br />        printf("%d\n", GetMin(str) + 1);<br />    }<br />    <br />    <span style="color: #0000FF; ">return</span> 0;<br />}</div><img src ="http://www.shnenglu.com/csu-yx-2013/aggbug/193541.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.shnenglu.com/csu-yx-2013/" target="_blank">yx</a> 2012-10-19 19:44 <a href="http://www.shnenglu.com/csu-yx-2013/archive/2012/10/19/193541.html#Feedback" target="_blank" style="text-decoration:none;">鍙戣〃璇勮</a></div>]]></description></item><item><title>hnu 2243 鑰冪爺璺尗鑼斺斿崟璇嶆儏緇?AC鑷姩鏈?鐭╅樀鍐ョ瘡鍔犲拰http://www.shnenglu.com/csu-yx-2013/archive/2012/10/18/193489.htmlyxyxThu, 18 Oct 2012 14:02:00 GMThttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/18/193489.htmlhttp://www.shnenglu.com/csu-yx-2013/comments/193489.htmlhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/18/193489.html#Feedback0http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193489.htmlhttp://www.shnenglu.com/csu-yx-2013/services/trackbacks/193489.html   棰樻剰鏄粰瀹歁涓ā寮忎覆錛岀劧鍚庣粰瀹氶暱搴錛岄棶涓嶈秴榪嘗鐨勬枃鏈嚦灝戝惈鏈変竴涓ā寮忕殑鎯呭喌鐨勬葷鏁般?br />
   榪樻槸鐢ㄦā寮忎覆寤虹珛Trie鍥撅紝鏍規嵁Trie鍥懼緩绔嬭搗璺緞闀垮害涓?鐨勭煩闃礛銆?br />   鎬繪儏鍐墊暟鐩負26^1+26^2+...+26^L銆備笉鍚ā寮忎覆鐨勬儏鍐墊繪暟涓虹煩闃礜 = M^1+M^2+M^3
+...+M^L鐨勭涓琛屼箣鍜屻傛繪儏鍐墊暟鐩噺鍘諱笉鍚ā寮忎覆鐨勬儏鍐靛氨鏄瓟妗堛?br />   榪欓噷鐢ㄥ埌浜嗙煩闃電殑涓浜涚畻娉曪紝姣斿蹇熷啣錛岃繕鏈夊揩閫熷啣姹傚拰銆備絾鏄紝鎴戠敤浜嗘搷浣滅閲嶈澆錛屾渶鎮插墽
鐨勬槸閲嶈澆鍚庣殑鎿嶄綔絎︽病鏈変紭鍏堢駭錛岃屾垜榪樺綋浣滄湁浼樺厛綰х殑鍦ㄧ敤錛屾墍浠ユ偛鍓т簡銆傘傘備竴鐩存牱渚嬮兘榪囦笉
鍘匯傘傘傚攭錛屾渶鍚庢墠鍙戠幇浜嗚繖涓棶棰樸傘傘傚啓浜?60琛屽乏鍙崇殑浠ｇ爜錛屽墠闈㈢殑涓閮ㄥ垎浠ｇ爜鍙互褰撲綔鐭?br />闃墊搷浣滅殑妯℃澘浜嗐傘傘俆rie鍥劇殑涔熶笉閿欙紝榪囧嚑澶╀及璁″緱鎵撳嵃涓嬫潵鐢ㄤ簡銆傘傘?br />
   浠ｇ爜濡備笅錛?br />
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;

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

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

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

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

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

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

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

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

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

    Matrix ans = SumPowMatrix(base, nN / 2);
    ans = ans + ((base^(nN / 2)) * ans);//閲嶈澆榪愮畻絎︿繚璇佷笉浜嗕紭鍏堢駭
    if (nN % 2)
    {
        ans = ans + (base^nN);//娌′紭鍏堢駭鍟?蹇呴』鍔犳嫭鍙?鏌ラ敊2涓皬鏃朵簡
    }
    return ans;
}

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

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

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

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

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

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

            //榪欓噷蹇呴』瑕佸姞涓奻ront->flag涓篺alse鐨勫垽鏂箞?鍔犱笉鍔犱細鐢熸垚涓嶅悓鐨勭煩闃?/span>
            if (!front->next[i]->flag)
            {
                ++M.nD[front->no][front->next[i]->no];
            }
        }
    }
}

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

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

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

    return 0;
}


yx 2012-10-18 22:02 鍙戣〃璇勮
]]>poj 2778 DNA Sequence AC鑷姩鏈?鐭╅樀蹇熷啣http://www.shnenglu.com/csu-yx-2013/archive/2012/10/18/193454.htmlyxyxThu, 18 Oct 2012 01:46:00 GMThttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/18/193454.htmlhttp://www.shnenglu.com/csu-yx-2013/comments/193454.htmlhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/18/193454.html#Feedback0http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193454.htmlhttp://www.shnenglu.com/csu-yx-2013/services/trackbacks/193454.html涓茬殑鍙兘鎬у埌搴曟湁澶氬皯縐嶃傘傘?br />   紜疄闈炲父涓嶇洿瑙傜殑鏍峰瓙銆傘傘?br />   瑙ｆ硶鏄厛瀛﹀AC鑷姩鏈猴紝寤虹珛璧稵rie鍥撅紝鏍規嵁trie鍥懼彲浠ュ緱鍒伴暱搴︿負1鐨勮礬寰勭煩闃碉紝鐒跺悗鍐嶅揩閫?br />鍐ュ緱鍒伴暱搴︿負N鐨勮礬寰勭煩闃點?br />   璇磋搗鏉ラ兘闈炲父綰犵粨錛屾病瀛﹁繃AC鑷姩鏈烘洿鍔犳棤娉曠悊瑙ｃ傚AC鑷姩鏈轟箣鍓嶆嵁璇村緱鍏堝Trie鏍戝拰KMP
鎵嶅ソ鐞嗚В銆傚AC鑷姩鏈烘悶Trie鍥懼氨鑺辮垂浜嗚繎2澶╀簡錛岀劧鍚庡紕鎳傝繖涓鍙堟槸涓澶╋紝濂藉湪鍩烘湰鏄庣櫧浜嗐?br />   椹笂蹇瘮璧涗簡錛屼粠闀挎槬鎹㈠埌閲戝崕涔熶笉鐭ラ亾鏄ソ鏄潖銆傘傘傝繕鏄急鑿滃晩銆傘傘?br />   璐翠笅鎴戠殑Trie鍥?蹇熷啣(鐩存帴浜屽垎浜?娌℃湁鍐欐垚鏁拌閲岄潰閭ｇ綆楁硶)...

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

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

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

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

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

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

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

int BuildAC(Trie* pRoot)
{
    memset(nMatrix, 0, sizeof(nMatrix));
    
    pRoot->fail = NULL;
    queue<Trie*> qt;
    qt.push(pRoot);
    while (!qt.empty())
    {
        Trie* front = qt.front();
        qt.pop();
        
        for (int i = 0; i < MAX_D; ++i)
        {
            if (front->next[i])
            {
                Trie* pNode = front->fail;
                while (pNode && pNode->next[i] == NULL)
                {
                    pNode = pNode->fail;
                }
                front->next[i]->fail = pNode? pNode->next[i] : pRoot;
                if (front->next[i]->fail->flag == true)
                {
                    front->next[i]->flag = true;
                }
                
                qt.push(front->next[i]);
            }
            else
            {
                front->next[i] = front == pRoot? pRoot : front->fail->next[i];
            }
            
            if (front->next[i]->flag == false)
            {
                nMatrix[front->no][front->next[i]->no]++;
            }
        }
    }
    
    return nP;//鑺傜偣鎬諱釜鏁?/span>
}

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

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

void MatrixPower(INT M[][MAX_P], int nSize, INT nP)
{
    if (nP == 1)
    {
        CopyMatrix(A, M, nSize);
        return;
    }
    
    MatrixPower(M, nSize, nP / 2);
    MultyMatrix(A, A, B, nSize);
    if (nP % 2)
    {
        MultyMatrix(B, M, A, nSize);
    }
    else
    {
        CopyMatrix(A, B, nSize);
    }
}

int main()
{
    INT nM, nN;
    
    InitIdx();
    while (scanf("%I64d%I64d", &nM, &nN) == 2)
    {
        InitTrie(pRoot);
        while (nM--)
        {
            scanf("%s", szPat);
            Insert(szPat);
        }
        int nSize = BuildAC(pRoot);
        
        MatrixPower(nMatrix, nSize, nN);
        INT nAns = 0;
        for (int i = 0; i < nSize; ++i)
        {
            nAns = (nAns + A[0][i]) % MOD;
        }
        printf("%I64d\n", nAns % MOD);
    }
    
    return 0;
}
   
   

yx 2012-10-18 09:46 鍙戣〃璇勮
]]>hnu 10076 Jimmy's Riddles DFAhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/12/193227.htmlyxyxFri, 12 Oct 2012 14:14:00 GMThttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/12/193227.htmlhttp://www.shnenglu.com/csu-yx-2013/comments/193227.htmlhttp://www.shnenglu.com/csu-yx-2013/archive/2012/10/12/193227.html#Feedback2http://www.shnenglu.com/csu-yx-2013/comments/commentRss/193227.htmlhttp://www.shnenglu.com/csu-yx-2013/services/trackbacks/193227.html   鎰熻鐢╠fa鍙渶瑕佷繚璇佺姸鎬佽漿鎹㈠浘瀵逛簡錛屽熀鏈笂灝變笉浼氬嚭bug浜嗭紝浣嗘槸鍏跺畠鐨勬柟娉曞幓鍖歸厤
榪欑綾諱技姝ｅ垯琛ㄨ揪寮忕殑瀛楃涓插氨瀹規槗鍑洪敊澶氫簡銆?br />
   鐧懼害鐧劇鐨凞FA瀹氫箟濡備笅錛?br />      鑻辨枃鍏ㄧО錛欴eterministic Finite Automaton, 綆鍐欙細DFA
銆銆DFA瀹氫箟錛氫竴涓‘瀹氱殑鏈夌┓鑷姩鏈猴紙DFA錛塎鏄竴涓簲鍏冪粍錛歁=錛圞錛?#931;錛宖錛孲錛孼錛夊叾涓?br />銆銆① K鏄竴涓湁絀烽泦錛屽畠鐨勬瘡涓厓绱犵О涓轟竴涓姸鎬侊紱
銆銆② Σ鏄竴涓湁絀峰瓧姣嶈〃錛屽畠鐨勬瘡涓厓绱犵О涓轟竴涓緭鍏ョ鍙鳳紝鎵浠ヤ篃縐?#931;涓鴻緭鍏ョ鍙峰瓧姣嶈〃錛?br />銆銆③ f鏄漿鎹㈠嚱鏁幫紝鏄疜×Σ→K涓婄殑鏄犲皠錛屽嵆錛屽 f錛坘i錛宎錛?kj錛岋紙ki∈K錛宬j∈K錛夊氨鎰忓懗鐫錛?br />褰撳墠鐘舵佷負ki錛岃緭鍏ョ涓篴鏃訛紝灝嗚漿鎹負涓嬩竴涓姸鎬乲j錛屾垜浠妸kj縐頒綔ki鐨勪竴涓悗緇х姸鎬侊紱
銆銆④ S ∈ K鏄敮涓鐨勪竴涓垵鎬侊紱
銆銆⑤ Z⊂K鏄竴涓粓鎬侀泦錛岀粓鎬佷篃縐板彲鎺ュ彈鐘舵佹垨緇撴潫鐘舵併?/span>

   璇ラ鐨勭姸鎬佽漿鎹㈠浘錛?br />   
   鐜板湪鍐嶆牴鎹姸鎬佽漿鎹㈠浘錛屽啓涓涓ā鎷熻漿鎹㈠叧緋葷殑鍖歸厤灝遍潪甯告柟渚夸簡銆傘傘?br />   浠ｇ爜濡備笅錛?br />
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

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

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

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

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

bool CheckState(vector<string>& vs)
{
    if (vs.empty()) return false;
    
    int nState = 0;
    for (int i = 0; i < vs.size(); ++i)
    {
        //printf("nState:%d, str:%s\n", nState, vs[i].c_str());
        switch (nState)
        {
            case 0:
                if (IsArticle(vs[i]))
                {
                    nState = 1;
                    break;
                }
                else if (IsNoun(vs[i]))
                {
                    nState = 2;
                    break;
                }
                else
                {
                    return false;
                }
                
            case 1:
                if (IsNoun(vs[i]))
                {
                    nState = 2;
                    break;
                }
                else
                {
                    return false;
                }
                
            case 2:
                if (vs[i] == "and")
                {
                    nState = 0;
                    break;
                }
                else if (IsVerb(vs[i]))
                {
                    nState = 3;
                    break;
                }
                else
                {
                    return false;
                }
                
            case 3:
                if (IsArticle(vs[i]))
                {
                    nState = 4;
                    break;
                }
                else if (IsNoun(vs[i]))
                {
                    nState = 5;
                    break;
                }
                else
                {
                    return false;
                }
                
            case 4:
                if (IsNoun(vs[i]))
                {
                    nState = 5;
                    break;
                }
                else
                {
                    return false;
                }
                
            case 5:
                if (vs[i] == "and")
                {
                    nState = 3;
                    break;
                }
                else if (vs[i] == ",")
                {
                    nState = 0;
                    break;
                }
                else
                {
                    return false;
                }
        }
    }
    
    return nState == 5;
}

int main()
{
    int nT;
    
    scanf("%d%*c", &nT);
    while (nT--)
    {
        vector<string> vs;
        string line, str;
        
        getline(cin, line);
        stringstream ss(line);
        while (ss >> str)
        {
            vs.push_back(str);
        }
        printf("%s\n", CheckState(vs) ? "YES I WILL" : "NO I WON'T");
    }
    
    return 0;
}


yx 2012-10-12 22:14 鍙戣〃璇勮
]]> 国内精品久久久久影院一蜜桃| 久久久久久久久66精品片| 69久久精品无码一区二区| 精品一区二区久久| 亚洲精品无码专区久久同性男| 性高湖久久久久久久久AAAAA| 久久夜色精品国产亚洲| 69国产成人综合久久精品| 国产精品欧美久久久久无广告 | 色天使久久综合网天天| 精品久久久久久中文字幕大豆网| 日韩人妻无码一区二区三区久久| 国产女人aaa级久久久级| 久久www免费人成看片| 国产精品免费久久久久久久久 | 国产精品美女久久久久| 国产精品成人无码久久久久久 | 久久久久国产精品嫩草影院| 亚洲午夜久久久久久噜噜噜| 伊人久久免费视频| 久久99精品久久久久久hb无码| 久久伊人五月天论坛| 久久青草国产精品一区| 午夜人妻久久久久久久久| 精品国产婷婷久久久| 久久精品男人影院| 国产麻豆精品久久一二三| 亚洲香蕉网久久综合影视| 久久天天躁狠狠躁夜夜2020一| 久久国产精品偷99| 久久久久婷婷| 久久国产热这里只有精品| 日本免费一区二区久久人人澡| 久久久久亚洲av无码专区| 久久久久亚洲av成人网人人软件| 久久久久亚洲AV成人网人人软件| 91亚洲国产成人久久精品网址| 久久超乳爆乳中文字幕| 久久精品国产99久久无毒不卡| 日韩乱码人妻无码中文字幕久久 | A狠狠久久蜜臀婷色中文网|