再一次体会到c++流的悲剧，秒杀和3s原来只是输入方式的不同，杯具~~

编译通过...

├ 测试数据 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

superyoi killed p1008 with a headshot by awp

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

当我看到众位神牛打出“置换群”三个字后，我在黑书百度GOOGLE维基百科逛了得有一个半小时多然后回来AC了。。。

思路和strini神牛的基本一样。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

其实很简单，不要想复杂了，先是想办法构成，然后用置换群的方法即可ac。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

虽然不懂什么叫置换群，但是思路还是很清晰的。。

一星星纪念～

根据群论原理，任何置换群都可以分解为若干个循环节。显然，这道题目就是冲着这点来的。因为如果某循环的长度为L，那么本题中只需要代价为L的操作。注意，这里的L!=1，这是因为只有一个人的循环节不需要任何代价的操作。到这里才只能拿三十分，因为圈是可以旋转的，常规方法需要O(n^2)才能解决。不妨这里以编号为1的人为基准，定义每个人到自己应该所在位置的距离。距离不超过n-1。可以通过最大值来寻找能在自己位置上的最多的人数（因为距离为x的人在旋转x次后转到自己的位置上），那么在比较好的情况下,可以优化到O(n)。

TIME: 1H

SUBMIT:

1 70 Error: 发现希望相邻是不精确的，于是改了个搜索方向。（以为题目给定的是按照左右方向，白书说过不能“假定”！）。

2 90 Error: 终于明白要取两个搜索方向的最大值。

3 Accepted.

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|__

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

using namespace std;

int n;

int a[50001],b[50001],c[50001];

int aim[50001];

void G_MAP()

{

bool mark[50001]={false};

int p=1,r=1;

while(p

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

考虑两种情形（貌似这两种情形很像，但又真的不同，后来才想起，在化学的手性碳原子那部分遇到过类似情况。。。）

然后就是运用置换群的知识

正反两遍...两遍...

不然就是70分啊...

不看题解的情况下竟然自己想到了...

记得以前老师给我们做过这题的..细节什么的现在做又忘记了..唉..

Flag 　　Accepted

题号 　　P1008

类型(?) 　　模拟

通过 　　1701人

提交 　　4835次

通过率 　　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

yaaaayyayayyayayayayayayayayayayayayayayayyaayayayayayayyaayayayay

var

n,max,i:longint;

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

begin

readln(n);

for i:=1 to n do

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

c[1]:=1;

c[2]:=a[1];

for i:=3 to n do

if c=a[c] then c[i]:=b[c]

else

if c=b[c] then c[i]:=a[c]

else begin

writeln(-1);

halt

end;

if c[n]b[1] then

begin

writeln(-1);

halt

end;

fillchar(d,sizeof(d),0);

for i:=1 to n do

inc(d[(c[i]-i+n)mod n]);

for i:=0 to n-1 do

if d[i]>max then max:=d[i];

fillchar(d,sizeof(d),0);

for i:=1 to n do

inc(d[(c[i]+i-1)mod n]);

for i:=0 to n-1 do

if d[i]>max then max:=d[i];

writeln(n-max);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

置换群,但建环是重点

#include

#include

using namespace std;

long N,seq[50001],p=1;

class

{

private:

long nbr[50001][3];

bool flag[50001];

bool isnbr(long v1,long v2)

{

for(int i=1;i nbr1 >> nbr2;

if(!G.AddE(i,nbr1)||!G.AddE(i,nbr2))

{

cout

哪位大牛帮忙看看我错哪里了

它只得90分

program fire;

type

arr=record

l,r:longint;

end;

var

num:array[1..50000]of longint;

a:array[1..50000]of arr;

b:array[1..50000]of longint;

i,k,j,n:longint;

begin

readln(n);

for i:=1 to n do

readln(a[i].l,a[i].r);

b[1]:=1;

b[n]:=a[1].l;

if a[b[n]].l=b[1]then b[n-1]:=a[b[n]].r

else b[n-1]:=a[b[n]].l;

i:=n-1;

b[2]:=a[1].r;

j:=2;

while j=0 then inc(num[a[i].l-i])

else inc(num[a[i].l-i+n]);

j:=0;

for i:=0 to n do

if num[i]>j then j:=num[i];

write(n-j);

end.

写的有点长

分析：学一个好思想：正难则反！由顺序到乱序我们很难快速找到，但是我们知道如何从乱序变为顺序！解决本题利用了组合数学中置换群的思想。

从第一个人处断开，将圆环的问题转化为序列的问题。如果可以，求出目标序列。求出目标序列复杂度O(n).

求出目标序列右移0至n-1位置时，不需要移动的人数。将目标序列反转，再求出目标序列右移0至n-1位置时，不需要移动的人数。求不需要移动的人数最大等价于求需要移动的人数最小。复杂度O(n)。

更详细的说：

引进“相对有序”这个概念，当两个人满足C[j]-C[i]==j-i时，两个相对有序。

题目要求最小的总代价，但是我们可以考虑倒过来想，要求最小的总代价亦即求最多有多少人不用移动，亦即相对有序。

然后我们引进一个辅助变量T=C-I,{C-I>=0},T=C[i]-I+N,{C[i]-I

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

先是物理大发了——以为 b1,b2...bm是连续的

看了牛们的题解 一次ac ：）

第一遍做的时候没有看题解，自己测了好几遍总是60分，看了n多大牛的解释才恍然大悟，竟然要正反两遍！！！唉，幸亏咱有测试数据，否则我可就惨了...

O(n)的求目标队列算法，都说是冒泡排序，我没看出来，倒是有点像。

物理自重啊，嘿嘿。

注意要正反两遍哦～

9MS？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

（好像那个冒泡是口胡，大家不要被那个蒙了

program fire;

var

st:array [1..50000,1..2] of longint;

k,final:array [0..50000] of longint;

ex:array [1..50000] of boolean;

p,max,i,n:longint;

begin

fillchar (st,sizeof(st),0);

fillchar (ex,sizeof(ex),0);

fillchar (final,sizeof(final),0);

fillchar (k,sizeof(k),0);

readln (n);

for i:=1 to n do readln (st,st);

final[1]:=1;p:=2;ex[1]:=true;

for i:=1 to n do begin

if ex[st[final[i],1]]=false then begin

final[p]:=st[final[i],1];

ex[st[final[i],1]]:=true;

inc(p);

end

else if ex[st[final[i],2]]=false then begin

final[p]:=st[final[i],2];

ex[st[final[i],2]]:=true;

inc(p);

end;

end;

if p-1n then begin

writeln (-1);

halt;

end;

max:=0;

for i:=1 to n do if final[i]>=i then inc(k[final[i]-i]) else inc(k[n-i+final[i]]);

for i:=0 to n-1 do if k[i]>max then max:=k[i];

fillchar (k,sizeof(k),0);

for i:=n downto 1 do if final[i]>=n-i+1 then inc(k[final[i]-n+i-1]) else inc(k[final[i]+i-1]);

for i:=0 to n -1 do if k[i]>max then max:=k[i];

writeln (n-max);

end.