今天下午，我們隊做了Pku Campus 2010，還算可以4個1y，做了6題，罰時挺少的。過了A,C,D,E,G,H    ^_^

   A 我當時找規律的，發現有遞推式，然后得推O(1)公式才能過...    1Y
   Poj 3761 找規律  別人有推公式的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<cstdlib>
#include<iostream>

using namespace std;

const int INF = 1000000000;
const int MAXN = 1000001;
const int MOD = 20100713;

void bruteForce()
{
    for(int n = 1 ; n < 10 ; n++)
    {
        vector<int> vt;
        for(int i = 0 ; i < n ; i++)
            vt.push_back(i);
        int cnt[10] = {0};
        do
        {
            vector<int>_vt(vt);
            //bubble sort
            int round = 0;
            for(int i = 0 ; i < n ; i++ , round++)
            {
                bool flag = false;
                for(int j = 1 ; j < n ; j++)
                    if(vt[j] < vt[j-1])
                    {
                        swap(vt[j-1],vt[j]);
                        flag = true;
                    }
                if(flag == false)break;
            }
            cnt[round]++;
            vt = _vt;
        }
        while( next_permutation(vt.begin() , vt.end()) );
        printf("n   %d:\n",n);
        for(int i = 0 ; i < n ; i++)
            printf("%d %d\n",i,cnt[i]);
        puts("");
    }
}
/*
 k\ n  1   2   3    4   5   6
    0   1   1   1   1   1   1
    1   0   1   3   7  15  31
    2       0   2  10  38  130
    3           0  6   42  222
    4              0   24  216
    5                  0   120

 可以發現：
                                          k
 dp[n,k] = k*dp[n-1,k] + ∑dp[n-1,j]
                                           0
 這樣子計算是O(n*k)的，TLE ,需要O(1)的公式
    dp[n,0] = 1
    dp[n,1] = 2^(n-1) - 1
 自然推出
    dp[n,2] = 2dp[n-1,2] + dp[n-1,2] + dp[n-1,1] + dp[n-1,0]
    = 3dp[n-1,2] + 2^(n-2)
 這個可以用特征方程推出dp[n,2] = 2*3^(n-2) - 2^(n-1)
 同理，就能知道
     dp[n,3] =3dp[n-1,3] + dp[n-1,3] + dp[n-1,2] +dp[n-1,1]+dp[n-1,0]
    = 4dp[n-1,3] +  2*3^(n-3)
 推出dp[n,3] = 2*3*4^(n-3) - 2*3^(n-2)
 對比猜想
    dp[n,0] = 1
    dp[n,1] = 2^(n-1) - 1
    dp[n,2] = 2*3^(n-2) - 2^(n-1)
    dp[n,3] = 2*3*4^(n-3) - 2*3^(n-2)
    
    dp[n,k] = k! * ( (k+1)^(n-k) - k^(n-k))

    http://roba.rushcj.com/?p=491
    下面的留言那里有人推公式的 Orz
 */


long long ipow(long long a, int n)
{
    if(n==0)return 1;
    if(n==1)return a % MOD;
    long long ans = ipow(a,n/2);
    ans = ans * ans % MOD;
    if(n&1)ans = ans*a%MOD;
    return ans;
}

long long f[MAXN];

int main()
{

#ifdef ONLINE_JUDGE
#else
   // freopen("in", "r", stdin);
   // freopen("out", "w", stdout);
#endif

    //bruteForce();

    //需要先預處理階乘
    f[0] = 1;
    for(int i = 1 ; i < MAXN ;i++)
        f[i] = f[i-1] * i % MOD;
    int n , k , T;
    for(scanf("%d",&T) ; T-- ; )
    {
        scanf("%d%d",&n,&k);
        printf("%lld\n" , f[k] * ((ipow(k+1,n-k) - ipow(k,n-k)) + MOD) % MOD);
    }
    return 0;
}



   C 樹形dp 1Y
   Poj 3763 ★★★
