Chieh's Blog

Because Of Coding

ZOJ Problem Set - 1967 Fiber Network

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

题意:给你个有向图,每条有向边有字母标识,然后有查询,每个给你u,v,从u到v路径上出现了那些字母,并且字母必须在每条路径的边上。

分析:假设只有一个字母的话,那么就很简单,因为n不是特别大,如果u到v有字母,那么就标记u可以到v,接着直接flyod跑一边,接着查询,就可以根据flyod跑出来是否联通给出答案。那么因为这里是有26个字母,所以可以跑26次flyod,然后对于每次询问,对26个字母都进行一遍查找,最后输出就好。最后啪啪啪就可以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;
int n;
const int maxn=234;
int ai[27][maxn][maxn];
char ch[27];
void init()
{
    memset(ai,0,sizeof(ai));
    int u,v;
    while(scanf("%d%d",&u,&v)!=EOF&&u)
    {
        scanf("%s",ch+1);
        int len=strlen(ch+1);
        for(int i=1; i<=len; i++)
        {
            ai[ch[i]-'a'+1][u][v]=1;
        }

    }
    for(int l=1; l<=26; l++)
    {
        for(int k=1; k<=n; k++)
        {
            for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=n; j++)
                {
                    if(ai[l][i][k]&&ai[l][k][j])ai[l][i][j]=1;
                }
            }
        }
    }
}

void play()
{
    int u,v;
    while(scanf("%d%d",&u,&v)!=EOF&&u)
    {
        bool flag=1;
        for(int i=1; i<=26; i++)
        {
            if(ai[i][u][v])
            {
                printf("%c",'a'+i-1);
                flag=0;

            }
        }
        if(flag)printf("-");
        printf("\n");
    }
    printf("\n");
}
int main()
{

    while(scanf("%d",&n)!=EOF&&n)
    {
        init();
        play();

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

ZOJ Problem Set - 1995 Spiderman

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

题意:就是给你n个数,它们的和不超过1000,接着就是你可以选择加或则减,就是说初始值是0,然后n步,你可以选择加上第i个数,或则减掉第i个数,但是减掉的时候不能小于0。求最后的数字是0,且使的加到的最大值最小。求出这个路径。

分析:这个题,刚开始的想法是,先是想想加加减减看看最后能不能到达0,那么直接可以用dp,因为有加又有减,所以一维数组就很难维护了,这里我就用二维数组,dp[i][j]表示第i个数过后,能不能到达j这个高度,那么看最后能不能成为0,就是能不能到达dp[n][0]了这样可以轻易的求出能不能到达0,但是现在我们需要知道最大值最小,所以需要维护点东西,这里分2中情况(这里定义ai为第i个数的大小)

(1)假设i-1能到达j,那么i肯定能到达j+ai[i],然后我们需要更新到达j+ai[i]的最大值,假设dp[i-1][j]为i-1过后,到达j的最大值的最小值,那么如果j+ai[i]>dp[i-1][j]的话,那么就得更新最大值的最小值,因为我们必须到达j+ai[i],反之的话就是dp[i-1][j],设这个值为qn,这个值是从dp[i-1][j]推过来的,所以更新dp[i][j+ai[i]]=min(dp[i][j+ai[i]],qn),这样高度最小

(2)假设i-1能到达j,且j-ai[i]>=0,那么肯定能到达j-ai[i],接着我们就可以根据第一种情况dp,但是有个地方不同,这里比较的是j和dp[i-1][j],因为j-ai[i]<j;接着就是跟第一种情况一样,设这里的只为pn,则dp[i][j-ai[i]]=min(dp[i][j-ai[i]],pn),

根据这两种我们就知道最大值最小是什么样的情况,最后需要输出,只要用一个数组li来记录,具体怎么记录?第一种情况,如果dp[i][j+ai[i]]比原来的数要小,那么就是li[i][j+ai[i]]指向i-1的j,另一种情况就是li[i][j-ai[i]]只想i-1的j,最后反推就是答案了,然后啪啪啪就可以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=1234;
int ai[maxn];
int dp[maxn][maxn];
int li2[maxn][maxn];
int T;
int n;
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
}
vector<int> V;
void play()
{
    for(int i=0; i<=n; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            if(dp[i-1][j]==INF)continue;
            int q=j+ai[i];
            int p=j-ai[i];
            int qn=max(dp[i-1][j],q);
            if(q<=1000&&qn<dp[i][q])
            {
                dp[i][q]=qn;
                li2[i][q]=j;
            }
            int pn=max(dp[i-1][j],j);
            if(p>=0&&pn<dp[i][p])
            {
                dp[i][p]=pn;
                li2[i][p]=j;
            }
        }
    }
    if(dp[n][0]!=INF)
    {
        V.clear();
        V.push_back(2);
        int st=n-1;
        int now=li2[n][0];
        while(st>=1){
            int next=li2[st][now];
            int ff=now-next;
            if(ff>0)V.push_back(1);
            else V.push_back(2);
            st--;
            now=next;
        }
        bool first=1;
        for(int i=V.size()-1;i>=0;i--){
            if(V[i]==1)printf("U");
            else printf("D");
        }
        printf("\n");
    }
    else
    {
        printf("IMPOSSIBLE\n");
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

ZOJ Problem Set - 2158 Truck History

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

题意:就是给你n个字母,每个字母由7个字符组成,且都是小写字母,而且不相等,每个字母有一个父亲,且到父亲的距离是跟父亲位置相同字母不同的位置数量,且根节点没有父亲,求距离和最小。

分析:一看,每个节点有个父亲,那么就是一棵树,且距离可以直接定义为父节点到自己点的边长距离,那么要求n-1条边的距离和最小,直接用最小生成树算法即可,我们只要预处理出每对的距离,然后用prim算法即可,因为是稠密图,prim跑得比较优秀,如果是稀疏图,那么直接就kruskal。总体复杂就是,距离n*n*7,prim算法为n*n,所以复杂的为O(n*)n,最后啪啪啪就可以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=2*1234;
char ch[maxn][10];
int n;
bool vis[maxn];
void init()
{
    for(int i=1; i<=n; i++)scanf("%s",ch[i]+1);
}
short dist[maxn][maxn];
short low[maxn];
void play()
{
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        dist[i][i]=0;
        for(int j=i+1; j<=n; j++)
        {
            int sum=0;
            for(int k=1; k<=7; k++)
            {
                if(ch[i][k]!=ch[j][k])sum++;
            }
            dist[i][j]=dist[j][i]=sum;
        }

    }
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    int pos=1;
    for(int i=2; i<=n; i++)
    {
        low[i]=dist[1][i];
    }

    for(int i=1; i<n; i++)
    {
        int MIN=INF;
        int idx=-1;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j]&&MIN>low[j])
            {
                MIN=low[j];
                idx=j;
            }
        }
        ans+=MIN;
        vis[idx]=1;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j]&&low[j]>dist[idx][j])
            {

                low[j]=dist[idx][j];
            }
        }
    }
    printf("The highest possible quality is 1/%d.\n",ans);
}
int main()
{
    while(scanf("%d",&n)&&n)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}

ZOJ Problem Set - 3777 Problem Arrangement

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

题意:给你n个题目,每个题目放在第i个位置有个值,有个程序可以随机生成1~n的排列,求生成的排列值大于m的期望次数

分析:这里的话需要推一下公式,需要用到极限的定理,因为假设n!种方案里,可行的方案概率为p,不可行为q(即1-p),则期望次数为

limn->无穷p*q^0*1+p*q^1*2+p*q^2*3....+p*q^(n-1)*n这个极限怎么求是关键,这里可以用错位相减法,即将式子乘以q,则为

