[Codevs] 1282 约瑟夫问题

1282 约瑟夫问题

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

有编号从1到N的N个小朋友在玩一种出圈的游戏。开始时N个小朋友围成一圈,编号为I+1的小朋友站在编号为I小朋友左边。编号为1的小朋友站在编号为N的小朋友左边。首先编号为1的小朋友开始报数,接着站在左边的小朋友顺序报数,直到数到某个数字M时就出圈。直到只剩下1个小朋友,则游戏完毕。

现在给定N,M,求N个小朋友的出圈顺序。

输入描述 Input Description

唯一的一行包含两个整数N,M。(1<=N,M<=30000)

输出描述 Output Description

唯一的一行包含N个整数,每两个整数中间用空格隔开,第I个整数表示第I个出圈的小朋友的编号。

样例输入 Sample Input

5 3

样例输出 Sample Output

3 1 5 2 4

分析 Analysis

现在有一个标准的1-n的递增排列

击鼓传花,每次数到 m 时就要去掉当前这个元素,然后继续从 0 计数

那么定义 sum( i ) 为元素 i 之前的当前实际存在的元素数,在计算过程中,sum( i ) 才是真正的位置

那么给每一个元素一个初始权值 1 ,维护每个元素以自己为端点的前缀和,就能愉快的计算 sum( i ) 啦

那么设 pos 为当前要操作的元素位置,根据 AET(Apparently Easy Theory) 原理,我们知道下一步的 pos = (pos-1)%len

但是我们计算的时候要把pos+1

那么线段树的内容就是维护前缀和且单点置零啦

注意查找

这次的线段树被阉割的非常阉割

代码 Code

 1 #include<cstdio>
 2 #include<iostream>
 3 #define mid (L+R)/2
 4 #define lc (rt<<1)
 5 #define rc (rt<<1|1)
 6 #define maxn 1000000
 7 using namespace std;
 8
 9 int Tree[maxn],n,m;
10 void maintain(int rt){Tree[rt] = Tree[lc]+Tree[rc];}
11 void build(int rt,int L,int R){
12     if(L == R) Tree[rt] = 1;
13     else{
14         build(lc,L,mid);
15         build(rc,mid+1,R);
16         maintain(rt);
17     }
18 }
19 void modify(int rt,int L,int R,int pos){
20     if(L == R) Tree[rt] = 0;
21     else{
22         if(pos <= mid) modify(lc,L,mid,pos);
23         else modify(rc,mid+1,R,pos);
24         maintain(rt);
25     }
26 }
27 int query(int rt,int L,int R,int val,int remain){
28     if(L == R) return L;
29     else{
30         if(val <= Tree[lc]+remain) return query(lc,L,mid,val,remain);
31         else return query(rc,mid+1,R,val,remain+Tree[lc]);
32     }
33 }
34
35 int main(){
36     scanf("%d%d",&n,&m);
37
38     build(1,1,n);
39
40     int pos = m,ans;
41     for(int i = n;i >= 1;i--){
42         pos = (pos-1)%(Tree[1]);
43 //        printf("###$$%d ",pos+1);
44         ans = query(1,1,n,pos+1,0);
45         printf("%d ",ans);
46         modify(1,1,n,ans);
47         pos += m;
48 //        getchar();
49     }
50
51     return 0;
52 }

阉割的非常严重的线段树

时间: 09-07

[Codevs] 1282 约瑟夫问题的相关文章

一个不简洁的约瑟夫环解法

约瑟夫环类似模型:已知有n个人,每次间隔k个人剔除一个,求最后一个剩余的. 此解法为变种,k最初为k-2,之后每次都加1. 例:n=5,k=3.从1开始,第一次间隔k-2=1,将3剔除,第二次间隔k-1=2,将1剔除.依此类推,直至剩余最后一个元素. 核心思路:将原列表复制多份横向展开,每次根据间隔获取被剔除的元素,同时将此元素存入一个剔除列表中.若被剔除元素不存在于剔除列表,则将其加入,若已存在,则顺势后移至从未加入剔除列表的元素,并将其加入.如此重复n-1次.面试遇到的题,当时只写了思路,没

【c语言】数据结构(约瑟夫生者死者游戏的问题)

