摘要: The Alliances In a fantasy world, there is a large island of a rectangular shape. The sides of the island happen to be exactly R miles and C miles long, and the whole island is divided into a grid ...  閱讀全文

聽說有版權(quán)問題不能貼題目？。那就只能先忍一忍了。
題目抽象為：我們有一個(gè)由有根樹構(gòu)成的森林，對(duì)這個(gè)森林進(jìn)行兩種操作：
把某棵子樹拔下來接到某一棵樹（可能還是那個(gè)子樹原來所在的樹）的某個(gè)節(jié)點(diǎn)下面，詢問某個(gè)節(jié)點(diǎn)在樹中的深度。

因?yàn)榘岩豢眠厵?quán)為1的樹的括號(hào)序列拿出來，樹上某兩點(diǎn)的距離就是在括號(hào)序列中兩點(diǎn)間沒匹配括號(hào)的個(gè)數(shù)（有左括號(hào)右括號(hào)選擇的區(qū)別，具體分析處理）。當(dāng)然，既然是對(duì)一群樹操作，那就直接用動(dòng)態(tài)樹就行了。

于是就去學(xué)了動(dòng)態(tài)樹。發(fā)現(xiàn)其實(shí)不算很難（1.指時(shí)間復(fù)雜度均攤logn的算法，還有基于輕重邊剖分的嚴(yán)格logn的算法 2.如果你對(duì)splay熟的話），寫起來也就基本上就是一棵splay，也算比較好寫的。。（以后就告別路徑剖分了。。太麻煩了。。復(fù)雜度也沒動(dòng)態(tài)樹好。。）

以下所說的動(dòng)態(tài)樹都是基于splay的時(shí)間復(fù)雜度均攤logn的動(dòng)態(tài)樹。

動(dòng)態(tài)樹的主要思想就是：類似輕重邊剖分一樣，把整棵樹劃分成若干實(shí)邊(solid edge)和虛邊(dashed edge)，但這個(gè)都是根據(jù)你的需要來設(shè)定的，不像輕重邊一樣每個(gè)點(diǎn)往下都必須有一條重邊（單獨(dú)的葉子節(jié)點(diǎn)算長(zhǎng)度為0的重邊），而是每次把你所需要操作的點(diǎn)到根的邊都改為實(shí)邊(expose操作)，且每個(gè)點(diǎn)往下的實(shí)邊數(shù)不超過1。修改沿途如果有一個(gè)點(diǎn)已經(jīng)有了實(shí)邊邊那么就把它原來的實(shí)邊改成虛邊。這樣每次對(duì)一個(gè)點(diǎn)操作都是在一條實(shí)路徑上(solid path)。對(duì)于每一條實(shí)路徑，都用一棵splay來維護(hù)就行了。（splay可以亂轉(zhuǎn)亂拔亂接太爽了。。- -!當(dāng)然是在一定規(guī)則下的亂。。）

     摘要:  貨幣兌換  問題描述     小 Y 最近在一家金券交易所工作。該金券交易所只發(fā)行交易兩種金券：A 紀(jì) 念券（以下簡(jiǎn)稱 A 券）和 B 紀(jì)念券（以下簡(jiǎn)稱 B 券）。每個(gè)持有金券的顧客都有 一個(gè)自己的帳戶。金券的數(shù)目可以是一個(gè)實(shí)數(shù)。     每天隨著市場(chǎng)的起伏波動(dòng)，兩種金券都有自己當(dāng)時(shí)的價(jià)值，即每一單位金券 當(dāng)天可以兌...  閱讀全文