qlimn->无穷                p*q^1*1+p*q^2*2....+p*q^(n-1)*(n-1)+p*q^(n)*n,然后两式一减,为(1-q)limn->无穷p+p*q^1+p*q^2...p*q^(n-1)-p*q^n*n,等比求和,即limn->无穷p*(1-q^n)/(1-q)-p*q^(n)*n,求极限后为可知这个极限为1/(1-q)即1/p,所以期望的次数是1/p,现在要求的是满足大于等于m的排列有多少个,因为n最大只有12,所以可以用状态压缩,最大也就只有4095,具体怎么搞?假设当前要确定的是第i个位置的数字,然后假设第j个题目放在第i个位置,那么我们可以去找i-1个位置,因为i-1个位置可以用二进制表示,所以可以很快找到然后把i-1个位置里面的值加上j在第i个的值,最后的话,大于等于m的方案数就是我们要求的复杂度O(n*n*2^n),最后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=13;
int C[maxn];
int ai[maxn][maxn];
int bi[5000][567];
int n,m,T;
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)scanf("%d",&ai[i][j]);
}
int gcd(int a,int b)
{
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(b,a%b);
}
void play()
{
    memset(bi,0,sizeof(bi));
    bi[0][0]=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            for(int k=1; k<C[n]; k++)
            {
                int t=k;
                bool flag=1;
                int q=0;
                for(int l=n-1; l>=0; l--)
                {
                    if(l+1==j&&t-C[l]<0)
                    {
                        flag=0;
                        break;
                    }
                    if(t-C[l]>=0)
                    {
                        t-=C[l];
                        q++;
                    }
                }
                if(q!=i)flag=0;
                if(flag)
                {
                    for(int l=0; l<=500; l++)
                    {
                        int now=l+ai[j][i];
                        if(now>500)now=500;
                        bi[k][now]+=bi[k-C[j-1]][l];
                    }
                }
            }.
        }
    }
    int fz=0;
    int fm=1;
    for(int i=m; i<=500; i++)fz+=bi[C[n]-1][i];
    for(int i=1; i<=n; i++)fm*=i;
    if(fz==0)printf("No solution\n");
    else
    {
        int p=gcd(fz,fm);
        printf("%d/%d\n",fm/p,fz/p);
    }
}
int main()
{
    C[0]=1;
    for(int i=1; i<=12; i++)C[i]=C[i-1]*2;
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }

    return 0;
}

 

ZOJ Problem Set - 3768 Continuous Login

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

题意:给你个数n,求最少的数,假设为a1...ak, 1+2+3...+a1+1+2+3+..a2.....+ak=n

分析:这题乍一看没有任何想法,但是我们可以暴力搜下,发现前100000最多只有3个,那么我们可以直接猜测最多只有三个,那么就可以开始搞了,先求出从1+2+。。。k>=123456789最大的n是多少,加入只有一个,直接二分查找,如果找不到,那么就尝试2个的,两个的话可以用夹逼定理,假设左边为1,右边为k,如果a1+ak>n那么就是太大了,r--,如果是<n,那么就是太小了l++,等于的话就说明2个可以,如果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;
int ai[16000];
int T,n;
int st;
void init()
{
    scanf("%d",&n);
}
int l,r;
bool Brsearch(int p)
{
     l=1;
     r=st-1;
    while(l<=r)
    {
        int ok=ai[l]+ai[r];
        if(ok==p)return 1;
        if(ok<p)l++;
        else r--;
    }
    return 0;

}
void play()
{
    int pos=lower_bound(ai+1,ai+st,n)-ai;
    if(ai[pos]==n)
    {
        printf("%d\n",pos);
        return;
    }
    if(Brsearch(n)){
        printf("%d %d\n",l,r);
        return;
    }
    for(int i=1;i<=n;i++){
        if(n>=ai[i]&&Brsearch(n-ai[i])){
            printf("%d %d %d\n",i,l,r);
            return;
        }
    }
}
int main()
{
    st=1;
    LL now=0;
    while(now<=123456789)
    {
        now+=st;
        ai[st]=now;
        st++;

    }

    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    return 0;
}

ZOJ Problem Set - 3791 An Easy Game

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

题意:给你n,k,m和两个长度为n的只包含'0'和'1'的字符串,给你k步,每步要正好改变s1字符串m个位置,使得k步后s1和s2相等,问总共有多少中方法,取模输出。

