置换群.....是什么？

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]>m then m:=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]>m then m:=d[i];

writeln(n-m);

是么？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

技巧性比较强吧，楼下不必构造2次，计算时从头至尾算一次，再倒过来算一次就行了

置换群思想...今天刚明白...

先构造新数列(要构造两次,否则只有70分),然后向右计算相对位置差,然后累加记录数组,然后用N减去相对位置差累加值最大的,就是答案...

Flag 　　Accepted

题号 　　P1008

类型(?) 　　其它

通过 　　1065人

提交 　　3000次

通过率 　　35%

难度 　　3

第3000个提交的

#include

using namespace std ;

int hash[50001];

int n , i , j , t , maxs(0) ;

inline void HASH ( int e[] )

{

for ( i = 1 ; i > n ;

int e[n+1] , h[n+1][2] , e2[n+1];

bool f[n+1] ;

for ( i = 1 ; i > h[i][0] >> h[i][1] ;

}

e[1] = 1 ;

f[1] = true ;

for ( i = 2 ; i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

纪念我第200次提交！过第79题。。。。

#include

#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

编译通过...

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

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

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

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

├ 测试数据 10：答案错误...程序输出比正确答案长

为什么我的程序不对？

#include

using namespace std;

#define MAXN 50000

int man[MAXN+2][2];

int cercle[MAXN+2]={0,1};

int used[MAXN+2]={0};

int reduce[2][MAXN+2]={0};

int n;

int main()

{

long i,p,q=1,t;

int max=0;

cin>>n;

for (i=1;i>man[i][0]>>man[i][1];

p=man[q][1];

for (i=2;i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

oh no

我在想``怎么样才能不看错这题呢

时间复杂度O(N)。。。

原来我一直把题意理解错。。。囧！！。。

关于“置换群”，请看LRJ的《算法艺术与信息学竞赛》P245那一小节，还是比较好理解的。

热烈庆祝用pascal AC的第二题~

p.s.我是C++的~~

解决效率不高，但AC了。

用距离来分类,统计在原位的最大人数,奇怪的是

b[1]:=1;

b[2]:=a[1,1];

b[n]:=a[1,2];

建环的时候,上面的改成

b[1]:=1;

b[2]:=a[1,2];

b[n]:=a[1,1];

最后一个点却过不了,太奇怪了.

对于初三刚刚中考完的我，要理解这题的意思是万万不能的。。。

看题解我知道了应该怎么做，但那不是我的，所以不做了。。。

哪天能证明出来那啥再来做

好简单啊

直接贪啊

(P.S.置换群?什么东东...)

我代码写了老长老长,结果还是只过了8个点,有没有搞错?

我想请问一下,我和大家的一样,先排列出目标状态.然后确定初始状态时使得最多的人在目标位置上,然后交换.但是得到的答案总是偏大一点.

然后我又把所有可以使最多的人在原位目标位置上的可能都尝试了一编(包括正反两个目标状态),结果还是只能过8个点,有2个点死都过不了!

我的算法有什么问题吗?

很委琐的说 我提交了8遍。。

0→0→10→10→10→10→70→AC

• -||

数论……好底歇的东西。