#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

/*
 *
 * 典型的约瑟夫问题
 * 约瑟夫问题是个有名的问题：N 个人围成一圈，从第一个开
 * 始报数，第 M 个将被杀掉，最后剩下一个，其余人都将被杀掉。
 * 例如 N=6，M=5，被杀掉的人的序号为 5，4，6，2，3。最后剩下 1 号。
 *
 * 这里采用一个递归解题 我们按照序号从 0 开始 m-1 个人退出
 * 假定第一个数到 m-1 的人退出后，那么将从下一个人重新计数
 * 我们假定这新的一轮开始的那个人序号为 0，那么在这一轮
 * 的 m-1 个人退出。
 * 那么，反过来，如果我们知道了第 i+1 轮退出的人在 i 轮一定是 j，
 * 我们可以通过 (j+m)%n 得知其在上一轮的位置
 *
 * @author: aisensiy(https://weibo.com/alistapart)
 */
int jos(int n, int m) {
    if(n==1) return 0;
    else return (jos(n-1, m) + m) % n;
}
int main()
{
    int n, m;
    cin>>n>>m;
    cout<<jos(n, m)<<endl;
    return 0;
}
[/code]

然后 poj 1012 是约瑟夫问题的一个变种，题目在这里[poj 1012](https://poj.org/problem?id=1012)

[code lang="cpp"]
#include <iostream>
#include <vector>
#include <cstring>
/*
 * https://poj.org/problem?id=1012
 *
 * 约瑟夫问题的变种，采用完全的模拟会超时
 * 这里用到的一些技巧在下面的注释中会解答
 * 感谢 mabaochang 同学让我明白了本题最核心
 * 的 trick.
 *
 * @author: aisensiy(https://weibo.com/alistapart)
 */
using namespace std;

int result[14];
int killed[14];
int next(int cur, int n) {
    while(1) {
        cur = (cur + 1) % n;
        if(!killed[cur]) {
            return cur;
        }
    }
}
bool work(int n, int m) {
    memset(killed, 0, sizeof(killed));
    int cur = 0, dead = 0;
    int count = n;
    while(1) {
        // 这里差不多就是最核心的 trick 了正常的约瑟夫问题这样的方式是不
        // 能获取正确的 killed 的人的位置的，但是由于本题要求是后 k 个人
        // 先被 killed，那么前 k 个人的位置是不应该被移动的（一旦移动了则说
        // 明这时的 m 不满足条件，会 break），并且只要满足每次 killed 人在 k 之
        // 后就行了，也不需要知道更具体的位置，采用这个公式就可以达到目的了
        cur = (cur + m - 1) % count;
        if(cur < n/2 && dead < n/2) return false;
        if(dead >= n/2) {
            return true;
        }
        killed[cur] = 1;
        dead++;
        count--;
    }
}
int main() {
    int j;
    // 由于一共只有这么十几个数据，那么为了避免在线的重复计算
    // 直接把所有结果算出来放到数组里就行了
    for(int i=1; i<=14; i++) {
        for(j=i+1; 1; j++)
            if(work(2 * i, j)) break;
        result[i-1] = j;
    }

    cin>>j;
    while(j) {
        cout<<result[j-1]<<endl;
        cin>>j;
    }
    return 0;
}

void (function() {
	var minWidth = parseInt(prompt("请输入最小宽度，默认为 200"), 10) || 200;
	var minHeight = parseInt(prompt("请输入最小高度，默认为 200"), 10) || 200;
	var imgs = [];
	var common = minWidth;

	function format(str, param) {
		return str.replace(/#{(\w+)}/gi, function(all, one) {
			return param[one.toLowerCase()];
		});
	}

	var tmp = Array.prototype.slice
			  .call(document.getElementsByTagName("img"));
	var inputs = document.getElementsByTagName('input');
	for(var i = 0, n = inputs.length; i < n; i++) {
		if(inputs[i].getAttribute('type') &&
		   inputs[i].getAttribute('type').toLowerCase() == 'image')
			tmp.push(inputs[i]);
	}

	for(var i = 0, n = tmp.length; i < n; i++) {
		if(tmp[i].tagName.toLowerCase() == 'input'
		   && (!tmp[i].getAttribute('type') ||
		   tmp[i].getAttribute('type')
		   && tmp[i].getAttribute('type') != 'image'))
			break;
		var src    = tmp[i].getAttribute('src'),
			box    = tmp[i].getBoundingClientRect(),
			width  = tmp[i].getAttribute('width') ||
					 (box.width || box.right - box.left),
			height = tmp[i].getAttribute('height') ||
					 (box.height || box.bottom - box.top);
		if(src && (src.indexOf('.jpg') || src.indexOf('.png'))
		   && width >= minWidth && height >= minHeight) {

			tmp[i].setAttribute('data-src', src);
			tmp[i].setAttribute('data-height', height);
			tmp[i].setAttribute('data-width', width);
			imgs.push(tmp[i]);
		}
	}
	var container = '';
	for(var i = 0, n = imgs.length; i < n; i++) {
		container += format('<img src="#{src}"  />', {
			'src'    : imgs[i].getAttribute('data-src'),
			'height' : imgs[i].getAttribute('data-height') * common /
					   imgs[i].getAttribute('data-width'),
			'width'  : common
		});
	}
	if(/firefox/i.test(navigator.userAgent))
		window.open('javascript: \'' + container + '\'');
	else
		document.write(container);
})();

