Chieh's Blog

Because Of Coding

ZOJ Problem Set - 3180 Number Game

Chieh posted @ 2015年7月21日 14:34 in ZOJ , 467 阅读

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

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter