首页 > 其他分享 >牛客题解 约瑟夫环

牛客题解 约瑟夫环

时间:2022-09-18 10:11:36浏览次数:100  
标签:return 牛客 int 题解 约瑟夫 vis num operate

链接:https://ac.nowcoder.com/acm/problem/22227
来源:牛客网

题解

作者 岛田小雅

正统的约瑟夫环我不会,看了一眼范围直接开始乱搞了。

我选择的方法是模拟,用递归函数实现(虽然也可以不用)

设置一个递归函数 \(operate()\),两个参数分别存正在报数的人 \(x\) 和他要报的数字 \(num\)。因为有人要出队,所以再开个 \(vis\) 数组存第 \(i\) 个人还在不在队伍里。函数要一直递归到只剩下一个人,所以再用一个变量 \(r\) 存还剩下几个人。每次一个人出队就维护 \(r\),当 \(r=1\) 的时候,结束递归。

最后在所有 \(vis\) 里面找那个还在队伍里的人然后输出出来就好了。

我会承认写的时候样例测了好几次都没过是因为少了个 return 吗。

话说回来为什么这么像 DFS 呢……

AC 代码

作者 岛田小雅
#include <bits/stdc++.h>
using namespace std;

const int N = 1e2+2;
int n, k, m;
bool vis[N];
int r;

void operate(int x, int num)
{
    x %= n;
    if(r == 1) return;
    if(vis[x])
    {
        operate(x+1,num);
        return;
    }
    if(num == m)
    {
        vis[x] = true;
        r--;
        operate(x+1,1);
    }
    else operate(x+1,num+1);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> m;
    r = n;
    for(int i = 0; i < n; i++) vis[i] = false;
    operate(k,1);
    for(int i = 0; i < n; i++)
    {
        if(!vis[i])
        {
            cout << i;
            break;
        }
    }
    return 0;
}

标签:return,牛客,int,题解,约瑟夫,vis,num,operate
From: https://www.cnblogs.com/CasseShimada/p/16704267.html

相关文章

  • 2022上半年软件设计师真题解析
    选择题 ......
  • AtCoder Beginner Contest 269 (A-F)题解
    A-AnywayTakahashi这里我还是关了ll的C开了忘了关害的F多了一发罚时#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+10;constintM=9982443......
  • 题解【CF1702G2 Passable Paths (hard version)】
    题目传送门。考虑建立虚树然后再上面搞树形DP。于是这道题就变成分讨题。设\(f_i\)表示\(i\)子树内的答案。若\(f_i=1\),表示\(i\)子树内的特殊点可以被一条链覆......
  • CF1718D 题解
    设\(k\)为\(a\)中的空位数量。首先咱们转化这个“相似”的条件,发现它其实是说,笛卡尔树的结构相同。那么我们把p建笛卡尔树然后把a的数往上填。如果此时有上面小于下......
  • Android安卓浏览器视频层级永远顶层问题解决方案
    在安卓手机上,使用video播放视频有个问题,video控件层级会永远在顶层,不利于视频互动H5开发,而IOS手机上不会有此问题。腾讯给出了如下解决方案:<videosrc="http://xxx.mp4......
  • AtCoder Beginner Contest 267 题解
    只会\(A\simG\)主观难度:\(A<B<C<E<D<F<G<Ex\)A-Saturday分别对周一到周五判断即可。#include<bits/stdc++.h>usingnamespacestd;inlineintread(){int......
  • 牛客网-SQL专项练习2
    ①从学生信息表(student)中提取姓名(name)列值为NULL的记录,SQL语句为:解析:注意不是只查name值,而是查name值为空的所有信息SQL语句为:SELECT*FROM studentWHEREnameisNU......
  • 牛客网-SQL专项练习1
    ①检索所有比“王华”年龄大的学生姓名、年龄和性别。SELECT语句:解析:第一步:先找到王华的年龄SELECTAGEFROMSWHRESN="王华";第二步:将第一步的结果作为条件进行......
  • "蔚来杯"2022牛客暑期多校训练营5
    ADon'tStarve巧妙在于拓扑排序为啥要开滚动数组因为对于长度相同的边我们只能选择一条而这些边属于同一个状态的为了防止更新的时候对同状态的点造成影响#inclu......
  • CF1305F Kuroni and the Punishment 题解
    一道比较简单的题,我居然调了这么久。思路看一眼这个题,发现好像没有什么思路。考虑来用一些巧妙的手法,比如随机化。首先证明一个结论,至少有一半的数只会被操作一次或者......