约瑟夫-从模拟到毒瘤

约瑟夫真是个好题。

约瑟夫的题有模拟,递推的标签。于是有两大类算法,三种题目。

入门练习类

复杂度$\Theta(NM)$

一般作者为了显示是个入门题会出$10^3 ~ 3 \times 10^4$的数据范围。(额,出到$10^5$仿佛还没见过)

而且一般会问整个序列。

模拟这个过程。

于是,有例子:

$5$个人报数,每报到$3$这个人就出列,下一个人从1开始报。

使用$LaTeX$。分$4$步

$$
\begin{array}{ccccc}
1&2&3&4&5\\
1&2&\not3&4&5\\
\not1&2&\not3&4&5\\
\not1&2&\not3&4&\not5\\
\not1&\not2&\not3&4&\not5
\end{align}
$$

于是最后只有$4$号留下了。

上个代码(模拟):

#include<cstdio>
int all[10000000];
int main(){
	int m,n;
	int bs=0,out=0,num=0;
//	out计数出去的人数\
	num记录当前的,\
	bs是报数计数器
    scanf("%d%d",&m,&n);
	do{
		++num;
		if(num==m+1) num=1; //循环下标
		if(all[num]==0) ++bs;//如果这个人没有出去,报数
		else continue; //已经出去了,跳过
		if(bs==n){//发现报到了
		    bs=0;
			all[num]=1;//干出去
			++out;//计数
			printf("%d ",num);//输出
		}
	}while(out!=m);//如果全出去了,结束。
	return 0;
}

递推类

时间复杂度$\Theta(N)$

于是$0<n,m<10^8$

并且只问最后一个人的编号。

于是递推。

如果我们要求$1$个人的序列的答案,

然后反向报数加人

可以先求出两个人的序列,在一直推到$N$个人,

每次重新编号,并且为了方便,我们把$[1,N]$平移到$[0,N-1]$。

于是本来有一个人。

后来的一个人排在了正确的位置上,

因为是反向报数,所以其实这个人就是最后出去的人。

而且现在的两个人中的最后出去的人的编号是对的。

于是一直推。

$$f_i=(f_{i-1}+m)\mod{n}$$

为了防止编号越出$n$,还得取个模。

放个代码(好短):

#include <iostream>
#include <cstdio>
#define LL long long

using namespace std;

LL ans=0,n,m;
int main(){
	ans=0;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		ans=(ans+m)%i;
	printf("%lld\n",ans+1);
}

于是还有另类的题(不过也是逆推)

第$i$次报$I$个数

不过也一样,只是把里面的改成

for(int i=n-1;i>=0;i--)
	ans=(ans+i)%(n-i+1);

 一样是逆推。

毒瘤类:

当作者不再冷静,就会把数据出成这个鬼样子:

$N\leq 10^9,M \leq 10^6$

总之$\Theta(N)$过不去了。

那么我们就要想想为啥$M$这么小,

于是可以利用类似分块(?)的思想。

在$\Theta(N)$的基础上,把不需要取模的那部分直接乘法加速。

于是变成$\Theta(M \log N)$

就终于干过毒瘤出题人啦。

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int m,n;
int main(){
	int T;
	for(cin>>T;T;T--){
		scanf("%d%d",&n,&m);
		int id=0;
		if(n>m){
			for(int i=1;i<=m;i++)
				id=(id+m)%i;
			for(int i=m+1;i<=n;i++){
				id=(id+m)%i;
				int jumpl=(i-id)/(m-1);
				if(i+jumpl<=n){
					id=(id+jumpl*m)%(i+jumpl);
					i+=jumpl;
				}
				else{
					id=id+(n-i)*m;
					break;
				}
			}
		}else{
			id=0;
			for(int i=1;i<=n;i++)
				id=(id+m)%i;
		}
		printf("%d\n",id+1);
	}
}

 

上一篇:B/S和C/S的区别?(面试题)


下一篇:第四阶段:Vue框架 day75 Vue--Vue配置bs环境