约瑟夫生者死者游戏:30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分:因此船长告诉大家,只有将全船一半的旅客投入海中,其余人才能幸免遇难.无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人开始,依次报数,数到第9个人,就把他投入大海中,然后从他的下一个人开始从1数起,数到第9个人,再将她投入大海,如此循环,直到剩下15个人乘客为止.问哪些位置是将被扔到大海的位置. 解法有许多种,可以用数组,应为涉及到删除操作,数组(顺序线性表)比较麻烦,但不必要删除,只需要给跳船的人(元素

算法系列:约瑟夫斯问题

约瑟夫斯问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题.在计算机编程的算法中,类似问题又称为约瑟夫环. 有{\displaystyle n}个囚犯站成一个圆圈,准备处决.首先从一个人开始,越过{\displaystyle k-2}个人(因为第一个人已经被越过),并杀掉第k个人.接着,再越过{\displaystyle k-1}个人,并杀掉第k个人.这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着. 问题是,给定了{\displaystyle n}和{

[ CodeVS冲杯之路 ] P2492

不充钱,你怎么AC? 题目:http://codevs.cn/problem/2492/ 在此先orz小胖子,教我怎么路径压缩链表,那么这样就可以在任意节点跳进链表啦(手动@LCF) 对于查询操作,直接树状数组(以下简称BIT)维护,修改操作就一个个暴力开方搞,再用差值单点更新BIT 不过这样会TLE,要加一点优化对不对,正如开头所说的路径压缩链表 路径压缩链表其实就是个并查集,在普通的链表里,删去两个连续的节点后会是下面这种情况,如删去2,3 当访问 2 的时候,会跳到3,但 3 已经删除了,

[CODEVS 1281] Xn数列

描述 给你6个数,m, a, c, x0, n, g Xn+1 = ( aXn + c ) mod m,求Xn http://codevs.cn/problem/1281/ 分析 比较裸的矩阵乘法题, 好久没做了, 写写思路 假设矩阵 A = { {a1, a2}, {a3, a4} }, B = { {b1, b2}, {b3, b4} }. 根据矩阵乘法的计算方法, 有 : A×B = { {a1b1+a2b2, a1b2+a2b4}, {a3b1+a4b3, a3b2+a4b4} }. 那

ytu 1067: 顺序排号(约瑟夫环)

1067: 顺序排号Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 31  Solved: 16[Submit][Status][Web Board] Description 有n人围成一圈,顺序排号.从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来的第几号的那位. Input 初始人数n Output 最后一人的初始编号 Sample Input 3 Sample Output 2 HINT Source freepro

约瑟夫环 C语言 单循环链表

/*---------约瑟夫环---------*/ /*---------问题描述---------*/ /*编号为1,2,-,n的n个人围坐一圈,每人持一个密码(正整数). 一开始任选一个正整数作为报数上限值m, 从第一个人开始自1开始顺序报数,报到m时停止. 报m的人出列,将他的密码作为新的m值,从他的下一个人开始重新从1报数, 如此下去,直至所有人全部出列为止.试设计一个程序求出列顺序.*/ /*---------问题分析---------*/ /*n个人围坐一圈,且不断有人出列,即频繁

Codevs 1257 打砖块

1257 打砖块 http://codevs.cn/problem/1257/ 题目描述 Description 在一个凹槽中放置了n层砖块,最上面的一层有n块砖,第二层有n-1块,……最下面一层仅有一块砖.第i层的砖块从左至右编号为1,2,……i,第i层的第j块砖有一个价值a[i,j](a[i,j]<=50).下面是一个有5层砖块的例子.如果你要敲掉第i层的第j块砖的话,若i=1,你可以直接敲掉它,若i>1,则你必须先敲掉第i-1层的第j和第j+1块砖. 你的任务是从一个有n(n<=5

codevs——T1219 骑士游历

 http://codevs.cn/problem/1219/ 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 查看运行结果 题目描述 Description 设有一个n*m的棋盘(2≤n≤50,2≤m≤50),如下图,在棋盘上有一个中国象棋马. 规定: 1)马只能走日字 2)马只能向右跳 问给定起点x1,y1和终点x2,y2,求出马从x1,y1出发到x2,y2的合法路径条数. 输入描述 Input Description 第一行2个整数n和m 第二行4个