分析:这种题一看,以为是按字符串DP,其实发现如果按字符串DP 那复杂度就太大了我们发现字符串就只有0,1,所以可以按状态来DP,具体DP 的话,假设当前为第i步,我们需要去m个位置,具体m个位置我们可以,不一样的位置取j个,那么一样的位置就是m-j个,然后从i-1进行迭代。如果i-1存在不同位置有x个,相同位置 为n-x个,如果x>=j&&n-x>=m-j,且这个方法是可以行的通的,i-1时的方法数为ans,那么我们就可以从x里面取j个,n-x取m-j个,这里的话是组合所以我们可以预处理出C[100][100],最后答案怎么算呢?仔细想想就会有思路,因为x里去了j个,所以剩下不一样的位置为x-j个,但是一样的位置里面取了,m-j个,最后剩下的不一样的位置 有x-j+m-j个同理,一样的位置有n-x-(m-j)+j个,假设为j为js,m-j为os,x为js1,n-x为os1,且更新后的为x-j+m-j为njs,n-x-(m-j)+j为nos,则状态方程为 ai[i][njs][nos]+=ai[i-1][js1][os1]*C[js1][js]*C[os1][os];记得取模,复杂度为n^3,最后啪啪啪就可以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 MOD=1000000009;
const int maxn=123;
LL ai[maxn][maxn][maxn];
LL C[maxn][maxn];
char ch1[maxn],ch2[maxn];
int n,k,m;
void init()
{
    int diff=0;
    scanf("%s%s",ch1+1,ch2+1);
    int len=strlen(ch1+1);
    for(int i=1; i<=len; i++)
    {
        if(ch1[i]!=ch2[i])diff++;
    }
    memset(ai,0,sizeof(ai));
    ai[0][diff][len-diff]=1;
}
void play()
{

    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<=m; j++)
        {
            int js=j;
            int os=m-j;
            for(int l=js; l<=100; l++)
            {
                int js1=l;
                int os1=n-l;
                if(os1<0)break;
                if(js1>=js&&os1>=os&&ai[i-1][js1][os1]>0)
                {
                    int njs=js1-js;
                    njs+=os;
                    int nos=os1-os;
                    nos+=js;
                    ai[i][njs][nos]+=((ai[i-1][js1][os1]*C[js1][js]%MOD)*C[os1][os]%MOD);
                    ai[i][njs][nos]%=MOD;
                }

            }
        }
    }
    printf("%lld\n",ai[k][0][n]);
}
int main()
{
    C[0][0]=1;
    for(int i=0; i<=100; i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1; j<i; j++)
        {
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
    }

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

ZOJ Problem Set - 3172 Extend 7-day Vacation

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

题意:就是找两个点,使得路径上的点最多。

分析:刚看不知道从何下手,再仔细看看note就好了,note前半部分就是说图是连通的,因为说点是直接或则间接相连的,后半部分说明图没有环,因为说如果出去之后要回原来的点,必须经过一条至少两次。有这个的话就可以知道给的图是颗树,然后求树上两点之间的点数最多,即距离最大。那么可以用树形DP,假设当前的点为k,它的子树最大的深度为i和j,那么就可以知道当前的路径为i和j之间的和再加1(k这个点),然后更新MAX,然后把k和最大的子树路径递归上去,用来更新k的父节点就可以了,然后最后要判断MAX是否大于7,最后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
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<n; i++)
    {
        scanf("%d%d",&u,&v);
        u++;
        v++;
        V[u].push_back(v);
        V[v].push_back(u);
    }
}
bool cmp(int a,int b)
{
    return a>b;
}
int MAX;
int DFS(int now,int fa)
{
    vector<int> need;
    need.push_back(0);
    need.push_back(0);
    for(int i=0; i<V[now].size(); i++)
    {
        int u=V[now][i];
        if(u==fa)continue;
        int p=DFS(u,now);
        need.push_back(p);
    }
    sort(need.begin(),need.end(),cmp);
    MAX=max(MAX,need[0]+need[1]+1);
    return need[0]+1;
}
void play()
{
    MAX=0;
    DFS(1,-1);
    if(MAX<7)printf("Impossible\n");
    else printf("%d\n",MAX);
}

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

ZOJ Problem Set - 3156 Taxi

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

题意:给你n个人n<=100,m辆车,n<=m<=100,然后给你n+m个坐标代表人和车的位置,最后再给你个速度v,求出最少的时间,使得每个人都有一辆车。(其中每个人都是同步进行的)

