摘要: 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 ...  閱讀全文

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

因為把一棵邊權為1的樹的括號序列拿出來，樹上某兩點的距離就是在括號序列中兩點間沒匹配括號的個數（有左括號右括號選擇的區別，具體分析處理）。當然，既然是對一群樹操作，那就直接用動態樹就行了。

于是就去學了動態樹。發現其實不算很難（1.指時間復雜度均攤logn的算法，還有基于輕重邊剖分的嚴格logn的算法 2.如果你對splay熟的話），寫起來也就基本上就是一棵splay，也算比較好寫的。。（以后就告別路徑剖分了。。太麻煩了。。復雜度也沒動態樹好。。）

以下所說的動態樹都是基于splay的時間復雜度均攤logn的動態樹。

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

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

http://acm.pku.edu.cn/JudgeOnline/problem?id=1739
基于連通性狀態壓縮的動態規劃(名字真長- -！)其實不算太難，以前都被它嚇住了。
hyf教了一次后，印象極其深刻，回路、路徑條數啥的從此再也不用向美國（霧）進口了。
簡要的說：f[i][j][k]表示在（i，j）這個格子的時候，m+1個插頭的情況是k，然后根據(i,j)左邊和上邊插頭（括號？）的情況進行連接，然后轉移到下一個格子。一個合法的狀態是一個括號表達式，有左括號，右括號和空格，且左右括號匹配。一個左括號和一個相應的右括號表示這兩個地方的路徑是連在一起的。轉移的時候分情況討論。
處理的時候先把所有合法的狀態都dfs出來，轉移的時候就方便了。。
PS：居然驚喜地進入了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
。。上邊這個鏈接如果有人下載就會保留7天。。。7天沒人下就沒了。。
欲購從速。。。
orz一切神牛。。

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

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

字符串

 

【題目描述】

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

【輸入】

輸入數據是一行，包括2個數字n和m

【輸出】

輸出數據是一行，包括1個數字，表示滿足要求的字符串數目，這個數可能會很大，只需輸出這個數除以20100403的余數

【樣例輸入】

2 2

【樣例輸出】

2

【數據范圍】

對于30%的數據，保證1<=m<=n<=1000

對于100%的數據，保證1<=m<=n<=1000000

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

#include <iostream>
#define ll long long
#define MOD 20100403
#define MAXN 2100000
 
using namespace std;

/**//*
   C(n+m,n) - C(n+m,n+1)
 */
ll n, m;
ll fact[MAXN+1];

ll PowerMod(ll a, int b){
   if (b == 0) return 1;
   ll t = PowerMod(a, b>>1);
   t = (t * t) % MOD;
   if (b&1) t = (t * a) % MOD;
   return t;
}
ll Rev(ll a){
   return PowerMod(a, MOD-2);
}
void Init(){
     cin >> n >> m;
}

ll C(int n, int m){
   return fact[n] * Rev(fact[m]) % MOD * Rev(fact[n-m]) % MOD;
}
void Solve(){
     fact[0] = 1;
     for (ll i = 1; i<=n+m; i++)
         fact[i] = (fact[i-1] * i) % MOD;
     cout << ((C(n+m,n) - C(n+m,n+1)) % MOD + MOD) % MOD;
}

int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    Init();
    Solve();
    return 0;
}

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