d192 - 11351 - Last Man Standing
題目描述
題目描述了約瑟夫斯問題的一個變體。給定 n 個人圍成一個圈，每次淘汰第 k 個人，直到只剩下一個人。要求輸出最後倖存者的編號。
解題思路
這題可以使用模擬的方式來解決。我們從 1 到 n 建立一個圓圈，然後按照題目描述的規則進行淘汰，直到只剩下一個人。由於 n 的範圍較大，直接模擬可能會比較慢。但題目中 k 的值是固定的，且每次淘汰後圓圈的大小會減小，因此可以通過模擬來解決。程式碼中，ans 變數記錄了最後倖存者的索引（從 0 開始），每次淘汰一個人後，ans 的值會更新。由於題目要求輸出倖存者的編號，因此最後需要將 ans 加 1。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
int t=read(),n,q;
for(int ca=1;ca<=t;++ca){
int ans=0;
n=read();
q=read();
for(int i=1;i<=n;++i)
ans=(ans+q)%i;
putchar_unlocked('C');
putchar_unlocked('a');
putchar_unlocked('s');
putchar_unlocked('e');
putchar_unlocked(' ');
write(ca);
putchar_unlocked(':');
putchar_unlocked(' ');
write(ans+1);
putchar_unlocked('\n');
}
}