最近开始解答网上评委的问题。我被困在SPOJ 中的这个问题 http://www.spoj.pl/problems/CODESPTC/:
下面是洗 N 张牌的算法：
- 这些牌被分成 K 个相等的牌堆，其中 K 是 N 的因数。
- 底部的 N/K 张牌按相同顺序属于第 1 堆（因此 .initial 堆的底部牌是第 1 堆的底部牌）。
- 从底部开始接下来的 N/K 张牌属于第 2 堆，依此类推。
- 现在洗完的牌堆的顶牌是第 1 堆的顶牌。下一张牌是第 2 堆的顶牌，...，洗完的牌堆的第 K 张牌是 K 堆的顶牌。那么 (K + 1) 第一张牌是现在位于第 1 堆顶部的牌，第 (K + 2) 张牌是现在位于第 2 堆顶部的牌，依此类推。
例如，如果N = 6且K = 3，则一副牌的顺序“ABCDEF”（从上到下）洗一次后将变为“ECAFDB”。
给定 N 和 K，最少需要多少次洗牌才能将堆恢复到原来的顺序？
我尝试模拟，但超出了时间限制。有数学方程式吗？
是的，这个问题有一个数学解决方案。
首先让我从一些关于如何解决此类问题的提示开始，然后我将给出一些关于实际解决方案的提示。我不会完全完成它，因此仍然存在一些挑战。
So: how to approach such problems? What you did is actually a good start. Write a simulation and run it against some small cases. The simulation should be fairly fast there. Now you have some more values. Write them down on a piece of paper and start staring at them. You have fro instance if K = x1 and N = y1 then the result is z1 and a lot more such pairs. Try to figure some formula. Focus on triples that have a fixed value for x, for y or for z. What do they have in common? And so on. You stare and usually you get a bright idea after some time :)
现在：关于这个特定问题的一些提示。进行一次洗牌迭代并记下每张牌的去向。例如，卡 1 位于位置 3，卡 3 位于位置 2，依此类推。请注意，某些链将以这种方式形成 - 例如在示例中 n=6，k=3，我们有一个长度为 6 的链： 1->3->2->6->4->5->1 。现在计算所有链的长度（每张卡都属于一个链）并尝试找出答案如何取决于这些长度。
希望这足以帮助您解决问题。
编辑：看看模拟单次迭代的约束可能会非常慢。如果是这种情况，在完成我在第二个技巧中建议的操作后，尝试计算链的长度，而无需实际模拟一次洗牌
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