分析:这种题的话,就是相当于把n个人匹配到m辆车的n辆中,可以用二分图匹配算法,匈牙利的话是O(VE)那怎么求这个最少时间呢,其实可以二分求,然后每次二分的时间t,我们可以用O(nm)的时间,求的用t的时间,n个人可以和m辆车的哪几辆匹配,然后建图,跑一边匈牙利,如果可以最大匹配的话,那么这个时间是ok的,那么我们把上限变为t-0.001,因为要保留两位小数,反之把下限变为t+0.001,继续二分,最后输出答案即可。复杂的为logT*(n*m+VE),还是ok的,因为n和m比较小,最后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=123;
struct he
{
    double x,y;
} Sky[2][maxn];
int n,m;
double ai[maxn][maxn];
double l,r;
double calT(int i,int j,double v)
{
    double dis=sqrt((Sky[0][i].x-Sky[1][j].x)*(Sky[0][i].x-Sky[1][j].x)+(Sky[0][i].y-Sky[1][j].y)*(Sky[0][i].y-Sky[1][j].y));
    return dis/v;
}
void init()
{
    for(int i=1; i<=n; i++)scanf("%lf%lf",&Sky[0][i].x,&Sky[0][i].y);
    for(int i=1; i<=m; i++)scanf("%lf%lf",&Sky[1][i].x,&Sky[1][i].y);
    double v;
    scanf("%lf",&v);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            ai[i][j]=calT(i,j,v);
        }
    }
    r=2000000.0/v;

}
bool bi[maxn][maxn];
int Link[maxn];
bool vis[maxn];
bool DFS(int now)
{
    for(int i=1; i<=m; i++)
    {
        if(bi[now][i]&&!vis[i])
        {
            vis[i]=1;
            if(Link[i]==0||DFS(Link[i]))
            {
                Link[i]=now;
                return true;
            }
        }
    }
    return false;
}
void play()
{
    double MIN=r;
    l=0;
    while(l<=r)
    {
        double mid=(l+r)/2;
        memset(bi,0,sizeof(bi));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(ai[i][j]<=mid)bi[i][j]=1;
            }
        }
        memset(Link,0,sizeof(Link));
        bool flag=1;
        for(int i=1; i<=n; i++)
        {
            memset(vis,0,sizeof(vis));
            if(DFS(i))continue;
            flag=0;
            break;
        }
        if(flag)
        {
            MIN=min(MIN,mid);
            r=mid-0.001;
        }
        else
        {
            l=mid+0.001;
        }

    }
    printf("%.2f\n",MIN);

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

ZOJ Problem Set - 3180 Number Game

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

题意:就是给你6个正整数,前面三个是结果的数字,后面三个是起始的数字,我们可以从起始的数据选择一个数,然后删除它,用另外两个的和减去以代替,然后一直反复,看能否到达结果的三个数字。

