Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
给大家提供一个简单的思路,轻拍用三个数组 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator