飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2029

题意：就是给你n个数，和m个查询，每个查询有个数q.从n个数选两个数，假设为a,b(a<b)，使得q在区间[a,b)内。并且要求这个b-a最小。

分析：起先要是b-a最小又要包含t。我们可以将n个数排序，然后取两个数a,b,使得，a<=t<b，并且a和b越接近越好，为什么呢？因为越接近的话b-a就越小，因为我们排了序。然后具体a和b我们可以二分查找位置，然后特殊情况稍微处理一下就可以了，最后啪啪啪就可以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 LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
vector<int> V;
int n,m;
void init()
{
    V.clear();
    int u;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&u);
        V.push_back(u);
    }
    sort(V.begin(),V.end());
}

void play()
{
    int t;
    while(m--)
    {
        scanf("%d",&t);
        int pos1=lower_bound(V.begin(),V.end(),t)-V.begin();
        int pos2=upper_bound(V.begin(),V.end(),t)-V.begin();
        if(pos1==n||pos2==n)
        {
            printf("no such interval\n");
            continue;
        }
        if(pos1!=pos2)
        {
            printf("[%d,%d)\n",V[pos1],V[pos2]);
            continue;
        }
        if(pos1==0)
        {
            printf("no such interval\n");
            continue;
        }
        printf("[%d,%d)\n",V[pos1-1],V[pos1]);

    }
    printf("\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3890

题意：有个人站在(0,0)位置，然后给你n*n的地图，其中地图中有黄金，怪物，坑，平地，因为题目简化了，坑不能进，怪物的地方不能进，黄金只有1块。人物的动作可以是转向，向前，挖金子，从(0,0)点出来，其中每个动作要花费10点的值，黄金值1000点值。求出来之后最大的值是多少.

分析：一看n<=20，且方向就只有4个，那么可以建立vis[20][20][4]的数组进行BFS模拟。

(1)由于数据非常小，所以我考虑到一点事情，就是如果黄金在sx,sy上，然后我们到达sx,sy,方向为1的值和到达sx,sy方向为2的值相同，然后从1到(0,0）比从2到(0,0)慢，那么如果我们到达1的时候就结束BFS，那么答案就错了，所以我是枚举到达sx,sy四个方向的值，然后再从这四个方向继续BFS回到(0,0)，然后求出最小值就好，其中一些细节不符合条件的直接输出-1就好。虽然代码有点长，但是也不是特边复杂

（2）可以直接打标记，就是假设黄金在sx，sy，如果到了sx，sy，那么直接标记拿到了黄金，最后到了(0,0)之后，如果拿到了黄金那么就是最优值，这样代码就边的比较短了

最后啪啪啪就可以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 LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
struct he
{
    int x,y,d,val;
};
const int maxn=2*12;
int ai[maxn][maxn];
bool vis[maxn][maxn][5];
int n,T;
int ex,ey;
void init()
{
    scanf("%d",&n);
    memset(ai,0,sizeof(ai));
    for(int i=0; i<=n; i++)ai[0][i]=ai[i][0]=ai[n+1][i]=ai[i][n+1]=2;
    int u,v,w;
    while(scanf("%d%d%d",&u,&v,&w)!=EOF&&u!=-1)
    {

        v++;
        w++;
        if(u==3)
        {
            ex=v;
            ey=w;
        }
        ai[v][w]=u;
    }
}
pair<int,int> calD(int d,int x,int y)
{
    if(d==1)return make_pair(x+1,y);
    if(d==2)return make_pair(x,y+1);
    if(d==3)return make_pair(x-1,y);
    if(d==4)return make_pair(x,y-1);
}
int BFS1(int dd)
{
    memset(vis,0,sizeof(vis));
    queue<he> Q;
    Q.push((he)
    {
        1,1,1,0
    });
    vis[1][1][1]=1;
    while(!Q.empty())
    {
        he now=Q.front();
        Q.pop();
        int nx=now.x;
        int ny=now.y;
        int nd=now.d;
        int nv=now.val;
        if(ai[nx][ny]==3&&nd==dd)
        {
            return nv;
        }
        pair<int,int> need=calD(nd,nx,ny);
        int x=need.first;
        int y=need.second;
        if(ai[x][y]!=1&&ai[x][y]!=2&&!vis[x][y][nd])
        {
            vis[x][y][nd]=1;
            Q.push((he)
            {
                x,y,nd,nv+10
            });
        }
        int d=nd+1;
        if(d==5)d=1;
        if(!vis[nx][ny][d])
        {
            vis[nx][ny][d]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10
            });
        }
        d=nd-1;
        if(d==0)d=4;
        if(!vis[nx][ny][d])
        {
            vis[nx][ny][d]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10
            });
        }
    }
    return -1;

}
int BFS2(int x1,int y1,int dd)
{
    memset(vis,0,sizeof(vis));
    vis[x1][y1][dd]=1;
    queue<he> Q;
    Q.push((he)
    {
        x1,y1,dd,0
    });
    while(!Q.empty())
    {
        he now=Q.front();
        Q.pop();
        int nx=now.x;
        int ny=now.y;
        int nd=now.d;
        int nv=now.val;
        if(nx==1&&ny==1)
        {
            return nv;
        }
        pair<int,int> need=calD(nd,nx,ny);
        int x=need.first;
        int y=need.second;
        if(ai[x][y]!=1&&ai[x][y]!=2&&!vis[x][y][nd])
        {
            vis[x][y][nd]=1;
            Q.push((he)
            {
                x,y,nd,nv+10
            });
        }
        int d=nd+1;
        if(d==5)d=1;
        if(!vis[nx][ny][d])
        {
            vis[nx][ny][d]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10
            });
        }
        d=nd-1;
        if(d==0)d=4;
        if(!vis[nx][ny][d])
        {
            vis[nx][ny][d]=1;
            Q.push((he)
            {
                nx,ny,d,nv+10
            });
        }
    }
    return -1;

}
void play()
{
    if(ai[1][1]==1||ai[1][1]==2)
    {
        printf("-1\n");
        return;
    }
    int MAX=-1;
    for(int i=1; i<=4; i++)
    {
        int ng=BFS1(i);
        if(ng==-1)
        {
            printf("-1\n");
            return;
        }
        int nb=BFS2(ex,ey,i);
        MAX=max(MAX,1000-20-nb-ng);

    }
    printf("%d\n",MAX);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3888

题意：给你n年，其中有m中关系，Xi Yi，代表从第Xi年可以回到Yi年，其中 Xi>=Yi,然后给你Q个查询，每个查询一个年份q，问你从第q年，至少有两种方案可以回到q年之前的年份有多少年。然后后面就是给你解释，第q年可以等到q年之后然后在回到q年之前。或则直接走，但是m种关系在一条路径中只能用一次。

分析：假设当前查询的是q年，那么我们要知道我们能回到q年之前至少有两条路径有多少年，我们可以从q~n之间的最小Yi和次小Yi。为什么，因为q可以等到q~n之间的一年然后回到最小Yi，或则q可以等到q~n之间的一年然后回到次小Yi，这样就有两条路径可以回到Yi到q之间的年份，且因为次小Yi是第二小的，所以剩下的都大于次小Yi，所以次小Yi是最优的。那么就可以从后往前推，每次更新次小Yi。然后查询的话，如果次小Yi大于等于q，那么就是0，因为回不去，如果小于q,那么就可以会q-次小Yi年，这样的话就Ok了，最后啪啪啪就可以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 LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=5*12345;
struct he
{
    int x,y;
} Sky[maxn];
int n,m,q;
bool cmp(he a,he b)
{

    return a.x>b.x;
}
void init()
{
    for(int i=1; i<=m; i++)scanf("%d%d",&Sky[i].x,&Sky[i].y);
    sort(Sky+1,Sky+1+m,cmp);
}
int ai[maxn];
void play()
{
    memset(ai,0,sizeof(ai));
    int l1=-1,l2=-1;
    for(int i=1; i<=m; i++)
    {
        int now=Sky[i].x;
        int next=Sky[i].y;
        if(l1==-1)l1=next;
        else if(l2==-1)
        {
            if(l1>next)
            {
                l2=l1;
                l1=next;
            }
            else
            {
                l2=next;
            }
        }
        else
        {
            if(next<l1)
            {
                l2=l1;
                l1=next;
            }
            else if(next<l2)
            {
                l2=next;
            }
        }
        ai[now]=l2;
    }

    for(int i=n; i>=1; i--)
    {
        if(ai[i]==-1)continue;
        if(ai[i]==0)
        {
            ai[i]=ai[i+1];
        }
    }
    int t;
    while(q--)
    {
        scanf("%d",&t);
        if(ai[t]==-1||ai[t]==0)printf("0\n");
        else
        {
            if(ai[t]>=t)printf("0\n");
            else printf("%d\n",t-ai[t]);
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&q)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3885

题意：给你n对数据Ai，Bi，Ai代表没有当前值，Bi代表目标值，然后有m个交换，Xi，Yi，说名Xi可以变为Yi，或则Yi可以变为Xi，求最小的交换次数，使得n个数据到达目标值。

分析：一看就知道，假设p为Ai-Bi，如果p大于0，那么i这个点必须要交换掉p个数，如果p<0那么就说明i必须要得到p个数，这样的话，如果我们想知道有可行的方案使得在改变后Ai全都变为Bi，我们可以使用最大流，但是这里我们将p>o加到s1里去,p<0加到s2里去，比较s1和s2是否相等，因为不等的话就肯定跑不了。如果相同，具体怎么建图?p大于0，那么就从超级源点加一条流量为p的边到i，如果小于0，那么就从i加一条流量为p的边到超级汇点，然后根据m个可以交换的边，加m条从Xi到Yi的边，和Yi到Xi的边，因为是双向的，且容量为INF，因为没有限制。这样设最大流max_flow，如果max_flow和s1相等，那么就是可行的。关键题目让我们求最少的交换次数，具体的交换次数就是经过Xi和Yi这条边多少次。那么想到这，应该就知道了，可以用最小费用最大流，p大于0，那么就从超级源点加一条流量为p的边到i且花费为0，如果小于0，那么就从i加一条流量为p的边到超级汇点，花费也为0，具体就是m条边的花费，因为经过一次就要加一次交换次数，那么就是流量为INF，花费为1，这样跑一边，如果max_flow和s1相等，那么输出最小花费就是答案，最后啪啪啪就可以AC了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define forr(i,f_start,f_end) for(int i=f_start;i<f_end;++i)
#define mem(x,i) memset(x,i,sizeof(x))
const int maxn = 123;
const int maxm = 123 * 8;
typedef long long LL;
const int INF = 0xfffffff;
int input()
{
    int a;
    scanf("%d", &a);
    return a;
}
int Flow;
///-----------------最小费用流-----------------
//cost 代表一个流量要的费用 cap代表容量
//init 到N+2,如果超级汇点就是0，N+1
//else 就是s到t init到多少个点加1
struct Edge
{
    int to, next, cap, flow, cost;
} edge[maxm];
struct MCMF
{
    int head[maxn], tol;
    int pre[maxn], dis[maxn];
    bool vis[maxn];
    int N;
    void init(int n)
    {
        N = n;
        tol = 0;
        memset(head, -1, sizeof(head));
    }

    void addedge(int u, int v, int cap, int cost)
    {
        edge[tol].to = v;
        edge[tol].cap = cap;
        edge[tol].cost = cost;
        edge[tol].flow = 0;
        edge[tol].next = head[u];
        head[u] = tol++;
        edge[tol].to = u;
        edge[tol].cap = 0;
        edge[tol].cost = -cost;
        edge[tol].flow = 0;
        edge[tol].next = head[v];
        head[v] = tol++;
    }

    bool spfa(int s, int t)
    {
        queue<int>q;
        for (int i = 0; i<N; i++)
        {
            dis[i] = INF;
            vis[i] = false;
            pre[i] = -1;
        }
        dis[s] = 0;
        vis[s] = true;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            vis[u] = false;
            for (int i = head[u]; i != -1; i = edge[i].next)
            {
                int v = edge[i].to;
                if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
                {
                    dis[v] = dis[u] + edge[i].cost;
                    pre[v] = i;
                    if (!vis[v])
                    {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
        }
        if (pre[t] == -1) return false;
        else return true;
    }
    //返回的是最大流，cost存的是最小费用
    int minCostMaxflow(int s, int t, int &cost)
    {
        int flow = 0;
        cost = 0;
        while (spfa(s, t))
        {
            int Min = INF;
            for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to])
            {
                if (Min > edge[i].cap - edge[i].flow)
                    Min = edge[i].cap - edge[i].flow;
            }
            for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to])
            {
                edge[i].flow += Min;
                edge[i ^ 1].flow -= Min;
                cost += edge[i].cost*Min;
            }
            flow += Min;
        }
        return flow;
    }
} mcmf;
///-----------------------------------------
int N, M;
int main()
{
    while (scanf("%d%d", &N, &M)!=EOF)
    {
        mcmf.init(N+2);
        int cmp=0;
        int cmp1=0;
        for(int i=1; i<=N; i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            int p=a-b;
            if(p>0)
            {
                cmp+=p;
                mcmf.addedge(0,i,p,0);

            }
            else if(p<0)
            {
                cmp1-=p;
                mcmf.addedge(i,N+1,-p,0);
            }
        }
        int a,b;
        for(int i=1; i<=M; i++)
        {
            scanf("%d%d",&a,&b);
            mcmf.addedge(a,b,INF,1);
            mcmf.addedge(b,a,INF,1);
        }
        int cost;
        int Flow = mcmf.minCostMaxflow(0, N+1, cost);
        if(cmp1!=cmp||cmp!=Flow)printf("-1\n");
        else   printf("%d\n",cost);

    }
    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=967

题意：给你个有向图，每条有向边有字母标识，然后有查询，每个给你u，v，从u到v路径上出现了那些字母，并且字母必须在每条路径的边上。

分析：假设只有一个字母的话，那么就很简单，因为n不是特别大，如果u到v有字母，那么就标记u可以到v，接着直接flyod跑一边，接着查询，就可以根据flyod跑出来是否联通给出答案。那么因为这里是有26个字母，所以可以跑26次flyod，然后对于每次询问，对26个字母都进行一遍查找，最后输出就好。最后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
int n;
const int maxn=234;
int ai[27][maxn][maxn];
char ch[27];
void init()
{
    memset(ai,0,sizeof(ai));
    int u,v;
    while(scanf("%d%d",&u,&v)!=EOF&&u)
    {
        scanf("%s",ch+1);
        int len=strlen(ch+1);
        for(int i=1; i<=len; i++)
        {
            ai[ch[i]-'a'+1][u][v]=1;
        }

    }
    for(int l=1; l<=26; l++)
    {
        for(int k=1; k<=n; k++)
        {
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=n; j++)
                {
                    if(ai[l][i][k]&&ai[l][k][j])ai[l][i][j]=1;
                }
            }
        }
    }
}

