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

飞机票： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21663

题意：就是给你n个需要处理的事情，第i个必须在li~ri完成，且数量是wi，完成时最大的速度最小是多少；

分析：求最大的速度最小我们可以使用二分来选择速度，但是怎么判断呢？果然还是太菜；其实可以根据时间来判断；具体怎么判断，时间递增，假设当前是j，则把所有左端点小于等于j的都压入到队列中，且按右端点排序（why?因为右端点越大我们可以在后面处理，所以这里贪心的想法），然后设当前还可以处理now个任务，当前碰到的是i，且任务数是w，我们可以判断下now和i的大小，把now和i都减去小的那个，如果now==0了，则退出了，因为不能再处理任务了，如果w不等于0则还没处理完，在压入到队列里。。。没一次j处理玩，可以判断下，如果最小的那个没处理完的r<=j则表明速度太小，返回false（why？？）因为下面大于j的时候已经不能处理它了，如果队列空了，且处理完了那么返回true，你懂得。。。。起先没有想到，，，太渣了。还是看别人的才反映过来。。。啪啪啪，就可以AC了~

/*
Author:Chieh
Because Of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=12345;
struct he
{
    int l,r,w;
    bool operator <(const he &a)const
    {
        return r > a.r;
    }
} JLJ[maxn];
priority_queue<he> q;
bool cmp(he a,he b)
{
    return a.l<b.l;
}
int n;
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d%d",&JLJ[i].l,&JLJ[i].r,&JLJ[i].w);
    }
}
bool check(int x)
{
    int i = 1, j = 0;
    while (!q.empty())
        q.pop();
    while (1)
    {
        while (i <= n && JLJ[i].l <= j)
            q.push(JLJ[i++]);
        int now = x;
        while (now != 0 && !q.empty())
        {
            he temp = q.top();
            q.pop();
            int m = min(now,temp.w);
            now -= m;
            temp.w -= m;
            if (temp.w != 0)
                q.push(temp);
        }
        j++;
        if (!q.empty() && q.top().r <= j)
            return false;
        if (q.empty() && i ==n+1)
            return true;
    }
}
void play()
{
    sort(JLJ+1,JLJ+1+n,cmp);
    int l=1;
    int r=1000000000;
    int MIN=r;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {

            r=mid-1;
            MIN=min(mid,MIN);
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%d\n",MIN);
}
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=16451

题意：就是给你一棵树，给你一个服务器，求在其余非叶子节点上放服务器，使任意的叶子节点到最近服务器的距离不超过k

分析：可以根据树形的性质来进行解决

具体步骤：用pair来存数据，如果first是1就是说有叶子节点没有服务器，如果first是2就说有服务器在；所以当我们搜到叶子节点的时候，返回(1,1),当搜到父子节点，我们对返回的子节点进行贪心选择，如果是1就选择距离最大的没有服务器的叶子节点，如果是2就选择最近的服务器，如果1+2的距离（1，为叶子节点最远距离，2为服务器最近距离）<=k那么就是可以访问到，则返回2，且服务器的距离要加1；如果>k那么就是说访问不到，那么我们要判断，如果1==k则必须架服务器了，不加则不满足条件，如果<k则返回叶子节点距离加1.一直递归到s节点，且s节点本身的2为0。。。ok复杂度为O（n-1)即边的数量；

啪啪啪。就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
vector<int> V[maxn];
int n,T,s,k;
void init()
{
    scanf("%d%d%d",&n,&s,&k);
    for(int i=1; i<=n; i++)V[i].clear();
    int u,v;
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        V[u].push_back(v);
        V[v].push_back(u);
    }
}
int MIN;
pair<int,int> DFS(int now,int fa)
{
    int a1=-1;
    int a2=-1;
    if(now==s)a2=0;
    for(int i=0; i<V[now].size(); i++)
    {
        int v=V[now][i];
        if(v==fa)continue;
        pair<int,int> p= DFS(v,now);
        if(p.first==1)
        {
            a1=max(a1,p.second);
        }
        else
        {
            if(a2==-1)a2=p.second;
            else
                a2=min(a2,p.second);
        }
    }
    if(a1==-1&&a2==-1)
    {
        return make_pair(1,1);
    }
    if(a1!=-1&&a2!=-1)
    {
        if(a1+a2<=k)
        {
            return make_pair(2,a2+1);
        }
        else
        {
            if(a1==k)
            {
                MIN++;
                return make_pair(2,1);
            }
            return make_pair(1,a1+1);
        }
    }
    if(a1==-1)
    {
        return make_pair(2,a2+1);
    }
    if(a1==k)
    {
        MIN++;
        return make_pair(2,1);
    }
    return make_pair(1,a1+1);
}
void play()
{
    MIN=0;
    DFS(s,0);
    printf("%d\n",MIN);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    return 0;
}

飞机票：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34699

题意：就是给你初始的汉诺塔大小升序，和目标的汉诺塔大小升序，求最小的移动步数；

分析：刚开始没有想法，后来想到了万法归宗，就是已知初始状态变回原始状态也是可行的就是说假如A,B,C三个分别有编号1，2，3的盘子，我们可以变回A，B，C只有A上有3个盘子的状态好复杂，所以我是用了反推的方法，先设A,B,C有3个盘子，然后推出A,B,C分别有1个盘子的步数为几步。。所以加个判断，加入当前盘子是A，当前要移动的最大盘是k，要移动到B，则上面的k-1个盘都要移动到C才行，就是2^(k-1)步，这里不用减1，因为k要移一步。这样先把初始的都先归到一个盘子一共要几步，然后根据当前的盘要移动到哪进行计算步数就ok了，

解释下吧：

对于第一个样例，我们可以把第3个盘提出来，则1，2个盘回到C上去，这样一共要3步+第三个盘要1步，就是4步，然后1，2都在C上，当要把2移到B上时，我们得把2上面的移到A上，则要1步+第二个盘要1步，就是2步，最后再加上第一个盘移一次就是答案了，7；

啪啪啪~就可以AC了

/*
Author:Chieh
Grow up happy
*/
#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=67;
struct he
{
    int s,e;
} JLJ[maxn];
int n;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d",&JLJ[i].s);
    for(int i=1; i<=n; i++)scanf("%d",&JLJ[i].e);
}
void play()
{
    int st=-1;
    for(int i=n; i>=1; i--)
    {
        if(JLJ[i].s!=JLJ[i].e)
        {
            st=i;
            break;
        }
    }
    if(st==-1)
    {
        printf("0\n");
        return;
    }
    LL sum=0;
    int now=6-JLJ[st].s-JLJ[st].e;
    for(int i=st-1; i>=1; i--)
    {
        if(JLJ[i].s==now)
            continue;
        else
        {

            sum+=((1LL)<<(i-1));
            now=6-JLJ[i].s-now;
        }
    }
    sum++;
    now=6-JLJ[st].s-JLJ[st].e;
    for(int i=st-1; i>=1; i--)
    {
        if(JLJ[i].e==now)continue;
        else
        {
            sum+=((1LL)<<(i-1));
            now=6-JLJ[i].e-now;
        }
    }
    printf("%lld\n",sum);
}
int main()
{
    int Ca=1;
    while(scanf("%d",&n)!=EOF)
    {   if(n==0)break;
        init();
        printf("Case %d: ",Ca++);
        play();
    }
    return 0;
}

飞机票： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=24665

题意：就是说给你个矩阵，你把0变为1，使矩阵中各个点的上下左右相加为偶数（如果上下左右存在的话），求改变最少的0的数量

分析：如果枚举每个点的话肯定就TLE了，但是我们可以只枚举第一行就行。。。这样就可以推出下面所有的行，因为下面的行可以根据当前行的上左右推出来，复杂度为2^n*(n^2),可以接受~，啪啪啪，AC啦

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#define LL long long
using namespace std;
const int maxn=20;
int T,n;
int ai[maxn][maxn];
int bi[maxn][maxn];
void init()
{
    scanf("%d",&n);
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            scanf("%d",&ai[i][j]);
        }
    }
}
int MIN;
void DFS(int depth,int sum)
{

    if(depth>n)
    {
        int now=sum;
        memset(bi,0,sizeof(bi));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                bi[i][j]=ai[i][j];
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                int tm=bi[i-1][j]+bi[i][j-1]+bi[i][j+1];
                if(tm%2==0)
                {
                    if(bi[i+1][j]==1)return;
                    else continue;
                }
                else
                {
                    if(bi[i+1][j]==0&&i+1<=n)
                    {
                        bi[i+1][j]=1;
                        now++;
                    }
                    else if(bi[i+1][j]==1)continue;
                    else
                    {
                        return;
                    }
                }
            }
        }
        MIN=min(now,MIN);
        return;

    }
    DFS(depth+1,sum);
    if(ai[1][depth]==0)
    {
        ai[1][depth]=1;
        DFS(depth+1,sum+1);
        ai[1][depth]=0;
    }

}
void play(int Case)
{
    MIN=1000000000;
    DFS(1,0);
    if(MIN==1000000000)MIN=-1;
    printf("Case %d: %d\n",Case,MIN);
}
int Case;
int main()
{   Case=1;
    scanf("%d",&T);
    while(T--)
    {
        init();
        play(Case);
        Case++;
    }
    //cout << "Hello world!" << endl;
    return 0;
}

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