http://acm.pku.edu.cn/JudgeOnline/problem?id=1739
基于連通性狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃(名字真長(zhǎng)- -！)其實(shí)不算太難，以前都被它嚇住了。
hyf教了一次后，印象極其深刻，回路、路徑條數(shù)啥的從此再也不用向美國(guó)（霧）進(jìn)口了。
簡(jiǎn)要的說：f[i][j][k]表示在（i，j）這個(gè)格子的時(shí)候，m+1個(gè)插頭的情況是k，然后根據(jù)(i,j)左邊和上邊插頭（括號(hào)？）的情況進(jìn)行連接，然后轉(zhuǎn)移到下一個(gè)格子。一個(gè)合法的狀態(tài)是一個(gè)括號(hào)表達(dá)式，有左括號(hào)，右括號(hào)和空格，且左右括號(hào)匹配。一個(gè)左括號(hào)和一個(gè)相應(yīng)的右括號(hào)表示這兩個(gè)地方的路徑是連在一起的。轉(zhuǎn)移的時(shí)候分情況討論。
處理的時(shí)候先把所有合法的狀態(tài)都dfs出來，轉(zhuǎn)移的時(shí)候就方便了。。
PS：居然驚喜地進(jìn)入了status第一頁？！。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 8
#define BLANK 0
#define LEFT 1
#define RIGHT 2
#define MAXSTATE 174420
#define MAXSTATEAMOUNT 835
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define ll long long

using namespace std;

int n,m;
char map[MAXN+1][MAXN+1];
int nState = 0;
int State[MAXSTATEAMOUNT+1];
int id[MAXSTATE+1];
int Tx, Ty, FinalState;
ll f[MAXN+1][MAXN+1][MAXSTATEAMOUNT+1];
ll ans;
void Reset(){
     nState = 0, Tx = -1;
     memset(f, 0, sizeof(f));
     ans = 0;
}

bool Init(){
     scanf("%d%d",&n,&m);
     if (!n) return false;
     Reset();
     for (int i = n-1; i>=0; i--){
         scanf("%s", map[i]);
         if (Tx == -1)
         for (int j = m-1; j>=0; j--)
             if (map[i][j] == '.'){
                Tx = i, Ty = j;
                break;
             }
         for (int j = 0; j<m; j++)
             if (map[i][j] == '.') map[i][j] = 0;
             else map[i][j] = 1;
     }
     return true;
}

void dfs(int pos, int r_bracket, int state){
     if (pos < 0){
        State[nState] = state;
        id[state] = nState;
        /*
        printf("%d: ", nState);
        for (int i = 0; i<=m; i++)
            printf("%d ", buffer[i]);
        printf("\n");
        */
        nState ++;
        return;
     }
     if (pos >= r_bracket) // blank
        dfs(pos - 1, r_bracket, (state << 2));
     if (pos > r_bracket) // right bracket
        dfs(pos - 1, r_bracket + 1, (state << 2) | RIGHT);
     if (r_bracket) // left bracket
        dfs(pos - 1, r_bracket - 1, (state << 2) | LEFT);
}

#define MASK 3
#define Get(state, p) (((state) >> (p<<1)) & MASK)

inline bool OK(int i, int j, int state){
     if (Get(state, j) == 1 && Get(state, j+1) == 2 && !(i == Tx && j == Ty)) return false;
     for (int k = 0; k<j; k++)
         if ((map[i][k] || map[i+1][k]) && Get(state, k)) return false;
     if (((j && map[i][j-1]) || (map[i][j])) && Get(state, j)) return false;
     for (int k = j+1; k<=m; k++)
         if (((i && map[i-1][k-1]) || (map[i][k-1])) && Get(state, k)) return false;
     return true;
}

inline int Modify(int state, int p, int v){
    return state - (((state >> (p << 1)) & MASK) << (p << 1)) + (v << (p << 1));
}

inline int FindRight(int p, int state){
    int cnt = 0, t;
    for (int i = p; i<=m; i++){
        t = Get(state,i);
        if (t == 1) cnt++;
        if (t == 2) cnt--;
        if (cnt == 0) return i;
    }
    return -1;
}

inline int FindLeft(int p, int state){
    int cnt = 0, t;
    for (int i = p; i>=0; i--){
        t = Get(state, i);
        if (t == 2) cnt++;
        if (t == 1) cnt--;
        if (cnt == 0) return i;
    }
    return -1;
}

