庆祝百题AC...

字典序法生成全排列

有兴趣的同学搜索一下全排列的生成算法，有好多种。

字典序法编程容易实现，而且求某个排列的下一个排列好使。

方法就是

如：2341

第一步：连续两数，满足左边2431->2413

完毕.

以上过程执行M次就OK了.

第一次写，没想到一次ac

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

就是字典全排列问题。。。

可惜我掌握的不好。。。

WA了一次

水题，一次AC秒杀

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var s:array[1..10000] of integer;

n,a,plus,p,k,b:integer;

procedure huan(var a,b:integer);

var c:integer;

begin

c:=a;

a:=b;

b:=c;

end;

begin

readln(n);

readln(plus);

for a:=1 to n do

read(s[a]);

for a:=1 to plus do

begin

p:=n-1;

while s[p]>s[p+1] do dec(p);

if p>0 then

begin

k:=n;

while s[k]

var

a,d:array[0..10000] of integer;

b,c:array[0..10000] of boolean;

n,m,i,t:integer;

procedure q;

var

k:integer;

begin

for k:=1 to n do write(d[k],' ');

halt;

end;

procedure p(x:integer);

var

j:integer;

begin

if x=n+1 then

begin

t:=t+1;

if t=m+1 then q;

exit;

end;

for j:=1 to n do

if (c[x]) and (b[j]) then

begin

d[x]:=j;b[j]:=false;

p(x+1);

d[x]:=0;b[j]:=true;

end

else if (b[j]) and (j=a[x]) then

begin

d[x]:=j;b[j]:=false;c[x]:=true;

p(x+1);

d[x]:=0;b[j]:=true;

end;

end;

begin

readln(n);

readln(m);

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

fillchar(b,sizeof(b),true);

fillchar(c,sizeof(c),false);

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

p(1);

end.

直接用深搜，稍微判断一下就可以了，属于秒杀的题目

第2000个通过此题&我的第130题。

有关全排列的算法；

某一全排列后的第m个；

但是不能用康拓展开。

排列生成法：

program mars;

var

a:array[1..10001] of integer;

b:array[1..10001] of boolean;

max,p,i,j,k,m,n:longint;

begin

readln(n);

readln(m);

for i:=1 to n do begin

read(a[i]);

b[a[i]]:=true;

end;

p:=n+1;

dec(k);

while 1=1 do begin

if p>n then

begin

dec(p);

inc(k);

b[a[p]]:=false;

if k=m then

break;

end;

repeat inc(a[p]) until not b[a[p]];

b[a[p]]:=true;

if a[p]>n then begin

b[a[p]]:=false;

dec(p);

b[a[p]]:=false;

end

else

begin

inc(p);

a[p]:=0;

end;

end;

for i:=1 to n-1 do

write(a[i],' ');

writeln(a[n]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

10分，20分，30分，90分，AC。 一个艰辛的历程！

题目其实就是叫你求一个排列的后K个全排列；

var

p,l,n,m,i1,i,j,t,k,x:integer;

s1,s2:ansistring;

a:array[1..10000]of longint;

begin

readln(n);

readln(m);

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

while m>0 do

begin

j:=n;

if a[j]>a[j-1] then

begin

t:=a[j];

a[j]:=a[j-1];

a[j-1]:=t;

end

else begin

while a[j]

var a:array[1..10000] of integer; i,j,k,t,n,m:integer; f:boolean;begin readln(n); readln(m); for i:=1 to n do read(a[i]); for i:=1 to m do begin j:=n; while (a[j-1]>a[j]) do dec(j); k:=j-1; j:=n; while (a[j]k) do dec(j); t:=a[k]; a[k]:=a[j]; a[j]:=t; qsort(k+1,n);/快排（略） end; for i:=1 to n-1 do write(a[i],' ');write(a[n]);end.这道题我用的是求数列1..n的第m个全排列的方法，而本题就是再继续m次

Program P1115;

var a:array[1..11000]of longint;

var n,m,i,j,p,q,t:longint;

begin

readln(n,m);

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

for i:=1 to m do{给火星人的手指+m次1}

begin

p:=n-1;

while a[p]>a[p+1]do dec(p);{找最长不上升序列的末尾}

q:=p+1;

while(q

program martian;

var

a:array[1..10001] of integer;

m,n,i,j,p,q,t:integer;

begin

readln(n);

readln(m);

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

for i:=1 to m do

begin

p:=n-1;

while a[p]>a[p+1] do dec(p);

q:=p+1;

while (qa[p]) do

inc(q);

dec(q);

t:=a[p];

a[p]:=a[q];

a[q]:=t;

for j:=p+1 to p+(n-p) div 2 do

begin

t:=a[j];

a[j]:=a[n+p+1-j];

a[n+p+1-j]:=t;

end;

end;

for i:=1 to n do

if not(i=n) then write(a[i],' ')

else writeln(a[i]);

end.

虽然是水题，可是偶的话痨病又犯了。

首先庆祝一下AC率首次超过10%～

然后，咳咳，我评论一下这题（正常人54我，直接看我楼下吧）

解题的办法很简单，

每次把这个序列从后往前找单调上升的。

然后把这部分重排就OK了。

但是，

根据题目，大家看看啊：

"第一行有一个正整数N，表示火星人手指的数目(1

从后往前找到第一个可以往上更新的数，更新，然后对于剩下的没有被分配的数，按照从小到大关系放在其后面，继续做下次，直到做了M次。虽然渐进时间复杂度是O(n^2m)，但是因为这道题的特殊性，所以均摊时间复杂度O(nm)。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

奇迹奇迹一天之内两次……一次ac noip题……^_^（本人太菜了……）；

题目不难，但是我考虑太烦了，所以测试了好多次……

var

n,k,l,l1,i,j,temp:longint;

a:array[1..10000]of longint;

begin

read(n,k);

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

for i:=1 to k do

begin

l:=n;

while a[l-1]>a[l] do dec(l);

l1:=n;

while a[l-1]>a[l1] do dec(l1);

temp:=a[l-1];a[l-1]:=a[l1];a[l1]:=temp;

for j:=l to (n+l) div 2 do

begin

temp:=a[j];a[j]:=a[n+l-j];a[n+l-j]:=temp;

end;

end;

write(a[1]);

for i:=2 to n do write(' ',a[i]);

end.

我终于登上火星了

编译通过...

├ 测试数据 01：运行时错误...|错误号: -1073741571

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

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

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

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

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

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

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

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

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

为什么？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

罪过罪过