本文主要是介绍POJ 1012 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题就是做模拟（从数据范围0<k<14可以看出来）。最naive的解法，即用一个bool数组保存每个位置是不是已经被杀了，同时m从k+1开始一个个试到了10左右就非常慢了，无法通过测试。可以通过以下两个trick的改进通过。这里尽可能解释清楚：
1.所有位置按照0，1，2，..., k, k + 1, ...编号，其中0~k-1为好人，从k开始，以后都是坏人，这些人都要杀掉。假设编号为t的人被杀掉后，那么下一个被杀的人的编号是多少？
为了效率，我们可以采用杀了一个人之后，就把这个人剔除出队的做法。（注：按照规则，这个人一定是坏人，即编号>=k，否则，我们可以跳出测试，宣布这个m不成立）。这样，就可以认为队列中后面的那个坏人替代了当前的编号，后面的所有坏人编号减一。只要新算出来的好人的编号是对的就可以了。假设这时队列中剩下left个人，那么所有的编号为0~(left - 1)，其中前面0~(k-1)的编号为好人。这时可以看出，下一个要杀的人的编号为(t + m - 1) % left。由于杀的都是坏人，并且他们之间不用区分，我们已经用后面的坏人代替了被杀的坏人，所以队列中的人都是活的，所以可以用上述公式直接跳过m-1个人即可。
2.我们可以将m从k+1开始逐一测试，但是有一个更有效的筛选条件：m%(k+1) = 0 或者 m % (k + 1) = 1，即m除以k+1的余数一定是0或者1，我们可以跳过别的数。
上面的这个结果可以在第一点的基础上分析出来。假设最后剩下了k+2个人，这时他们的编号为0, 1, ..., k - 1, k, k + 1（这时基于第一点，杀的坏人的编号都被替代了），其中k和k+1为坏人。这时只有两种情况下m能过测试：a)k先死，下次选k+1；b)k+1先死，下次选k。基于第一点分析中的下一跳公式，对于情况a)，我们有(k + m - 1) % (k + 1) = k；对于情况b)，我们有(k+1 + m - 1) % (k + 1) = k。可以看出，我们只是替换了第一点的公式中t = k 或者 t = k + 1，且剩下的人的个数left = k + 1。从情况a)的公式我们有k + m - 1 = a(k+ 1) + k，继而m = a(k + 1) + 1，其中a是一个倍数，即m除以k+1的余数是1。同理，从情况b)的公式我们可以推出，m除以k+1的余数还可以是0。
有了上述两点优化，程序就可以过所有测试点了。由于测试数据的范围很小，所以可以提前算出所有情况，也可以按需算出一个后保存结果（因为根据discuss,测试数据有重复）。
第一点改进：
| 1012 | Accepted | 216K | 219MS | C++ | 833B |
| 1012 | Accepted | 216K | 47MS | C++ | 913B |
/*
ID: thestor1
LANG: C++
TASK: poj1012
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;int main()
{int k, m;std::vector<int> joseph(14, 0);for (k = 1; k < 14; ++k){// cout << "k: " << k << endl;for (m = k + 1; ;){int cur = 0, left = 2 * k, i;for (i = 0; i < k; ++i){cur = (cur + m - 1) % left;if (cur < k){break;}left--;}if (i == k){joseph[k] = m;break;}if (m % (k + 1) == 0){m++;}else{m += k;}}}while (cin >> k && k){ cout << joseph[k] << endl;}return 0;
}
这篇关于POJ 1012 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