分析:这种题一看,如果从初始状态推结果状态是很复杂的,因为每一次都有3个数字可以选择,所以复杂度肯定太高了,所以考虑用结果的三个数字推初始数据,因为假设结果数字为a1 a2 a2且a1<a2<a3,如果a1+a2-1=a3,说明a3是推过来的,所以可以把a3改回原来的数字,假设为a'3,那么a'3怎么算呢,因为我们知道现在a2最大,那么可以以为a1+a'3-1=a2,所以a'3=a2-a1+1,所以把a3换了,然后一直重复看看,能不能推到起始的三个数字。这里如果我们有a1+a2-1=a3的话,那么我们只要a1和a2能找到2个数字一样就可以了。因为a3可以变为任意数,然后的话如果a1+a2-1!=a3,那么特殊处理一下就行了,记得循环终止,如果a1+a2-1恒等于a3的时候,那么就可以终止了,因为死循环了,最后啪啪啪就可以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 ai[4],bi[4],T;
void init()
{
    for(int i=1; i<=3; i++)scanf("%d",&ai[i]);
    for(int i=1; i<=3; i++)scanf("%d",&bi[i]);

}
bool vis[4];
void play()
{
    while(1)
    {
        sort(ai+1,ai+4);
        sort(bi+1,bi+4);
        if(ai[1]+ai[2]-1!=ai[3])
        {
            if(ai[1]==bi[1]&&ai[2]==bi[2]&&ai[3]==bi[3])
            {
                printf("Yes\n");
                return;
            }
            else
            {
                printf("No\n");
                return;
            }
        }
        int sum=0;
        vis[1]=vis[2]=vis[3]=0;
        for(int i=1; i<=2; i++)
        {
            for(int j=1; j<=3; j++)
            {
                if(ai[i]==bi[j]&&!vis[j])
                {
                    vis[j]=1;
                    sum++;
                }
            }
        }
        if(sum>=2)
        {
            printf("Yes\n");
            return;
        }
        ai[3]=ai[2]+1-ai[1];
        if(ai[1]==1&&ai[2]==ai[3])break;

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

HDU 5277 YJC counts stars

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

题意:就是给你n个点n个坐标xi,yi(1<=i<=n),然后给你m条边,表示u和v相连,保证没重边,也保证没有边相交。然后 让你求最大的点子集,使里面的点可以两两相连(不是图相连,线段相连),且求处个数。

分析:其实分析分析,就发现最大就只有4个点的点急,因为5个点就会有边相交,与题目不符,所以只要枚举到4个点就行了,具体怎么枚举才比较好?可以先枚举两两的,就是加入i和j有边相连,就把i和j算一对保存起来,这样我们就知道两两相连的子集个数有多少个了,怎么枚举三个的,很简单,只要把两个相连的与一个个点比较,只要这两个点能同事与第三个点连接,那么就是ok的,这里注意:假设i和j和k是属于三个相连的,我们求出来两两的就是(i,j)(i,k)(j,k)然后枚举三个点的时候会有三种方法,但是实际上就只有1种,所以答案要/3,这样我们就知道三个点的自己个数了,现在是四个点了,四个点也很方便,只要把两个点的两两进行判断就行了,只要互不相同然后互相连接就可以了,但是要注意:假设我们i,j,p,q,是四个相连的点集,那么我们两两求出来的就是(i,j)(i,p)(i,q)(j,p)(j,q)(p,q),这样的话,他们两两按数序的话会求出来三组,因为我们重复计算了,所以答案要/3到此为止,所有的都已经判断了, 按照4,3,2,1只要有一个是满足的,直接ok,结束。然后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
int x[maxn],y[maxn];
int ai[maxn][maxn];
int n,m;
void init()
{
    for(int i=1; i<=n; i++)scanf("%d%d",&x[i],&y[i]);
    int u,v;
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        ai[u][v]=ai[v][u]=1;
    }
}
int bi[maxn*maxn][2];
void play()
{
    if(m==0)
    {
        printf("1 %d\n",n);
        return;
    }
    if(m==1)
    {
        printf("2 1\n");
        return ;
    }
    int st=1;
    int sum2=0;
    //判断连通性
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            if(ai[i][j])
            {
                bi[st][0]=i;
                bi[st][1]=j;
                st++;
                sum2++;
            }
        }
    }
    int sum3=0;
    //判断三个点的
    for(int i=1; i<st; i++)
    {
        for(int j=1; j<=n; j++)
        {
            int u=bi[i][0];
            int v=bi[i][1];
            if(ai[u][j]&&ai[v][j])
            {
                sum3++;
            }
        }
    }
    int sum4=0;
    //判断四个点的
    for(int i=1; i<st; i++)
    {
        for(int j=i+1; j<st; j++)
        {
            int u1=bi[i][0];
            int u2=bi[i][1];
            int v1=bi[j][0];
            int v2=bi[j][1];
            if(u1!=v1&&u1!=v2&&u2!=v1&&u2!=v2&&ai[u1][v1]&&ai[u1][v2]&&ai[u2][v1]&&ai[u2][v2])sum4++;
        }
    }
    if(sum4!=0)
    {
        printf("4 %d\n",sum4/3);

    }
    else if(sum3!=0)
    {
        printf("3 %d\n",sum3/3);
    }
    else if(sum2!=0)
    {
        printf("2 %d\n",sum2);
    }


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