首页 > 代码库 > usaco-3.2-spin-pass
usaco-3.2-spin-pass
模拟题，量不大。
转动360秒以后，所有轮子回到起始角度。因此如果360秒以后还没有出现重合情况的话，就可以退出循环了。
如何判断五个轮子重合呢？起初我也没有很好的方法，一个个去判断重合区域实在是太麻烦了。后来想到一个好方法。把 360度的轮子分成360个区域，用整形数组表示，如果一个轮子的缺口在这个区域内，则这个小区域加1，计算5个轮子的所有缺口。然后遍历这个数组，如果 有个区域的值>=5，表明这个区域上面至少有5个缺口，则5个缺口重合，退出循环。
/*ID: qq104801LANG: C++TASK: spin*/#include <iostream>#include <fstream>#include <bitset>#include <cstdio>#include <algorithm>using namespace std;#define PI 360int speed[6];bitset<PI> curr[6],next[6];void test(){ freopen("spin.in","r",stdin); freopen("spin.out","w",stdout); int num,start,end; for(int i=1;i<=5;i++) { cin>>speed[i]>>num; for(int j=1;j<=num;j++) { cin>>start>>end; end+=start; for(int k=start;k<=end;k++) curr[i].set(k%PI); } } int angle=0; bool flag; while(angle<PI) { for(int i=0;i<PI;++i) { flag=false; for(int j=1;j<=5;j++) if(!curr[j].test(i)) { flag=true; break; } if(!flag) { cout<<angle<<endl; return; } } for(int i=1;i<=5;i++) { for(int j=0;j<PI;j++) next[i][j]=curr[i][(j+PI-speed[i])%PI]; curr[i]=next[i]; } ++angle; } cout<<"none"<<endl; }int main () { test(); return 0;}
test data:
USACO TrainingGrader Results 9 users onlineCHN/3 IND/1 IRN/1 KGZ/1 ROM/1 USA/1 VNM/1USER: cn tom [qq104801]TASK: spinLANG: C++Compiling...Compile: OKExecuting... Test 1: TEST OK [0.005 secs, 3376 KB] Test 2: TEST OK [0.019 secs, 3376 KB] Test 3: TEST OK [0.032 secs, 3376 KB] Test 4: TEST OK [0.019 secs, 3376 KB] Test 5: TEST OK [0.003 secs, 3376 KB] Test 6: TEST OK [0.016 secs, 3376 KB] Test 7: TEST OK [0.008 secs, 3376 KB] Test 8: TEST OK [0.030 secs, 3376 KB]All tests OK.YOUR PROGRAM (‘spin‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated congratulations.Here are the test data inputs:------- test 1 ----30 1 0 120180 1 10 10035 1 20 9031 1 30 8032 1 50 60------- test 2 ----30 1 350 350180 1 10 10035 1 67 2331 1 30 432 1 50 7------- test 3 ----180 1 0 120180 1 120 120180 1 240 12031 1 30 432 1 50 7------- test 4 ----1 1 140 3591 1 200 3591 1 4 12 1 6 11 1 300 300------- test 5 ----45 5 140 13 300 17 0 15 20 3 40 173 1 200 359105 2 4 1 50 50179 3 6 1 8 1 359 33 1 300 300------- test 6 ----45 5 120 13 200 17 0 15 20 3 32 173 5 200 100 1 30 50 10 70 2 75 1105 2 100 1 50 20179 3 6 1 8 1 359 33 1 300 359------- test 7 ----73 5 207 101 1 35 57 11 71 2 75 145 5 125 13 200 17 0 15 20 3 32 196 5 100 12 50 13 0 2 300 39 250 1119 5 6 1 8 1 359 1 245 1 123 115 5 300 1 231 1 185 1 179 2 0 18------- test 8 ----73 5 207 11 1 35 57 11 71 2 75 145 5 125 3 200 17 0 15 20 3 32 196 5 100 1 50 1 0 2 300 39 250 1119 5 6 1 8 1 359 1 245 1 123 115 5 300 1 231 1 185 1 179 2 0 1Keep up the good work!Thanks for your submission!
usaco-3.2-spin-pass
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。