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

题意：就是给你时钟的分针和时针的角度，且乘上12000，求现在的时间是几时几分几秒，且秒要是10的倍数。而且题目给的是劣角的角度，即不会大于12000*180，

分析：枚举时间的话肯定不会超时，怎么判断角度呢，我们可以先求出分针的角度，加入当前的时间是i:j:k，且k是10的倍数，那么分针的角度就是j*6+0.1*k，因为一秒分钟转0.1度，分针一分钟转6度，可以知道j*6+0.1*k是整数，假设是q。我们知道时针转的角度是i*30,因为小时转30度，且每分钟转1/360*30，所以总的转了i*30+30*q/360,因为有精度误差，因为30*q不一定能整除，但是题目给了乘上12000，所以可以直接提高倍数，就是q=12000*q,设时针角度为p,所以p=i*30*12000+30*q/360,因为q已经乘过了，所以不用乘了。这样就可以保证q和p都是整数，但是还有个问题就是劣角，所以一共有两个角。一个是abs(q-p)，一个是360*12000-abs(q-p)，因为扩大了12000，只要其中一个和输入的角度一样就是对的时间。中间不要用double，直接int，因为我double就wa，int就AC，然后啪啪啪就可以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 n;
void init()
{

}
void play()
{
    for(int i=0; i<=11; i++)
    {
        for(int j=0; j<=59; j++)
        {
            for(int k=0; k<=59; k+=10)
            {
                int q=j*6;
                q+=0.1*k;
                q*=12000;
                int p=i*30*12000;
                p+=q*30/360;
                int s1=abs(q-p);
                int s2=360*12000-s1;
                if(s1==n||s2==n)
                {
                    printf("%02d:%02d:%02d\n",i,j,k);
                }
            }
        }
    }

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

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

题意：给你n个点和m条边的无向图，可能不是连接在一起的，并且没有子环和平行边，求最小添加几条边可以使它包含奇数点的圈，并且求满足这样方案的方法有多少种，两种方案不同即边的设置不完全一样。

分析：起先可以很容易知道最少的边不会超过3，即0，1，2，3，为什么？加入所有的点都不相连，即m等于0，那么肯定对任意三点添加三条边就可以有奇数点的圈，总方案就是C（n,3）即n*(n-1)*(n-2)/3;然后就可以用染色的方法对0，1，2进行判断，具体怎么判断，假设当前点为i，且i没有访问过，那么对i进行DFS，可以设i点的颜色为0，与i相连的点颜色为1，并且对i相连的没有访问过的边继续按照这个染色方法染色，即当前点的颜色为0，则相连的边为1，反之同理。假设当前的节点为now,它的邻边v被访问过，如果它们的颜色一样的话，就说明包含奇数点的圈，为什么？因为点是根据0，1，0，1染色的，因为两个相邻的颜色一样，说明，就是1，0，1，0，....1，因为没有最后一个点，它就是偶数个，包含了，它就是奇数个，只要是这样，就说明不用添加边，则为0条边，一种方法。反之的话，继续搜索，并且记录，染色为1的点的个数，和染色为0的点的个数。当搜索完的时候，得到为1的点为p,为0的点的数量为q,我们要使它包含奇数个点，所以我们要选择两个点，且它们之间的数量为奇数，因为我们知道只要两个点的颜色一样，则它们之间肯定包含了奇数个点的圈，所以我们从p里选择两个，即C（p,2）=p*(p-)/2，同理从q中选两个C(q,2)=q*(q-)/2，加到总方法里去，对每一块都分别进行统计，当计算完的时候，当总数为0的时候，又因为m不等于0，所以最多是2个点相连，所以总数就是m*(n-2)，即m里选择条边，n-2选择一个点，然后输出，这时候我们必须添加两条边，如果总数大于0，则最多只要添加一条边，输出答案就好，最后啪啪啪就可以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=123456;
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<=m; i++)
    {
        scanf("%d%d",&u,&v);
        V[u].push_back(v);
        V[v].push_back(u);
    }
}
bool vis[maxn];
bool color[maxn];
LL cc[2];
bool flag;
LL MIN;
void DFS(int now)
{
    vis[now]=1;
    cc[color[now]]++;
    for(int i=0; i<V[now].size(); i++)
    {
        int v=V[now][i];
        if(!vis[v])
        {
            color[v]=!color[now];
            DFS(v);
        }
        else if(color[v]==color[now])
        {
            flag=1;
        }
    }
}
void play()
{
    if(m==0){
        LL ans=1LL*n*(n-1)*(n-2)/6;
        printf("3 %I64d\n",ans);
        return;
    }
    memset(vis,0,sizeof(vis));
    flag=0;
    LL ans=0;
    memset(color,0,sizeof(color));
    for(int i=1; i<=n; i++)
    {
        if(vis[i])continue;
        cc[0]=cc[1]=0;
        DFS(i);
        if(flag){
            printf("0 1\n");
            return;
        }
        ans+=cc[0]*(cc[0]-1)/2;
        ans+=cc[1]*(cc[1]-1)/2;
    }
    if(ans==0){
        printf("2 %I64d\n",1LL*m*(n-2));
        return;
    }
    printf("1 %I64d\n",ans);


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

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

题意：给你个桌子，有n个桌脚（n<=1e5），每个桌脚有个高度为ai，拆掉每个桌脚需要力量bi，现在问你拆除桌脚使桌子稳定，且用力最小，桌子稳定的条件是最大的那个脚的总数必须大于当前脚数量的一半，假设有当前有5个桌脚，要使稳定，需要3个最大的脚，假设4个，则要3个最大脚，只有1个他就是稳定的。

分析：我们可以枚举脚的长度，怎么枚举？？按脚长度排个序，然后假设长度为k的脚的数量从l到r，即有r-l+1个为k的数量。然后我们可以来个辅助数组ci，就是大于k脚长度需要花费的总力气，这个力气可以从后往前推，因为我们是从小到大对脚长度进行排序，那么初始必须花费的力气是c[r+1]，然后我们有r-l+1的数量，设为sum，则我们可以保留sum-1（因为大于一半）个脚，因为前面有l-1个脚，我们可以拆除l-1-（sum-1）个脚。设为des，如果des<=0,则不用拆了，因为我们已经足够，如果大于0,则要从前面l-1选择des个脚拆除，我们贪心的话，肯定会拆需要力量最小的脚，因为力量<=200，所以我们可以用个数组need[200]表示前面各个力量有多少个然后从小到达选择des个，设为力量需要为p，这总共需要力量c[r+1]+p，然后去最小值因为我们要处理need[200]，所以我们要一个辅助数组记录l到r需要的各个力量，然后处理完l~r则把辅助数组的数据加到need上去，让下一次可以继续迭代，复杂度O(n*200)，最后啪啪啪就可以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=123456;
int n;
struct he
{
    int len,val;
} Sky[maxn];
bool cmp(he a, he b)
{
    return a.len<b.len;
}
int bi[maxn];
int ai[234];
int ci[234];
void init()
{
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&Sky[i].len);
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&Sky[i].val);
    }
    sort(Sky+1,Sky+1+n,cmp);
    bi[n+1]=0;
    for(int i=n; i>=1; i--)
    {
        bi[i]=Sky[i].val;
        bi[i]+=bi[i+1];
    }
    Sky[n+1].len=INF;
    Sky[0].len=0;

}

