首先我们发现这个出局的情况就是普通约瑟夫问题

那我们就可以用 $O(n)$ 的时间来算出前 $n$ 个人的出局情况

然后我们就可以进行枚举直到满足 $f_i=i$ 停止

最后累加一下答案即可

        f[1]=0;
		for(int i=2;i<=n;i++) f[i]=(f[i-1]+m)%i;
		for(int i=1;i<=n;i++) f[i]++;
		now=n;
		while(now!=f[now]){
			ans+=now-f[now]; 
			now=f[now];
		}
		ans+=2*now;
		printf("%lld\n",ans);

#include<bits/stdc++.h>
using namespace std;
const int N=5e7+5;
int f[N];
int main()
{
	int n,m;
	cin>>n>>m;
	f[1]=0;
	for(int i=2;i<=n;i++)f[i]=(f[i-1]+m)%i;
	for(int i=1;i<=n;i++)f[i]++;
	int k=n;
	while(k!=f[k])k=f[k];
	cout<<n+k<<'\n';
	return 0;
}

题意：

给定一个环，有n个点，每个点的编号依次为1~n，每次游戏从1号开始报数，报到m的暂时出局，直到只剩一个点k，然后将大于k的所有点永久出局并将ans加上n-k的值，直到k=n,将ans加上2*k,问ans的值

做法

1.暴力

首先每轮游戏都是裸的约瑟夫环，我们可以O(n)算每一轮的答案，然后暴力加

code:

#include <bits/stdc++.h>
using namespace std;

long long n, m;

void read(){
	cin >> n >> m;
}

long long dfs(long long n,long long m){
	long long k = 0;
	for(long long i = 1;i <= n; i++){
		k = (k + m) % i;
	}
	k++;
	if(k == n) return 2 * k;
	else return dfs(k, m) + n - k;
}

void compute(){
	cout << dfs(n,m);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}

这个题其实暴力就能过

2.正解

我们发现每一轮求的值可以预处理出来 （空间换时间）

code:

#include <bits/stdc++.h>
using namespace std;

long long n, m;

void read(){
	cin >> n >> m;
}

long long dfs(long long n,long long m){
	long long k = 0;
	for(long long i = 1;i <= n; i++){
		k = (k + m) % i;
	}
	k++;
	if(k == n) return 2 * k;
	else return dfs(k, m) + n - k;
}

void compute(){
	cout << dfs(n,m);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}

警示后人

赛时没算空间导致爆0

这里给出一个防止MLE的方法

(来自wsh大佬的做法)

这个可以输出开的空间大小

#include <bits/stdc++.h>
using namespace std;

bool mlea;

long long a[1000000];

bool mleb;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	printf("%lf MB\n",(&mleb-&mlea-1)/1024.0/1024.0);
	return 0;
}