首页 > 代码库 > 【HDOJ】1276 士兵队列训练问题
【HDOJ】1276 士兵队列训练问题
初看这道题目很像尤瑟夫问题, 区别是每次都是从1开始。解法也很类似。数学解递推公式。
假定第K次报数后，余下人数不超过3个人。
若第K次为1-3报数，那么由这三个数的当前索引n可推上一次报数之前的编号为n+(n-1)/2，该式也很容易理解，因为每三个人就要去掉第三个人，因此(n-1)/2可以知道已经减少了几个人，加上基础编号n就是上一次报数的编号；
若第K次为1-2报数，这个很简单，当前索引为n的数在上一次报数时编号为2n-1。
因此，县求解报数的次数，然后逆向求得余下的数字的初始值。
1 #include <cstdio> 2 #include <cstring> 3 4 int main() { 5 int t, n, m; 6 int i, j; 7 int a[4]; 8 9 scanf("%d", &t);10 while (t--) {11 scanf("%d", &n);12 m = 0;13 while (n > 3) {14 ++m;15 if (m & 1)16 n -= n/2;17 else18 n -= n/3;19 }20 for (i=1; i<=n; ++i)21 a[i] = i;22 while (m > 0) {23 if (m & 1) {24 for (i=1; i<=n; ++i)25 a[i] = 2*a[i]-1;26 } else {27 for (i=1; i<=n; ++i)28 a[i] = a[i]+(a[i]-1)/2;29 }30 --m;31 }32 printf("%d", a[1]);33 for (i=2; i<=n; ++i)34 printf(" %d", a[i]);35 printf("\n");36 }37 38 return 0;39 }
【HDOJ】1276 士兵队列训练问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。