4.6 模拟赛小记

小寄，嘿嘿，嘿嘿。

T1 猴子选大王

首先声明我是智障，然后本题时根据子任务分开解决。

对于第一个子任务，可以看一下 [luogu P8671 约瑟夫环](https://www.luogu.com.cn/problem/P8671)，用 f 存当前所选个数下的答案下标，易推得公式 f[i] = (f[i - 1] + m) % i。

怎么推得？正难则反，不妨设想当环中只剩下一人时、剩下二人时.....刚开始时，分别能得到 f[1] = 0，f[2] = (f[1] + m) % 2, f[3] = (f[3] + m) % 3....f[i] = (f[i - 1] + m % i)。参考了本题其他题解。

对于第二个子任务，当 m = 1 时，不难得到最后一个即为答案。

对于第三个子任务，可以模拟进行规律寻找。答案即找到这个数二进制下最高位 1，该数与这个 2 的幂之差乘二加一。太抽象了，具体见代码，还是建议自己手动模拟。
```cpp
#include<bits/stdc++.h>
#define intt long long
using namespace std;
const intt N = 1e8 + 10;
intt n, m;
intt vis[N];
void did1()
{
intt sum = 0;
for(int i = 2; i <= n; i ++ ) sum = (sum + m) % i;
cout << sum + 1;
}
void did2() {cout << n;}
bool check(intt k)
{
intt low = k & -k;
if(low != k || k == 0) return 0;
return 1;
}
intt bpow(intt a, intt b)
{
intt ans = 1;
while(b)
{
if(b % 2) ans = ans * a;
a = a * a;
b /= 2;
}
return ans;
}
void did3()
{
if(check(n)) {cout << 1; return;}
if(check(n + 1)) {cout << n; return;}
intt i = 0, nn = n;
while(nn)
{
nn >>= 1;
i ++;
}
i --;
printf("%lld", (n - bpow(2, i)) * 2 + 1);
}
signed main()
{
scanf("%lld%lld", &n, &m);
if(n <= 10000000)
{
did1();
return 0;
}
if(m == 1)
{
did2();
return 0;
}
if(m == 2)
{
did3();
return 0;
}
}
```
T2 好人与坏人

还是和约瑟夫问题有关，在早期我甚至做过，居然不会写了，属实难绷。