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

飞机票：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://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://codeforces.com/problemset/problem/510/C

题意：就是给你n个字符串，按字典序从上到下递增，判断字典序是否正确，正确输出任意一个可行的方案，不行则impossible

分析：刚开始看对题，但是自己想法错误，大晚上想法不行啊后来还是想回来了，我的想法是分治法。

假设n个字符串，第i个到第j个（i<j）的第一个字符都是一样的，则它们还得比较第二个字符。。。。第k个字符，直到不一样为止。

当不一样时我们就可以加边了，假设不一样的字符是第k个，则字符串i的第k个字符<字符串j的第k个字符，加单向边，一直到最后，然后用floyd判断有无环，有环则impossible，没环则输出可行方案可以方案怎么输出，我是枚举的，因为数量不大，假设当前的字符是i，则判断有没有j可以到i的，如果j输出过了，则跳过，如果没有，则可以证明i是当前最小的，把i输出来，然后标记i就行了。。。这里还有个地方，就是字符串长度的问题，假设到比较第k个字符串了，来个标记，如果从i到p是空的，p+1是不空的，则改变标记，这样后面如果有空的，就是impossible，直接返回~

PS：大晚上明明返回标记了，后面忘了判断输出了，fst了改一下就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;
map<char,int> M;
map<int,char> M1;
const int maxn=30;
int ai[maxn][maxn];
char ch[123][123];
int n;
int len;
void init()
{
    len=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%s",ch[i]+1);
        int q=strlen(ch[i]+1);
        len=max(len,q);
    }
}
bool flag;
int st;
void DFS(int now,int l,int r)
{
    if(!flag)return ;
    char before='A';
    int ks=0;
    int os=-1;
    for(int i=l; i<=r; i++)
    {
        int q=strlen(ch[i]+1);
        char p=ch[i][now];
        if(now>q&&os==-1)continue;
        os=1;
        if(now>q)
        {
            flag=0;
            return;
        }
        if(before=='A')
        {
            ks=l;
            before=ch[i][now];
        }
        else
        {
            if(before==p)
            {
                continue;
            }
            else
            {
                if(M[before]==0)
                {
                    M[before]=st;
                    M1[st]=before;
                    st++;
                }
                if(M[p]==0)
                {
                    M[p]=st;
                    M1[st]=p;
                    st++;
                }
                int u=M[before];
                int v=M[p];
                before=p;
                ai[u][v]=1;
                if(i-1==ks)
                {
                    ks=i;
                    continue;
                }
                else
                {
                    DFS(now+1,ks,i-1);
                }
                ks=i;
            }
        }
    }

    if(r==ks)return;
    else if(ks==0)return;
    DFS(now+1,ks,r);
}
bool vis[maxn];
void play()
{
    memset(ai,0,sizeof(ai));
    memset(vis,0,sizeof(vis));
    flag=1;
    M.clear();
    M1.clear();
    st=1;
    DFS(1,1,n);
    if(!flag)
    {
        printf("Impossible\n");
        return;
    }
    for(int k=1; k<=29; k++)
    {
        for(int i=1; i<=29; i++)
        {
            for(int j=1; j<=29; j++)
            {
                if(ai[i][k]&&ai[k][j])
                {
                    ai[i][j]=1;
                }

            }
        }
    }

    for(int i=1; i<=29; i++)
    {
        for(int j=1; j<=29; j++)
        {
            if(ai[i][j]&&ai[j][i])
            {
                printf("Impossible\n");
                return;
            }
        }
    }
    for(char  i='a'; i<='z'; i++)
    {
        if(M[i]==0)printf("%c",i);
    }
    while(1)
    {
        bool ok=0;
        for(int i=1; i<=29; i++)
        {
            if(vis[i])continue;
            if(M1[i]!=0)
            {
                bool flag=1;
                for(int j=1; j<=29; j++)
                {
                    if(vis[j])continue;
                    if(M1[j]==0)continue;
                    if(ai[j][i])
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag)
                {
                    printf("%c",M1[i]);
                    vis[i]=1;
                    ok=1;
                }
            }
        }
        if(!ok)break;
    }
    printf("\n");

}
int main()
{

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