Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

给大家提供一个简单的思路,轻拍

Posted by potato_lxd at 2012-06-14 17:41:02 on Problem 1029
用三个数组
bool normal[1024];
bool light[1024];
bool heavy[1204];
来保存每一个硬币是 1 肯定没问题, 2 可能是轻的 3 可能是重的
初始化都是false,代表我们什么都不知道

对于每一次测验结果
如果是平局,那么所有参与测验的硬币都肯定没问题
如果是一边轻
那么所有没参与测验的硬币都肯定没问题
而轻的一边则可能是轻的,重的一边可能是重的
这样从信息上没有漏掉任何信息

最后遍历所有硬币
if 他的normal[i]是true,他肯定没问题
else if 他的light[i]和heavy[i]同时是true,他也肯定没问题,因为如果他是轻的或者重的,那么测验结果不可能暗示他既可能轻也可能重
所以这样遍历之后,我们知道每个硬币是安全/不安全的
如果不安全的硬币只有一个,输出之
如果不安全的硬币大于1,输出0

下面贴16MS代码,其实为了可读性麻烦了很多,完全应该0MS

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <math.h>
#include <string>

using namespace std;

#define FOR(x,y) for(int x = 0;x < y;x++)
#define MSET(x) memset(x,0,sizeof(x))

class w// w类保存一次测验结果,提供两个接口验证一个硬币在不在这次测试的左边或者右边
{
public:
	w()
	{
		MSET(l);
		MSET(r);
		n = 0;
	}
	int l[512];
	int r[512];
	bool InLeft(int i)
	{
		bool ret = false;
		FOR(j,n)
		{
			if (l[j] == i)
			{
				return true;
			}
		}
		return ret;
	}
	bool InRight(int i)
	{
		bool ret = false;
		FOR(j,n)
		{
			if (r[j] == i)
			{
				return true;
			}
		}
		return ret;
	}
	int n;
	string res;
};
bool normal[1024];
bool light[1024];
bool heavy[1204];
int main()
{
	int n,k;
	MSET(normal);
	MSET(light);
	MSET(heavy);
	cin>>n>>k;
	w * tests = new w[k];
	FOR(i,k)
	{
		cin>>tests[i].n;
		FOR(j,tests[i].n)
		{
			cin>>tests[i].l[j];
		}
		FOR(j,tests[i].n)
		{
			cin>>tests[i].r[j];
		}
		cin>>tests[i].res;
	}
	FOR(i,k)
	{
		if (tests[i].res == "=")
		{
			for(int j = 1; j <= n; j++)
			{
				if (tests[i].InLeft(j)||tests[i].InRight(j))
				{
					normal[j] = true;
				}
			}
		}
		else if (tests[i].res == "<" || tests[i].res == ">")
		{
			for (int j = 1; j <= n; j++)
			{
				if (tests[i].InLeft(j) == false && tests[i].InRight(j) == false)
				{
					normal[j] = true;
				}
				else if (tests[i].InLeft(j) && tests[i].res == "<")
				{
					light[j] = true;
				}
				else if (tests[i].InLeft(j) && tests[i].res == ">")
				{
					heavy[j] = true;
				}
				else if (tests[i].InRight(j) && tests[i].res == "<")
				{
					heavy[j] = true;
				}
				else if (tests[i].InRight(j) && tests[i].res == ">")
				{
					light[j] = true;
				}
			}
		}
	}
	int ret = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!(normal[i] || (light[i] && heavy[i])))
		{
			if (ret == 0)
			{
				ret = i;
			}
			else 
			{
				ret = 0;
				break;
			}
		}
	}
	printf("%d\n",ret);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator