飞机票：http://codeforces.com/contest/552/problem/D

题意：给你n个点，两两相连，一共有多少个三角形是已给出n个点中三个点组成的

分析：这题的话O（n³）能过，我不知道出题人是什么意思，，，我的话是n*40000.最多也就O(10*n*n)的复杂度，跑了173ms。直接进入正题：此题可以用计数容斥来做，具体就是对与每个点i 对(i+1~n)进行枚举。(1<=i<=n)具体的做法是：假设当前的点是i，枚举(i+1~n)和i的斜率，并把斜率存入到数组中，因为最大的yj-yi=200 xj-xi=200，所以存入到200*200的数组中就可以了但是这里我们必须把(yj-yi)和(xj-xi)的最大公约数求出来，假设除了最大公约数后分别为p和q，因为这样才可以知道斜率为p/q的点关于i有多少个。这里的话，我们可以预处理下1~200每对的最大公约数，这样就是O（1）的时间求最大公约数了。而且我是用了两个数组，一个存斜率是正数，一个存斜率是负数，而且还得存p=0或q=0的情况。最后就是对三角形的个数进行统计，假设斜率为k的点有有l个，除了l个点和i点后有r个点，则三角形个数就是l*r，因为l上选一个点，i一个点，r上一个点，计算完后，需要把重复的除掉，因为对于两个点a和b，我们计算了a到b和b到a的，所以最后除以2就可以了，然后加到总数上去最后啪啪啪，就可以AC了。

