2018-2019 ACM-ICPC, Asia Shenyang Regional Contest K. Let the Flames Begin 经典约瑟夫问题 + 思维
思维题   发布于 2019-08-27   699人围观  0条评论
思维题   发表于 2019-08-27   699人围观  0条评论

题目大意

n个人围成一圈,从1号开始报数,报到k的人出圈,然后再从下一个人开始新一轮报数。问经过第m个出圈的人最开始的编号是多少。

题解

经典约瑟夫问题,想必大家都知道递推式吧……

f(n,m) = (f(n-1,m-1) + k) % n

好了就是这样,至于具体证明貌似说刘汝佳的白书上有?

但是我们注意到此题数据范围真的是太大了,我们不能使用O(m)的做法了……

不,并不是不能用,只是当m小于等于k的时候我们可以这么做(这时候m的范围只有2x106),但是如果是k小于等于m的时候我们就要另作讨论了。

首先如果k = 1,那我们直接输出m就好,因为题目保证n ≥ m;

但是如果k > 1……

我们注意到,如果k比较小,远小于n-m的话,我们可能进行d轮都轮不完一圈,所以我们考虑可以用乘法跳项的思想来加速递推式的推进。

最终的复杂度不是很清楚是多少,但是由于使用了乘法来加速,所以我们中间实际上跳过了很多不必要取模的项,整体复杂度就比较低了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;
int t;
ll d,now,a;
ll ans = 0;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    int cas = 0;
    while(t--){
        cas++;
        ans = 0;
        cin >> n >> m >> k;
        ll ans = (k - 1) % (n - m + 1) + 1;
        if(k == 1){
            ans = m;
        }
        else if(k >= m){
            for(ll i = 2;i <= m;++i)
                ans = (ans + k - 1) % (n - m + i) + 1;
        }
        else{
            now = 1,a = n - m;
            while(now < m){
                d = (now + a - ans);
                if(d < 0)d = 0;
                if(d % k){
                    d /= k;
                    d++;
                }
                else d /= k;
                if(d == 0)d++;
                if(now + d >= m)d = m - now;
                now += d;
                ll mod = now + a;
                ans = (ans + k * d % mod - 1 + mod) % mod + 1;
            }
        }
        cout << "Case #" << cas << ": " << ans << "\n";
    }
    return 0;
}


上一篇: 2018 ICPC 徐州赛站网络赛 H Ryuji doesn't want to study 线段树

下一篇: 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest E.The Kouga Ninja Scrolls 曼哈顿距离转换契比雪夫距离 + 线段树单点修改

立即登录,发表评论
没有帐号?立即注册
0 条评论