栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 2731 Yet Another Josephus...

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 2731 Yet Another Josephus...

#include <stdio.h>#include <cstring>#define maxl 2010int n, m, p, out[maxl], c[maxl];int list[maxl], top;int get_survive(int n, int m){int ans = 0;for(int i=1; i<=n; ++i) ans = (ans + m) % i;return ans;}int get_kth(int k){if(m == 1) return k;int D = m * k;while(D > n){D = (D - n - 1) / (m - 1) + D - n;}return D;}int mod(int x, int m){return (x % m + m) % m;}int lowbit(int x){ return x & -x; }void add(int idx, int x){for(idx++; idx<maxl; idx+=lowbit(idx)) c[idx] += x;}int Sum(int idx){int ans = 0;for(idx++; idx; idx-=lowbit(idx)) ans += c[idx];return ans;}int getSum(int a, int b){if(a > b) return 0;else return Sum(b) - Sum(a - 1);}int getValue(int x){int l = 1, r = n, mid, ans = -1;while(l <= r){mid = (l + r) / 2;int k = Sum(mid);if(k >= x){ans = mid;r = mid - 1; }else l = mid + 1;}return ans;}void solve(){for(int i=0; i<=n; ++i) out[i] = 0;memset(c, 0, sizeof c);for(int i=1; i<=n; ++i) add(i, 1);int cnt, k = 0;for(cnt=1; cnt<=n; ++cnt){int x = (k + 1 > n) ? 1 : k + 1;int lsum = getSum(1, k - 1);int rsum = getSum(k, n);int pp = (lsum + m - 1) % (lsum + rsum);k = getValue(pp + 1);add(k, -1);if(k == p) break;out[k-1] = 1;}cnt--;int left = n - cnt;top = 0;for(int i=0; i<n; ++i){int x = (p - 1 + i) % n;if(!out[x]) list[top++] = x + 1;}k = get_survive(left, m);k = mod(k - m + 1, top);int nk = mod(-k, top);printf("%dn", list[nk]);}int main(){while(scanf("%d%d%d", &n, &m, &p), (n + m + p)){int k = get_survive(n, m);if(k == p - 1) printf("%dn", p);else{solve();}}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/380132.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号