void play()
{
    int u,v;
    while(scanf("%d%d",&u,&v)!=EOF&&u)
    {
        bool flag=1;
        for(int i=1; i<=26; i++)
        {
            if(ai[i][u][v])
            {
                printf("%c",'a'+i-1);
                flag=0;

            }
        }
        if(flag)printf("-");
        printf("\n");
    }
    printf("\n");
}
int main()
{

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

    }
    //   cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=995

题意：就是给你n个数，它们的和不超过1000，接着就是你可以选择加或则减，就是说初始值是0，然后n步，你可以选择加上第i个数，或则减掉第i个数，但是减掉的时候不能小于0。求最后的数字是0，且使的加到的最大值最小。求出这个路径。

分析：这个题，刚开始的想法是，先是想想加加减减看看最后能不能到达0，那么直接可以用dp，因为有加又有减，所以一维数组就很难维护了，这里我就用二维数组，dp[i][j]表示第i个数过后，能不能到达j这个高度，那么看最后能不能成为0，就是能不能到达dp[n][0]了这样可以轻易的求出能不能到达0，但是现在我们需要知道最大值最小，所以需要维护点东西，这里分2中情况（这里定义ai为第i个数的大小）

(1)假设i-1能到达j，那么i肯定能到达j+ai[i]，然后我们需要更新到达j+ai[i]的最大值，假设dp[i-1][j]为i-1过后，到达j的最大值的最小值，那么如果j+ai[i]>dp[i-1][j]的话，那么就得更新最大值的最小值，因为我们必须到达j+ai[i]，反之的话就是dp[i-1][j]，设这个值为qn，这个值是从dp[i-1][j]推过来的，所以更新dp[i][j+ai[i]]=min(dp[i][j+ai[i]],qn),这样高度最小

