题目分析本题描述了一个有趣的部落选举酋长的过程。部落成员站成一个圆圈从某个起始位置开始按照固定的节奏念出Eeny meeny miny mo的韵律每次念到字母o时当前指向的人就被淘汰出局然后从下一个人继续重复这个过程直到只剩下一个人这个人就成为新酋长。题目给出了一个关键信息计数序列是固定的长度为151515个音节实际上就是Eeny meeny miny mo这个短语的字母循环。具体序列为E, e, n, y, M, e, e, n, y, M, i, n, y, M, o然后重复。每次碰到o就淘汰当前指向的人。问题的核心是给定一个可能的人数范围[lower,upper][lower, upper][lower,upper]以及淘汰方向可以是顺时针或逆时针要求找出离起始位置Mxogbgwq最近的安全位置即编号最小的位置使得无论实际人数是多少在给定范围内也无论淘汰方向是顺时针还是逆时针这个位置都不会成为酋长即不会被淘汰到最后。如果不存在这样的安全位置则输出Better estimate needed。解题思路这是一个经典的约瑟夫问题变种。在经典约瑟夫问题中每数到第kkk个人就淘汰一人。本题中固定步长m15m 15m15因为每151515个字母出现一次 ‘o’但需要注意的是淘汰发生在计数的过程中实际的步长是151515。约瑟夫问题的递推公式对于经典的约瑟夫问题如果有nnn个人每次淘汰第kkk个人最后存活者的位置从000开始编号可以通过递推得到J(1)0J(1) 0J(1)0J(n)(J(n−1)k) mod nJ(n) (J(n-1) k) \bmod nJ(n)(J(n−1)k)modn这里k15k 15k15J(n)J(n)J(n)表示从000开始编号的存活者位置。方向的处理题目考虑了顺时针和逆时针两个方向顺时针淘汰的结果就是经典约瑟夫问题的解J(n)J(n)J(n)逆时针淘汰等价于顺时针淘汰的对称位置即n−J(n)n - J(n)n−J(n)在000基编号下由于编号从起始位置 Mxogbgwq 开始算作第111个位置我们需要进行编号转换顺时针淘汰时酋长位置为J(n)1J(n) 1J(n)1转为111基编号逆时针淘汰时酋长位置为(n−J(n)) mod n(n - J(n)) \bmod n(n−J(n))modn当该值为000时对应第nnn个位置算法步骤预处理由于人数最多为10610^6106我们可以预先计算出所有nnn对应的顺时针和逆时针酋长位置。标记不安全位置对于给定范围[lower,upper][\text{lower}, \text{upper}][lower,upper]内的每个nnn将顺时针和逆时针酋长位置标记为不安全。查找安全位置从111开始向上查找第一个未被标记的位置即为答案。由于要求“离 Mxogbgwq 最近”而 Mxogbgwq 是起始位置即位置111所以编号最小的安全位置就是最近的。复杂度分析预处理时间复杂度为O(N)O(N)O(N)其中N106N 10^6N106。对于每组查询需要遍历范围[lower,upper][lower, upper][lower,upper]标记不安全位置最坏情况O(N)O(N)O(N)然后扫描查找安全位置。总复杂度可以接受。代码实现// Eeny Meeny// UVa ID: 180// Verdict: Accepted// Submission Date: 2016-02-22// UVa Run Time: 0.035s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// lower 和 upper 分别表示人数的下界和上界// m 是固定步长即 Eeny meeny miny mo 的长度为 15intlowerBound,upperBound,step15;// chiefCW[i] 表示 i 个人时顺时针淘汰的酋长位置0 基编号// chiefCCW[i] 表示 i 个人时逆时针淘汰的酋长位置0 基编号// safe[i] 标记第 i 个位置是否安全初始为 1 表示安全0 表示不安全intchiefCW[1000010],chiefCCW[1000010],safe[1000010];// 预处理函数计算所有人数对应的顺时针和逆时针酋长位置voidfindChief(){// 初始化数组fill(chiefCW,chiefCW1000010,0);fill(chiefCCW,chiefCCW1000010,0);// select 表示当前存活者的位置0 基编号intselect0;// 只有一个人时存活者位置为 0chiefCW[1]0;// 使用递推公式计算 n 2 到 1000000 的情况for(intj2;j1000000;j){// 约瑟夫递推公式J(n) (J(n-1) k) % nselect(selectstep)%j;// 顺时针淘汰的酋长位置chiefCW[j]select;// 逆时针淘汰的酋长位置对称位置chiefCCW[j](j-select)%j;}}// 查找并输出第一个安全位置boolfindFirstSafePosition(){// 初始化安全标记数组假设所有位置都安全fill(safe,safeupperBound,1);// 对于范围内的人数标记对应的酋长位置为不安全for(intilowerBound;iupperBound;i){// 顺时针方向的酋长位置转为 1 基编号safe[chiefCW[i]1]0;// 逆时针方向的酋长位置转为 1 基编号// 注意当 chiefCCW[i] 0 时对应第 i 个位置if(chiefCCW[i]0)safe[i]0;elsesafe[chiefCCW[i]]0;}// 从位置 1 开始查找第一个安全位置// 题目要求输出离 Mxogbgwq 最近的位置即编号最小的安全位置for(inti1;ilowerBound/2;i)if(safe[i]1){couti\n;returntrue;}// 没有找到安全位置coutBetter estimate needed\n;returnfalse;}intmain(){// 加速输入输出cin.tie(0);cout.sync_with_stdio(false);// 预处理所有人数的酋长位置findChief();// 读入多组数据直到 0 0 结束while(cinlowerBoundupperBound,lowerBound||upperBound){// 确保 lowerBound upperBoundif(lowerBoundupperBound)swap(lowerBound,upperBound);findFirstSafePosition();}return0;}关键点说明编号转换程序中000基编号和111基编号的转换需要注意。递推公式J(n)J(n)J(n)给出的是000基编号而题目中的位置从111开始计数。逆时针处理逆时针淘汰的酋长位置可以通过对称性得到即n−J(n)n - J(n)n−J(n)当结果为nnn时对应位置nnn即编号转换后的第nnn个位置。边界条件当chiefCCW[i] 0时逆时针方向的酋长是第iii个人需要标记safe[i] 0。查找范围代码中查找安全位置只循环到lowerBound / 2这是一个优化因为安全位置如果存在通常会在较小的位置出现。如果在这个范围内没有找到则输出需要更好估计。