/*
    題意：給出一棵樹，問添加最少的邊使得每個點走出一個哈密頓回路（每個點只走一次，且邊不重復走）
    樹形dp,一開始狀態設計不清晰，想著既然是環，就定義把整棵子樹搞成環的最小代價，發現需要多一個搞成鏈的狀態
    其實，只需要定義把子樹搞成鏈的最小代價即可
    dp[u]把子樹搞成鏈，u為鏈的一個端點
    _dp[u]把子樹搞成鏈，u為鏈的中間點

    處理一棵樹時，其實就是串鏈子，把子樹的鏈串起來
    對于dp[u]，可以選擇dp[v],_dp[v] ，還有要把num個兒子串起來，需要加num-1條邊串起來
    即∑min{dp[v],_dp[v]} + num - 1   但這樣子有可能都是_dp[v]，即根u不與子樹連起來，
    本來就該選擇一個_dp[v]去掉，加上dp[v] 或者直接對某個_dp[v]+1，發現效果都是一樣的，最多只增加1，
    所以不用枚舉選擇一個_dp[v]去掉換上dp[v]，直接加上1即可！

    同理，對于_dp[u] ，∑min{dp[v],_dp[v]} + num - 1
    看選了多少個_dp[v] ，不夠的話要補鏈

    最后的答案是對dp[1],_dp[1]補成環
    dp[1] , 即1是一個鏈的端點，就要看之前選了多少個dp[v]了，多于1個的話，就不用加邊了
    _dp[1] 就得加多一條邊，連接兩個子樹

 */

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<cstdlib>
#include<iostream>

using namespace std;

const int INF = 1000000000;
const int MAXN = 100010;

struct Edge
{
    int v;
    Edge *next;
};

Edge *E[MAXN] , *pE , edges[MAXN*2];
int dp[MAXN] , _dp[MAXN];
int cnt[MAXN];

void add(int u ,int v)
{
    pE->v = v;
    pE->next = E[u];
    E[u] = pE++;
}

void dfs(int u, int p)
{
    cnt[u] = 0;
    int num = 0 , tot = 0;
    for(Edge *it = E[u] ; it ; it = it->next)
    {
        int v = it->v;
        if(v == p)continue;
        num ++;
        dfs(v,u);
        if(dp[v] <= _dp[v])
        {
            cnt[u] ++;
            tot += dp[v];
        }
        else tot += _dp[v];
    }
    if(num == 0)dp[u] = _dp[u] = 0;
    else
    {
        dp[u] = num - 1 + tot;
        _dp[u] = num - 2 + tot;
        if(cnt[u] < 1)dp[u] ++;
        if(cnt[u] < 2)_dp[u] += (2-cnt[u]);
    }
  //  printf("%d %d %d %d\n",u,cnt[u],dp[u],_dp[u]);
}

