Magic Master(2019年南昌网络赛E题+约瑟夫环)

目录
  • 题目链接
  • 题意
  • 思路
  • 代码

题目链接

传送门

题意

初始时你有\(n\)张牌(按顺序摆放)，每一次操作你将顶端的牌拿出，然后按顺序将上面的\(m\)张牌放到底部。

思路

首先我们发下拿走\(1\)后就变成了总共有\(n-1\)个人数到\(m+1\)的人出局，问你每个人是第几个出局的，很明显的约瑟夫环。

比赛的时候我还在推公式，然后发现机房有人用暴力模拟过了，尤其是题解也是暴力，就很无语。

如果这题标程不假并且只给\(1s\)，那么该怎么写呢？

这题由于\(n\)很大，我们肯定不能将\(n\)个人出局顺序一一枚举，然后我们发现\(q\)很小，因此我们就对查询的那个编号进行求解即可。

由于第一个人始终是第一个出局的，那么我们将他特判掉，然后\(n=n-1\)，又由于是数到\(m+1\)出局，因此令\(m=m+1\)，然后开始解题。

假设当前有\(n(n\geq m\)人，那么将会出局\(m,2m,3m,\dots,\lfloor\frac{n}{m}\rfloor*m\)，然后将\(\lfloor\frac{n}{m}\rfloor*m+1,\lfloor\frac{n}{m}\rfloor*m+2,\dots,n\)和前面没有出局的人拼接起来变成\(\lfloor\frac{n}{m}\rfloor*m+1,\lfloor\frac{n}{m}\rfloor*m+2,\dots,n,1,\dots\)，然后更新现在查询的人的编号是多少即可。

注意当\(n时，再用上式就会发现没有人出局，因此需要转变思路，每次出局编号为\((m-1)\% n+1\)，\(m-1\)后再取模加一是处理掉模\(n\)等于\(0\)的情况，之后就和上面一样拼接即可，这部分只需要循环\(m\)次，也就是说最多循环\(10\)次。

用这种方法只需要跑\(2ms\)，因此这次网络赛给的时限使得这题成为了一道假题。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson (rt<<1)
#define rson (rt<<1|1)
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< (tot / m) * m) x = x - (tot / m) * m;
                else x = tot - (tot / m) * m + x - (x / m);
                tot -= tot / m;
            }
        }
    }
    return 0;
}
迷之数论比赛题解感想

相关

标签