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;
}