题目描述约瑟夫问题是一个经典问题nnn个人编号为1,2,…,n1, 2, \dots, n1,2,…,n站成一圈每数到第mmm个人就将其处决直到只剩最后一个人。约瑟夫聪明地选择了自己的位置使自己成为最后幸存的人。本题是约瑟夫问题的一个变种。假设有kkk个好人和kkk个坏人。在圆圈中前kkk个位置是好人编号1∼k1 \sim k1∼k后kkk个位置是坏人编号k1∼2kk1 \sim 2kk1∼2k。需要找到一个最小的mmm使得在处决过程中所有坏人都在第一个好人被处决之前被处决。输入格式输入文件包含多行每行一个整数kkk0k140 k 140k14。最后一行是0表示输入结束。输出格式对于每个kkk输出一行包含对应的最小mmm。样例输入3 4 0样例输出5 30样例解释当k3k 3k3时m5m 5m5总人数n6n 6n6处决顺序为5,4,6,2,3,15, 4, 6, 2, 3, 15,4,6,2,3,1。前三个处决的都是坏人5,4,65, 4, 65,4,6然后才处决好人。当k4k 4k4时m30m 30m30总人数n8n 8n8可以验证前444个被处决的都是坏人。题目分析问题的本质这是一个约瑟夫问题的变种核心约束是前kkk个位置是好人后kkk个位置是坏人需要mmm使得在处决过程中前kkk个被处决的人全部是坏人注意并不是要求坏人先全部被处决再处决好人那样顺序就不对了而是要求第一个被处决的好人出现在第k1k1k1次或更晚。换句话说前kkk次处决必须全部是坏人。与经典约瑟夫问题的联系经典约瑟夫问题中给定nnn和mmm处决顺序是确定的。我们可以模拟这个过程检查是否满足“前kkk次处决都是坏人”的条件。直接枚举的可行性k14k 14k14因此n2k≤26n 2k \leq 26n2k≤26。理论上mmm可能很大但我们可以从mk1m k1mk1开始逐个尝试。然而直接暴力枚举mmm可能较慢因为mmm的上界未知。关键观察如果mmm是解那么m mod (2k)m \bmod (2k)mmod(2k)可能有一定的规律实际上mmm可能大到几千甚至几万如k13k 13k13时m137496m 137496m137496优化策略步长优化不需要逐个测试每个mmm可以按kkk的倍数跳跃模拟优化使用公式计算下一个被处决的位置而不是真的删除元素缓存结果由于输入可能包含重复的kkk预先计算并缓存解题思路步骤一问题重述设总人数n2kn 2kn2k好人位置为0∼k−10 \sim k-10∼k−1改用000-based 索引方便取模运算坏人位置为k∼2k−1k \sim 2k-1k∼2k−1。我们需要找到最小的mmm使得在约瑟夫过程中前kkk次选中的位置全部≥k\geq k≥k即都是坏人。步骤二约瑟夫过程的模拟使用000-based 索引约瑟夫过程可以如下模拟intn2*k;intindex0;// 当前起始位置for(inti0;ik;i){index(indexm-1)%n;// 下一个被处决的位置if(indexk){// 如果选中的是好人returnfalse;// 条件不满足}// 移除该位置n 减 1// 注意移除后下一个位置应该是当前 index因为后面的元素前移indexindex%(n-1);// 调整位置n--;}returntrue;步骤三枚举范围的确定最小的mmm至少是k1k1k1因为如果m≤km \leq km≤k则第一次处决的位置是(m−1) mod (2k)(m-1) \bmod (2k)(m−1)mod(2k)这可能落在好人区间内。更严格的观察设n2kn 2kn2k第一次处决的位置是(m−1) mod n(m-1) \bmod n(m−1)modn要求这个位置≥k\geq k≥k即(m−1) mod n∈[k,n−1](m-1) \bmod n \in [k, n-1](m−1)modn∈[k,n−1]这等价于m mod n∈[k1,n]m \bmod n \in [k1, n]mmodn∈[k1,n]但实际枚举时可以从mk1m k1mk1开始按步长kkk或111递增。步骤四步长优化注意到如果mmm是一个解那么mnm nmn也可能是一个解不一定因为移除元素后nnn在变化。但有一个重要的观察如果mmm除以nnn的余数相同第一次处决的位置相同。因此我们可以只检查mmm在某个范围内的值。实际上可以通过以下方式跳跃设stepkstep kstepk或step1step 1step1但更高效的实现是枚举mmm时只考虑那些使第一次处决位置落在坏人区间内的mmm步骤五预处理缓存由于k14k 14k14只有131313个可能的输入值。我们可以预先计算所有kkk对应的mmm并缓存。这样对于每个查询只需O(1)O(1)O(1)时间输出。步骤六代码实现细节在实际代码中使用两层循环外层循环遍历可能的mmm从k1k1k1开始按某种步长递增内层循环模拟kkk次处决检查是否全是坏人为了加速代码中使用了一个巧妙的跳跃策略对于每个mmm尝试m,m1,…,mkm, m1, \dots, mkm,m1,…,mk范围内的值如果这个范围内没有解则mmm增加kkk继续这样做的原理是当mmm增加kkk时约瑟夫过程中所选位置的变化具有周期性。算法复杂度分析时间复杂度对于每个kkk可能需要尝试多个mmm值每个mmm的模拟需要O(k)O(k)O(k)时间由于k14k 14k14mmm的上界虽然可能达到10510^5105量级但实际枚举次数可控UVa 评测时间0.0400.0400.040秒空间复杂度使用map\texttt{map}map缓存131313个结果O(1)O(1)O(1)正确性证明引理 1如果mmm是一个解那么m mod (2k)m \bmod (2k)mmod(2k)一定在[k1,2k][k1, 2k][k1,2k]范围内。证明第一次处决的位置是(m−1) mod (2k)(m-1) \bmod (2k)(m−1)mod(2k)它必须≥k\geq k≥k因此(m−1) mod (2k)∈[k,2k−1](m-1) \bmod (2k) \in [k, 2k-1](m−1)mod(2k)∈[k,2k−1]即m mod (2k)∈[k1,2k]m \bmod (2k) \in [k1, 2k]mmod(2k)∈[k1,2k]。□\square□引理 2对于固定的kkk解一定存在。证明考虑m2km 2km2k第一次处决的位置是(2k−1) mod (2k)2k−1(2k-1) \bmod (2k) 2k-1(2k−1)mod(2k)2k−1是坏人。但后续过程不一定满足。实际上当mmm足够大时处决顺序会变化。可以证明解一定存在但具体数值需要计算。□\square□引理 3代码中的跳跃策略每次增加kkk不会遗漏解。证明如果mmm是一个解那么mkm kmk是否一定是解不一定。但代码中在每个mmm值处检查了mmm到mkmkmk范围内的所有值因此不会遗漏任何解。□\square□参考代码// Joseph// UVa ID: 305// Verdict: Accepted// Submission Date: 2016-06-26// UVa Run Time: 0.040s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);// 缓存已经计算过的结果避免重复计算mapint,intcache;intk;while(cink,k){// 如果已经计算过直接输出缓存结果if(cache.find(k)!cache.end()){coutcache[k]endl;continue;}intstartk;// 起始搜索位置while(true){boolanswerIsHerefalse;// 在 [start1, startk] 范围内检查每个 mfor(intistart1;istartk;i){intn2*k;// 当前剩余人数intcounter0;// 已处决的坏人数量intindex0;// 当前起始位置// 模拟 k 次处决while(counterk){// 计算下一个被处决的位置0-basedindex(indexi-1)%n;// 如果被处决的是好人位置 k条件不满足if(indexk)break;counter;// 处决了一个坏人// 移除该位置调整 index 和 n// 如果 index 是最后一个则下一个位置是 0indexindex(n-1)?index:0;n--;// 人数减少 1}// 如果成功处决了 k 个坏人if(counterk){coutiendl;cache[k]i;answerIsHeretrue;break;}}if(answerIsHere)break;// 当前范围内没有找到解增加步长继续搜索startk;}}return0;}总结本题的核心在于约瑟夫问题的模拟使用000-based 索引和取模运算条件判断检查前kkk次处决是否都是坏人搜索优化按步长kkk跳跃搜索并在每个范围内检查kkk个值结果缓存避免重复计算关键点回顾知识点说明约瑟夫问题每数到mmm的人被处决索引变换使用000-based 索引简化取模运算好人/坏人分布前kkk个是好人后kkk个是坏人条件约束前kkk次处决必须全是坏人搜索策略跳跃搜索 范围枚举缓存优化map\texttt{map}map缓存已计算结果约瑟夫问题的递推公式经典约瑟夫问题中最后幸存者的位置可以由递推公式计算J(1)0,J(n)(J(n−1)m) mod n J(1) 0, \quad J(n) (J(n-1) m) \bmod nJ(1)0,J(n)(J(n−1)m)modn但本题需要的是特定的mmm使得删除顺序满足条件因此必须模拟整个过程。