(2)假设i-1能到达j，且j-ai[i]>=0,那么肯定能到达j-ai[i],接着我们就可以根据第一种情况dp，但是有个地方不同，这里比较的是j和dp[i-1][j]，因为j-ai[i]<j;接着就是跟第一种情况一样,设这里的只为pn,则dp[i][j-ai[i]]=min(dp[i][j-ai[i]],pn),

根据这两种我们就知道最大值最小是什么样的情况，最后需要输出，只要用一个数组li来记录，具体怎么记录?第一种情况,如果dp[i][j+ai[i]]比原来的数要小，那么就是li[i][j+ai[i]]指向i-1的j，另一种情况就是li[i][j-ai[i]]只想i-1的j,最后反推就是答案了，然后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
int ai[maxn];
int dp[maxn][maxn];
int li2[maxn][maxn];
int T;
int n;
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
}
vector<int> V;
void play()
{
    for(int i=0; i<=n; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            if(dp[i-1][j]==INF)continue;
            int q=j+ai[i];
            int p=j-ai[i];
            int qn=max(dp[i-1][j],q);
            if(q<=1000&&qn<dp[i][q])
            {
                dp[i][q]=qn;
                li2[i][q]=j;
            }
            int pn=max(dp[i-1][j],j);
            if(p>=0&&pn<dp[i][p])
            {
                dp[i][p]=pn;
                li2[i][p]=j;
            }
        }
    }
    if(dp[n][0]!=INF)
    {
        V.clear();
        V.push_back(2);
        int st=n-1;
        int now=li2[n][0];
        while(st>=1){
            int next=li2[st][now];
            int ff=now-next;
            if(ff>0)V.push_back(1);
            else V.push_back(2);
            st--;
            now=next;
        }
        bool first=1;
        for(int i=V.size()-1;i>=0;i--){
            if(V[i]==1)printf("U");
            else printf("D");
        }
        printf("\n");
    }
    else
    {
        printf("IMPOSSIBLE\n");
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1158

题意：就是给你n个字母，每个字母由7个字符组成，且都是小写字母，而且不相等，每个字母有一个父亲，且到父亲的距离是跟父亲位置相同字母不同的位置数量，且根节点没有父亲，求距离和最小。

分析：一看，每个节点有个父亲，那么就是一棵树，且距离可以直接定义为父节点到自己点的边长距离，那么要求n-1条边的距离和最小，直接用最小生成树算法即可，我们只要预处理出每对的距离，然后用prim算法即可，因为是稠密图，prim跑得比较优秀，如果是稀疏图，那么直接就kruskal。总体复杂就是，距离n*n*7,prim算法为n*n，所以复杂的为O(n*)n,最后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=2*1234;
char ch[maxn][10];
int n;
bool vis[maxn];
void init()
{
    for(int i=1; i<=n; i++)scanf("%s",ch[i]+1);
}
short dist[maxn][maxn];
short low[maxn];
void play()
{
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        dist[i][i]=0;
        for(int j=i+1; j<=n; j++)
        {
            int sum=0;
            for(int k=1; k<=7; k++)
            {
                if(ch[i][k]!=ch[j][k])sum++;
            }
            dist[i][j]=dist[j][i]=sum;
        }

    }
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    int pos=1;
    for(int i=2; i<=n; i++)
    {
        low[i]=dist[1][i];
    }

    for(int i=1; i<n; i++)
    {
        int MIN=INF;
        int idx=-1;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j]&&MIN>low[j])
            {
                MIN=low[j];
                idx=j;
            }
        }
        ans+=MIN;
        vis[idx]=1;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j]&&low[j]>dist[idx][j])
            {

                low[j]=dist[idx][j];
            }
        }
    }
    printf("The highest possible quality is 1/%d.\n",ans);
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5264

题意：给你n个题目，每个题目放在第i个位置有个值，有个程序可以随机生成1~n的排列，求生成的排列值大于m的期望次数

分析：这里的话需要推一下公式，需要用到极限的定理，因为假设n!种方案里，可行的方案概率为p，不可行为q(即1-p),则期望次数为

limn->无穷p*q^0*1+p*q^1*2+p*q^2*3....+p*q^(n-1)*n这个极限怎么求是关键，这里可以用错位相减法，即将式子乘以q,则为

qlimn->无穷                p*q^1*1+p*q^2*2....+p*q^(n-1)*(n-1)+p*q^(n)*n，然后两式一减，为(1-q)limn->无穷p+p*q^1+p*q^2...p*q^(n-1)-p*q^n*n,等比求和，即limn->无穷p*(1-q^n)/(1-q)-p*q^(n)*n,求极限后为可知这个极限为1/(1-q)即1/p，所以期望的次数是1/p，现在要求的是满足大于等于m的排列有多少个，因为n最大只有12，所以可以用状态压缩，最大也就只有4095,具体怎么搞？假设当前要确定的是第i个位置的数字，然后假设第j个题目放在第i个位置，那么我们可以去找i-1个位置，因为i-1个位置可以用二进制表示，所以可以很快找到然后把i-1个位置里面的值加上j在第i个的值，最后的话，大于等于m的方案数就是我们要求的复杂度O(n*n*2^n),最后啪啪啪就可以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 LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=13;
int C[maxn];
int ai[maxn][maxn];
int bi[5000][567];
int n,m,T;
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)scanf("%d",&ai[i][j]);
}
int gcd(int a,int b)
{
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(b,a%b);
}
void play()
{
    memset(bi,0,sizeof(bi));
    bi[0][0]=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int k=1; k<C[n]; k++)
            {
                int t=k;
                bool flag=1;
                int q=0;
                for(int l=n-1; l>=0; l--)
                {
                    if(l+1==j&&t-C[l]<0)
                    {
                        flag=0;
                        break;
                    }
                    if(t-C[l]>=0)
                    {
                        t-=C[l];
                        q++;
                    }
                }
                if(q!=i)flag=0;
                if(flag)
                {
                    for(int l=0; l<=500; l++)
                    {
                        int now=l+ai[j][i];
                        if(now>500)now=500;
                        bi[k][now]+=bi[k-C[j-1]][l];
                    }
                }
            }.
        }
    }
    int fz=0;
    int fm=1;
    for(int i=m; i<=500; i++)fz+=bi[C[n]-1][i];
    for(int i=1; i<=n; i++)fm*=i;
    if(fz==0)printf("No solution\n");
    else
    {
        int p=gcd(fz,fm);
        printf("%d/%d\n",fm/p,fz/p);
    }
}
int main()
{
    C[0]=1;
    for(int i=1; i<=12; i++)C[i]=C[i-1]*2;
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }

    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5231

