飞机票： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34531

题意：就是给你n个人，m种关系a b，b是a的父亲，且父亲只有一个，而且自己不可能是自己的祖先，求父亲在儿子前面的方案数取模

分析：题意稍微想下其实是一堆树，我们可以先把无根转换为有根，就是把森林转换成树，我们可以把没有父亲的借点全部连在0这个节点上，这样就是一棵树。然后怎么求解呢。假设当前的节点fa，它有3个儿子，且每个儿子那一块分别有i1，i2，i3个人，而且每个的方案数分别为j1，j2，j3。。。那我们可以知道除了当前的父节点一共有i1+i2+i3个人，假设为sump，当前的父节点肯定要在他们前面，所以不用计算，位置固定，然后下面三个子树可以随机组合，就是说我们可以有C(sump,i1)种方案来放置i1中的人，但是这里还不够完整，因为这个还没有排列好，就是说i1中的人顺序应该怎么样，因为我们知道j1，所以只要两个相乘就可以，why?因为选i1的方案数就是选取了i1个位置，然后他们的方案共有j1，所以两个相乘就可以，就是C（sump,i1)*j1,那么i2就不是这样求了，因为sump减少了i1个人，所以只有sump-i1个人了所以是C（sump-i1,i2)*j2,那么第三个就是C(sump-i1-i2,i3)*j3，这样方案就是了，然后将三个相乘就是当前的方案数了。记得取模不是一般的取模，因为带有除法，但是有模版，接下来我要证明无论顺序怎么样都没有问题：C（sump,i1)*C(sump-i1,,i2)=C(sump,i2)*C(sump-i2,i1)其实很简单，左边展开和右边张开通分就可以然后啪啪啪就可以AC了~

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define INF 1e9
#define EPS 1e-9
#define LL long long
#define MOD 1000000007
using namespace std;
const int maxn=12345*4;
vector<int> V[maxn];
int n,m;
int fa[maxn];
void init()
{
    memset(fa,0,sizeof(fa));
    scanf("%d%d",&n,&m);
    V[0].clear();
    for(int i=1; i<=n; i++)
    {
        V[i].clear();
    }
    int u,v;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        fa[u]=v;
    }
    for(int i=1; i<=n; i++)
    {
        u=fa[i];
        V[u].push_back(i);
    }
}
LL exp_mod(LL a, LL b, LL p)
{
    LL res = 1;
    while(b != 0)
    {
        if(b&1) res = (res * a) % p;
        a = (a*a) % p;
        b >>= 1;
    }
    return res;
}

LL Comb(LL a, LL b, LL p)
{
    if(a < b)   return 0;
    if(a == b)  return 1;
    if(b > a - b)   b = a - b;

    LL ans = 1, ca = 1, cb = 1;
    for(LL i = 0; i < b; ++i)
    {
        ca = (ca * (a - i))%p;
        cb = (cb * (b - i))%p;
    }
    ans = (ca*exp_mod(cb, p - 2, p)) % p;
    return ans;
}

LL Lucas(int n, int m, int p)
{
    LL ans = 1;

    while(n&&m&&ans)
    {
        ans = (ans*Comb(n%p, m%p, p)) % p;
        n /= p;
        m /= p;
    }
    return ans;
}

pair<int,LL> DFS(int now)
{

    int sum=0;
    LL ans=1;
    vector<pair<int,LL> > S;
    for(int i=0; i<V[now].size(); i++)
    {
        int v=V[now][i];
        pair<int,LL> p=DFS(v);
        sum+=p.first;
        S.push_back(p);
    }
    int tm=sum;
    for(int i=0; i<S.size(); i++)
    {
        int a1=S[i].first;
        LL a2=S[i].second;
        LL pq=Lucas(tm,a1,MOD);
        ans=((pq*a2)%MOD)*ans%MOD;
        tm-=a1;
    }
    return make_pair(sum+1,ans);
}
void play()
{
    pair<int,LL> p=DFS(0);
    printf("%lld\n",p.second);
}
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//   cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=28550

题意：给你一个字符串，假设长度为len，分割成len/k个字符串，假设一共有n个，每个被分割的部分可以随便重组，然后将n个字符串按1~n顺序排列，求最少的块，块定义为连接的是相同的字母。

分析：DP 复杂度n*26*26

