130 条题解
-
0
gamejifan LV 7 @ 2007-11-04 11:15:58
这题的叙述，让我误会了一年多。tzkq……3q..要早知道是这种意思早就ac了这题。。显然没什么大意思，看过组合数学或者学过群论的都懂。。ms跟polya计数法那个循环的意思。。
写的时候竟然因为交换的时候写错一个字母wa。我汗。
-
0
Alexandria LV 3 @ 2007-11-01 13:33:16
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms好强大的题啊，不看题解还真不会！
-
0
clfhaha1234 LV 3 @ 2007-10-30 18:09:04
请问什么是置换群啊？可以讲讲吗？………………
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms什么是置换群？不知道。。。照样过。。。。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
southstarj1 LV 3 @ 2007-10-02 18:50:54
思想：
置换群。（相关知识自己查）
对于一组数据，按各人的意愿排出一个序列，
如果无法排出，就输出-1。
再将环状序列变成链状，则这个目标序列为一个置换群，
与原序列（按1到n的一列）满足：
交换的最少人数等于目标序列与原序列不重合的人数。
因为总共有2n个目标序列（正反各n种），都算一遍就行了。步骤：
1. 读入数据；
2. 构造一个目标序列；
3. 统计该序列中元素位置与该元素在原序列位置的差值（同一方向）为i{i ∈ [0, n)}的元素个数；
4. 将该序列的反序统计一遍；
5. 从这些数据中选取一个最大的值max；
6. 输出n - max；注意：
构造目标序列时判断能否构造的条件；
统计一次差值的复杂度是O(n)；
统计差值的目的是求与原序列最多的重合人数； -
0
the_melody LV 3 @ 2007-09-03 17:58:28
Accepted 有效得分：100 有效耗时：0ms
好经典的题奥 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msHOHO~~~看讨论的时候看到有人提到‘置换群’这个东西，突然想起来我刚买的一本组合数学上有这么一块东西，就拿过来看了。。。。
然后就出现上面的东西了。。。。置换群，本来想求轮换的，发现轮换比较多，还是找不参与交换的比较好记。。。。优化的方法。。。我看了下好象不只一个人讲过了。。。而且似乎我跟他们的都一样（没仔细看）所以就不说了。。。效率是O(n)的。。不用建环。
-
0
maomingming LV 3 @ 2006-11-06 18:40:15
考虑旋转后最多可能重合的情况，另要注意圈可以反过来
-
0
BambooLeaf LV 3 @ 2006-09-26 18:17:26
见过的最牛最简单的方法……
将此题转换为冒泡排序，记录下所有交换的次数和两数间的距离，加上就行了……—__—|||
具体是这样的，我们反向思维，本来是要求一个有序数列求出成为无序数列的代价，现在我们把无序数列（即目标数列）进行冒泡排序，然后……就是这样……
看完之后，偶巨汗……
gamejifan
LV 7
@ 2007-11-04 11:15:58
