Skip to content

14095: 【原4095】春樱对决

题目

题目描述

author: pig 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4095

【试题描述】

在这万物复苏的春天,“春樱对决”比赛开始啦!晴明有N个式神,他想从这N个式神里选一个来当这次活动海报的主角。因为想当主角的式神非常多,于是晴明就定下了这样一个选拔的规矩:

将N个式神从左到右排成一排,编号为1~N。从第1个式神开始进行1~M的正向报数,报到的第M个式神出列,再从下一个式神开始继续1到M报数、出列。如果按照某个方向报数到尾部,那么再反方向继续报数。如此进行下去,直到剩下一个式神,而这个式神就是本次“春樱对决”海报的主角。

第一个来到这个寮的两面佛渴望能成为主角,毕竟这是他唯一可能成为主角的时刻了。于是佛佛求你编个程序帮助他实现这个愿望,告诉他要想当主角,他的编号应该是多少。

【输入要求】

输入文件仅有一行包含二个用空格隔开的整数N,M (N≤10^5,M≤10^9)。

【输出要求】

输出文件仅有一行包含一个整数表示一个整数,表示这个两面佛在队列中的编号。

【输入样例】

9 3

【输出样例】

8

FineArtz's solution

/* 春樱对决 */
#include <iostream>
using namespace std;

class Node{
public:
    int sum = 0, l = 0, r = 0;
};

int n, m, ans = 0;
Node a[100005 * 4];
bool b[100005];

void buildTree(int x, int l, int r){
    if (l == r){
        a[x].sum = 1;
        a[x].l = l;
        a[x].r = r;
        return;
    }
    a[x].l = l;
    a[x].r = r;
    int mid = (l + r) / 2;
    buildTree(x * 2, l, mid);
    buildTree(x * 2 + 1, mid + 1, r);
    a[x].sum = a[x * 2].sum + a[x * 2 + 1].sum;
}

int sum(int l, int r, int x = 1){
    if (l <= a[x].l && r >= a[x].r)
        return a[x].sum;
    int mid = (a[x].l + a[x].r) / 2;
    int ret = 0;
    if (l <= mid)
        ret += sum(l, r, x * 2);
    if (r > mid)
        ret += sum(l, r, x * 2 + 1);
    return ret;
}

void del(int y, int x = 1){
    if (a[x].l == y && a[x].r == y){
        a[x].sum = 0;
        return;
    }
    int mid = (a[x].l + a[x].r) / 2;
    if (y <= mid)
        del(y, x * 2);
    else
        del(y, x * 2 + 1);
    a[x].sum = a[x * 2].sum + a[x * 2 + 1].sum;
}

int count(int k, int p, int &d){
    if (d == 1){
        int l = k, r = n - 1, mid;
        while (l <= r){
            mid = (l + r) / 2;
            int t = sum(k, mid);
            if (t == p + 1){
                if (b[mid])
                    break;
                else
                    r = mid - 1;
            }
            else if (t < p + 1)
                l = mid + 1;
            else
                r = mid - 1;
        }
        del(mid);
        b[mid] = false;
        if (sum(mid, n - 1) != 0){
            l = mid + 1;
            r = n - 1;
            int mid2;
            while (l < r){
                mid2 = (l + r) / 2;
                if (sum(mid, mid2) >= 1)
                    r = mid2;
                else
                    l = mid2 + 1;
            }
            k = l;
        }
        else{
            l = 0;
            r = mid - 1;
            int mid2;
            while (l < r){
                mid2 = (l + r) / 2 + (l + r) % 2;
                if (sum(mid2, mid) >= 1)
                    l = mid2;
                else
                    r = mid2 - 1;
            }
            k = r;
            d = -1;
        }
    }
    else{
        int l = 0, r = k, mid;
        while (l <= r){
            mid = (l + r) / 2;
            int t = sum(mid, k);
            if (t == p + 1){
                if (b[mid])
                    break;
                else
                    l = mid + 1;
            }
            else if (t > p + 1)
                l = mid + 1;
            else
                r = mid - 1;
        }
        del(mid);
        b[mid] = false;
        if (sum(0, mid) != 0){
            l = 0;
            r = mid - 1;
            int mid2;
            while (l < r){
                mid2 = (l + r) / 2 + (l + r) % 2;
                if (sum(mid2, mid) >= 1)
                    l = mid2;
                else
                    r = mid2 - 1;
            }
            k = l;
        }
        else{
            l = mid + 1;
            r = n - 1;
            int mid2;
            while (l < r){
                mid2 = (l + r) / 2;
                if (sum(0, mid2) >= 1)
                    r = mid2;
                else
                    l = mid2 + 1;
            }
            k = r;
            d = 1;
        }
    }
    return k;
}

int main(){
    cin >> n >> m;
    --m;
    for (int i = 0; i < n; ++i)
        b[i] = true;
    buildTree(1, 0, n - 1);
    int d = 1, k = 0;
    for (int i = n; i > 1; --i){
        int p = m % (2 * i - 2);
        if (d == 1){
            int t = sum(k, n - 1);
            if (p + 1 <= t)
                k = count(k, p, d);
            else if (p + 1 <= t + i - 1){
                int l = 0, r = n - 1, mid;
                while (l < r){
                    mid = (l + r) / 2 + (l + r) % 2;
                    if (sum(mid, n - 1) >= 1)
                        l = mid;
                    else
                        r = mid - 1;
                }
                d = -1;
                k = count(r, p - t + 1, d);
            }
            else{
                int l = 0, r = n - 1, mid;
                while (l < r){
                    mid = (l + r) / 2;
                    if (sum(0, mid) >= 1)
                        r = mid;
                    else
                        l = mid + 1;
                }
                k = count(l, p - t - i + 2, d);
            }
        }
        else{
            int t = sum(0, k);
            if (p + 1 <= t)
                k = count(k, p, d);
            else if (p + 1 <= t + i - 1){
                int l = 0, r = n - 1, mid;
                while (l < r){
                    mid = (l + r) / 2;
                    if (sum(0, mid) >= 1)
                        r = mid;
                    else
                        l = mid + 1;
                }
                d = 1;
                k = count(l, p - t + 1, d);
            }
            else{
                int l = 0, r = n - 1, mid;
                while (l < r){
                    mid = (l + r) / 2 + (l + r) % 2;
                    if (sum(mid, n - 1) >= 1)
                        l = mid;
                    else
                        r = mid - 1;
                }
                k = count(r, p - t  - i + 2, d);
            }
        }
    }
    cout << ++k << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

bool check[100009] = { 0 };

int main() {
    int N, M;
    cin >> N >> M;

    auto cnt = N, pos = 0;

    for (int left = 0, right = cnt; cnt > 1; --cnt) {
        left = cnt - right;
        //计算最后一步的位移
        auto step = M % (2 * cnt - 2);
        if (step == 0)
            step = cnt * 2 - 2;
        if (step <= right) {
            //移动
            for (int i = 0; i < step; )
                if (!check[++pos])
                    ++i;
            right -= step;
        }
        else if (step < right * 2) {
            //移动
            for (int i = 0; i < right * 2 - step;)
                if (!check[++pos])
                    ++i;
            right = step - right;
        }
        else if (step < right * 2 + left - 1) {
            //移动
            for (int i = 0; i < step - right * 2 + 1;)
                if (!check[--pos])
                    ++i;
            right = step - right;
        }
        else {
            //移动
            for (int i = 0; i < cnt * 2 - 1 - step;)
                if (!check[--pos])
                    ++i;
            right += cnt * 2 - 2 - step;
        }
        check[pos] = true;
    }

    printf("%d", pos);

    return 0;
}

q4x3's solution

/**
 * 究极约瑟夫环
 * 线段树
 * 最难的不是树而是各种边界判断
 **/
#include <iostream>

using namespace std;

const int MAXN = 1e5 + 233;
// num表示编号叶子为编号非叶子为0 tree表示该段剩余人数
int num[MAXN << 2], tree[MAXN << 2];
int N, M, tmp1, tmp2;

void build(int rt, int l, int r) {
    if(l == r) {
        tree[rt] = 1;
        num[rt] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void del(int rt, int l, int r, int x) {
    if(l == r) {
        tree[rt] = 0;
        num[rt] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    if(tree[rt << 1] >= x) {
        del(rt << 1, l, mid, x);
    } else {
        del(rt << 1 | 1, mid + 1, r, x - tree[rt << 1]);
    }
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

int query(int rt, int l, int r) {
    if(l == r) return num[rt];
    int mid = (l + r) >> 1;
    int tmp1 = query(rt << 1, l, mid), tmp2 = query(rt << 1 | 1, mid + 1, r);
    return tmp1 > tmp2 ? tmp1 : tmp2;
}

int main() {
    scanf("%d%d", &N, &M);
    if(M == 1) printf("%d\n", N);
    else if(N == 1) printf("1\n");
    else {
        build(1, 1, N);
        bool dir = 1; // 1 right, 0 left
        tmp1 = 1;
        for(int i = N;i > 1;-- i) {
            if(dir) {
                if(M < i + 1 - tmp1) {
                    tmp1 += (M - 1);
                    del(1, 1, N, tmp1);
                } else {
                    tmp1 = M - i + tmp1;
                    tmp2 = tmp1 / (i - 1);
                    tmp1 %= (i - 1);
                    if(tmp1 == 0) {
                        -- tmp2;
                        tmp1 = i - 1;
                    }
                    if(tmp2 % 2 == 0) {
                        tmp1 = i + 1 - tmp1;
                        dir = 0;
                        del(1, 1, N, tmp1);
                    } else {
                        dir = 1;
                        del(1, 1, N, tmp1);
                    }
                }
            } else {
                if(M < tmp1 - 1) {
                    tmp1 -= M;
                    del(1, 1, N, tmp1);
                } else {
                    tmp1 = M - tmp1 + 2;
                    tmp2 = tmp1 / (i - 1);
                    tmp1 %= (i - 1);
                    if(tmp1 == 0) {
                        -- tmp2;
                        tmp1 = i - 1;
                    }
                    if(tmp2 % 2 == 0) {
                        dir = 1;
                        del(1, 1, N, tmp1);
                    } else {
                        tmp1 = i + 1 - tmp1;
                        dir = 0;
                        del(1, 1, N, tmp1);
                    }
                }
            }
        }
        printf("%d\n", query(1, 1, N));
    }
    return 0;
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
long long seq[400005] = {};
bool exist[400005]    = {};
struct set {
    int l;
    int r;
    int current;
    long long& value;
    set left() {
        return set{l, (l + r) >> 1, current << 1, seq[current << 1]};
    }
    set right() {
        return set{((l + r) >> 1) + 1, r, current << 1 | 1, seq[current << 1 | 1]};
    }
    bool isleaf() { return !(r - l); }
};
void buildtree(set s) {
    if (s.isleaf()) {
        s.value = 1;
        return;
    }
    buildtree(s.left());
    buildtree(s.right());
    s.value = s.left().value + s.right().value;
    return;
}
long long query(int l, int r, set s) {
    if (l > r)
        return 0;
    if (l <= s.l && s.r <= r) {
        return s.value;
    }
    int mid      = (s.l + s.r) >> 1;
    long long q1 = 0, q2 = 0;
    if (l <= mid) {
        q1 = query(l, r, s.left());
    }
    if (r > mid) {
        q2 = query(l, r, s.right());
    }
    return q1 + q2;
}
void update(int l, set s) {
    if (l < s.l || s.r < l) {
        return;
    }
    if (s.isleaf()) {
        s.value = 0;
        return;
    }
    int mid = (s.l + s.r) >> 1;
    if (l <= mid) {
        update(l, s.left());
    } else {
        update(l, s.right());
    }
    s.value = s.left().value + s.right().value;
    return;
}

int binarysearch(int l, int r, int num, set ss) {
    int llim = l, mid;
    while (l <= r) {
        mid   = (l + r) / 2;
        int t = query(llim, mid, ss);
        if (t == num) {
            if (exist[mid])
                return mid;
            else
                r = mid - 1;
        } else if (t < num)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return 0;
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    buildtree(set{1, N, 1, seq[1]});
    for (int i = 1; i <= N; i++) {
        exist[i] = true;
    }
    int current    = 1;
    bool direction = 0; //pos
    int q          = N;
    while (q != 1) {
        int amounts = M % (2 * (q - 1));
        int rr      = query(current + 1, N, set{1, N, 1, seq[1]});
        int ll      = query(1, current - 1, set{1, N, 1, seq[1]});
        if (amounts == 0) {
            int p = current;
            if ((ll == 0) || (direction && rr != 0)) {
                p        = binarysearch(p + 1, N, 1, set{1, N, 1, seq[1]});
                exist[p] = false;
                update(p, set{1, N, 1, seq[1]});
            } else {
                p        = binarysearch(1, p - 1, ll, set{1, N, 1, seq[1]});
                exist[p] = false;
                update(p, set{1, N, 1, seq[1]});
            }
            q = query(1, N, set{1, N, 1, seq[1]});
            continue;
        }
        if (!direction) {
            if (amounts < rr + 1) {
                current        = binarysearch(current, N, amounts, set{1, N, 1, seq[1]});
                exist[current] = false;
                update(current, set{1, N, 1, seq[1]});
                current = binarysearch(current + 1, N, 1, set{1, N, 1, seq[1]});
                q       = query(1, N, set{1, N, 1, seq[1]});
                continue;
            }
            if (amounts >= rr + 1 && amounts < rr + q) {
                amounts -= rr + 1;
                current   = N;
                direction = 1;
                amounts++;
                current        = binarysearch(1, N, q - amounts + 1, set{1, N, 1, seq[1]});
                exist[current] = false;
                update(current, set{1, N, 1, seq[1]});
                current = binarysearch(1, current - 1, q - amounts, set{1, N, 1, seq[1]});
                q       = query(1, N, set{1, N, 1, seq[1]});
                continue;
            }
            if (amounts >= rr + q) {
                amounts -= rr + q;
                current   = 1;
                direction = 0;
                amounts++;
                current        = binarysearch(1, N, amounts, set{1, N, 1, seq[1]});
                exist[current] = false;
                update(current, set{1, N, 1, seq[1]});
                current = binarysearch(current + 1, N, 1, set{1, N, 1, seq[1]});
                q       = query(1, N, set{1, N, 1, seq[1]});
                continue;
            }
        } else {
            if (amounts < ll + 1) {
                current        = binarysearch(1, current, ll - amounts + 2, set{1, N, 1, seq[1]});
                exist[current] = false;
                update(current, set{1, N, 1, seq[1]});
                current = binarysearch(1, current - 1, ll - amounts + 1, set{1, N, 1, seq[1]});
                q       = query(1, N, set{1, N, 1, seq[1]});
                continue;
            }
            if (amounts >= ll + 1 && amounts < ll + q) {
                amounts -= ll + 1;
                current   = 1;
                direction = 0;
                amounts++;
                current        = binarysearch(1, N, amounts, set{1, N, 1, seq[1]});
                exist[current] = false;
                update(current, set{1, N, 1, seq[1]});
                current = binarysearch(current + 1, N, 1, set{1, N, 1, seq[1]});
                q       = query(1, N, set{1, N, 1, seq[1]});
                continue;
            }
            if (amounts >= ll + q) {
                amounts -= ll + q;
                current   = N;
                direction = -1;
                amounts++;
                current        = binarysearch(1, N, q - amounts + 1, set{1, N, 1, seq[1]});
                exist[current] = false;
                update(current, set{1, N, 1, seq[1]});
                current = binarysearch(1, current - 1, q - amounts, set{1, N, 1, seq[1]});
                q       = query(1, N, set{1, N, 1, seq[1]});
                continue;
            }
        }
    }
    printf("%d", current);
    return 0;
}

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4095.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int m;
int f(int cur, int d, int n){
    if (n == 1) return 0;
    int cm = m, k, kk, rr;
    if (d == 0){
        // left
        if (m > cur) {
            cm -= cur;
            k = cm % (2 * n - 2);
            kk = (k == 0 ? 2 * n - 3: k - 1);
            if (kk < n - 1) rr = 1;
            else kk = 2 * n - 2 - kk, rr = 0;
        }else {
            k = cur - m;
            kk = k + 1;
            if (kk == 0) rr = 1;
            else rr = 0; 
        }
    }else {
        // right
        if (m > n - 1 - cur) {
            cm -= n - 1 - cur;
            k = (n - 1 + cm) % (2 * n - 2);
            kk = (k == 0 ? 2 * n - 3: k - 1);
            if (kk < n - 1) rr = 1;
            else kk = 2 * n - 2 - kk, rr = 0;
        }else {
            k = cur + m;
            kk = k - 1;
            if (kk == n - 1) rr = 0;
            else rr = 1; 
        }
    }

    if (kk == 0) return 1 + f(0, 1, n - 1);
    else if (kk == n - 1) return f(n - 2, 0, n - 1);
    else {
        int res;
        if (rr == 1) 
            res = f(kk, (kk == n - 2 ? 0: 1), n - 1);    
        else 
            res = f(kk - 1, (kk == 1 ? 1: 0), n - 1);
        if (res >= kk) ++res;
        return res;
    }
}
void solve(){
    int n = read();
    m = read();
    printf("%d\n", f(0, 1, n) + 1);
}
int main(){
    solve();
    return 0;
}