分析：其实这个题难懂的是题意啊~~~后来百度下骰子游戏菜知道这个题的意思。。先来看下骰子游戏的规则

规则略微有点复杂，刚开始可能不太明白，我详细解释下：

你的终极目标是占领所有的地块，你的颜色是紫色。
占领地块的方法就是用你的地块攻击相邻的地块，胜负由这两个地块上的骰子掷出点数决定。
1）如果你赢了，那么原来地块上的骰子变成一个，新占领地块上的骰子数 = 原来地块骰子数 - 1 ；
2）如果平了或者输了，那么你的地块上的骰子也会变成一个。
只要你的地块上的骰子数大于一个，就可以攻击别人。
在攻击结束时，点击 "End Turn" 可以补充兵力，补充的总数是你此时连在一起的地块的总数，分配则是随机的。每个地块上最多有 8 颗骰子。

提示策略：刚开始的时候尽量把自己的地都连到一起，中期的时候怎样布阵对于进攻和防守都很重要，后期基本都是八颗八颗的硬碰硬了 :P

看了应该就秒懂了吧。反正题目就是说给你攻击者的骰子数和防御者的骰子数。然后求攻击者赢得概率（就是说攻击者的点数严格大于防御者的点数）。。。这里要注意：如果攻击者的骰子数是1，那么就不能攻击，意思就是说赢得概率是0。。。然后你就可以根据概率来搞了。。。对于数学概率的渣渣，，，只有这么一个想法就是说把攻击者的点数枚举。。。怎么枚举法？？