/*
Author:Chieh
Because Of Coding
*/
#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
#define EPS 1e-9
using namespace std;
int x1[201][201];
int y11[201][201];
int G[201][201];
const int maxn=2*1234;
struct he
{
    int x,y;
} Sky[maxn];
int n;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d%d",&Sky[i].x,&Sky[i].y);
}
void play()
{
    LL ans=0;
    for(int i=1; i<=n; i++)
    {
        memset(x1,0,sizeof(x1));
        memset(y11,0,sizeof(y11));
        int l=0;
        int r=0;
        for(int j=i+1; j<=n; j++)
        {
            int q=Sky[i].y-Sky[j].y;
            int p=Sky[i].x-Sky[j].x;

            if(p==0)
            {
                l++;
            }
            else if(q==0)
            {
                r++;
            }
            else
            {
                int nn=G[abs(q)][abs(p)];
                q/=nn;
                p/=nn;
                if(q>0&&p>0)
                {
                    x1[q][p]++;
                }
                else if(q<0&&p<0)
                {
                    x1[-q][-p]++;
                }
                else
                {
                    y11[abs(q)][abs(p)]++;
                }
            }

        }
        LL sum=0;
        int sk=n-i;
        if(l!=0)
        {
            sum+=(sk-l)*l;
        }
        if(r!=0)
        {
            sum+=(sk-r)*r;
        }
        for(int j=1; j<=200; j++)
        {
            for(int k=1; k<=200; k++)
            {
                int p=x1[j][k];
                int q=y11[j][k];
                if(p!=0)
                {
                    sum+=(sk-p)*p;
                }
                if(q!=0)
                {
                    sum+=(sk-q)*q;
                }
            }
        }
        sum/=2;
        ans+=sum;
    }
    printf("%I64d\n",ans);
}
int GCD(int a,int b)
{
    if(a<b)swap(a,b);
    if(a%b!=0)
    {
        return GCD(b,a%b);
    }
    return b;
}
int main()
{
    for(int i=1; i<=200; i++)
    {
        for(int j=1; j<=200; j++)
        {
            G[i][j]=GCD(i,j);
        }
    }

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

飞机票:http://codeforces.com/contest/552/problem/C

题意：给你w和m，然后用w⁰.w¹.w²......w¹⁰⁰，放在天平两侧，且m肯定要放，w可以用完，但是每个只有一个，使得天平平衡。

分析：数学题，我们假设有个数组ai，且长度为0~100，且ai对应w⁰.w¹.w²......w¹⁰⁰其中，ai可以为1，0，-1，我们现在的目标就很明确了a0*w⁰+a1*w¹+a2*w²......a100*w¹⁰⁰=m如果ai为1的话，就是说指数为i的要放在天平与m相反的盘子里，如果是0，就是这个数不用用，如果是1，就是放在与m相同的地方。然后我们可以提取这些数的最大公约数，则有w⁰(a0+a1*w¹/w⁰+a2*w²/w⁰...... ）=m

从这个公式我们可以推出，m必须要可以整除w^0，因为不能整除就是NO了，然后就剩下(a0+a1*w¹/w⁰+a2*w²/w⁰...... ）=m/w⁰ ,把a0移过来(a1*w¹/w⁰+a2*w²/w⁰...... ）=m/w⁰ +a0 则左边可以用前面的方法继续迭代，右边的话a0有三种可能，且如果这三种可能没有一种可以使得右边整除左边的最大公约数，则也是NO，因为w>2,所以这三种可能做多就一种满足。然后当右边=1的时候就结束，因为左边和右边一样了，YES。然后啪啪啪，就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#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
#define EPS 1e-9
using namespace std;
int w,m;
void init(){

}
void play(){
    int t=0;
    while(1){
        if(m==1){
            printf("YES\n");
            return;
        }
        if(m%w!=0){
            if((m+1)%w==0){
                m=m+1;
                m/=w;
            }
            else if((m-1)%w==0){
                m=m-1;
                m/=w;
            }
        }
        else{
            m/=w;
        }
        t++;
        if(t==101){
            printf("NO\n");
            return;
        }
    }
}
int main()
{
    while(scanf("%d%d",&w,&m)!=EOF){
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

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

题意：给你一个数组A，A[i]^A[j]之后，假设为P，求lowbit(P)（就是P最低位为1的位置，然后就是2^为1位置）。然后求和，这里的话要计算两遍，即i和j j和i算两个，并不算一个。

分析：起先以为是最低位：不用为2的幂掌握的不够深刻啊。然后百度才知道要幂的。。。这次印象深刻了这种题的话，可以用分治，即分成两个块然后求值。具体怎么求值：

(1)先把所有的数转换为2进制。

(2)从最低位开始，如果是1就放入左边块，如果是0就放入右边块。(这里我是定义vector l,r ，每次是1就存入l，右边就存入r)，这样的话就知道l里的元素和r里的元素是异或之后最低位为当前深度的2的幂，然后把l的大小*r的大小*2加到答案里去。*2是因为l和r算一边，然后r和l算遍。

(3)然后把l和r分别进行第二步。因为l和r已经不相干了。这里要及时退出，就是当l和r其中是0时就要退出，不然会TLE

总体复杂的O(n*logn)，然后啪啪啪，就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#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
#define EPS 1e-9
using namespace std;
const int maxn=5*12345;
int T;
int n;
int  ai[maxn];
int bi[30];
struct he
{
    bool isok[30];
} Sky[maxn];
int MOD=998244353;
void getBir()
{
    for(int i=1; i<=n; i++)
    {
        memset(Sky[i].isok,0,sizeof(Sky[i].isok));
        for(int j=29; j>=0; j--)
        {
            if(ai[i]-bi[j]>=0)
            {
                ai[i]-=bi[j];
                Sky[i].isok[j]=1;
            }
        }
    }
}
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
    getBir();

}
LL ans;
void DFS(vector<int> V,int depth)
{
    if(depth==30)
    {
        return;
    }
    if(V.size()==0)return;
    vector<int> l;
    vector<int> r;
    for(int i=0; i<V.size(); i++)
    {
        int id=V[i];
        if(Sky[id].isok[depth])
        {
            l.push_back(id);
        }
        else
        {
            r.push_back(id);
        }
    }
    int ls=l.size();
    int rs=r.size();
    LL p=ls*rs;
    ans=(ans+((p*(bi[depth]%MOD)%MOD)*2)%MOD)%MOD;
    DFS(l,depth+1);
    DFS(r,depth+1);
}
int Case;
void play()
{
    ans=0;
    vector<int> V;
    for(int i=1;i<=n;i++)V.push_back(i);
    DFS(V,0);
    printf("Case #%d: %I64d\n",++Case,ans);
}
int main()
{
    bi[0]=1;
    for(int i=1; i<=29; i++){bi[i]=bi[i-1]*2;}
    scanf("%d",&T);
    Case=0;
    while(T--)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://codeforces.com/contest/551/problem/C

题意：有一个数组ai[]，有n个元素，ai[i]代表第i个元素的值，有m个学生，学生在最左边，且到第i个元素要i秒，且使第i个元素值减1需要花费1秒，求m个人使所有值为0最少要多少时间，学生可以同时行动。

分析：题目一看，必然二分啊，但是怎么维护这个值呢？这里有2种方法，假设当前判断的值是mid

(1)从后往前推：假设最右边不为0的下标为k，则学生到k需要花费k秒，如果mid<=k直接就不行，因为到了k这个点就没时间了。所以mid肯定要大于k，然后ai[k]就要减掉mid-k的值，这样就是最优的，因为学生的时间没有一秒浪费。

(2)从前往后推：这个情况有点难理解，只能YY了，假设当前的人在i,且后面有值的地方在j（i<j）,如果当前这个人再拿一个i的值，他到不了j或则到了j已经没有时间了，这样就有时间浪费了，但是我们会发现，下个人他就多了1秒的时间，就是他如果能到j，则他可以多拿一个，并不会影响到最优值。有点难理解哇~

我的代码是用第二种方法的，复杂度为O（log2INF*n）INF=2*1e18，要及时跳出循环，不然就TLE了，啪啪啪，就可以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 1e20
#define EPS 1e-9
using namespace std;
const int maxn=123456;
LL ai[maxn];
LL bi[maxn];
int n,m;
void init()
{

    for(int i=1; i<=n; i++)
    {
        scanf("%I64d",&ai[i]);
        bi[i]=ai[i];

    }
}
void play()
{
    LL l=0;
    LL r=INF;
    LL ans=r;
    LL p=INF;
    for(int i=n; i>=1; i--)
    {
        if(ai[i]>0)
        {
            p=i;
            break;
        }
    }
    if(p==INF)
    {
        printf("0\n");
        return;
    }
    n=p;
    while(l<=r)
    {
        LL mid=(l+r)/2;
        int st=1;
        for(int i=1; i<=m; i++)
        {
            LL t=mid;
            int ti=st;
            for(int j=st; j<=n; j++)
            {
                LL now=ai[j]+ti;
                if(now>t)
                {
                    st=j;
                    t-=ti;
                    if(t>0)
                    {
                        ai[j]-=t;
                    }
                    break;
                }
                else
                {
                    t-=now;
                    ai[j]=0;
                    ti=1;
                    st=j;
                }
            }
            if(st==n&&ai[n]<=0)break;
        }
        bool flag=0;
        if(st==n&&ai[n]<=0)flag=1;
        LL p=ai[n];
        for(int i=1; i<=n; i++)ai[i]=bi[i];
        if(!flag)
        {
            l=mid+1;
        }
        else
        {
            r=mid-1;
            ans=mid;
        }
    }
    printf("%I64d\n",ans);
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票：http://codeforces.com/contest/551/problem/B

题意:给你三个字符串，a,b,c，只包含小写字母,求字符串a重新排列后k包含最多的不重叠字串，为b或则为c.

分析：先想想先重组b或则c,会发现这个贪心不正确，因为可能重组一次b后，后面先重组c会比较优然后我就卡题了，一点感觉都没有，而且还分三种情况先b再c，或c再b，或则两个一起来，后面才发现这种贪心明显是错的，因为不是最优的。一直wa test12后来看了下字符串长度为1e5，可以暴力直接过。o(︶︿︶)o ，弱死了，想了半天，至于暴力，就是先预处理出都重组b的情况，假设为sum1,然后枚举sum1,推出重组c的情况sum2，求sum1+sum2的最大值，然后输出，复杂度0(sum1*26)sum1<=100000,所以还是非常快的，啪啪啪，就可以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=123456;
char ch1[maxn];
char ch2[maxn];
char ch3[maxn];
int ai[27];
int bi[27];
int ci[27];
int len1,len2,len3;
void init()
{
    len1=strlen(ch1+1);
    len2=strlen(ch2+1);
    len3=strlen(ch3+1);
    memset(ai,0,sizeof(ai));
    memset(bi,0,sizeof(bi));
    memset(ci,0,sizeof(ci));
    for(int i=1; i<=len1; i++)
    {
        int t=ch1[i]-'a'+1;
        ai[t]++;

    }
    for(int i=1; i<=len2; i++)
    {
        int t=ch2[i]-'a'+1;
        bi[t]++;
    }
    for(int i=1; i<=len3; i++)
    {
        int t=ch3[i]-'a'+1;
        ci[t]++;

    }
}
void play()
{

    int sum1=1000000000;
    for(int i=1; i<=26; i++)
    {
        if(bi[i]>0)
        {
            sum1=min(sum1,ai[i]/bi[i]);
        }
    }
    int l=-1,r=-1;
    for(int i=0; i<=sum1; i++)
    {
        for(int j=1; j<=26; j++)
        {
            ai[j]-=(bi[j]*i);
        }
        int sum2=1000000000;
        for(int j=1; j<=26; j++)
        {
            if(ci[j]>0)
            {
                sum2=min(sum2,ai[j]/ci[j]);
            }
        }
        for(int j=1; j<=26; j++)
        {
            ai[j]+=(bi[j]*i);
        }
        if(l==-1&&r==-1)
        {
            l=i;
            r=sum2;
        }
        else
        {
            if(l+r<i+sum2)
            {
                l=i;
                r=sum2;
            }
        }
    }
    for(int i=1; i<=l; i++)printf("%s",ch2+1);
    for(int i=1; i<=r; i++)printf("%s",ch3+1);
    for(int i=1; i<=l; i++)
    {
        for(int j=1; j<=26; j++)
        {
            ai[j]-=bi[j];
        }
    }
    for(int i=1; i<=r; i++)
    {
        for(int j=1; j<=26; j++)
        {
            ai[j]-=ci[j];
        }
    }
    for(int i=1; i<=26; i++)
    {
        for(int j=1; j<=ai[i];j++)printf("%c",'a'+i-1);
    }
    printf("\n");

}
int main()
{
    while(scanf("%s%s%s",ch1+1,ch2+1,ch3+1)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}

飞机票： 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=16762

题意：给你n个服务，然后每个服务有时间di，和执行时间si，如果执行后的时间超过di，则惩罚值为max(0,最终的时间-di)，求最大两个惩罚值相加最小。

分析：二分套二分套二分，复杂度logn*n*logn*n。。。ORZ

第一个二分是确定两个和最小值用的，假设当前检测的值是x，则我们枚举每个服务，然后第二个二分，二分x的值，且l要大于等于x/2向上取整，r为x，这个是为了确定两个其中一个比较大的值，那么另一个值就可以为x-大的值，然后第三个二分，用来确定k应该插入到哪里去，假设大的值为i，小的值为j，则每个服务的d值都得家j，但是k的d值要加i，应该能理解，然后不是属于k的我们只要排序一次就够了，因为加了跟没加排序不变，然后用第三个二分把k插进去，按更新后的d从小到大，why??因为d越大的话，它的可用区域越大，贪心~所以把小的先处理，如果当前执行的任务超过了当前的d，如果是k，那就是说明k更新的值太小，所以第二个二分的l=mid+1，如果不是k，且超过了，那个r=mid-1，k太大~，如果可以，那么就说明当前方案是可以的，更新第一个二分。。。最后输出，over，啪啪啪，AC~

/*
Author:Chieh
Because of You
*/
#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=5*123;
struct he
{
    int s,d;
} JLJ[maxn];
int T,n;
bool cmp(he a,he b)
{
    return a.d<b.d;
}
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d%d",&JLJ[i].s,&JLJ[i].d);
}
vector<he> V;
int isOK(int x,int y,int idx)
{
    int l=0;
    int r=V.size()-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(V[mid].d+y>JLJ[idx].d+x)
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    V.insert(V.begin()+l, JLJ[idx]);
    int ip=l;
    int before=0;
    for(int i=0; i<V.size()-1; i++)
    {
        int tm=y;
        if(i==ip)tm=x;
        int s=V[i].s;
        int d=V[i].d+tm;
        if(s+before>d)
        {
            V.erase(V.begin()+ip);
            if(i==ip)return 1;
            return 2;
        }
        else before+=s;
    }
    V.erase(V.begin()+ip);
    return 0;
}
bool check(int x)
{

    for(int i=1; i<=n; i++)
    {
        V.erase(V.begin()+i-1);
        int l=x/2;
        int r=x;
        if(x%2!=0)l++;
        while(l<=r)
        {
            int mid=(l+r)/2;
            int t=isOK(mid,x-mid,i);
            if(t==0)
            {
                V.insert(V.begin()+i-1,JLJ[i]);
                return 1;
            }
            if(t==1)
            {
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        V.insert(V.begin()+i-1,JLJ[i]);
    }
    return 0;
}
void play()
{
    sort(JLJ+1,JLJ+1+n,cmp);
    V.clear();
    for(int j=1; j<=n; j++)
    {
        V.push_back(JLJ[j]);
    }
    he a;
    a.s=0;
    a.d=2000000000;
    V.push_back(a);
    int l=0;
    int r=1000000;
    int MIN=1000000000;
    while(l<=r)
    {
        int mid = (l + r) / 2;
        if(check(mid))
        {
            MIN=min(mid,MIN);
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    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=17264

题意：就是给你两个轨道，分别为W，E然后有n个时刻，每个时刻回来pi和qi个飞机分别到W，E，且每个时刻能从W，E中起飞一辆飞机，但是刚飞到的飞机不能起飞。且每个机场当前的飞机编号为0~飞机数量-1。求两个机场一起最大编号的最小值。

分析：我的想法是二分+贪心+树状数组。

二分是为了求最小值，贪心和树状数组主要是判断用的。二分的边界就不用说了，我是直接用了l=1，r=100000，因为每个机场飞机最多的时候就只有100000，不过答案求出来要减一个1才行，因为是0开始的开始进入主题了；

假设当前判断的速度是x，则我们循环累计每个机场的数量，且每次存入树状数组（后面logn有用）。假设W机场每个时刻飞来ai两飞机。则当前W机场有sum（1。。。k）；假设我sum[0]，如果sum[0]>x了，那就说明前面的飞机必须起飞need=sum[0]-x辆了，然后就用到了贪心思想：因为每个时刻只能起飞一辆飞机，所以我们从1开始，枚举。。。而且我们用一个vis数组记录当前是否有飞机起飞过，有的话，就继续向后。当当前时间是m时。则我们可以用树状数组求的前面的还有没有飞机，如果有，我们就可以起飞，然后树状树状数组减1、、、如果当m=k的时候还不行说明方案不可行，直接返回false，如果可以那么继续循环，一直到最后。。。如果可以则返回true 更新最小值、、、这里哪里用了贪心呢，就是sum那里大于x时，因为我们从前面开始取的话，这样后面大于x时的选择空间更大。。。这样就可以了，复杂度为log（100000）*(n+2*n*logn)就是logn^2*n了吧，速度还是ok的，啪啪啪就可以AC了

/*
Author:Chieh
Because of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
using namespace std;
const int maxn=5*1234;
int C[2][maxn];
int lowbit(int x)
{
    return x&(-x);
}
int sum(int n,int idx)
{
    int sum=0;
    while(n>0)
    {
        sum+=C[idx][n];
        n=n-lowbit(n);
    }
    return sum;
}
int n,T;
void change(int i,int x,int idx)
{
    while(i<=n)
    {
        C[idx][i]=C[idx][i]+x;
        i=i+lowbit(i);
    }
}

struct he
{
    int a,b;
} JLJ[maxn];
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&JLJ[i].a,&JLJ[i].b);
    }
}
bool vis[maxn];
int summ[2];
int s[2];
bool check(int x)
{
    memset(vis,0,sizeof(vis));
    memset(C[0],0,sizeof(C[0]));
    memset(C[1],0,sizeof(C[1]));
    summ[0]=summ[1]=0;
    s[0]=s[1]=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=1; j++)
        {
            int tp=JLJ[i].a;
            if(j==1)
            {
                tp=JLJ[i].b;
            }
            summ[j]+=tp;
            if(summ[j]>x)
            {
                int need=summ[j]-x;
                int st=1;
                while(st<=need)
                {
                    if(s[j]==i)return 0;
                    if(vis[s[j]])
                    {
                        s[j]++;
                    }
                    else
                    {
                        int p=sum(s[j],j);
                        if(p>0)
                        {
                            change(s[j],-1,j);
                            st++;
                            vis[s[j]]=1;
                            s[j]++;
                        }
                        else
                        {
                            s[j]++;
                        }
                    }
                }
                summ[j]=x;
            }
            change(i,tp,j);
        }
    }
    return 1;
}
void play()
{
    int l=1,r=100000;
    int MIN=r;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            MIN=min(MIN,mid);
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }

    }
    printf("%d\n",MIN-1);
}

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