隐藏
「WC2010」排序机 - 提交答案题 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「WC2010」排序机 - 提交答案题

题目大意

    轮换$g:(q_1\,\,q_2\,\,q_3\cdots q_k)$是一个从$\lbrace1,2,\ldots,n\rbrace$到$\lbrace1,2,\ldots,n\rbrace$的一一映射,它将$q_1$映射为$q_2$,$q_2$映射为$q_3$,$\ldots$,$q_k$映射为$q_1$,而在$q_1,q_2,\ldots,q_k$中没有出现的整数映射到自身。即:$g(q_1)=q_2,g(q_2)=q_3,\ldots,g(q_k)=q_1$,而对于在$q_1,q_2,\ldots,q_k$中没有出现的$x$,$g(x)=x$。定义将轮换$g$应用到一个$\lbrace1,2,\ldots,n\rbrace$的排列$(p_1,p_2,\ldots,p_n)$上的结果为:$g(p_1,p_2,\ldots,p_n)=(g(p_1),g(p_2),\ldots,g(p_n))$例如,对排列$(3,1,5,4,2)$应用轮换$(1\,\,3\,\,4)$进行变换后可得到排列$(4,3,5,1,2)$。给定$\lbrace1,2,\ldots,n\rbrace$的一个排列$(p_1,p_2,\ldots,p_n)$和一些轮换,请给出一种使用尽量 少的轮换次数将该排列变换为$(1,2,\ldots,n)$的方法。每个轮换可以使用多次。


评测方式

点击下载输入数据与答案验证器,在cmd中使用命令checker num,其中$num$是数据编号即可检验答案是否合法。
注意仅仅是检验合法性,并不会回答分数。

点击下载评测用具,内含使用说明。


数据分析

数据点$1\sim3$

数据很小,第一个点也可以手玩。
估计是搜索。

数据点$4$

发现$k$始终为$2$,$q_2$始终为$q_1+1$,形成单链形状。

数据点$5$

发现$k$始终为$2$,所有$q_1$和$q_2$的置换都存在,是一个完全图。

数据点$[6,7]$

发现$k$始终为$2$,形成一棵树,且是一个菊花图,以$1$为根。

数据点$[8,10]$

发现$k$始终为$2$,形成一棵树。
接下来的不太容易发现,$q_2$始终为$\lfloor\frac{q_1}2\rfloor$。
因此形成一个堆。
其中$[8,9]$是满二叉堆,而$10$是一个普通的二叉堆。


码农时间

点击下载我的程序与答案。

sort1.in$$\rightarrow$$sort3.in,手动迭代加深计算答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

int n,m,p[55][55],pos[55],Now[55],a[55],ans[55];

void Move_Forward(int id) {
int tmp=pos[p[id][p[id][0]]];
for(int j=p[id][0]; j>=2; j--)pos[p[id][j]]=pos[p[id][j-1]];
pos[p[id][1]]=tmp;
for(int j=1; j<=n; j++)Now[pos[j]]=j;
}

void Move_Back(int id) {
int tmp=pos[p[id][1]];
for(int j=1; j<p[id][0]; j++)pos[p[id][j]]=pos[p[id][j+1]];
pos[p[id][p[id][0]]]=tmp;
for(int j=1; j<=n; j++)Now[pos[j]]=j;
}

void Dfs(int depth) {
if(depth>9)return;
bool bj=1;
for(int i=1; i<=n; i++)
if(pos[i]!=i) {
bj=0;
break;
}
if(bj) {
printf("%d\n",depth-1);
for(int i=1; i<depth; i++)printf("%d\n",ans[i]);
exit(0);
}
for(int i=1; i<=m; i++) {
Move_Forward(i);
ans[depth]=i;
Dfs(depth+1);
Move_Back(i);
}
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
Now[i]=a[i]=Get_Int();
pos[a[i]]=i;
}
for(int i=1; i<=m; i++) {
p[i][0]=Get_Int();
for(int j=1; j<=p[i][0]; j++)p[i][j]=Get_Int();
}
Dfs(1);
return 0;
}

sort4.in单链数据。直接上冒泡排序,答案次数就是逆序对个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

int n,m,p[505],pos[505],id[505];
vector<int> ans;

int main() {
freopen("sort4.in","r",stdin);
freopen("sort4.out","w",stdout);
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
p[i]=Get_Int();
pos[p[i]]=i;
}
for(int i=1;i<=m;i++) {
Get_Int();
id[Get_Int()]=i;
Get_Int();
}
for(int i=1; i<=n; i++)
for(int j=p[i]-1; j>=i; j--) {
ans.push_back(id[j]);
swap(pos[j],pos[j+1]);
p[pos[j]]=j;
p[pos[j+1]]=j+1;
}
printf("%d\n",ans.size());
for(int x:ans)printf("%d\n",x);
return 0;
}