void Solve(){
     dfs(m, 0, 0);
     f[0][0][id[(1 << 2) + (2 << (2 * m))]] = 1;
     FinalState = (1 << (2 * Ty)) + (2 << (2 * (Ty+1)));
     int p, q, tmp, tmp2, state, v, i, j, k;
     ll *a;
     for (i = 0; i < n; i++){
         for (j = 0; j < m; j++){
             a = f[i][j+1];
             for (k = 0; k < nState; k++)
                 if ((v = f[i][j][k])){
                     state = State[k];
                     p = Get(state, j), q = Get(state, j+1);
                     if (p == 0 && q == 0){
                        if (!map[i][j]){
                            tmp = Modify(Modify(state, j, 1), j+1, 2);
                            if (OK(i, j+1, tmp))
                               a[id[tmp]] += v;
                        }else
                             a[k] += v;
                     }else if(p == 0){ // conditions below ensured map[i][j] is empty, because there exists at least one bracket on one side of the grid (i,j)
                           if (OK(i, j+1, state))
                              a[k] += v;
                           tmp = Modify(Modify(state, j, q), j+1, 0);
                           if (OK(i, j+1, tmp))
                              a[id[tmp]] += v;
                     }else if (q == 0){
                           if (OK(i, j+1, state))
                              a[k] += v;
                           tmp = Modify(Modify(state, j, 0), j+1, p);
                           if (OK(i, j+1, tmp))
                              a[id[tmp]] += v;
                     }else{
                         tmp = Modify(Modify(state, j, 0), j+1, 0);
                         if (p == 1 && q == 1){
                               tmp2 = Modify(tmp, FindRight(j+1, state), 1);
                               if (OK(i, j+1, tmp2))
                                  a[id[tmp2]] += v;
                         }else if (p == 2 && q == 2){
                               tmp2 = Modify(tmp, FindLeft(j, state), 2);
                               if (OK(i, j+1, tmp2))
                                  a[id[tmp2]] += v;
                         }else if (p == 1 && q == 2){
                               if (i == Tx && j == Ty && state == FinalState){
                                  printf("%I64d\n", v);
                                  return;
                               }
                         }else if (p == 2 && q == 1){
                               if (OK(i, j+1, tmp))
                                  a[id[tmp]] += v;
                         }
                     }
                 }
         }
         for (int k = 0; k < nState; k++)
             if (Get(State[k], m) == 0 && OK(i+1, 0, tmp = (State[k] << 2)))
                f[i+1][0][id[tmp]] += f[i][m][k];
     }
     printf("%I64d\n", ans);
}

int main(){
    while (Init())
          Solve();
    return 0;
}


http://d.namipan.com/d/1d015405c37f1b310d80af62e6bb5697f9367b00b7732d01
。。上邊這個(gè)鏈接如果有人下載就會(huì)保留7天。。。7天沒人下就沒了。。
欲購從速。。。
orz一切神牛。。

     摘要: 很久以前有且寫過一次splay。。。然后被它要記父親的旋轉(zhuǎn)囧到。。然后從此就再也沒寫過。。這幾天剛省選完沒事做，就準(zhǔn)備再寫一下。在sqybi神牛的文章的指導(dǎo)下很快又回憶起了splay的操作。。于是從頭開始YY一個(gè)splay。。。總體感覺比treap要難寫。。（Treap性價(jià)比真的很高），但要比treap強(qiáng)大許多。。。感覺上splay完全可以代替線段樹了。。只是常數(shù)太大了。。做了兩道splay的題：...  閱讀全文

     摘要: 序列操作   【題目描述】 lxhgww最近收到了一個(gè)01序列，序列里面包含了n個(gè)數(shù)，這些數(shù)要么是0，要么是1，現(xiàn)在對(duì)于這個(gè)序列有五種變換操作和詢問操作： 0 a b 把[a, b]區(qū)間內(nèi)的所有數(shù)全變成0 1 a b 把[a, b]區(qū)間內(nèi)的所有數(shù)全變成1 2 a b 把[a,b]區(qū)間內(nèi)的所有數(shù)全部取反，也就是說把所有的0變成1，把所有的1變成0 3 a b 詢問[a, b]...  閱讀全文      摘要: 傳送帶   【題目描述】 在一個(gè)2維平面上有兩條傳送帶，每一條傳送帶可以看成是一條線段。兩條傳送帶分別為線段AB和線段CD。lxhgww在AB上的移動(dòng)速度為P，在CD上的移動(dòng)速度為Q，在平面上的移動(dòng)速度R。現(xiàn)在lxhgww想從A點(diǎn)走到D點(diǎn)，他想知道最少需要走多長(zhǎng)時(shí)間 【輸入】 輸入數(shù)據(jù)第一行是4個(gè)整數(shù)，表示A和B的坐標(biāo)，分別為Ax，Ay，Bx，By 第二行是4個(gè)整數(shù)，表示...  閱讀全文