int main()
{

#ifdef ONLINE_JUDGE
#else
    freopen("in", "r", stdin);
#endif

    int n;
    while( ~scanf("%d",&n) )
    {
        pE = edges;
        for(int i = 1;  i <= n ; i++)
            E[i] = NULL;
        int u ,v;
        for(int i = 1 ; i < n ;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        dfs(1,1);
        int A = dp[1] + (cnt[1] <= 1);//寫成cnt[u]錯了一次  #_#
        int B = _dp[1] + 1;
        printf("%d\n",min(A,B));
    }
    return 0;
}



   D 預處理dist[] 用Trie樹加速枚舉查找  1TLE 1 RE 1 WA 
   Poj 3764 ★★★★ 樹路徑上異或值最大   
/*
    題意 : 求一棵樹上某條路徑，其邊權的異或值最大
    比賽時我想到先以0為根dfs出每個點到0的路徑的異或值dist[u]，  然后要求兩點間路徑的異或值就是 dist[a] ^ dist[b]
    這樣問題就轉化為怎么在這個dist[]里面找出最大的異或值、自身值

    起初的一個貪心的思路：
    最高位為1的肯定要選，而且不能被異或掉，所以按照最高位來分組
    這樣就枚舉最高的那一組的那些值去跟其它組的值異或，找最大
    同時，對于x，要找y,使得異或后增大的話，找的只需是x的最左的0那一位，但y該位是1的，這樣必定會增大值
    如 x = 1101101  ， 找最高位為4的那一組，該組為空的話就找第1組，然后只需枚舉這一組的y跟x的異或值即可

    但這樣子做還是會超時，這樣的枚舉只會優化常數

    比賽時zeus提出用Trie樹做，這樣子枚舉時復雜度就很低了，果然，在Trie樹走就可以了

    做法是，對剩余那些組（最高位那組不用加進去，它是用來枚舉的）建立Trie樹
    然后對最高位那組的所有值在Trie樹上走，先選擇使得異或值為1的點走，沒有就只好走異或值為0的了

    原來《淺談信息學競賽中的“0”和“1”》有提到建立Trie樹搞

    “對某個值s，要查找n個權值中和其異或最大的，trie樹確實是最佳選擇”
 */
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<cstdlib>
#include<iostream>

using namespace std;

const int INF = 1000000000;
const int MAXN = 100010;


struct Edge
{
    int v , w;
    Edge *next;
};

Edge *E[MAXN] , *pE , edges[MAXN*2];

struct Node
{
    Node *ch[2];
};

Node *pN , nodes[MAXN*31];

Node *newNode()
{
    for(int i = 0 ; i < 2; i++)
        pN->ch[i] = NULL;
    return pN++;
}

int dist[MAXN];

void dfs(int u , int p ,int W)
{
    dist[u] = W;
    for(Edge *it = E[u] ; it ; it = it->next)
    {
        int v = it->v , w = it->w;
        if(v == p)continue;
        dfs(v,u,w^W);
    }
}

void add(int u , int v , int w)
{
    pE->v = v;
    pE->w = w;
    pE->next = E[u];
    E[u] = pE++;
}


void insert(Node *root ,int len , int x)
{
    if(len < 0)return;
    bool who = (x>>len)&1 ;
    if(root->ch[who] == NULL )root->ch[who] = newNode();
    insert(root->ch[who] , len-1 , x);
}

int gao(Node *root , int len ,int x)
{
    if(root == NULL)return x;
    if(len < 0 )return x;
    bool who = (x>>len)&1;
    who ^= 1;
    if(root->ch[who] == NULL )who ^= 1;
    return gao(root->ch[who] , len-1 , who ? x ^ (1<<len) : x );
}

int main()
{

#ifdef ONLINE_JUDGE
#else
    freopen("in", "r", stdin);
#endif

    int n ;
    while( ~scanf("%d",&n) )
    {
        pE = edges;
        pN = nodes;
        for(int i = 0 ; i< n ; i++)
            E[i] = NULL;

        int u ,v ,w;
        for(int i =1 ;i < n ; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }

        dfs(0,0,0);

        vector<int> vt[32];
        for(int i = 0 ; i < n ; i++)
        {
            if(dist[i] == 0)continue;
            for(int j = 30 ; j >= 0 ; j--)
            {
                if( dist[i] & (1<<j) )
                {
                    vt[j].push_back(dist[i]);
                    break;
                }
            }
        }

        int  high = 30;
        while(high >=0 && vt[high].size() == 0) high--;
        if(high < 0)
        {
            puts("0");
        }
        else
        {
            
            Node *root = newNode();//insert all the highest < high
            for(int i = high - 1 ; i >= 0 ; i--)
            {
                for(int j = 0 , jsize = vt[i].size() ; j < jsize ; j++)
                {
                    insert(root , 30 , vt[i][j]);
                }
            }
            
            int ans = 0 , size = vt[high].size();
            for(int i = 0 ; i < size ; i++)
            {
                int x = vt[high][i] ;
                ans = max(ans , x);
                ans = max(ans , gao(root , 30 , x) );
            }
            printf("%d\n" ,ans);
        }
    }
    return 0;
}



   E,G,H 略


   更詳細的報告見：
   http://blog.csdn.net/yuhailin060/archive/2010/05/10/5576255.aspx
   http://roba.rushcj.com/?p=491