K - Let the Flames Begin Gym - 101955K（约瑟夫环/2018icpc沈阳）

VJ地址

思路：因为m和k的最小值一定小于2E6，那么我们可以分情况来求，如果m比较小直接o（m） 递推求出第m个死的人，如果k比较小，我们在每一轮+k的时候取模的操作都是无效的，我们可以用乘法累积起来再求。
先给出约瑟夫环的模板

//从第一个开始报数，数到k的将被杀掉 int josepus(int n,int k) {int r=0;for(int i=2;i<=n;i++) r=(r+k)%i;return r+1; //0~n-1 所以最后结果+1 } //第m个被杀掉的人 int josepus(int n,int m,int k) {r=(k-1)%(n-m+1);for(int i=2;i<=m;i++){r=(r+k)%(n-m+i);}return r+1; }

该题代码

#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se secondusing namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int > pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=2520; const ll N=2e5+10;int main(){iosint t;cin>>t;int cc=0;while(t--){ll n,m,k;cin>>n>>m>>k;ll ans=0;if(k==1) ans=m;else{if(m<k){ans=(k-1)%(n-m+1);for(int i=2;i<=m;i++){ans=(ans+k)%(n-m+i);}ans++;}else{ans=(k-1)%(n-m+1);ll now=1;ll t;while(now<m){t=(n-m+now-ans+k-2)/(k-1);//向上取整if(now+t>m){ans=(ans+(m-now)*k)%n;}else ans=(ans+t*k)%(n-m+now+t);now+=t;}ans++;}}cout<<"Case #"<<++cc<<": "<<ans<<endl;}return 0; }

参考博客https://blog.csdn.net/weixin_42373330/article/details/102492424

总结

以上是生活随笔为你收集整理的K - Let the Flames Begin Gym - 101955K（约瑟夫环/2018icpc沈阳）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。