2019-08-15

lightoj 1179 Josephus Problem hdu 3089 Josephus again 约瑟夫环各种姿势

缘起

约瑟夫环是重要的一类问题, 遂找题目来搞. lightoj 1179 Josephus Problem 和 hdu 3089 Josephus again

这两道题目处理的都是经典的约瑟夫环, 并不涉及约瑟夫环的各种变体.

分析

lightoj 1179 Josephus Problem

题意很裸

历史学家弗拉维乌斯·约瑟夫斯（Flavius Josephus）讲述了在公元67年的罗马 - 犹太人冲突中罗马人如何占领他指挥的
Jotapata镇。逃跑时，约瑟夫斯发现自己被困在一个有40个同伴的洞穴里。罗马人发现了他的行踪，并邀请他投降，但他的
同伴拒绝允许他这样做。因此他建议他们一个接一个地杀死对方，这个命令由抽签决定。传统认为影响这个地段的手段是站成一个圆圈，并且从某个点开始计算，每三个人轮流被杀。这个过程的唯一幸存者是约瑟夫斯，后来他向罗马人投降。这
引出了一个问题：如果约瑟夫斯先前在一个黑暗的角落里安静地练习了41块石头，或者他数学上计算过他应该采用第31个位置才能生存？

现在你处于类似的情况。有n个人围成一圈。这些人的编号从1到n循环。例如，1和n相邻，1和2也相邻。伯爵从第一个人开
始。每次你数到k并且第k个人被杀死并从圆圈中移除。然后计数从下一个人开始。最后还有一个人。给定n和k，你必须找到最后一个活着的人的位置。

【输入】
输入以整数T（≤200）开头，表示测试用例的数量。
每种情况包含两个正整数n（1≤n≤10^5）和k（1≤k<2^31）

【输出】
对于每种情况，打印案例编号和最后剩余人员的位置。

【样例输入】
6
2 1
2 2
3 1
3 2
3 3
4 6

【样例输出】
Case 1: 2
Case 2: 1
Case 3: 3
Case 4: 3
Case 5: 2
Case 6: 3

【限制】
Time limit 2000 ms
Memory limit 32768 kB

hdu 3089 Josephus again

在我们的Jesephus游戏中，我们从围绕一个圆圈编号为1到n的n个人开始，并且我们消除了每个k剩余的人，直到只有一个幸
存。 例如，这里是n = 10，k = 2的起始配置，消除顺序是2,4,6,8,10,3,7,1,9。所以5幸存。问题：确定幸存者的编号J（n，k）。

【输入】
有多种情况，以EOF结束， 每种情况都有两个整数，n，k。 （1 <= n <= 10^12,1 <= k <= 1000）

【输出】
每行输出 J(n, k)

【样例输入】
10 2
10 3

【样例输出】
5
4

【限制】
Time limit 1000 ms
Memory limit 32768 kB

约瑟夫环有

dp
队列
链表
线段树
数组

5姿势，但是对于n超大的题目, 链表和数组不适用（内存会爆）.

数组和链表

数组和链表其实就是模拟，不展示了，为什么呢? 因为只能一步一步的模拟（而不能快速计算，因为数组和链表经过若干次都会有”洞”, 所以不能快速计算的），每步的复杂度是O(k)，则算法的复杂度就是 O(N*K), 对于上面的题目显然都是会T掉的. 而且，链表比数组直观的多. 使用链表模拟推荐使用stl的 list （#include ，他是stl中的双向循环链表, 这样代码写起来会简短很多）

队列

队列模拟是一个比较有意思的算法. 而且写起来比数组和链表更短.

想法就是使用stl queue, 伊始是将1,…,n全部进队, 然后搞一个计数器i,i从1开始计数, 每次将队首出队，然后看i到没到k, 如果到了的话，则出去的队首就是此次要被kill的，则队首不必再次进队（计数器归1），如果没到，则出去的队首再次进队，计数器+1.

虽然精妙，但是依旧基于模拟，所以复杂度依旧是O(nk) 居高不下~ 肯定吃T

dp

我们同样将问题简化为:n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求最后的幸存者编号(最后加1就得到原问题的答案)
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为m%n=m的人开始）:m m+1 m+2 … n-2, n-1, 0, 1, 2, … m-2并且从m开始报0。现在我们把他们的编号做一下转换：
m–> 0, m+1–> 1, m+2–> 2,…,m-2–> n-2
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是这个子问题的最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是最初n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x’=(x+m)%n,则x’是原问题最终胜利者(当然,为了得到1~n这个原问题的解,必须再加1)
所以dp公式是 f[1]=0;f[i]=(f[i-1]+m)%i; (2<=i<=n),最后1~n的原问题的答案就是f[n]+1

//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int n,k;

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	for(int tt = 1; tt<=t;tt++)
	{
		scanf("%d%d", &n,&k);
		int x = 0;
		for (int i = 2; i<=n;i++) x = (x+k)%i;
		printf("Case %d: %d\n", tt, ++x);
	}
	return 0;
}

lightoj ac情况

Status	Accepted
Time	62ms
Memory	1156kB
Length	347
Lang	C++
Submitted	2019-08-15 09:39:11
Shared
RemoteRunId	1553814

但是类似的代码提交hdu的题目就T了. 原因无外乎就是n太大了——1万亿!!! 下面的代码提交 hdu，则

//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

typedef long long LL;

LL n,k;

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%lld%lld", &n, &k))
	{
		LL x = 0;
		for (LL i = 1; i<=n;i++) x = (x+k)%i;
		printf("%lld\n", ++x);
	}
	return 0;
}