起先我们可以将n个字串进行预处理，记录每个字母在当前串是否存在，不需要记录多少个（因为我们贪心的想法，肯定会把同一个串里同一个字母合在一起，这样才最优），然后我们记录长度，因为长度为1的要特殊处理,假设存在数组为ai，长度数组为bi，然后我们dp，假设当前处理的是i，如果bi[i]不等于1，那么我们枚举i里面的字母，如果当前字母是j，如果i-1也存在j，那么我们可以把i-1里面不是用j放第一的那种方案拿过来然后加上当前的bi[i]-1和我们当前的方案比一下，取最小的,因为合并，所以少了1个，假设我们定义数组islast记录把字母放在最后的最优解，计算好后，我们就知道把j放在当前的第一最优解是多少了，然后枚举其他不是j的，更新把他们放在最后的最优解。。。结束后，我们要更新最优解，因为最优解加上bi[i+1]就是i+1不管怎么排的下限、、、

这里我只处理了bi!=1，如果等于1,就好办了，直接把当前的最优和i-1存在j的比一下就好了，相当于直接把j扔到i-1里去了具体DP思想看代码。。。啪啪啪，就可以AC了

/*
Author:Chieh
Because of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#define LL long long
#define INF 1e9
using namespace std;
const int maxn=1234;
int k,T;
char ch[maxn];
bool ai[maxn][27];
int islast[maxn][27];
int bi[maxn];
void init()
{
    scanf("%d%s",&k,ch+1);
}
void play()
{
    memset(ai,0,sizeof(ai));
    memset(bi,0,sizeof(bi));
    int len=strlen(ch+1);
    int n=len/k;
    for(int i=0; i<=n; i++)
        for(int j=1; j<=26; j++)islast[i][j]=INF;
    for(int i=1; i<=n; i++)
    {
        int st=(i-1)*k+1;
        int en=i*k;
        for(int j=st; j<=en; j++)
        {
            int p=ch[j]-'a'+1;
            if(!ai[i][p])bi[i]++;
            ai[i][p]=1;
        }
    }
    int before=0;
    for(int i=1; i<=n; i++)
    {
        before+=bi[i];
        int now=before;
        if(bi[i]==1)
        {
            for(int j=1; j<=26; j++)
            {
                if(ai[i][j])
                {
                    islast[i][j]=min(before,islast[i-1][j]);
                    now=islast[i][j];
                    break;
                }
            }

        }
        else
        {
            for(int j=1; j<=26; j++)
            {
                if(!ai[i][j])continue;
                int tm=min(islast[i-1][j]-1+bi[i],before);
                for(int k=1; k<=26; k++)
                {
                    if(ai[i][k]&&k!=j)
                    {
                        islast[i][k]=min(islast[i][k],tm);
                    }
                }
                now=min(tm,now);
            }
        }
        before=now;
    }
    int MIN=INF;
    for(int i=1; i<=26; i++)
    {
        MIN=min(islast[n][i],MIN);
    }
    printf("%d\n",MIN);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//   cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19219

题意：给你一个长度为n的序列，求最长的奇数长度，使前k+1严格递增，后k+1个严格递减

分析：两次LIS 复杂度(n*logn+n*logn)=n*logn

先根据LIS求出1~n每个位置的最长递增序列长度，这里从1至n计算,然后求n~1各位置的最长序列长度，这里从n至1计算，为了不增加编码长度，可以把序列倒转，然后再求一遍，然后比较每个位置左边和右边最长序列的最小值，然后乘以2-1，每次更新MAX，最后的MAX就是最长的符合要求的长度了，这里我用了bi[0]和bi[1]两个数组，其中bi[0]是从1~n的，bi[1]是从n~1的，那么每次更新的话，就是bi[i]和bi[n-i+1]（原始位置的右边）然后取最小，MIN*2-1即可，更新MAX，OK了~啪啪啪。就可以AC了

/*
Author:Chieh
Because of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
const int maxn=12345;
int ai[maxn],ans[maxn],n,bi[2][maxn],sw[maxn];
int len;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
}
int brsearch(int x)
{
    int left=0,right=len;
    while(left<right)
    {
        int   mid = left+(right-left)/2;
        if(ans[mid]>=x) right=mid;
        else left=mid+1;
    }
    return left;
}
void CalLIS(int status)
{
    ans[1] = ai[1];
    bi[status][1]=1;
    len=1;
    for(int i=2; i<=n; i++)
    {
        if(ai[i]>ans[len])
        {
            ans[++len]=ai[i];
            bi[status][i]=len;
        }
        else
        {
            int pos=brsearch(ai[i]);
            ans[pos] = ai[i];
            bi[status][i]=pos;
        }
    }
}
void play()
{
    CalLIS(0);
    for(int i=1; i<=n; i++)
        sw[i]=ai[n-i+1];
    for(int i=1; i<=n; i++)
        ai[i]=sw[i];
    CalLIS(1);
    int MAX=0;
    for(int i=1; i<=n; i++)
    {
        int p=min(bi[0][i],bi[1][n-i+1]);
        MAX=max(p*2-1,MAX);
    }
    printf("%d\n",MAX);

}
int main()
{

    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
    return 0;
}

飞机票：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34699

题意：就是给你初始的汉诺塔大小升序，和目标的汉诺塔大小升序，求最小的移动步数；

分析：刚开始没有想法，后来想到了万法归宗，就是已知初始状态变回原始状态也是可行的就是说假如A,B,C三个分别有编号1，2，3的盘子，我们可以变回A，B，C只有A上有3个盘子的状态好复杂，所以我是用了反推的方法，先设A,B,C有3个盘子，然后推出A,B,C分别有1个盘子的步数为几步。。所以加个判断，加入当前盘子是A，当前要移动的最大盘是k，要移动到B，则上面的k-1个盘都要移动到C才行，就是2^(k-1)步，这里不用减1，因为k要移一步。这样先把初始的都先归到一个盘子一共要几步，然后根据当前的盘要移动到哪进行计算步数就ok了，

解释下吧：

对于第一个样例，我们可以把第3个盘提出来，则1，2个盘回到C上去，这样一共要3步+第三个盘要1步，就是4步，然后1，2都在C上，当要把2移到B上时，我们得把2上面的移到A上，则要1步+第二个盘要1步，就是2步，最后再加上第一个盘移一次就是答案了，7；

啪啪啪~就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#define LL long long
using namespace std;
const int maxn=67;
struct he
{
    int s,e;
} JLJ[maxn];
int n;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d",&JLJ[i].s);
    for(int i=1; i<=n; i++)scanf("%d",&JLJ[i].e);
}
void play()
{
    int st=-1;
    for(int i=n; i>=1; i--)
    {
        if(JLJ[i].s!=JLJ[i].e)
        {
            st=i;
            break;
        }
    }
    if(st==-1)
    {
        printf("0\n");
        return;
    }
    LL sum=0;
    int now=6-JLJ[st].s-JLJ[st].e;
    for(int i=st-1; i>=1; i--)
    {
        if(JLJ[i].s==now)
            continue;
        else
        {

            sum+=((1LL)<<(i-1));
            now=6-JLJ[i].s-now;
        }
    }
    sum++;
    now=6-JLJ[st].s-JLJ[st].e;
    for(int i=st-1; i>=1; i--)
    {
        if(JLJ[i].e==now)continue;
        else
        {
            sum+=((1LL)<<(i-1));
            now=6-JLJ[i].e-now;
        }
    }
    printf("%lld\n",sum);
}
int main()
{
    int Ca=1;
    while(scanf("%d",&n)!=EOF)
    {   if(n==0)break;
        init();
        printf("Case %d: ",Ca++);
        play();
    }
    return 0;
}

飞机票： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=24665

题意：就是说给你个矩阵，你把0变为1，使矩阵中各个点的上下左右相加为偶数（如果上下左右存在的话），求改变最少的0的数量

分析：如果枚举每个点的话肯定就TLE了，但是我们可以只枚举第一行就行。。。这样就可以推出下面所有的行，因为下面的行可以根据当前行的上左右推出来，复杂度为2^n*(n^2),可以接受~，啪啪啪，AC啦

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#define LL long long
using namespace std;
const int maxn=20;
int T,n;
int ai[maxn][maxn];
int bi[maxn][maxn];
void init()
{
    scanf("%d",&n);
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            scanf("%d",&ai[i][j]);
        }
    }
}
int MIN;
void DFS(int depth,int sum)
{

    if(depth>n)
    {
        int now=sum;
        memset(bi,0,sizeof(bi));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                bi[i][j]=ai[i][j];
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                int tm=bi[i-1][j]+bi[i][j-1]+bi[i][j+1];
                if(tm%2==0)
                {
                    if(bi[i+1][j]==1)return;
                    else continue;
                }
                else
                {
                    if(bi[i+1][j]==0&&i+1<=n)
                    {
                        bi[i+1][j]=1;
                        now++;
                    }
                    else if(bi[i+1][j]==1)continue;
                    else
                    {
                        return;
                    }
                }
            }
        }
        MIN=min(now,MIN);
        return;

    }
    DFS(depth+1,sum);
    if(ai[1][depth]==0)
    {
        ai[1][depth]=1;
        DFS(depth+1,sum+1);
        ai[1][depth]=0;
    }

}
void play(int Case)
{
    MIN=1000000000;
    DFS(1,0);
    if(MIN==1000000000)MIN=-1;
    printf("Case %d: %d\n",Case,MIN);
}
int Case;
int main()
{   Case=1;
    scanf("%d",&T);
    while(T--)
    {
        init();
        play(Case);
        Case++;
    }
    //cout << "Hello world!" << endl;
    return 0;
}