POj 1879 Tempus et mobilius Time and motion (模拟+群)

题目特别长,大意为球的传递。

三个轨道,一个库。各自是分钟单位的轨道。5min单位的轨道。一小时单位的轨道。还有就是n容量的库。

每过一分钟,一个小球从库里面出来,库符合先进先出,进入分钟轨道。假设分钟轨道里面已经有了4个,那么这四个就滑入库,而这个球则进入5min轨道,假设5min轨道已经有了11个。这11个就滑入库。而这个球则滑入小时轨道。假设小时轨道已经有了11个,则这11个滑入库。这个球最后滑入库。在轨道中的球滑入库中,轨道里的球满足先进后出。

如此,轨道是栈。库是队列。并且模拟过程也出来了。

暴力会爆


这个题目

提升了我的调试能力。

1. 大规模数据用freopen输入输出,再用UE等软件对照diff,找到问题后再调试

2.中途设置条件输出。


#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#define maxn 1005
using namespace std;
int N,M;
int a[200];
int q[60*24*10];
int Mstack[3][20];//sec min hou
int top[3];
int vis[200];
int head,tail;
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}
int solve()
{
	int i,j,k,flag;
	int cnt,ans;
	for(i=1;i<=N;i++)
		q[i]=a[i]=i;
	head=1;tail=N+1;
	memset(top,0,sizeof(top));
	memset(vis,0,sizeof(vis));
	for(j=tail,i=1;i<=60*24;i++)
	{
		if(top[0]==4){
			for(k=0;k<4;k++) q[j++]=Mstack[0][--top[0]];
			if(top[1]==11){
				for(k=0;k<11;k++) q[j++]=Mstack[1][--top[1]];
				if(top[2]==11){
					for(k=0;k<11;k++) q[j++]=Mstack[2][--top[2]];
					q[j++]=q[i];
				}else	Mstack[2][top[2]++]=q[i];
			}else	Mstack[1][top[1]++]=q[i];		
		}else	Mstack[0][top[0]++]=q[i];

		/*if(i>=720)
			printf("%d
",q[i]);

		printf("
");*/
			
	}
	ans=1;
	for(j=i;j<N+i;j++)
	{
		if(vis[j-i+1]==0)
		{
			vis[j-i+1]=1;
			k=q[j];
			cnt=1;
			while(vis[k]==0)
			{
				cnt++;
				vis[k]=1;
				k=q[i+k-1];
			}
			ans=ans/gcd(ans,cnt)*cnt;
		}
	}
	return ans;
}
int main()
{
//freopen("E:\out.txt","w",stdout);
    while(scanf("%d",&N),N)
    {
		printf("%d balls cycle after %d days.
",N,solve());
	}
    return 0;
}


原文地址:https://www.cnblogs.com/mengfanrong/p/5168312.html