飞机票：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;
}

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

题意：就是找两个点，使得路径上的点最多。

分析：刚看不知道从何下手，再仔细看看note就好了，note前半部分就是说图是连通的，因为说点是直接或则间接相连的，后半部分说明图没有环，因为说如果出去之后要回原来的点，必须经过一条至少两次。有这个的话就可以知道给的图是颗树，然后求树上两点之间的点数最多，即距离最大。那么可以用树形DP，假设当前的点为k，它的子树最大的深度为i和j，那么就可以知道当前的路径为i和j之间的和再加1（k这个点），然后更新MAX，然后把k和最大的子树路径递归上去，用来更新k的父节点就可以了，然后最后要判断MAX是否大于7，最后啪啪啪就可以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=1234;
vector<int> V[maxn];
int n,m;
void init()
{
    for(int i=1; i<=n; i++)V[i].clear();
    int u,v;
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        u++;
        v++;
        V[u].push_back(v);
        V[v].push_back(u);
    }
}
bool cmp(int a,int b)
{
    return a>b;
}
int MAX;
int DFS(int now,int fa)
{
    vector<int> need;
    need.push_back(0);
    need.push_back(0);
    for(int i=0; i<V[now].size(); i++)
    {
        int u=V[now][i];
        if(u==fa)continue;
        int p=DFS(u,now);
        need.push_back(p);
    }
    sort(need.begin(),need.end(),cmp);
    MAX=max(MAX,need[0]+need[1]+1);
    return need[0]+1;
}
void play()
{
    MAX=0;
    DFS(1,-1);
    if(MAX<7)printf("Impossible\n");
    else printf("%d\n",MAX);
}

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?problemId=3127

题意：给你n个人n<=100，m辆车，n<=m<=100，然后给你n+m个坐标代表人和车的位置，最后再给你个速度v,求出最少的时间，使得每个人都有一辆车。(其中每个人都是同步进行的)

分析：这种题的话，就是相当于把n个人匹配到m辆车的n辆中，可以用二分图匹配算法，匈牙利的话是O（VE）那怎么求这个最少时间呢，其实可以二分求，然后每次二分的时间t，我们可以用O（nm）的时间，求的用t的时间，n个人可以和m辆车的哪几辆匹配，然后建图，跑一边匈牙利，如果可以最大匹配的话，那么这个时间是ok的，那么我们把上限变为t-0.001，因为要保留两位小数，反之把下限变为t+0.001，继续二分，最后输出答案即可。复杂的为logT*(n*m+VE),还是ok的，因为n和m比较小，最后啪啪啪就可以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=123;
struct he
{
    double x,y;
} Sky[2][maxn];
int n,m;
double ai[maxn][maxn];
double l,r;
double calT(int i,int j,double v)
{
    double dis=sqrt((Sky[0][i].x-Sky[1][j].x)*(Sky[0][i].x-Sky[1][j].x)+(Sky[0][i].y-Sky[1][j].y)*(Sky[0][i].y-Sky[1][j].y));
    return dis/v;
}
void init()
{
    for(int i=1; i<=n; i++)scanf("%lf%lf",&Sky[0][i].x,&Sky[0][i].y);
    for(int i=1; i<=m; i++)scanf("%lf%lf",&Sky[1][i].x,&Sky[1][i].y);
    double v;
    scanf("%lf",&v);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            ai[i][j]=calT(i,j,v);
        }
    }
    r=2000000.0/v;

}
bool bi[maxn][maxn];
int Link[maxn];
bool vis[maxn];
bool DFS(int now)
{
    for(int i=1; i<=m; i++)
    {
        if(bi[now][i]&&!vis[i])
        {
            vis[i]=1;
            if(Link[i]==0||DFS(Link[i]))
            {
                Link[i]=now;
                return true;
            }
        }
    }
    return false;
}
void play()
{
    double MIN=r;
    l=0;
    while(l<=r)
    {
        double mid=(l+r)/2;
        memset(bi,0,sizeof(bi));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(ai[i][j]<=mid)bi[i][j]=1;
            }
        }
        memset(Link,0,sizeof(Link));
        bool flag=1;
        for(int i=1; i<=n; i++)
        {
            memset(vis,0,sizeof(vis));
            if(DFS(i))continue;
            flag=0;
            break;
        }
        if(flag)
        {
            MIN=min(MIN,mid);
            r=mid-0.001;
        }
        else
        {
            l=mid+0.001;
        }

    }
    printf("%.2f\n",MIN);

}
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?problemId=3221

题意：就是给你6个正整数，前面三个是结果的数字，后面三个是起始的数字，我们可以从起始的数据选择一个数，然后删除它，用另外两个的和减去以代替，然后一直反复，看能否到达结果的三个数字。

分析：这种题一看，如果从初始状态推结果状态是很复杂的，因为每一次都有3个数字可以选择，所以复杂度肯定太高了，所以考虑用结果的三个数字推初始数据，因为假设结果数字为a1 a2 a2且a1<a2<a3，如果a1+a2-1=a3，说明a3是推过来的，所以可以把a3改回原来的数字，假设为a'3，那么a'3怎么算呢，因为我们知道现在a2最大，那么可以以为a1+a'3-1=a2,所以a'3=a2-a1+1,所以把a3换了，然后一直重复看看，能不能推到起始的三个数字。这里如果我们有a1+a2-1=a3的话，那么我们只要a1和a2能找到2个数字一样就可以了。因为a3可以变为任意数，然后的话如果a1+a2-1!=a3,那么特殊处理一下就行了，记得循环终止，如果a1+a2-1恒等于a3的时候，那么就可以终止了，因为死循环了，最后啪啪啪就可以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;
int ai[4],bi[4],T;
void init()
{
    for(int i=1; i<=3; i++)scanf("%d",&ai[i]);
    for(int i=1; i<=3; i++)scanf("%d",&bi[i]);

}
bool vis[4];
void play()
{
    while(1)
    {
        sort(ai+1,ai+4);
        sort(bi+1,bi+4);
        if(ai[1]+ai[2]-1!=ai[3])
        {
            if(ai[1]==bi[1]&&ai[2]==bi[2]&&ai[3]==bi[3])
            {
                printf("Yes\n");
                return;
            }
            else
            {
                printf("No\n");
                return;
            }
        }
        int sum=0;
        vis[1]=vis[2]=vis[3]=0;
        for(int i=1; i<=2; i++)
        {
            for(int j=1; j<=3; j++)
            {
                if(ai[i]==bi[j]&&!vis[j])
                {
                    vis[j]=1;
                    sum++;
                }
            }
        }
        if(sum>=2)
        {
            printf("Yes\n");
            return;
        }
        ai[3]=ai[2]+1-ai[1];
        if(ai[1]==1&&ai[2]==ai[3])break;

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

飞机票：http://acm.hdu.edu.cn/showproblem.php?pid=5277

题意：就是给你n个点n个坐标xi,yi(1<=i<=n)，然后给你m条边，表示u和v相连,保证没重边，也保证没有边相交。然后 让你求最大的点子集，使里面的点可以两两相连(不是图相连，线段相连)，且求处个数。

分析:其实分析分析，就发现最大就只有4个点的点急，因为5个点就会有边相交，与题目不符，所以只要枚举到4个点就行了，具体怎么枚举才比较好？可以先枚举两两的，就是加入i和j有边相连，就把i和j算一对保存起来，这样我们就知道两两相连的子集个数有多少个了，怎么枚举三个的，很简单，只要把两个相连的与一个个点比较，只要这两个点能同事与第三个点连接，那么就是ok的，这里注意：假设i和j和k是属于三个相连的，我们求出来两两的就是(i,j)(i,k)(j,k)然后枚举三个点的时候会有三种方法，但是实际上就只有1种，所以答案要/3，这样我们就知道三个点的自己个数了，现在是四个点了，四个点也很方便，只要把两个点的两两进行判断就行了，只要互不相同然后互相连接就可以了，但是要注意:假设我们i，j，p,q，是四个相连的点集，那么我们两两求出来的就是(i,j)(i,p)(i,q)(j,p)(j,q)(p,q)，这样的话，他们两两按数序的话会求出来三组，因为我们重复计算了，所以答案要/3到此为止，所有的都已经判断了， 按照4,3,2,1只要有一个是满足的，直接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=1234;
int x[maxn],y[maxn];
int ai[maxn][maxn];
int n,m;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d%d",&x[i],&y[i]);
    int u,v;
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        ai[u][v]=ai[v][u]=1;
    }
}
int bi[maxn*maxn][2];
void play()
{
    if(m==0)
    {
        printf("1 %d\n",n);
        return;
    }
    if(m==1)
    {
        printf("2 1\n");
        return ;
    }
    int st=1;
    int sum2=0;
    //判断连通性
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            if(ai[i][j])
            {
                bi[st][0]=i;
                bi[st][1]=j;
                st++;
                sum2++;
            }
        }
    }
    int sum3=0;
    //判断三个点的
    for(int i=1; i<st; i++)
    {
        for(int j=1; j<=n; j++)
        {
            int u=bi[i][0];
            int v=bi[i][1];
            if(ai[u][j]&&ai[v][j])
            {
                sum3++;
            }
        }
    }
    int sum4=0;
    //判断四个点的
    for(int i=1; i<st; i++)
    {
        for(int j=i+1; j<st; j++)
        {
            int u1=bi[i][0];
            int u2=bi[i][1];
            int v1=bi[j][0];
            int v2=bi[j][1];
            if(u1!=v1&&u1!=v2&&u2!=v1&&u2!=v2&&ai[u1][v1]&&ai[u1][v2]&&ai[u2][v1]&&ai[u2][v2])sum4++;
        }
    }
    if(sum4!=0)
    {
        printf("4 %d\n",sum4/3);

    }
    else if(sum3!=0)
    {
        printf("3 %d\n",sum3/3);
    }
    else if(sum2!=0)
    {
        printf("2 %d\n",sum2);
    }


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