字符串

 

【題目描述】

lxhgww最近接到了一個(gè)生成字符串的任務(wù)，任務(wù)需要他把n個(gè)1和m個(gè)0組成字符串，但是任務(wù)還要求在組成的字符串中，在任意的前k個(gè)字符中，1的個(gè)數(shù)不能少于0的個(gè)數(shù)。現(xiàn)在lxhgww想要知道滿足要求的字符串共有多少個(gè)，聰明的程序員們，你們能幫助他嗎？

【輸入】

輸入數(shù)據(jù)是一行，包括2個(gè)數(shù)字n和m

【輸出】

輸出數(shù)據(jù)是一行，包括1個(gè)數(shù)字，表示滿足要求的字符串?dāng)?shù)目，這個(gè)數(shù)可能會(huì)很大，只需輸出這個(gè)數(shù)除以20100403的余數(shù)

【樣例輸入】

2 2

【樣例輸出】

2

【數(shù)據(jù)范圍】

對(duì)于30%的數(shù)據(jù)，保證1<=m<=n<=1000

對(duì)于100%的數(shù)據(jù)，保證1<=m<=n<=1000000

=================================================================
。。。這題是最悲劇的一題。。。以前做過原題。。。然后考試的時(shí)候緊張的啥都不知道了。。。數(shù)學(xué)不過關(guān)啊！！T_T
一種推導(dǎo)是這樣的：
總的01串的數(shù)量為C(n+m,n)，考慮除去不符合條件的。
對(duì)于一個(gè)不符合條件的01串，一定有某個(gè)位置使得0的個(gè)數(shù)第一次超過1的個(gè)數(shù)，比如：
1010011010
      |
設(shè)該位置是p，在1~p中1的個(gè)數(shù)為a，0的個(gè)數(shù)為a+1
則在p~n+m中，1的個(gè)數(shù)為n-a，0的個(gè)數(shù)為m-a-1
如果對(duì)p~n+m中的0和1取反，則在p~n+m中，1的個(gè)數(shù)為m-a-1，0的個(gè)數(shù)為n-a
對(duì)于這樣一個(gè)變換后的串，共有m-1個(gè)1，n+1個(gè)0。
由于每一個(gè)不符合條件的有n個(gè)1，m個(gè)0的01串都可以唯一確定對(duì)應(yīng)一個(gè)有m-1個(gè)1，n+1個(gè)0的01串，
并且每一個(gè)有m-1個(gè)1，n+1個(gè)0的01串一定有一個(gè)位置開始0的個(gè)數(shù)第一次多于1的個(gè)數(shù)，把這個(gè)位置之后的串取反后得到的01串可以唯一確定對(duì)應(yīng)一個(gè)有n個(gè)1，m個(gè)0的不符合條件的01串，所以這兩種串是一一對(duì)應(yīng)的。
所以不符合條件的串的個(gè)數(shù)為C(n+m,n+1)
所以最后的答案為C(n+m,n) - C(n+m,n+1)
PS：算這個(gè)的時(shí)候可以分解質(zhì)因數(shù)（hyf神牛神做法），也可以用逆元解決除法的問題。因?yàn)?span lang=EN-US>20100403是質(zhì)數(shù)，所以逆元就可以不用解方程算了，直接取a^(p-2)次方即可。

     摘要: 股票交易   【題目描述】 最近lxhgww又迷上了投資股票，通過一段時(shí)間的觀察和學(xué)習(xí)，他總結(jié)出了股票行情的一些規(guī)律。 通過一段時(shí)間的觀察，lxhgww預(yù)測(cè)到了未來T天內(nèi)某只股票的走勢(shì)，第i天的股票買入價(jià)為每股APi，第i天的股票賣出價(jià)為每股BPi（數(shù)據(jù)保證對(duì)于每個(gè)i，都有APi>=BPi），但是每天不能無限制地交易，于是股票交易所規(guī)定第i天的一次買入至多只能購買ASi股，...  閱讀全文