sort5.in完全图数据。
既然是完全图,也就是说可以任意交换两个数。
考虑当前序列最少的交换方式。
根据置换群原理,最少的交换次数$=n-$置换个数。
方案就按照置换内部构造即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=1005;

int n,m,map[maxn][maxn],Dfn[maxn],Lowlink[maxn],Instack[maxn],Stack[maxn],step=0,top=0,SCC=0;
vector<int>edges[maxn],Circle[maxn];

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

void Tarjan(int Now) {
Dfn[Now]=Lowlink[Now]=++step;
Stack[++top]=Now;
Instack[Now]=1;
for(int Next:edges[Now]) {
if(!Dfn[Next]) {
Tarjan(Next);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
} else if(Instack[Now])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
}
if(Dfn[Now]==Lowlink[Now]) {
int y;
SCC++;
do {
y=Stack[top--];
Circle[SCC].push_back(y);
Instack[y]=0;
} while(y!=Now);
reverse(Circle[SCC].begin(),Circle[SCC].end());
}
}

int main() {
freopen("sort5.in","r",stdin);
freopen("sort5.out","w",stdout);
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int();
AddEdge(i,x);
}
for(int i=1; i<=n; i++)
if(!Dfn[i])Tarjan(i);
for(int i=1; i<=m; i++) {
Get_Int();
int x=Get_Int(),y=Get_Int();
map[x][y]=map[y][x]=i;
}
printf("%d\n",n-SCC);
for(int i=1; i<=SCC; i++) {
int size=Circle[i].size();
for(int j=0; j<=size-2; j++)printf("%d\n",map[Circle[i][j]][Circle[i][j+1]]);
}
return 0;
}

sort6.in$$\rightarrow$$sort7.in菊花图数据。
这种数据只需要让$1$出去绕圈,直到没有圈为止。
似乎也有别的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

int n,m,pos[1005],id[1005],Now;
vector<int> ans;

int main() {
freopen("sort7.in","r",stdin);
freopen("sort7.out","w",stdout);
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int();
pos[x]=i;
if(x==1)Now=i;
}
for(int i=1; i<=m; i++) {
Get_Int();
Get_Int();
id[Get_Int()]=i;
}
while(Now!=1) {
ans.push_back(id[Now]);
swap(Now,pos[Now]);
}
while(true) {
pos[1]=1;
bool bj=0;
for(int i=1; i<=n; i++)
if(pos[i]!=i) {
bj=1;
Now=pos[i];
ans.push_back(id[i]);
swap(pos[i],pos[1]);
break;
}
if(!bj)break;
while(Now!=1) {
ans.push_back(id[Now]);
swap(Now,pos[Now]);
}
}
printf("%d\n",ans.size());
for(int x:ans)printf("%d\n",x);
return 0;
}

sort8.in$$\rightarrow$$sort10.in堆式数据。
堆式数据,考虑记录每个位置的数$a[]$,以及每个数所在位置$pos[]$。
不难想到贪心思路:
优先将深度大的数归位
这样做的原因是,若先将深度小的数归位,后归位深度大的数时就会扰乱深度小的那些数。
因为是堆式编号,因此从大到小归位即可。
每次归位的时候,取出当前数$num$和当前位置$pos$,得到他们在树上的路径,依次将路径$num\rightarrow pos$上的数依次放到$pos$位置,最终使得$pos$归位。
因为是堆,时间复杂度为$O(n\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=40005;

int n,m,a[maxn],Pos[maxn],Depth[maxn],Up_Move[maxn];
vector<int> ans;

#define ls num<<1
#define rs num<<1|1
#define fa num>>1

void Cal(int pos) {
if(a[pos]==pos)return;
int num=a[pos],son1=num,son2=pos;
if(Depth[son1]<Depth[son2])swap(son1,son2);
static int path[maxn];
fill(path+1,path+n+1,0);
while(Depth[son1]!=Depth[son2]) {
path[son1]=1;
son1>>=1;
}
while(son1!=son2) {
path[son1]=path[son2]=1;
son1>>=1;
son2>>=1;
}
path[son1]=1;
while(num!=pos) {
path[num]=0;
int next=0;
if(path[fa])next=fa;
else if(path[ls])next=ls;
else next=rs;
if(next>num)ans.push_back(Up_Move[next]); //向下走
else ans.push_back(Up_Move[num]); //向上走
swap(Pos[num],Pos[next]);
a[Pos[num]]=num,a[Pos[next]]=next;
num=next;
}
}

int main() {
freopen("sort10.in","r",stdin);
freopen("sort10.out","w",stdout);
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)Depth[i]=Depth[i>>1]+1;
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
Pos[a[i]]=i;
}
for(int i=1; i<=m; i++) {
Get_Int();
Up_Move[Get_Int()]=i;
Get_Int();
}
for(int i=n; i>=1; i--)Cal(i);
printf("%d\n",ans.size());
for(int x:ans)printf("%d\n",x);
return 0;
}

姥爷们赏瓶冰阔落吧~