usaco_3_2_3_spin.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROB:spin
LANG: C++
*/
/*
直接模拟可作。
注意到所有齿轮在转过360秒后事实上转过了speed圈，所以又开始在0位置对齐了。所以如果转过360秒后还没有找到的话，那么就是找不到了，输出none。
这道题让我很无奈……
大家一定要注意，那个长度它要从0算起……比如长度为30，那么实际上就是起始位置st+0,st+1…st+30,所以缺口真正上缺了31个……
这个问题让我试了好久，唉！！那么长时间，结果加个等号就OK了。
另外就是那个旋转的方向了……可以看到我源程序中的moveleft和moveright两个函数，方向也是试出来的，汗!!!
另外……生平第一次使用bitset，嘿嘿……
*/
#include <fstream>
#include <iostream>
#include <string>
#include <memory>
#include <algorithm>
#include <bitset>
#define cin fin
using namespace std;
ifstream fin("spin.in");
ofstream fout("spin.out");
void moveleft(bitset<360> &bs,int speed)
{
	int i,j,k;
	bitset<360> a(1);
	bitset<360> b;
	for(i=1;i<speed;i++) {a<<=1;  a|=1;}
	//a<<=(360-speed);
	a=a&bs;
	bs>>=speed;	
	a<<=(360-speed);
	bs|=a;
}
void moveright(bitset<360> &bs,int speed)
{
	int i,j,k;
	bitset<360> a(1);
	bitset<360> b;
	for(i=1;i<speed;i++) {a<<=1;  a|=1;}
	a<<=(360-speed);
	a=a&bs;
	bs<<=speed;	
	a>>=(360-speed);
	bs|=a;
}

int main()
{
   bitset<360> bs[5];
   bitset<360> bst(131);
   int w[5][5][2];
   int wn[5],speed[5];
   int i,j,k;
 /*  for(i=359;i>340;i--) bst[i]=1;
   for(i=0;i<360;i++) cout<<bst[i];
   cout<<endl;
   move(bst,10);
for(i=0;i<360;i++) cout<<bst[i];*/
   
   
   for(i=0;i<5;i++)
   {
	   cin>>speed[i];
	   cin>>wn[i];
	   for(j=0;j<wn[i];j++)  {
			cin>>w[i][j][0]>>w[i][j][1];
			for(k=w[i][j][0];k<=w[i][j][1]+w[i][j][0];k++) bs[i][k%360]=1;
	   }	
//	   for(j=0;j<bs[i].size();j++) cout<<bs[i][j];	
   }
   for(i=0;i<360;i++)
   {
	   bst.reset();
	   bst.flip();
	   for(j=0;j<5;j++) bst&=bs[j];
	   if(bst.count()) break;
	   for(j=0;j<5;j++) moveright(bs[j],speed[j]);	  
   }
 //  for(i=0;i<5;i++) {for(j=0;j<bs[i].size();j++) fout<<bs[i][j];	fout<<endl;}
   if(i<360) fout<<i<<endl;
   else fout<<"none"<<endl;
   return 0;
}