/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define INF 1e-9
using namespace std;
const int maxn=1234;
int n;
double ai[maxn][maxn];
double bi[maxn][maxn*2];
double ans[maxn];
void init()
{
    memset(ai,0,sizeof(ai));
    memset(bi,0,sizeof(bi));
    ai[0][0]=1;
    for(int i=1; i<=2*1000; i++)
    {
        //w
        for(int j=1; j<=i; j++)
        {
            int w=j;
            int b=i-j;
            if(w<=1000&&b<1000)
            {
                ai[w][b]+=(ai[w-1][b]/2.0);
                if(w>b)
                bi[w][w+b]+=(ai[w-1][b]/2.0);
            }
        }
        //b
        for(int j=1; j<=i; j++)
        {
            int w=i-j;
            int b=j;
            if(b<=1000&&w<1000)
            {
                ai[w][b]+=(ai[w][b-1]/2.0);
                if(b>w)
                bi[b][w+b]+=(ai[w][b-1]/2.0);
            }
        }
    }

    for(int i=1; i<=1000; i++)
    {
        double tm=0;
        for(int j=0; j<=i*2; j++)
        {
            tm+=bi[i][j]*j;
        }
        ans[i]=tm;
    }

}

void play()
{
    scanf("%d",&n);
    printf("%.2f\n",ans[n]);


}
int T;
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {

        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}
/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define INF 1e9
#define INF 1e-9
using namespace std;
const int maxn=1234;
int n;
double ai[maxn][maxn];
double ans[maxn];
void init()
{
    memset(ai,0,sizeof(ai));
    for(int i=0; i<=1000; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            int w=i;
            int b=j;
            if(w==0&&b==0)ai[i][j]=1;
            else
            {
                if(w!=0)
                {
                    ai[w][b]+=(ai[w-1][b]/2.0);
                }
                if(b!=0)
                {
                    ai[w][b]+=(ai[w][b-1]/2.0);
                }
                if(w>b)
                {
                    ans[w]+=(ai[w-1][b]/2.0)*(w+b);
                }
                if(b>w)
                {
                    ans[b]+=(ai[w][b-1]/2.0)*(w+b);
                }
            }
        }
    }
}