#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <cstring>
/*
 * 题目: A Plug for UNIX | POJ 1087
 * http://poj.org/problem?id=1087
 *
 * 核心是最大流算法
 * 不过我倒是觉得更重要的是如何构造这个图
 *
 * @author: aisensiy(http://weibo.com/alistapart)
 */
using namespace std;

#define LIM 600
#define INF 100000

int graph[LIM][LIM]; 		//二维数组的图结构
int q[LIM];					//广度遍历所有需要的队列
int front, rear;			//队列的头尾
int r[LIM][LIM];			//残留网络

int pre[LIM];				//追朔广度遍历结果的前驱数组

map<string, int> id;		//用于生成字符串映射正数

int n, m, k;
int order = 2;				//初始 ID
int s = 0, t = 1;

/**
 * <h2>关于构建最大流的图</h2>
 * 在算法导论里面有讲，这种多源点多汇点的网络问题，都可以
 * 为其添加一个超级源点与超级汇点来解决。
 * 那么如何构建这个图使之转化为通解的最大流问题就成了这个
 * 题的重点。
 *
 * 首先按照题意可知，设备算是源点，而插口算是汇点。
 * 那么需要在设备之前添加超级源点 s，在插口之后添加超级汇点
 * t。
 *
 * 由于插口的数量是有限的，那么插口到超级汇点的容量 c(u, t) 应
 * 当等于插口的个数，counter(u) = 1。
 * 这个个数我们可以在输入的时候计算出来。
 * 超级源点与设备之间的容量 c(s, v) 可以为构建这种方法的默认值 INF。
 *
 * <h2>关于如何把字符串转换成图中的节点</h2>
 * 这是我一开始很头疼的事情。
 * 在网上找了一些这道题的解析，受益匪浅。
 * http://blog.csdn.net/ChinaCzy/article/details/5713749
 * 这个我觉得非常不错。
 * 作者用一个 map<string, int>为输入的字符串指定一个 id 就像是数据库里面
 * 设定为自增的主键一样。非常不错的想法。
 */

void create_graph() {
	int i;
	memset(graph, 0, sizeof(graph));
	string plug, device, adaptor;

	cin>>n;
	for(i=0; i<n; i++) {
		cin>>plug;
		id[plug] = order++;
		graph[id[plug]][t] = 1;
	}

	cin>>m;
	for(i=0; i<m; i++) {
		cin>>device>>plug;
		if(!id[plug]) id[plug] = order++;
		id[device] = order++;
		graph[s][id[device]] = INF;
		graph[id[device]][id[plug]] = 1;
	}

	// 建立适配器插口与接口的关系，由于适配器是无限多的
	// 设定 capacity = INF
	cin>>k;
	for(i=0; i<k; i++) {
		cin>>adaptor>>plug;
		if(!id[adaptor]) id[adaptor] = order++;
		if(!id[plug]) id[plug] = order++;

		graph[id[adaptor]][id[plug]] = INF;
	}

	memcpy(r, graph, sizeof(graph));
}

// 广度遍历
bool bfs(int s, int t, int n) {
	int front = rear = 0;
	int u, v;
	memset(pre, -1, sizeof(pre));
	q[rear++] = s;
	while(rear > front) {
		u = q[front++];
		for(v=0; v<n; v++) {
			if(pre[v] == -1 && r[u][v] > 0) {
				pre[v] = u;
				q[rear++] = v;
				if(v == t) return true;
			}
		}
	}
	return false;
}

// 最大流算法
int max_flow(int s, int t, int n) {
	int max = 0, inc, u, v;

	while(true) {
		if(!bfs(s, t, n)) break;

		inc = INF;
		for(v=t; v!=s; v=u) {
			u = pre[v];
			if(r[u][v] < inc) inc = r[u][v];
		}
		for(v=t; v!=s; v=u) {
			u = pre[v];
			r[u][v] -= inc;
			r[v][u] += inc;
		}
		max += inc;
	}

	return max;
}

int main() {
	create_graph();
	int max = max_flow(s, t, order);
	cout<<m - max<<endl;
}