摘要: 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股，...  阅读全文