ZOJ Problem Set - 3180 Number Game
Chieh
posted @ 2015年7月21日 14:34
in ZOJ
, 480 阅读
飞机票: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; }