已知n，那么攻击者的点数就是在n~6*n之间。。。然后枚举每个点数所占的概率。。。就是 k的可能方法有几种/6^n就是k的概率、、然后你要赢：那么就是m~6*m之间小于k的概率 那么就是(m~k-1)之间所有可能的方法/6^m的概率、、、然后从将所有的相加就是答案。。。这里计数方法，我先是DFS。。。其实也不慢，但是也不快。。。后来想到了DP。。。就是按骰子数来DP，然后当前骰子有6中可能1~6,然后看前面的是否出现过k,出现过，那么当前(k+(1~6））就要累加了。。。这样复杂度就直接变为(6*n)^2

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#define LL long long
using namespace std;
int ai[2][9][49];
int bi[2];
int p;
void play()
{
    if(bi[0]<=1)
    {
        printf("0\n");
        return;
    }
    for(int z=0; z<=1; z++)
    {
        int e=6*bi[z];
        memset(ai[z][0],0,sizeof(ai[z][0]));
        ai[z][0][0]=1;
        for(int j=1; j<=bi[z]; j++)
        {
            memset(ai[z][j],0,sizeof(ai[z][j]));
            for(int i=1; i<=6; i++)
            {
                for(int k=0; k<=e; k++)
                {
                    if(ai[z][j-1][k]>0)
                    {
                        ai[z][j][k+i]+=ai[z][j-1][k];
                    }
                }
            }
        }
    }
    int fm=pow(6.0,bi[0]);
    int fm1=pow(6.0,bi[1]);
    for(int i=1; i<=6*max(bi[0],bi[1]); i++)
    {
        ai[1][bi[1]][i]=ai[1][bi[1]][i]+ai[1][bi[1]][i-1];
    }
    double over=0;
    for(int i=1; i<=6*bi[0]; i++)
    {
        double pop=((double)(ai[0][bi[0]][i]))/fm;
        double pop1=((double)(ai[1][bi[1]][i-1]))/fm1;
        over=over+(pop*pop1);
    }
    printf("%.8lf\n",over);
}
int main()
{
    while(scanf("%d%d",&bi[0],&bi[1])!=EOF)
    {
        play();
    }
    return 0;
}

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

由于昨天有事。。。所以没怎么细想。。。然后一直以为只要深度相同。。。然后子节点个数相同就可以了。。。然后就一直Wa。。。后来自己把自己的想法推翻了。。。直接看下图：

然后这里的话。。。如果按我起先的想法肯定是wa的因为1层都有2个子节点。二层有3个节点和2个节点。三层有2，0，0，3，0个节点

但是这两棵树明显不同、、debug爽啊。。。接着我的想法就是。。。那把每个节点的深度算出来和他的子树节点的深度都算出来。。。然后排序比较。。。这个想法明显是正确。。但是速度不快啊~~~囧。然后百度了一下。。。有一种方法是跟括号匹配差不多。。。就是说经过父节点（，回到了父节点就），然后括号里面的可以交换位置。。。交换出最小字典序。。。然后比较是否相同，还有一种方法：好像说是只要把深度算出来然后计算子树节点数排序比较就可以了。。。但是为什么呢。。感觉也不怎么对。。。画个图。。。其实这个想法是错误的

这个的序列是0010101001011100101011和0010101010101100010111。。。然而这个是diff。但是前面的跑出来的是same。。所以错误的。。。估计测试数据没有这个数据。我还是不传输错误的代码了。。。就用那个速度慢的吧

/*
Author:Chieh
Grow up happy
*/
#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=3456;
char ch[2][maxn];
struct he
{
    int dep;
    vector<int> V;
} JLJ[2][1567];
void init()
{
    scanf("%s%s",ch[0]+1,ch[1]+1);
}
int idx,st, p;
int len;
void DFS(int now,int dep)
{
    JLJ[p][now].dep=dep;
    while(idx<=len&&ch[p][idx]=='0')
    {
        idx++;
        st++;
        int q=st;
        DFS(q,dep+1);
        for(int j=0; j<JLJ[p][q].V.size(); j++)
        {
            JLJ[p][now].V.push_back(JLJ[p][q].V[j]+1);
        }
    }

    JLJ[p][now].V.push_back(0);
    sort(JLJ[p][now].V.begin(),JLJ[p][now].V.end());
    idx++;
    return;

}
bool cmp(he a,he b)
{
    if(a.dep!=b.dep)return a.dep<b.dep;
    if(a.V.size()!=b.V.size())return a.V.size()<b.V.size();
    for(int i=0; i<a.V.size(); i++)
    {
        if(a.V[i]>b.V[i])
        {
            return 1;
        }
        else if(a.V[i]<b.V[i])
        {
            return 0;
        }
    }
    return 0;
}
void play()
{
    if(strlen(ch[0]+1)!=strlen(ch[1]+1))
    {
        printf("different\n");
        return;
    }
    len=strlen(ch[0]+1);
    for(int i=0; i<=len/2; i++)
    {
        JLJ[0][i].dep=0;
        JLJ[0][i].V.clear();
        JLJ[1][i].dep=0;
        JLJ[1][i].V.clear();
    }
    idx=1;
    st=0;
    p=0;
    DFS(0,0);
    idx=1;
    st=0;
    p=1;
    DFS(0,0);
    sort(JLJ[0],JLJ[0]+st+1,cmp);
    sort(JLJ[1],JLJ[1]+st+1,cmp);
    //cout<<st<<endl;
    for(int i=0; i<=st; i++)
    {
        if(JLJ[0][i].dep!=JLJ[1][i].dep)
        {
            printf("different\n");
            return;
        }
        if(JLJ[0][i].V.size()!=JLJ[1][i].V.size())
        {
            printf("different\n");
            return;
        }
        for(int j=0; j<JLJ[0][i].V.size(); j++)
        {
            if(JLJ[0][i].V[j]!=JLJ[1][i].V[j])
            {
                printf("different\n");
                return;
            }
        }

    }
    printf("same\n");
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}

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

分析：起先想要把所有可能求出来。。。然后二分答案。。。但是内存不够呀然后各种优化啊。。。还是不行啊。。。果然是彩笔~接着就想着暴力。。。暴力你妹啊！！！各种TLE啊~~~没办法了。。想着在线二分。。。但是二分k还是r呢。。。第一直觉是k。。然后就往k里面想了。。。发现k无法正常二分。。。必需要有什么东西可以限制k的大小就可以二分。。。想想r不是很小么40...那就用r来限制k二分。。。接着就是各种悲剧渣死了。。。各种Wa。。。后来看了别人的题解。。。发现我二分里面有些是多余的。。。果然是自己贱啊但是想法还是正确的。。最后改了几个地方就AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
LL n;
LL cal(int e)
{
    LL l=2,r=min(n,1000000LL);
    while(l<=r)
    {
        LL mid=(l+r)/2;
        LL over=1;
        LL tm=1;
        for(int i=1; i<=e; i++)
        {
            tm=tm*mid;
            over+=tm;
            if(over>n+1)break;
        }
        if(over==n+1||over==n)return mid;
        if(over>n+1)r=mid-1;
        else
        {
            l=mid+1;
        }
    }
    return 0;
}
void play()
{
    LL a=1,b=n-1;
    for(int i=2; i<=39; i++)
    {
        LL t=cal(i);
        if(t==0)continue;
        if(t*i<a*b)
        {
            a=i;
            b=t;
        }
        else if(t*i==a*b)
        {
            if(a>i)
            {
                a=i;
                b=t;
            }
        }
    }
    printf("%lld %lld\n",a,b);
}
int main()
{

    while(scanf("%lld",&n)!=EOF)
    {
        play();
    }
    return 0;
}

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

今天起来一道2-sat。。。巩固知识~~~

分析：题目的意思就是说求函数最大能递归到第几层。。。告诉你a,b,c数组。。。x数组未知。。。题目秒懂。。。那个程序就不解释了，ACMer肯定能够看得懂:).这种题该怎么搞？？其实这里发现一个限制递归的地方就是

if dep < m and x[a[dep]] + x[b[dep]]
 != c[dep] then go(dep + 1, n, m)

那个<m就不用讲了。。如果>=m就溢出a,b,c数组了。。。那么其实就是后面的那个条件。。。我们二分0~（m-1）。假设当前的值是mid。。。那么就可以加边了。。。循环从0~mid。。。取出a[k]和b[k],c[k]的值（语文有限。。。望看懂~）那么如果c[k]的值是0.那么x[a[k]]+x[b[k]]的值至少有一个是1 如果是c[k]是1 那么两个值必须相同。。。如果是2 那么两个值肯定不同。。这里发现其实这个跟那个位运算2-sat题型差不多。。。然后把边添加了跑一下tarjan。。。如果不行。。说明递归层太深、、、r=mid-1.如果可以，那么l=mid+1...这样找到最大值即可~啪啪啪。。。TLE（vector忘记清0了。。。bug啊！！！）最后只要把深度+1就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=456;
const int Maxn=12345;
struct he
{
    int a,b,c;
} JLJ[Maxn];
vector<int> V[maxn];
int n,m;
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d",&JLJ[i].a,&JLJ[i].b,&JLJ[i].c);
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    int l=0;
    int r=m-1;
    int over=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        for(int i=0;i<=2*n;i++)V[i].clear();
        for(int i=0; i<=mid; i++)
        {
            int u=JLJ[i].a*2;
            int v=JLJ[i].b*2;
            int t=JLJ[i].c;
            if(t==2)
            {
                V[u].push_back(v^1);
                V[v].push_back(u^1);
            }
            else if(t==1)
            {
                V[u].push_back(v);
                V[v].push_back(u);
                V[u^1].push_back(v^1);
                V[v^1].push_back(u^1);
            }
            else
            {
                V[u^1].push_back(v);
                V[v^1].push_back(u);
            }
        }
        indexx=cntnum=0;
        scnt=-1;
        memset(dfn,-1,sizeof(dfn));
        memset(instack,0,sizeof(instack));
        for(int i=0; i<2*n; i++)
        {
            if(dfn[i]==-1)tarjan(i);
        }
        bool flag=1;
        for(int i=0; i<n; i++)
        {
            if(belong[i*2]==belong[i*2+1])
            {
                flag=0;
                break;
            }
        }
        if(!flag)
        {
            r=mid-1;
            continue;
        }
        over=max(over,mid);
        l=mid+1;
    }
    printf("%d\n",over+1);

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

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

