14095: 【原4095】春樱对决

题目描述

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

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 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(){