结果是 Time Limit Exceeded. 需要优化

1	for (LL i = 1; i<=n;i++) x = (x+k)%i;

这个递推式子——需要减少for循环的次数——很直观的，如果i很大的话，因为k固定，其实就是x+=k. 模掉i其实起不到任何作用. 这就是优化的契机，如果i很大的话, 则i以1为步长增长，而x以k为步长增长, 假设增长a步, 如果

1
2
3

x+a*k<i+a的话，即a*(k-1)<i-x （注意, k=1恒成立, 因为i>x总是成立——x是余数嘛~）
则x可以一口气加a*k,i可以一口气加a, 而不需要一次一次的+k,这样就有效降低了循环的次数. 这是约瑟夫环问题dp的一种加速
a<(i-x)/(k-1)

下面给出hdu的ac代码

//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

typedef long long LL;

LL n,k;

#define MIN(a,b) ((a)<(b)?(a):(b))

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%lld%lld", &n, &k))
	{
		LL x = 0,a;
		for (LL i = 2; i<=n;)
		{
			a = (i-x)%k?(i-x)/k:(i-x)/k-1; // x+a*k<i
			if (!a) // 如果要取余
			{
				x = (x+k)%i; // 那就取余吧~ 这就是上述被T掉的代码的dp步骤
				++i;
			}
			else // 如果可以加速
			{
				if (a<n-i) // 也要看是不是到底了(因为i最多到n)
				{
					x+=a*k; // 放开来加速,别担心!
				}
				else
				{
					x+=(n-i+1)*k; // 加到底了
					break;
				}
				if (i==n) break;
				i+=MIN(a, n-i); // 别忘了 i<=n, 所以不能加的超过n-i
			}
		}
		printf("%lld\n", ++x);
	}
	return 0;
}

ac情况

30283841	2019-08-15 12:26:13	Accepted	3089	78MS	1208K	612 B	G++	yfsyfsyfs

真快~ 哪怕 1e12 这种n, 答案也是秒出. 但是理解了上面的算法不难知道——k越小，则加速效果（即跳步）越明显. 我试过 n=1e12, k=3 这种，答案是秒出的，但是如果k很大（例如接近n），则加速效果不明显.

线段树

复杂度是O(NlogN), 不消说，肯定不能用来做hdu，只能用来做lightoj,

算导上有这样一道题，假设n个人站成环形，且有一个正整数m<=n。从某个指定的人开始，沿环报数，每遇到第m个人就让其出列，且报数继续进行下去。执行这一过程，直到所有人出列。每个人出列的次序定义为整数1，2，3，…，n的（n，m）-Josephus排列。
例如，（7，3）-Josephus排列为（3，6，2，7，5，1，4）。设计一个算法，时间复杂度要求O（nlogn）时间，使给定的整数n和m，输出（n，m）-Josephus排列。
对于约瑟夫环问题，如果是求最后一个出列的人，有O（n）的算法上面已经给出了O(n)算法以及它的吊炸天优化.

但是现在是要输出序列，则O(n)算法失效——它只能快速知道最后幸存的人. 但是这里如果我们用循环链表来模拟的话，很明显时间复杂度是O（n*m）的，既然算导说有O（nlogn）的算法那就肯定有啦，答案是线段树。

首先给出[1,n]的线段树.并且每个节点记录了这个区间的左右端点以及这个区间上还剩下的人数. 下面考虑删除一个人,那么期间我们一直维护一个相对位置(所谓相对位置指的是相对现在的人数的位置).然后根据这个相对位置求出绝对位置

下面是lightoj的ac代码

//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL
const int maxn = 1e5+5;
int n,k;

struct SegTreeNode // (点)线段树
{
	int l,r,res; // [l,r]区间上剩下res个人
}segTree[maxn<<2]; // 0索引不用存储数据，数组而不是链表加快速度

void build(int l, int r, int root) // 递归建立以root为根的线段树
{
	segTree[root].l = l;
	segTree[root].r = r;
	segTree[root].res = r-l+1;
	if (l==r) return;
	int mid = ((l+r)>>1);
	build(l, mid, root<<1);
	build(mid+1, r, root<<1|1);
}

int calc(int xiangdui, int i) // 计算xiangdui对应的绝对位置
{
	segTree[i].res--; // [l,r]上被kill掉了一个人
	if (segTree[i].l == segTree[i].r) // 如果当前节点已经是单点节点的话
	{
		return segTree[i].l;
	}
	if (xiangdui <= segTree[i<<1].res)
	{
		return calc(xiangdui, i<<1); // 跳左孩子
	}
	return calc(xiangdui-segTree[i<<1].res, i<<1|1); // 跳右孩子
}

int main() 
{

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	for (int i = 1; i<=t; i++)
	{
		scanf("%d%d", &n, &k);
		build(1,n,1); // 建树
		int xiangdui =1;
		while(n--) // 每次kill掉一个人, kill n人
		{
			xiangdui = (xiangdui+k-1)%segTree[1].res;
			if (!xiangdui) xiangdui = segTree[1].res;
			int ans = calc(xiangdui, 1); // kill 掉一个人, 返回的ans是绝对位置
			if (!n) // n为0的时候, 才打印绝对位置(否则的话, 就仅仅是计算而已)
			{
				printf("Case %d: %d\n", i, ans); // 计算绝对位置
			}
		}
	}
	return 0;
}

ac情况

Status	Accepted
Time	1016ms
Memory	5844kB
Length	1196
Lang	C++
Submitted	2019-08-15 14:00:55
Shared
RemoteRunId	1554085