从这一题我对2-sat有更深的了解了。。。起先以为2-sat要添加一定可行的边。。。其实不然。。。要求添加可能可以的边。。。意思就是说两个组每个组2个人A1 A2,B1,B2 如果A1选了不能选B1，那么不管A2选了能不能选B1。。。都添加A2 B1这条边搞了一天2-sat 什么鬼~~~反正现在深入了解了。。。好了。。直接正题~~~

分析。。这题就是说给你n个组。每个组有两个球。。每个球有坐标。。从每个组里选择一个球。。且所有球不重叠。。。球最大球径是多少。。。其实就是2-sat问题。。。怎么搞呢？？先求出每队之间的距离。。。即一共有四个距离。。。即(A1,B1),(A1,B2),(A2,B1),(A2,B2) 三维距离很简单。。。((x1-x2）^2+(y1-y2)^2+(z1-z2)^2)^0.5即可。。搜噶然后二分球径。。。这里可以剪下枝。。。怎么搞呢。。。先从上面的距离选出最大的距离作为r,l为0。。。然后在循环里面可以判断下那四个距离是否都小于R，如果小于R。。则不符合条件。。直接继续二分。。。如果有一个可以则。。。根据2-sat建边。。。这里得知道要添加可能的边（起先不知道。。Wa到死）一共有四种可能。。所以有4种添边方案。。。然后每次二分跑一下tarjan。。。如果符合条件。。则l变为mid+e...这里e是定义的精度。。。如果不可以。。那r就要变为mid-e...当可行的时候。。。可以定义一个double记录最大符合条件的球径。。。其实起先我还卡了一下为什么距离要跟球径的两倍比较。。。后来想了一下球可以转的啊。。。太菜了。。。最后精度又是个问题。。。但是只要保留4位小数就可以了。。。因为是spj。。。然后啪啪啪！！！AC！！！

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=456;
const double e=0.0001;
struct he
{
    int a,b,c;
} JLJ[maxn];
vector<int> V[maxn];
double dist[maxn][maxn];
int n;
void init()
{
    for(int i=0; i<n; i++)
    {
        scanf("%d%d%d",&JLJ[i*2].a,&JLJ[i*2].b,&JLJ[i*2].c);
        scanf("%d%d%d",&JLJ[i*2+1].a,&JLJ[i*2+1].b,&JLJ[i*2+1].c);
    }

}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
double cal(double a,double b,double c,double d,double e,double f)
{
    return sqrt((a-d)*(a-d)+(b-e)*(b-e)+(c-f)*(c-f));
}
void play()
{
    double MAX=0;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            dist[i*2][j*2]=cal(JLJ[i*2].a,JLJ[i*2].b,JLJ[i*2].c,JLJ[j*2].a,JLJ[j*2].b,JLJ[j*2].c);
            dist[i*2][j*2+1]=cal(JLJ[i*2].a,JLJ[i*2].b,JLJ[i*2].c,JLJ[j*2+1].a,JLJ[j*2+1].b,JLJ[j*2+1].c);
            dist[i*2+1][j*2]=cal(JLJ[i*2+1].a,JLJ[i*2+1].b,JLJ[i*2+1].c,JLJ[j*2].a,JLJ[j*2].b,JLJ[j*2].c);
            dist[i*2+1][j*2+1]=cal(JLJ[i*2+1].a,JLJ[i*2+1].b,JLJ[i*2+1].c,JLJ[j*2+1].a,JLJ[j*2+1].b,JLJ[j*2+1].c);
            MAX=max(MAX,dist[i*2][j*2]);
            MAX=max(MAX,dist[i*2][j*2+1]);
            MAX=max(MAX,dist[i*2+1][j*2]);
            MAX=max(MAX,dist[i*2+1][j*2+1]);
        }
    }
    double l=0;
    double r=MAX;
    double over=0;
    while(l<=r)
    {
        double mid=(l+r)/2;
        double d=mid*2;
        bool flag=1;
        for(int i=0; i<=2*n; i++)V[i].clear();
        for(int i=0; i<n; i++)
        {  if(!flag)break;
            for(int j=i+1; j<n; j++)
            {
                if(dist[i*2][j*2]<d&&dist[i*2+1][j*2]<d&&dist[i*2][j*2+1]<d&&dist[i*2+1][j*2+1]<d)
                {
                    flag=0;
                    break;
                }
                if(dist[i*2][j*2+1]<d)
                {
                    V[i*2].push_back(j*2);
                    V[j*2+1].push_back(i*2+1);
                }
                if(dist[i*2][j*2]<d)
                {
                        V[i*2].push_back(j*2+1);
                        V[j*2].push_back(i*2+1);
                }
                if(dist[i*2+1][j*2+1]<d)
                {
                    V[i*2+1].push_back(j*2);
                    V[j*2+1].push_back(i*2);
                }
                if(dist[i*2+1][j*2]<d)
                {
                    V[i*2+1].push_back(j*2+1);
                    V[j*2].push_back(i*2);
                }

            }
        }
        if(!flag){
            r=mid-e;
            continue;
        }
        indexx=cntnum=0;
        scnt=-1;
        memset(dfn,-1,sizeof(dfn));
        memset(instack,0,sizeof(instack));
        for(int i=0; i<2*n; i++)
        {
            if(dfn[i]==-1)tarjan(i);
        }
        for(int i=0; i<n; i++)
        {
            if(belong[i*2]==belong[i*2+1])
            {
                flag=0;
                break;
            }
        }
        if(!flag)
        {
            r=mid-e;
            continue;
        }
        over=max(over,l);
        l=mid+e;

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