今天下午，我们队做了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