啊呜~

一年前误解了题意~

一年后理解了题意~

然后就是1次美妙的AC

PS:[误]解[理]解~~~[物理]？

lgxcgd说的太对了！太感谢了5555

NOIP也会考高等数学...

由于原图是环，所以置换群可表示为一次循环。作差是个好方法。

但求冒泡排序是怎么作的

Flag 　　Accepted

题号 　　P1008

类型(?) 　　模拟

通过 　　1504人

提交 　　4282次

通过率 　　35%

难度 　　3

提交 讨论 题解 状态

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

纪念一下……第1500个AC……

Flag 　　 Accepted

题号 　　P1008

类型(?) 　　模拟

通过 　　1500人

提交 　　4274次

通过率 　　35%

难度 　　3

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

置换群是正解

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 338ms

├ 测试数据 05：答案正确... 322ms

├ 测试数据 06：答案正确... 306ms

├ 测试数据 07：答案正确... 338ms

├ 测试数据 08：答案正确... 338ms

├ 测试数据 09：答案正确... 322ms

├ 测试数据 10：答案正确... 306ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2270ms

算镜像时偷了点懒，不过也算一遍AC了

a：拆环成队，寻求目标队列。

b：b1,b2...bm不是连续的，而且是任意的。只要有成立目标队列，与原来的队列相匹配就可以知道有多少（设为n个）需要移动位置，则代价就是n。

c：目标队列有多种情况，可以反转，也可以左右移动。

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

当时的时间限制好像是2s。。有个题解说把1定为第一项然后进行冒泡排序。。不过这里是1s 啊。。。也行只有置换群了吧。

看不懂，只好搁浅

什么时候想清楚了再做

program p1008;

var i,n,k,j,sum1,sum2,ans,max:longint;

　　 a,b,w,d,c:array[0..50005] of longint;

begin

readln(n);

for i:=1 to n do

readln(a[i],b[i]);

w[1]:=1; w[2]:=a[w[1]];

k:=1;

repeat

inc(k);

if w[k-1]=a[w[k]] then w[k+1]:=b[w[k]]

　　else if w[k-1]=b[w[k]] then w[k+1]:=a[w[k]]

　　 else begin

　　　　　　 writeln(-1);

　　　　　　 exit;

　　　　　　 end;

until k=n;

if w[n+1]w[1] then

　　　　　　 begin

　　　　　　 writeln(-1);

　　　　　　 exit;

　　　　　　 end;

for i:=1 to n do

begin

a[i]:=w[i]-i;

b[i]:=w[n-i+1]-i;

if a[i]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

秒杀......

置换群,做2n次,顺时针和逆时针.

对于一个置换,最小操作费用是所有循环长度的和.因此实际上是找出2n个置换中哪个置换循环长度为1的数量最多.

⊙﹏⊙b汗

不知道的以为这是数学竞赛......

...

我的数论与图论可以说脑袋里空白一片.........

怎么办，我的竞赛啊

........

算了 看了题解 大家写的

总算弄懂这道题了

先前以为b1，b2,b3..bm是连续的

没想到是任意的！！！！！！！！！

诶 叹悲歌未切 为撼奈何编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

总算AC了

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-

program p1008;

var i,n,k,j,sum1,sum2,ans,max:longint;

a,b,w,d,c:array[0..50005] of longint;

begin

readln(n);

for i:=1 to n do

readln(a[i],b[i]);

w[1]:=1; w[2]:=a[w[1]];

k:=1;

repeat

inc(k);

if w[k-1]=a[w[k]] then w[k+1]:=b[w[k]]

else if w[k-1]=b[w[k]] then w[k+1]:=a[w[k]]

else begin

writeln(-1);

exit;

end;

until k=n;

if w[n+1]w[1] then

begin

writeln(-1);

exit;

end;

for i:=1 to n do

begin

a[i]:=w[i]-i;

b[i]:=w[n-i+1]-i;

if a[i]

构造巧妙、、看来还是要学好数论和图论额、、、、

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：运行超时...

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：0 有效耗时：0ms

无奈 哪位哥哥救救我

把置换解释成度为2图,真有才.

求出序列,正反分别做一次差就行了.

讲建环吧。数组w表示环，我用的是一种类似并查集的方法。

begin

read(n);

for i:=1 to n do read(a[i],b[i]);

t:=2;w[1]:=1;w[2]:=a[1];

while true do begin

if a[w[t]]w[t-1]then w[t+1]:=a[w[t]]//是否在左边

else if b[w[t]]w[t-1]then w[t+1]:=b[w[t]]//是否在右边

else begin writeln(-1);halt;end;//失败判断

inc(t);

if t>n then break;

end;

if w[n+1]w[1]then begin writeln(-1);halt;end;//本句一定要加！！！！！！

end.