K - Let the Flames Begin

題意：

n個(gè)人圍成一個(gè)環(huán)，編號(hào)分別是1~n，從第一個(gè)人開(kāi)始報(bào)數(shù)，報(bào)道k的人被移除，然后下一個(gè)人從1重新報(bào)，一直這樣進(jìn)行。問(wèn)第m給被移除的人報(bào)數(shù)是多少？
一共T組數(shù)據(jù)，所有組數(shù)據(jù)的min{m,k}的總和不會(huì)超過(guò)2e6

題解:

經(jīng)典約瑟夫環(huán)，約瑟夫環(huán)的模板：

//從第一個(gè)開(kāi)始報(bào)數(shù)，數(shù)到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 所以最后結(jié)果+1 } //第m個(gè)被殺掉的人 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; }

min{m,k}的總和不會(huì)超過(guò)2e6
當(dāng)m<k時(shí)，m的總和不會(huì)超過(guò)2e6，我們可以直接用約瑟夫環(huán)的模板，復(fù)雜度O(m)
當(dāng)m>k時(shí)，直接用模板會(huì)超時(shí)，我們注意看公式(r+k)%(n-m+i);當(dāng)k小時(shí)，此時(shí)k可能遠(yuǎn)小于n，因?yàn)閚的范圍可以達(dá)到1e18，那么ans可能加上好幾輪k都無(wú)法取模，所有我們用乘法加速，直接求出ans+c*k>(n-m+i),求c的值，這樣可以加速運(yùn)算

代碼：

#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){/*ans+c*k>(n-m+i)c>((n-m+i)-ans)/k*/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; }

總結(jié)

以上是生活随笔為你收集整理的K - Let the Flames Begin的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。