void play()
{
    memset(ai,0,sizeof(ai));
    int l=-1;
    int MIN=INF;
    memset(ci,0,sizeof(ci));
    for(int i=1; i<=n+1; i++)
    {
        if(Sky[i].len!=Sky[i-1].len)
        {
            if(l!=-1)
            {
                int ok=(i-1-l)+1;
                int xy=ok-1;
                xy=l-1-xy;
                int sum=bi[i];
                if(xy>0)
                {
                    for(int j=1; j<=200; j++)
                    {
                        if(xy<=ai[j])
                        {
                            sum+=xy*j;
                            break;
                        }
                        else
                        {
                            xy-=ai[j];
                            sum+=ai[j]*j;
                        }
                    }
                }
                if(sum<MIN)MIN=sum;
            }
            for(int j=1; j<=200; j++)
            {
                ai[j]+=ci[j];
            }
            l=i;
            memset(ci,0,sizeof(ci));
            int v=Sky[i].val;
            ci[v]++;
        }
        else
        {
            int v=Sky[i].val;
            ci[v]++;
        }
    }
    printf("%d\n",MIN);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

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

题意：给你n个区间li，ri，且ri<li+1,(1<=i<n)，li<=ri,然后给你m座桥，每个有个长度ai，然后要求把桥搭在区间上，且满足桥的长度

大于等于li+1-ri,且小于等于ri+1-li,求能否用桥把所有的相邻区间连接起来，并且输出每个相邻区间对应的桥下标。

分析：起先一看以为是二分图，但是看边太多直接放弃。这里我们 可以知道一个东西。就是相邻区间需要的桥的最大值和最小值，假设两个相邻区间li,ri  li+1,ri+1,我们定义他们的坐标为i，则可知需要的最小长度为li+1-ri,最大长度为ri+1-li,假设为最小为le最大为ri，接着我们再把m条桥排序，从小到大。接着运用贪心看看怎么贪?假设当前要判断桥i属于哪个区间le ri,我们必须把所有可以用桥i的区间找出来，然后找右端点最小的，为什么?因为大伙都可以用它，当然我们要使用剩余使用量最小的来接受它，不然给别人，它都亏。搞到这里就知道怎么贪了吧。就是把le ri按左区间排序，如果一样不用管。然后来个优先队列，假如当前的le<=桥i的长度，就把它加到优先队列，为什么？？因为我们不知道它满不满足，但是只要它的右端点最小，然后比桥i的长度还短，那么直接就No了，因为别人都比它好。优先队列干嘛用的？就是取右端点最小的，因为我们前面判断过的比较小的le可能要在这个时候用到。总体复杂的就是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=2*123456;
LL l[maxn],r[maxn];
struct he
{
    int id;
    LL l,r;
    bool operator<(const he& a)const
    {
        return r>a.r;
    }
} Sky[maxn];
LL ai[maxn];
struct he1
{
    LL val;
    int id;
} Sky1[maxn];
int can[maxn];
int n,m;
bool cmp(he1 a,he1 b)
{
    return a.val<b.val;
}
void init()
{
    for(int i=1; i<=n; i++)
    {
        scanf("%I64d%I64d",&l[i],&r[i]);
    }
    for(int i=1; i<=m; i++)
    {
        scanf("%I64d",&Sky1[i].val);
        Sky1[i].id=i;
    }
    sort(Sky1+1,Sky1+1+m,cmp);
}
bool cmp2(he a,he b)
{
    if(a.l!=b.l)return a.l<b.l;
    return a.r<b.r;
}
priority_queue<he> pq;
void play()
{
    int st=0;
    for(int i=2; i<=n; i++)
    {

        LL a1=l[i]-r[i-1];
        LL a2=r[i]-l[i-1];
        st++;
        Sky[st].l=a1;
        Sky[st].r=a2;
        Sky[st].id=st;
    }
    sort(Sky+1,Sky+1+st,cmp2);
    while(!pq.empty())pq.pop();
    int now=1;
    for(int i=1; i<=m; i++)
    {
        int id=Sky1[i].id;
        LL val=Sky1[i].val;
        while(now<=st)
        {
            if(Sky[now].l<=val)
            {
                pq.push(Sky[now]);
                now++;
            }
            else
            {
                break;
            }
        }
        if(pq.empty())continue;
        he aa=pq.top();
        pq.pop();
        if(aa.r<Sky1[i].val)
        {
            printf("No\n");
            return;
        }
        int idx=aa.id;
        can[idx]=id;
    }
    if(!pq.empty()||now!=st+1)
    {
        printf("No\n");
        return ;
    }
    printf("Yes\n");
    for(int i=1; i<=st; i++)
    {
        printf("%d ",can[i]);
    }
    printf("\n");

}
int main()
{

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

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

题意：就是给你k个已经按大小递增的序列，每个有mi个1<=mi<=n,m1+m2+,,mk=n，其中1到n只出现一次。求组合成从1到n的序列最小的时间值，具体的每秒能做的事是，把序列拆掉或把序列合并，拆掉的话必须有一个是独立的不能两个子序列一起拆开，比如序列1-2-3-4，可以把1或4拆下来，但是不能拆成1-2 3-4这样是非法的。合并的话也是有规律的，就是以1为首的字串不能何在一个序列长度大于1的序列里面，这样也是非法的，比如序列1-2-3 和序列5-6合并成1到6要3秒，因为5-6包含2长度，所以要拆开，成为5和6，然后5合并，6合并。题意比较坑爹啊~

分析：知道题意后就可以瞎搞了，很简单，就是把包含1的序列后面能递增到几个拿出来先，如果后面没了，初始时间就是0，如果后面还有就是1，因为要拆开，然后后面的序列都要拆，因为要把包含1的合并进去，所以假设序列长度为len，则拆要len-1，合并要len，所以共要len*2-1,所有加起来就是答案，然后啪啪啪就可以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=123456;
int idx[maxn];
vector<int> V[maxn];
int first[maxn];
int n,k;
LL MIN;
void init()
{
    int m;
    MIN=0;
    for(int i=1; i<=k; i++)
    {
        V[i].clear();
        first[i]=0;
        scanf("%d",&m);
        bool flag=1;
        for(int j=1; j<=m; j++)
        {
            int u;
            scanf("%d",&u);
            if(u==1)
            {
                flag=0;
                int p=1;
                for(int z=j+1; z<=m; z++)
                {   j=z;
                    scanf("%d",&u);
                    if(u==++p)continue;
                    MIN+=(m-z+1)*2;
                    break;
                }
            }
        }
        if(flag){
            MIN+=(m*2)-1;
        }
    }
}
void play()
{

    printf("%I64d\n",MIN);

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

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

题意：就是有个人叫DD，他参见乒乓球比赛，然后要拿冠军，(就是赢得场数最多的人),给你m个初始的结果和下面还要比的场次，问DD能否拿冠军，其中只能有一个冠军(即不能有多个最大值)

分析:一看这道题，就知道贪心取DD能赢的最大值，即加入DD已经赢了p场，然后他下面还比了q场，贪心的话，他最多能赢p+q场，所以其余的人最多只能赢p+q-1场，因为不能有一样的最大值。先判断当前每个人已经赢了的场数，假设p+q=a1,别人当前赢得场数为a2。a3...an，如果a2到an其中有大于等于a1那么直接就是no了，因为不管怎么比，都不可能比a1小了如果都小于a1的话，就必须找个方法判断到底行不行？从前面可以知道第i个人最多只能赢a1-ai-1场，这样才小于a1,设为b2.b2..b3，然后假设第i个人和其他人除了DD一共比了k场，那么他最多只能赢bi场，因为限制。然后就是想什么方法判断每个人都满足。这里就用到了最大流算法。假设有个源点s，假如每对人i和j比了kij场，那么就有从s流kij的流量到i和j，我们可以定义为点vij,然后vij可以流向vi和vj，因为这个没有限制，但是可以定义为kij，因为最大了.最后我们可以定义个汇点，然后从vi流bi个流量到t，因为最大只能是bi，最后跑一边最大流，看它能不能是一个可行流，即除了和DD比的场数之外，所有的场数是否可以满足要求。最后啪啪啪就可以AC了。

/*
Author:Chieh
Because Of Coding
*/
/*
O(E^2 V)
E//边数
V//节点
//每次按最短的s-t路径进行增广
*/
#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=5*12;
map<string,int> M;
struct he
{
    int to,val,id;
};
vector<he> V[3000];
int n,m;
char ch1[12],ch2[12],ch3[12];
int win[maxn];
int next[maxn][maxn];
int Link[maxn][maxn];
void init()
{
    for(int i=1; i<3000; i++)
    {
        V[i].clear();
    }
    M.clear();
    ch1[1]='D';
    ch1[2]='D';
    ch1[3]='\0';
    M[ch1+1]=1;
    memset(win,0,sizeof(win));
    memset(next,0,sizeof(next));
    int st=1;
    for(int i=1; i<=m; i++)
    {
        scanf("%s%s%s",ch1+1,ch2+1,ch3+1);
        if(M[ch1+1]==0)
        {
            M[ch1+1]=++st;
        }
        if(M[ch2+1]==0)
        {
            M[ch2+1]=++st;
        }
        int t1=M[ch1+1];
        int t2=M[ch2+1];
        if(ch3[1]=='w')
        {
            win[t1]++;
        }
        else
        {
            win[t2]++;
        }
    }
    scanf("%d",&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%s%s",ch1+1,ch2+1);
        if(M[ch1+1]==0)
        {
            M[ch1+1]=++st;
        }
        if(M[ch2+1]==0)
        {
            M[ch2+1]=++st;
        }
        int t1=M[ch1+1];
        int t2=M[ch2+1];
        if(t1>t2)swap(t1,t2);
        next[t1][t2]++;
    }
    for(int i=2; i<=n; i++)
    {
        win[1]+=next[1][i];
    }
}
int fa[3000];
int idx[3000];
bool vis[3000];
bool BFS(int s,int t)
{
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    fa[s]=s;
    vis[s]=1;
    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        if(now==t)return 1;
        for(int i=0; i<V[now].size(); i++)
        {
            int u=V[now][i].to;
            int w=V[now][i].val;
            if(w>0&&!vis[u])
            {
                vis[u]=1;
                fa[u]=now;
                idx[u]=i;
                Q.push(u);
            }
        }
    }
    return 0;
}
void play()
{
    for(int i=2; i<=n; i++)
    {
        if(win[i]>=win[1])
        {
            printf("No\n");
            return;
        }
    }//判断是否没开始就不能满足了
    int st=1;
    for(int i=2; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            Link[i][j]=++st;
        }
    }
    for(int i=2; i<=n; i++)
    {
        Link[i][i]=++st;
    }
    st++;
    LL com=0;
    for(int i=2; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            if(next[i][j]!=0)
            {
                int val=next[i][j];
                int v=Link[i][j];
                com+=val;
                V[1].push_back((he)
                {
                    v,val,V[v].size()
                });
                V[v].push_back((he)
                {
                    1,0,V[1].size()-1
                });
                int u1=Link[i][i];
                int u2=Link[j][j];
                V[v].push_back((he)
                {
                    u1,val,V[u1].size()
                });
                V[u1].push_back((he)
                {
                    v,0,V[v].size()-1
                });
                V[v].push_back((he)
                {
                    u2,val,V[u2].size()
                });
                V[u2].push_back((he)
                {
                    v,0,V[v].size()-1
                });
            }
        }
    }
    for(int i=2; i<=n; i++)
    {
        int id=Link[i][i];
        int val=win[1]-win[i]-1;
        V[id].push_back((he)
        {
            st,val,V[st].size()
        });
        V[st].push_back((he)
        {
            id,0,V[id].size()-1
        });
    }

    LL MAX=0;
    while(BFS(1,st))
    {
        int MIN=2*INF;
        int now=st;
        while(fa[now]!=now)
        {
            int f=fa[now];
            int id=idx[now];
            MIN=min(MIN,V[f][id].val);
            now=f;
        }
        MAX+=MIN;
        now=st;
        while(fa[now]!=now)
        {
            int f=fa[now];
            int id=idx[now];
            int idd=V[f][id].id;
            V[f][id].val-=MIN;
            V[now][idd].val+=MIN;
            now=f;
        }
    }
    if(MAX==com)printf("Yes\n");
    else printf("No\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?problemId=1891

题意：给你一个最终的数组，求初始数组，初始数组转化为最终数组的过程如下。假设有a1,a2...a8

第一次:a1+a2,a3+a4,a5+a6,a7+a8,a1-a2,a3-a4,a5-a6,a7-a8这八个数，

第二次:a1+a2+a3+a4,a5+a6+a7+a8,a1+a2-a3-a4,a5+a6-a7-a8,a1-a2,a3-a4,a5-a6,a7-a8,

第三次:a1+a2+a3+a4+a5+a6+a7+a8,a1+a2+a3+a4-a5-a6-a7-a7,a1+a2-a3-a4,a5+a6-a7,a8,a1-a2,a3-a4,a5-a6,a7,a8;

知道最后一项的第一项是从a1加到a8的时候停止，然后给你最终数列，即第三次的结构，求a1~a8,

分析：先从简单的开始，就拿例子直接来，可以发现我们加入可以把第三项推到第二项，然后把第二项推到第一项，最后把第一项还原成最初项，答案就出来了。怎么把第三项还原成第二项?可以发现第三项前面两项相加除2就是第二项的第一个，相减除2就是第二项的第二个，然后其余的不变。然后第二项怎么还原成第一项，发现第二项的第一个加第三个除以2是第一项的第一个，相减除以2是第一项的第二个，那么规律就有了。假设第三项为第一层，我们只把i从1枚举到层数，然后ai+ai+层数/2就是下面的相对应的项，ai-ai+层数/2也是相对应的项，怎么知道相对应的项，，我是来个下标计算的，因为每次都是增加两个，且是递增的，所以只要把下标进行改变就可以知道对应的是下一层哪个项了，其中我还有个辅助数组，因为如果ai在计算时就改变肯定会影响最终 结果计算完成后，层数就要乘以2，因为是2倍改变，然后就可以啪啪啪，AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=300;
int n;
int ai[maxn];
int bi[maxn];
void init()
{
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
}
int ci[]= {1,2,4,8,16,32,64,128,256};
void play()
{
    if(n==1)
    {
        printf("%d\n",ai[1]);
        return;
    }
    int e=0;
    for(int i=0; i<=8; i++)
    {
        if(ci[i]<<1==n)
        {
            e=i;
            break;
        }
    }
    for(int i=0; i<=e; i++)
    {
        int st=1;
        for(int j=1; j<=n; j++)bi[j]=ai[j];
        for(int j=1; j<=ci[i]; j++)
        {
            int p=(ai[j]+ai[j+ci[i]])>>1;
            int q=(ai[j]-ai[j+ci[i]])>>1;
            bi[st]=p;
            bi[st+1]=q;
            st=st+2;
        }
        for(int j=1; j<=n; j++)ai[j]=bi[j];
    }
    bool first=1;
    for(int i=1; i<=n; i++)
    {
        if(!first)printf(" ");
        first=0;
        printf("%d",ai[i]);
    }
    printf("\n");

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

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

题意：就是给你一颗树包含n个点(n<=10000)和边权值，求任意两点之间的平均距离，即任意两点距离和除以有多少个点对。

分析：容易计算点对数就是n*(n-1)/2，如何求总距离和，可以考虑两个点，假设为u，v，且有条边(u,v)权值为x，这样我们就可以知道，x肯定要用u子节点的个数*v子节点的个数(其中子节点代表u下面所有的节点个数)，包含各自本身，因为u子节点到v子节点必定要经过(u,v）这条边，这样的话我们就可以递归处理了，假设当前节点为u，它的子节点数加它本身有p个，则它父亲节点v那一块就有n-p个。然后总距离就加上p*(n-p)*x了。最后啪啪啪，就可以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=12345;
int T;
vector<int> V[maxn];
vector<int> G[maxn];
int n;
void init()
{
    int u, v,w;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        V[i].clear();
        G[i].clear();
    }
    for(int i=1; i<n; i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        u++;
        v++;
        V[u].push_back(v);
        V[v].push_back(u);
        G[u].push_back(w);
        G[v].push_back(w);
    }
}
double ans;
int DFS(int now,int fa,double val)
{
    int chi=1;
    for(int i=0; i<V[now].size(); i++)
    {
        int u=V[now][i];
        int w=G[now][i];
        if(u==fa)continue;
        chi+=DFS(u,now,w);
    }
    int oth=n-chi;
    ans=ans+(val*oth*chi);
    return chi;
}
void play()
{
    ans=0;
    DFS(1,-1,0);
    double fm=(n*(n-1)/2);
    printf("%.10f\n",ans/fm);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}

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

题意：给你N个数ai 1<=i<=n,N<=1000，以及Q个查询,Q<=100000，每个查询有两个整数L,R 求[L,R]逆序对的数量(逆序对就是当i<j 时，ai>aj)

分析：要求[L,R]之间的逆序对数量，且Q<=100000,我们可以O（n^2)的时间求出[i,j]之间的逆序对的数量，i<=j,然后用O（1）的时间查询答案，具体怎么算，我们先来个辅助数组fi[maxn][maxn]，其中maxn是题目给的最大N，因为N最大是1000，所以数组大小为1000000，不会爆空间，然后我们令fi[i][j]，表示以i为逆序对的端点，然后计算j从i~1，以j为右端点的总数，用递推就可以在O（n^2)算出来,接着来个sum[maxn][maxn]数组，这个数组就是答案，其中sum[i][j]表示从i到j一共用多少组逆序对，因为我们有fi数组，所以只要累加fi数组就可以了，j从i到n，然后sum[i][j]=sum[i][j-1]+fi[j][i];这个怎么解释，好好想想就知道了，假设我们要知道从i到j的sum，因为我们已经知道sum[i][j-1]的sum了，而以j结尾，且已i开始的之间的总数就是fi[j][i]，所以加上就是答案，复杂度O（n*n+Q),然后啪啪啪，就可以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=1234;
LL ai[maxn];
LL fi[maxn][maxn];
LL sum[maxn][maxn];
int n,Q;
void init()
{
    for(int i=1; i<=n; i++)scanf("%I64d",&ai[i]);
}
void play()
{

    memset(fi,0,sizeof(fi));
    memset(sum,0,sizeof(sum));
    for(int i=1; i<=n; i++)
    {
        fi[i][i]=0;
        for(int j=i-1; j>=1; j--)
        {
            fi[i][j]=fi[i][j+1];
            if(ai[i]<ai[j])
            {
                fi[i][j]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        sum[i][i]=0;
        for(int j=i+1;j<=n;j++){
            sum[i][j]=sum[i][j-1]+fi[j][i];
        }
    }
    int L,R;
    while(Q--)
    {
        scanf("%d%d",&L,&R);
        printf("%I64d\n",sum[L][R]);
    }

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

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

题意：给你个没有括号的正确表达式，其中只包含*和+，和1~9的数字，添加一个括号，使得最后的数字最大。

分析：假设一共有n个数字，其实就是在选择两个标i和j(i<=j)使得1~i-1和i~j和j+1~n的计算最大。具体可以维护前缀和后缀，具体需要维护哪些值，前缀的话，假设从1~i,我们维护这个值的大小，但是还不够，因为我们不知道紧接的是*还是+,如何是+的话还是很好处理的，只要把两个相加就好了，如果是乘，我们还得维护1~i最后一个+后面的数字的大小，因为我们要把它与后面的数字相乘然后后缀也是一样的，维护相同的值，不一样的是方向相反，因为我们如果从前面开始，后缀就没办法维护了。具体求数组的方法是使用栈来求(这里就不细讲，是每个人应该会的)假设我们已经求的前缀的和li和前缀要维护最右边的数字lvali 和后缀的和ri和维护最左边的值rvali，接下来就是枚举需要加括号的地方。假设为在i前面加和在j后面加。则有

求的前缀到i-1的值为 ls，后缀到j+1的值为rs，且lval为v1 ，rval为v2，中间的i到j的结果为s。

(1)如果i前面的符号是*和j后面的符号是*,则大小sum就为ls+rs-v1-v2+v1*s*v2

因为v1和v2要和s乘为新的数，所以要减去。

(2)如果只有i前面的符号是*,则大小sum为ls-v1+v1*s+rs;

因为后面的话是直接加上去的。

(3)如果只有j+1后面的符号为*，则跟(2)差不多性质

(4)如果i从1开始，则只要考虑rs的情况

(5)如果j到了n,则只要考虑ls的情况

复杂度为O（n*n）然后啪啪啪，就可以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=5678;
char ch[maxn];
int  ai[maxn];
int  bi[maxn];
int len;
LL lr[2][maxn];
LL limit[2][maxn];

int st;
void get()
{
    for(int i=0; i<2; i++)
    {
        int s=1;
        int c=1;
        int cz=-1;
        if(i==1)
        {
            s=st;
            c=-1;
            cz=0;
        }
        lr[i][s]=ai[s];
        vector<LL> V;
        LL sum=ai[s];
        V.push_back(ai[s]);
        limit[i][s]=ai[s];
        for(int j=1; j<st; j++)
        {
            s=s+c;
            if(bi[s+cz]==1)
            {
                LL q=V[V.size()-1];
                LL p=q*ai[s];
                V[V.size()-1]=p;
                sum=sum-q+p;
            }
            else
            {
                V.push_back(ai[s]);
                sum=sum+ai[s];
            }
            lr[i][s]=sum;
            limit[i][s]=V[V.size()-1];
        }

    }

}
void init()
{
    len=strlen(ch+1);
    st=0;
    for(int i=1; i<=len; i++)
    {
        if(ch[i]=='*')
            bi[st]=1;
        else if(ch[i]=='+')
            bi[st]=0;
        else
        {
            st++;
            ai[st]=ch[i]-'0';
        }
    }
    get();
}
void play()
{
    LL MAX=0;
    for(int i=1; i<=st; i++)
    {
        vector<LL>V;
        LL sum=0;
        for(int j=i; j<=st; j++)
        {
            if(j==i)
            {
                V.push_back(ai[i]);
                sum=ai[i];
            }
            else
            {
                if(bi[j-1]==1)
                {
                    LL q=V[V.size()-1];
                    LL p=q*ai[j];
                    V[V.size()-1]=p;
                    sum=sum-q+p;
                }
                else
                {
                    V.push_back(ai[j]);
                    sum=sum+ai[j];
                }
            }
            int ln=i-1;
            int rn=j+1;
            LL ll=lr[0][ln];
            LL rr=lr[1][rn];
            if(ln>=1&&rn<=st)
                if(bi[ln]==1&&bi[j]==1)
                    MAX=max(MAX,ll+rr-limit[0][ln]-limit[1][rn]+limit[0][ln]*limit[1][rn]*sum);
                else if(bi[ln]==1)
                    MAX=max(MAX,ll+rr-limit[0][ln]+limit[0][ln]*sum);
                else if(bi[j]==1)
                    MAX=max(MAX,ll+rr-limit[1][rn]+limit[1][rn]*sum);
                else
                    MAX=max(MAX,ll+rr+sum);
            else if(ln>=1)
                if(bi[ln]==1)
                    MAX=max(MAX,ll-limit[0][ln]+limit[0][ln]*sum);
                else
                    MAX=max(MAX,ll+sum);
            else if(rn<=st)
                if(bi[j]==1)
                    MAX=max(MAX,rr-limit[1][rn]+limit[1][rn]*sum);
                else
                    MAX=max(MAX,rr+sum);
            else
                MAX=max(MAX,sum);
        }
    }
    printf("%I64d\n",MAX);
}
int main()
{
    while(scanf("%s",ch+1)!=EOF)
    {
        init();
        play();

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