Problem Description In order to remember history, King plans to play losephus problem in the parade gap.He calls?n(1≤n≤5000)?soldiers, counterclockwise in a circle, in label?1,2,3...n.

The first round, the first person with label?1?counts off, and the man who report number?1?is out.

The second round, the next person of the person who is out in the last round counts off, and the man who report number?2?is out.

The third round, the next person of the person who is out in the last round counts off, and the person who report number?3?is out.



The N - 1 round, the next person of the person who is out in the last round counts off, and the person who report number?n?1?is out.

And the last man is survivor. Do you know the label of the survivor?
Input The first line contains a number?T(0<T≤5000), the number of the testcases.

For each test case, there are only one line, containing one integer?n, representing the number of players.
Output Output exactly?T?lines. For each test case, print the label of the survivor.
Sample Input 2 2 3
Sample Output 2 2 Hint: For test case #1：the man who report number $1$ is the man with label $1$, so the man with label $2$ is survivor. For test case #1：the man who report number $1$ is the man with label $1$, so the man with label 1 is out. Again the the man with label 2 counts $1$, the man with label $3$ counts $2$, so the man who report number $2$ is the man with label $3$. At last the man with label $2$ is survivor. 題意：n個(gè)人排成一圈，每回合殺死一個(gè)人，殺死后從那個(gè)人的下一個(gè)人開(kāi)始數(shù)數(shù)，第i個(gè)回合數(shù)到i的那個(gè)人被殺死，問(wèn)最后剩下的人的編號(hào)是多少。 思路：這題和約瑟夫環(huán)有點(diǎn)像，我們?cè)O(shè)f[n]為總?cè)藬?shù)為n時(shí)，按照題目中的規(guī)則殺，最后剩下來(lái)的人的編號(hào)是多少。我們每次殺死一個(gè)人后就重新編號(hào)，那么f[1]=0,即當(dāng)最后只剩下一個(gè)人時(shí)，他經(jīng)過(guò)重新編號(hào)后新的編號(hào)為0，那么在上一輪，他的編號(hào)為t=(0+n-1)%2,倒數(shù)第二輪他的編號(hào)為(t+n-2)%3,這樣可以依次類推到f[n]，就是答案了，所以這題只要用O(n^2)的復(fù)雜度初始化一下就行了。 這種方法有個(gè)缺陷，就是不能知道每一次殺死的人的編號(hào)是什么，如果要知道每一次殺死的人的編號(hào)，我們可以用線段樹(shù)做。我們?cè)诰€段樹(shù)上對(duì)于每一段維護(hù)其剩余的空位數(shù)，那么我們每次計(jì)算這一次殺死的人是線段樹(shù)總區(qū)間的第幾個(gè)人，這樣就可以知道每次的編號(hào)是多少了，如果這題用線段樹(shù)，為了防超時(shí)，可以打個(gè)表。

#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<string> #include<bitset> #include<algorithm> using namespace std; typedef long long ll; typedef long double ldb; #define inf 99999999 #define pi acos(-1.0) #define maxn 6006 int a[maxn]; void init() {int i,j;a[1]=1;for(i=2;i<=5000;i++){int num=0;//for(j=i-1;j>=1;j--){for(j=1;j<=i;j++){num=(num+i-j+1)%j;}a[i]=num+1;} }int main() {int n,m,i,j,T;init();scanf("%d",&T);while(T--){scanf("%d",&n);printf("%d\n",a[n] );}return 0; }
下面的程序還要打個(gè)表再提交。 #include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<string> #include<bitset> #include<algorithm> using namespace std; typedef long long ll; typedef long double ldb; #define inf 99999999 #define pi acos(-1.0) #define maxn 5006 struct node{int l,r,num; }b[4*maxn];int n; void build(int l,int r,int th) {int mid;b[th].l=l;b[th].r=r;b[th].num=r-l+1;if(l==r)return;mid=(l+r)/2;build(l,mid,th*2);build(mid+1,r,th*2+1); }void update(int num,int cishu,int th) {int mid;if(b[th].l==b[th].r){b[th].num=0;if(cishu==n)printf("%d,",b[th].l);return;}if(b[th*2].num>=num){update(num,cishu,th*2);}else{update(num-b[th*2].num,cishu,th*2+1 );}b[th].num=b[th*2].num+b[th*2+1].num; }int main() {int t,m,i,j,T,k;freopen("o.txt","w",stdout);for(n=1;n<=5000;n++){build(1,n,1);int p=1;int tot=n;for(k=1;k<=n;k++){p=(p+k-1)%tot; //這里算這回合殺死的人的編號(hào)的空格數(shù)if(p==0)p=tot;update(p,k,1);if(p==tot)p=1; //這里算出這回合殺死人后，下一回合第一個(gè)數(shù)數(shù)的編號(hào),也可以看做是下一回合站第幾個(gè)空位tot--; //每次總?cè)藬?shù)減1}} }

轉(zhuǎn)載于:https://www.cnblogs.com/herumw/p/9464516.html

總結(jié)

以上是生活随笔為你收集整理的hdu5643 King's Game(约瑟夫环+线段树)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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