首页 > 其他分享 >「洛谷」题解:P1996 约瑟夫问题

「洛谷」题解:P1996 约瑟夫问题

时间:2024-04-25 19:11:37浏览次数:24  
标签:出圈 题目 int 题解 visit 队列 P1996 洛谷 样例

题目传送门

先看题目:

题目描述

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

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

输入格式

输入两个整数 \(n,m\)。

输出格式

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

样例 #1

样例输入 #1

10 3

样例输出 #1

3 6 9 2 7 1 8 5 10 4

提示

\(1 \le m, n \le 100\)

这道题目就是一道队列的应用,但是因为手写队列会比STL快很多,所以需要手写队列更好一点,以下是代码(欢迎抄袭)

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, m, s = 0;
	scanf("%d %d", &n, &m);
    bool visit[200] = {0};
    for(int k = 0; k < n; ++ k) {
        for(int i = 0; i < m; ++ i){
			if(++ s > n) s = 1;
			if(visit[s]) -- i;
		}
        printf("%d ",s);
		visit[s] = true;
    }
    return 0;
}

这道题么不仅仅运用了队列,也运用了标记数组(比如visit数组),但是这道题目总体来说还是比较经典和简单的,欢迎各位奆老来找茬帮助本蒟蒻更好的提高!

标签:出圈,题目,int,题解,visit,队列,P1996,洛谷,样例
From: https://www.cnblogs.com/charzie-blog/p/18158376

相关文章

  • [题解] [NOIP2011 提高组] Mayan 游戏
    [题解][NOIP2011提高组]Mayan游戏题目描述有一个\(7\)行\(5\)列的格子棋盘,有的格子上有方块。方块有重力,即如果一个方块下面没有其他方块,他就会往下掉,直到触底或者下面有方块为止。每个方块都有自己的颜色,如果连着三个竖着或者横着的方块颜色相同,它们就会消除。如果出......
  • 洛谷题单指南-动态规划2-P1874 快速求和
    原题链接:https://www.luogu.com.cn/problem/P1874题意解读:一个数字字符串s,分解成几个整数,和为n,计算最少加号个数,也就是计算最少分解的整数个数-1。解题思路:此题虽然分类在动态规划,但数据量不大,DFS更加直观和易于理解,所以采用DFS暴搜+剪枝来解决。搜索思路是对数字字符串依次枚......
  • CF1774G Segment Covering 题解
    题目链接点击打开链接题目解法这么牛的题!!!我第一眼看到偶\(-\)奇想到的是LGV/xk有一堆线段的题先考虑有没有线段之间的特殊关系这道题中,如果有线段\(x\)包含线段\(y\),则线段\(x\)是无用的,因为如果选了\(x\),那么选不选\(y\)无所谓,因为是偶\(-\)奇,所以贡献抵消了......
  • 重庆软航H5 PDF签章产品经nginx代理之后在浏览器中在线打开PDF盖章时提示:签章失败:网络
    问题现象:问题描述:在系统中集成了软航H5PDF签章产品,软航H5PDF签章产品的对应服务是通过nginx代理的,在奇安信浏览器中在线打开PDF点击产品的工具栏上的盖章按钮:选定印章之后,在PDF文档上选定盖章位置之后,提示:签章失败:网络错误。最近在做这个软航H5PDF电子签章产品的测试,就简......
  • CF518F 题解
    观察到一条管道的拐点数量只有\(3\)种可能的取值:没有拐点,即管道呈现一条直线。有\(1\)个拐点。有\(2\)个拐点。分别对应了下面三种情况:....#....#.*..#*********..***...#....#*...#*.#.........
  • 2023CPCC河南省赛题解+总结
    2023CPCC河南省赛题解+总结比赛链接:https://codeforces.com/gym/104354答题情况:答题情况开题顺序是:A-F-H-K-E-B-G题面链接:https://codeforces.com/gym/104354/attachments/download/20061/statements_2.pdfProblemA.小水獭游河南签到题,队友写的题意:  给你一个字符......
  • git命令下,mac环境下载依赖相关报错问题解决方案
    1.安装fundry框架curl-Lhttps://foundry.paradigm.xyz|bash2.写入环境变量source/Users/xx/.bashrc3.foundryup问题1报错:致命错误:无法访问'https://github.com/foundry-rs/forge-std解决方案:设置hosts文件:添加指定url的ip地址:140.82.112.4github.com185.1......
  • 【题解】A566.三点共线
    题目大意,给定在平面直角坐标系中的多个点,判断有多少个三元组\((A,B,C)\)满足共线性质。题目链接:A566.三点共线。大题思路就是暴力所有的三元组,判断三个元素的斜率是否相同即可。其实还有其他方法可以做,我个人感觉用斜率法最简单。有几点需要注意:在计算斜率的时候,如果多......
  • 洛谷题单指南-动态规划2-P4933 大师
    原题链接:https://www.luogu.com.cn/problem/P4933题意解读:求有多少个子序列可以组成等差序列解题思路:1、暴力DFS如果实在想不出动规的方法,对于n<=20的数据,可以DFS枚举所有子序列的子集,再判断是否是等差数列。30分代码:#include<bits/stdc++.h>usingnamespacestd;const......
  • ABC350 E - Toward 0 题解
    AtCoderBeginnerContest350E-Toward0原题地址题意给定四个数NAXY,你可以对N进行以下两种操作。花费X的代价将N变成\(\lfloor\cfrac{N}{A}\rfloor\)花费Y的代价掷一颗骰子,设掷出结果是i,将N变成\(\lfloor\cfrac{N}{i}\rfloor\)你需要执行若干次......