首页 > 其他分享 >洛谷P1996约瑟夫问题

洛谷P1996约瑟夫问题

时间:2024-05-26 21:32:45浏览次数:27  
标签:输出 数到 出圈 10 int 约瑟夫 P1996 洛谷 报数

题目描述 P996约瑟夫问题

n 个人围成一圈,从第一个人开始报数,数到 m 的人出列,再由下一个人重新从 11 开始报数,数到 m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1 名小朋友,而该题是全部出圈。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数,按顺序输出每个出圈人的编号。

输入输出样例

输入 

10 3

输出 

3 6 9 2 7 1 8 5 10 4

说明/提示

1≤m,n≤100

用数组来模拟双向链表

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int num[N],nxt[N],pre[N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		num[i]=i;
		nxt[i]=i+1;
		pre[i]=i-1;
	}
	pre[1]=n; nxt[n]=1;
	int x=1,cnt=1;                         //cnt为编号x的人的报数,第1个人报数1 
	while(n)
	{
		if(cnt==m){
			--n;                           //人数-1 
			cout<<num[x]<<" ";
			nxt[pre[x]]=nxt[x];
			pre[nxt[x]]=pre[x];
			cnt=0;                         //让下一个报数的人报1 
		}
		x = nxt[x];                        //让编号为x的人原本相邻的下一个人报数 
		++cnt;
	} 
	return 0;
}

标签:输出,数到,出圈,10,int,约瑟夫,P1996,洛谷,报数
From: https://blog.csdn.net/BigNbYQQ/article/details/139220820

相关文章

  • Smart - Luogu —— 智能的洛谷
    目录安装Stylus谷歌Edge安装Smart-Luogu使用尾声安装Styluslink点击推荐下载,获取crx文件谷歌先点击右上角三个点,再点击扩展程序,然后点击管理扩展程序,进入管理扩展界面,把开发者模式选上,把crx文件拖入即可Edge先点击右上角三个点,再点击扩展,然后点击管理扩展程序,进入......
  • 二叉树搜索树 洛谷P5076
    洛谷P1827#include<bits/stdc++.h>usingnamespacestd;intn,root,cnt,opt,x;structnode{intvalue,left,right,size,num;node(intl,intr,ints,intv):left(l),right(r),size(s),value(v),num(1){}node(){}}t[10010];voidu......
  • 洛谷[普及]:P1149 [NOIP2008 提高组] 火柴棒等式
    [NOIP2008提高组]火柴棒等式感谢题目提供者CCF_NOI题目描述给你n 根火柴棍,你可以拼出多少个形如A+B=C 的等式?等式中的A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字 的拼法如图所示:注意:1.加号与等号各自需要两根火柴棍;2.如果,则......
  • 深度优先搜索 洛谷P1605迷宫
    深度优先搜索洛谷P1605迷宫题目描述给定一个$N\timesM$方格的迷宫,迷宫里有$T$处障碍,障碍处不可通过。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标,每个方格最多经过一次,问有多少种从起点坐标到终点坐标的方......
  • 广度优先搜索 洛谷P2895Meteor Shower S
    广度优先搜索洛谷P2895[USACO08FEB]MeteorShowerS题面翻译题目描述贝茜听说一场特别的流星雨即将到来:这些流星会撞向地球,并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑,发誓要找到一个安全的地方(一个永远不会被流星摧毁的地方)。如果将牧场放入一个直角坐标系中,贝茜......
  • 二分答案 洛谷P3853路标设置
    这个题思路和洛谷P2440有点像,建议先看P2440这个题,较简单。[TJOI2007]路标设置题目背景B市和T市之间有一条长长的高速公路,这条公路的某些地方设有路标,但是大家都感觉路标设得太少了,相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题,我们把公路上相邻路标的最......
  • 广度优先搜索 洛谷P1443马的遍历(bfs超时问题)
    广度优先搜索洛谷P1443这里先介绍一下广度优先搜索:广度优先搜索就是先将第一步可能的步骤全部记录,遍历过后,再将由第一步到达的第二步全部记录并遍历,直到最后全部遍历。而此题要求我们求得最少步数,广度优先就能够达到最少步数的要求,因为广度优先是先通过搜索所有可能的第n步才......
  • 深度优先搜索 洛谷P1219八皇后
    深度优先搜索洛谷P1219这是一道经典的深度优先搜索问题,深度优先搜索可用以下模板:voiddfs(intdepth){ if(达到边界){ 记录解 } for(枚举在depth这一深度,能够使用的解){ if(解可行){ 记录解(记录已经被使用) dfs(depth+1) 恢复解(恢复原状) } }}题目要求我们......
  • 二分答案 洛谷2440木材加工
    二分答案题目详见洛谷P2440木材加工分享一下自己新学习的二分答案的方法,开始可能有点奇怪为啥这样能做,但其实思路很简单。起始思路题目要求我们求最大的分解长度,所以我(们)最开始想的肯定是从大到小(求最大值)枚举答案,看看是否满足,满足不了就加1。但这样暴力肯定是会超时的,那我们......
  • 洛谷 P4383 [八省联考 2018] 林克卡特树
    原题等价于在树上选出\(k+1\)条不相交链,最大化边权和。树形DP。设\(f_{u,k,0/1/2}\)表示在\(u\)的子树中选了\(k\)条链,\(u\)的度数为\(0,1,2\)的最大边权和。注意到状态里缺了链退化为单个点的情况,可以把它放到\(f_{u,k,2}\)中(相当于自环)。转移时分讨一......