void play()
{
    scanf("%d",&n);
    printf("%.2f\n",ans[n]);


}
int T;
int main()
{
    init();
    scanf("%d",&T);
    while(T--)
    {

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

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=123;
//bool isC[maxn][maxn];
vector<int> V[maxn];
int n,E;
void init(){
    for(int i=1;i<=100;i++)V[i].clear();
    int u,v;
  //  memset(isC,0,sizeof(isC));
    for(int i=1;i<=n;i++){
        scanf("%d%d",&u,&v);
        if(u==v)continue;
        V[u].push_back(v);
     //   isC[u][v]=1;
    }
    /*for(int k=1;k<=100;k++){
        for(int i=1;i<=100;i++){
            for(int j=1;j<=100;j++){
                if(isC[i][k]&&isC[k][j])isC[i][j]=1;
            }
        }
    }*/
    scanf("%d",&E);
}
bool flag;
bool vis[maxn];
void DFS(int now){
    if(flag)return;
    for(int i=0;i<V[now].size();i++){
        int v=V[now][i];
        if(vis[v]){
            flag=1;
            return;
        }
        vis[v]=1;
        DFS(v);
        vis[v]=0;
    }
}
void play(){
    flag=0;
    memset(vis,0,sizeof(vis));
    vis[E]=0;
    DFS(E);
    if(flag)printf("No\n");
    else printf("Yes\n");
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        if(n<0)break;
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=3*12345;
struct he
{
    int l,r;
    LL lazy;
    LL sum;
} Sky[maxn*4];
void BuildTree(int l,int r,int now)
{
    Sky[now].l=l;
    Sky[now].r=r;
    Sky[now].lazy=0;
    Sky[now].sum=0;
    if(l==r)return;
    int mid=(l+r)/2;
    BuildTree(l,mid,now*2);
    BuildTree(mid+1,r,now*2+1);
}
void Push(int now)
{
    if(Sky[now].lazy==0)return;
    int nl=Sky[now].l;
    int nr=Sky[now].r;
    if(nl==nr)return;
    LL v=Sky[now].lazy;
    int mid=(nl+nr)/2;
    Sky[now*2].lazy=v;
    Sky[now*2].sum=v*(mid-nl+1);
    Sky[now*2+1].lazy=v;
    Sky[now*2+1].sum=v*(nr-mid);
    Sky[now].lazy=0;
}
void Update(int l,int r,int now,LL val)
{
    if(Sky[now].l==l&&Sky[now].r==r)
    {
        Sky[now].lazy=val;
        Sky[now].sum=val*(r-l+1);
        return;
    }
    int mid=(Sky[now].l+Sky[now].r)/2;
    if(r<=mid)
    {
        Update(l,r,now*2,val);
    }
    else if(l>mid)
    {
        Update(l,r,now*2+1,val);
    }
    else
    {
        Update(l,mid,now*2,val);
        Update(mid+1,r,now*2+1,val);
    }
    Sky[now].sum=Sky[now*2].sum+Sky[now*2+1].sum;

}
LL Query(int l,int r,int now)
{
    if(Sky[now].l==l&&Sky[now].r==r)
    {

        return Sky[now].sum;
    }
    int mid=(Sky[now].l+Sky[now].r)/2;
    LL o1=0;
    LL o2=0;
    Push(now);
    if(r<=mid)
    {
        o1=Query(l,r,now*2);
    }
    else if(l>mid)
    {
        o2=Query(l,r,now*2+1);
    }
    else
    {
        o1=Query(l,mid,now*2);
        o2=Query(mid+1,r,now*2+1);
    }
    return o1+o2;

}
int n,m;
LL Calc(LL val, int dn, bool isok)
{
    if(val>=0){
        int p=val/dn;
        if(isok)return p+1;
        else return p;
    }
    else{
        int p=val/dn;
        if(isok)return p;
        else return p-1;
    }
}

void init()
{
    BuildTree(1,n,1);
    int t;
    LL sum=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&t);
        Update(i,i,1,t);
        sum+=t;
    }
    int l,r;
    while(m--)
    {
        scanf("%d%d",&l,&r);
        if(l>r)swap(l,r);
        LL p=Query(l,r,1);
        int len=(r-l+1);
        if(p%len==0)
        {
            Update(l,r,1,p/len);
        }
        else
        {
            if(Sky[1].sum<=sum)
            {
            Update(l,r,1,Calc(p,r-l+1,1));
            }
            else
            {
                Update(l,r,1,Calc(p,r-l+1,0));
            }
        }
    }
}

void play()
{
    bool first=1;
    for(int i=1; i<=n; i++)
    {
        LL p=Query(i,i,1);
        if(!first)printf(" ");
        first=0;
        printf("%lld",p);
    }
    printf("\n");
    printf("\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=8*12345;
bool isP[maxn];
int n;
const int MOD=1000000007;
LL ai[2][maxn];
LL sum[maxn];
int bi[maxn];
int E;
void init()
{
    memset(isP,0,sizeof(isP));
    isP[1]=1;
    for(int i=2; i<=80000; i++)
    {
        if(isP[i])continue;
        for(int j=i+i; j<=80000; j+=i)
        {
            isP[j]=1;
        }
    }

    E=0;
    for(int i=1; i<=80000; i++)
    {
        if(isP[i])
        {
            isP[i]=0;
            continue;
        }
        isP[i]=1;
        E++;
        bi[E]=i;
    }

    memset(ai,0,sizeof(ai));
    for(int i=1; i<=E; i++)
    {
        for(int j=i; j<=E; j++)
        {
            LL t1=bi[i];
            LL t2=bi[j];

            if(t1+t2<=80000)
            {
                ai[0][t1+t2]=(ai[0][t1+t2]+1);
            }
            if(t1*t2<=80000)
            {
                ai[1][t1*t2]=(ai[1][t1*t2]+1);
            }
        }
    }
}
int k;
void play()
{
    sum[k]=0;
    sum[k]+=isP[k];
    LL p=(ai[0][k]+ai[1][k]);
    sum[k]=(sum[k]+p)%MOD;
    LL n1=0;
    LL n2=0;
    for(int i=1; i<=E; i++)
    {
        if(bi[i]>=k)break;
        int t=k-bi[i];
        if(t%2==0)
        {
            int q=t/2;
            if(q==bi[i])
            {
                n1+=2;
            }
            else n1+=isP[q];
        }
        n1=(n1+ai[0][t]);
        n2=(n2+ai[1][t]);
        int q=k%bi[i];
        if(q==0)
        {
            t=k/bi[i];
            int q=sqrt(t);
            if(q*q==t)
            {
                if(q==bi[i])
                {
                    n1+=2;
                }
                else n1+=isP[q];
            }
            n1=(n1+ai[1][t]);
        }
    }
    n1=n1/3;
    sum[k]=(sum[k]+n1);
    sum[k]=(sum[k]+n2);
    printf("%lld\n",sum[k]);
}
int main()
{
    init();
    while(scanf("%d",&k)!=EOF)
    {
        play();
    }
    return 0;
}

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

题意：就是给你n行，第i行有i个字符，字符可以是'@','*','?'，其中需要确定?的值，根据题目的4中限制，使得得到@最多，或则@最少，输出这个值。

分析：看一下这4种类型可以知道，假设为2行，第一行一个字符，第二行两个，所以我们可以知道无论第一行是什么，第二行都必须是@*或则*@，这样的话我们就知道，假设在第k行，有k个字符，如果第j个字符是@,那么第j-1是*,j+1也是*,然后根据j-1和j+1可以继续第k行剩下的数据。所以，假设第k行都是?，那么如果k%2==0，那么@和*只能平分。反之，设得到@最多为MAX，最少为MIN，那么，MAX多加个1，因为有k/2个*和k/2+1个@,MIN 的话就是k/2个@和k/2+1个*。如果第k行第i个是*，那么可知包含*的话，前面有i个字符，后面有af=k-i+1个字符，那么我们就可以知道MAX和MIN就都得有i/2个和af/2个，因为第i个是*，所以不用管是否奇偶。反之，一样MAX和MIN就都得有i/2个和af/2个，但是这里就得再考虑，如果i是奇数，那么我们得再加个1，因为i也是，如果af是奇数，同理，但是我们这里多记了1次i这个位置，所以都要减1。最后输出MAX和MIN就好了，啪啪啪就可以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;
char ch[maxn];
int n;
int MAX,MIN;
void init()
{
    MAX=0;
    MIN=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%s",ch+1);
        bool flag=1;
        for(int j=1; j<=i; j++)
        {
            int af=i-j+1;
            if(ch[j]=='*')
            {
                flag=0;
            }
            if(ch[j]=='@')
            {
                if(j%2==1)
                {
                    MAX++;
                    MIN++;
                }
                if(af%2==1)
                {
                    MAX++;
                    MIN++;
                }
                MAX-=1;
                MIN-=1;
                flag=0;
            }
            if(!flag)
            {
                MAX+=j/2;
                MIN+=j/2;
                MAX+=af/2;
                MIN+=af/2;
                break;
            }
        }

        if(flag)
        {
            MAX+=i/2;
            MIN+=i/2;
            if(i%2==1)MAX++;
        }
    }
}

void play()
{
    printf("%d %d\n",MAX,MIN);
}

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

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

题意：起先看的很迷糊啊。就是给你C*R的矩阵，然后矩阵里面是#(不可走)或.(可走)，然后Input最后一句话每两个点之间最多正好就一条路，所以说路径不包含圈，所以是棵树，然后Output说输出两个点之间最长的长度是多少。

分析：知道题意的话就很简单了。可以用树形DP ，假设当前的节点为fa，如果它没有子节点，那么它就是叶子节点，那么直接返回1，如果它有一个子节点，那么最长就是子节点返回的值，用这个值更新最大值，然后返回最大值+1到fa的父节点，如果它有多余两个子节点。那么从它的子节点选择2个最大子节点，然后相加,更新最大值，再把最大值的一个子节点+1返回到fa的父节点，这样最后的最大值就是我们要求的最大路径了。啪啪啪就可以AC了。

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
bool ai[maxn][maxn];
int T;
int n,m;
char ch[maxn];
void init()
{
    scanf("%d%d",&m,&n);
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=n; i++)
    {
        scanf("%s",ch+1);
        for(int j=1; j<=m; j++)
        {
            if(ch[j]=='.')ai[i][j]=1;
        }
    }
}
bool cmp(int a,int b)
{
    return a>b;
}
bool vis[maxn][maxn];
int MAX;
int c1[]= {1,0,-1,0};
int c2[]= {0,1,0,-1};
int DFS(int x,int y)
{
    int l1=-1,l2=-1;
    for(int i=0; i<4; i++)
    {
        int nx=x+c1[i];
        int ny=y+c2[i];
        if(!ai[nx][ny])continue;
        if(vis[nx][ny])continue;
        vis[nx][ny]=1;
        int q=DFS(nx,ny);
        if(l1==-1){
            l1=q;

        }
        else{
            if(q>l1){
                l2=l1;
                l1=q;
            }
            else if(q>l2){
                l2=q;
            }
        }
    }
    if(l1==-1)
    {
        return 1;
    }
    if(l2==-1)
    {
        MAX=max(MAX,l1);
        return l1+1;
    }
    MAX=max(MAX,l1+l2);
    return l1+1;

}
void play()
{
    MAX=0;
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(!vis[i][j])
            {
                vis[i][j]=1;
                if(!ai[i][j])continue;
                DFS(i,j);
            }
        }
    }
    printf("Maximum rope length is %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=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;
}