题意：给你个数n,求最少的数,假设为a1...ak, 1+2+3...+a1+1+2+3+..a2.....+ak=n

分析：这题乍一看没有任何想法，但是我们可以暴力搜下，发现前100000最多只有3个，那么我们可以直接猜测最多只有三个，那么就可以开始搞了，先求出从1+2+。。。k>=123456789最大的n是多少，加入只有一个，直接二分查找，如果找不到，那么就尝试2个的，两个的话可以用夹逼定理，假设左边为1，右边为k，如果a1+ak>n那么就是太大了，r--,如果是<n,那么就是太小了l++，等于的话就说明2个可以，如果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;
int ai[16000];
int T,n;
int st;
void init()
{
    scanf("%d",&n);
}
int l,r;
bool Brsearch(int p)
{
     l=1;
     r=st-1;
    while(l<=r)
    {
        int ok=ai[l]+ai[r];
        if(ok==p)return 1;
        if(ok<p)l++;
        else r--;
    }
    return 0;

}
void play()
{
    int pos=lower_bound(ai+1,ai+st,n)-ai;
    if(ai[pos]==n)
    {
        printf("%d\n",pos);
        return;
    }
    if(Brsearch(n)){
        printf("%d %d\n",l,r);
        return;
    }
    for(int i=1;i<=n;i++){
        if(n>=ai[i]&&Brsearch(n-ai[i])){
            printf("%d %d %d\n",i,l,r);
            return;
        }
    }
}
int main()
{
    st=1;
    LL now=0;
    while(now<=123456789)
    {
        now+=st;
        ai[st]=now;
        st++;

    }

    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    return 0;
}

飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5299

题意：给你n，k，m和两个长度为n的只包含'0'和'1'的字符串，给你k步，每步要正好改变s1字符串m个位置,使得k步后s1和s2相等，问总共有多少中方法，取模输出。

分析：这种题一看，以为是按字符串DP，其实发现如果按字符串DP 那复杂度就太大了我们发现字符串就只有0，1，所以可以按状态来DP，具体DP 的话，假设当前为第i步，我们需要去m个位置，具体m个位置我们可以，不一样的位置取j个，那么一样的位置就是m-j个，然后从i-1进行迭代。如果i-1存在不同位置有x个，相同位置 为n-x个，如果x>=j&&n-x>=m-j，且这个方法是可以行的通的，i-1时的方法数为ans,那么我们就可以从x里面取j个，n-x取m-j个，这里的话是组合所以我们可以预处理出C[100][100]，最后答案怎么算呢？仔细想想就会有思路，因为x里去了j个，所以剩下不一样的位置为x-j个，但是一样的位置里面取了,m-j个，最后剩下的不一样的位置 有x-j+m-j个同理，一样的位置有n-x-(m-j)+j个，假设为j为js，m-j为os,x为js1，n-x为os1，且更新后的为x-j+m-j为njs，n-x-(m-j)+j为nos,则状态方程为 ai[i][njs][nos]+=ai[i-1][js1][os1]*C[js1][js]*C[os1][os];记得取模，复杂度为n^3,最后啪啪啪就可以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 MOD=1000000009;
const int maxn=123;
LL ai[maxn][maxn][maxn];
LL C[maxn][maxn];
char ch1[maxn],ch2[maxn];
int n,k,m;
void init()
{
    int diff=0;
    scanf("%s%s",ch1+1,ch2+1);
    int len=strlen(ch1+1);
    for(int i=1; i<=len; i++)
    {
        if(ch1[i]!=ch2[i])diff++;
    }
    memset(ai,0,sizeof(ai));
    ai[0][diff][len-diff]=1;
}
void play()
{

    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<=m; j++)
        {
            int js=j;
            int os=m-j;
            for(int l=js; l<=100; l++)
            {
                int js1=l;
                int os1=n-l;
                if(os1<0)break;
                if(js1>=js&&os1>=os&&ai[i-1][js1][os1]>0)
                {
                    int njs=js1-js;
                    njs+=os;
                    int nos=os1-os;
                    nos+=js;
                    ai[i][njs][nos]+=((ai[i-1][js1][os1]*C[js1][js]%MOD)*C[os1][os]%MOD);
                    ai[i][njs][nos]%=MOD;
                }

            }
        }
    }
    printf("%lld\n",ai[k][0][n]);
}
int main()
{
    C[0][0]=1;
    for(int i=0; i<=100; i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1; j<i; j++)
        {
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
    }

    while(scanf("%d%d%d",&n,&k,&m)!=EOF)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}