NOIP2020 移球游戏

NOIP2020 移球游戏

前言

此题位于t3位置，并且是noip第一次考构造题和special judge。考场上由于不会t2觉得t3更简单，并且常年在cf上打比赛觉得构造题十分熟悉而写了t3放弃t2。但由于不会使用spj导致代码漏洞百出（事实上自己写这个题spj非常简单）最后混了10分。其实考场上想出的思路也只能得40分。还是太菜了呀！

题目

题目链接

移球游戏

输入文件名：ball.in

输出文件名：ball.out

共 20 个测试点，每个测试点 5 分

每个测试点限时 1 秒，运行内存上限 512MB

小 C 正在玩一个移球游戏，他面前有 n + 1 根柱子，柱子从 1 ∼ n+1 编号，其中 1 号柱子、2 号柱子、…、n。n 号柱子上各有 m 个球，它们自底向上放置在柱子上，n+1 号柱子上初始时没有球。这 n×m 个球共有 n 种颜色，每种颜色的球各 m 个。

初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。

小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 xx 号柱子上的球移动到 y 号柱子上的要求为:

x 号柱子上至少有一个球;
y 号柱子上至多有 m−1m−1 个球;
只能将 x 号柱子最上方的球移到 y 号柱子的最上方。
小 C 的目标并不难完成，因此他决定给自己加加难度:在完成目标的基础上，使用的操作次数不能超过 820000。换句话说，小 C 需要使用至多 820000 次操作完成目标。

小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。

输入格式
输入文件名为 ball.in。

第一行两个用空格分隔的整数 n，m。分别表示球的颜色数、每种颜色球的个数。 接下来 n 行每行 m 个用单个空格分隔的整数，第 i 行的整数按自底向上的顺序依次给出了 i 号柱子上的球的颜色。

输出格式
输出文件名为 ball.out。

本题采用自定义校验器（special judge）评测。 你的输出的第一行应该仅包含单个整数 kk，表示你的方案的操作次数。你应保证 0 \leq k \leq 8200000≤k≤820000。

接下来 k 行每行你应输出两个用单个空格分隔的正整数 x,y，表示这次操作将 x 号柱子最上方的球移动到 y 号柱子最上方。你应保证 1 \leq x, y \leq n + 11≤x,y≤n+1 且 x \neq yx 

​	
 =y。

样例 1 输入
2 3
1 1 2
2 1 2
样例 1 输出
6
1 3
2 3
2 3
3 1
3 2
3 2

解法

40pts

每次将同种颜色的球移至一个柱子不断缩小问题。对于一个深度为\(m\)的球要想移到某个柱子只需要\(2m\)次（将他上方的m-1个球移走，将这个球移至一个柱子，将m-1个球移回来，再将这个球移至最终要放的目标柱）。平均下每个深度都有一个要移动的球，所以平均复杂度为\(O(nm^2)\)

code

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define ll long long
#define ull unsigned long long
using namespace std;
int zhu[110][510];
int ci[510];
//int name[100];
int bz[820010][2];
int endd=0;
int n,m;
void print(int x,int y){
	bz[endd][0]=x;
	bz[endd++][1]=y;
	zhu[y][++zhu[y][0]]=zhu[x][zhu[x][0]--];
	return;
}
void mymove(int l,int d,int len,int zl){
	if(d==zhu[l][0]){
		print(l,len);
		return;
	}
	int i=1;
	for(;i<=len&&zhu[l][0]>=d;){
		if(i==l){
			++i;
			continue;
		}
		if(zhu[i][0]<m){
			print(l,i);
		}
		else{
			++i;
		}
	}
	if(i==len){
		if(l==1){
			print(len-1,l);
			print(len,len-1);
			i=len-1;
		}
		else{
			print(1,l);
			print(len,1);
			i=1;
		}
	}
	while(zhu[len][0]>0&&zhu[len][zhu[len][0]]!=zl){
		print(len,l);
	}
	print(i,len);
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		zhu[i][0]=m;
		for(int j=1;j<=m;++j){
			scanf("%d",&zhu[i][j]);
		}
	}
	n++;
	for(int i=0;i<n;++i){
		int len=n-i;
		if(len==2)break;
		int minp=zhu[1][zhu[1][0]];
		for(int j=1;j<len;++j){
			for(int k=zhu[j][0];k>=1;--k){
				if(zhu[j][k]==minp){
					int temp=zhu[j][0];
					mymove(j,k,len,minp);
					if(zhu[j][0]==temp)++k;
				}
			}
		}
		if(len>2){
			for(int j=1;j<len-1;){
				if(zhu[j][0]<m){
					print(len-1,j);
				}
				else{
					++j;
				}
			}
		}
	}
	printf("%d\n",endd);
	for(int i=0;i<endd;++i){
		printf("%d %d\n",bz[i][0],bz[i][1]);
	}
	return 0;
}

100pts

遇到这种题目正解一定要带一个log，只好往分治那方面想。所以可以把所有颜色一分两半，同类颜色在各自一半（并不要求同颜色连续）。

具体如何把颜色分类可用一个例子来说明。为方便描述，l表示左端点，r表示右端点，m表示中点这里用a表示要分类的柱子，b表示零时借用柱子，c表示空柱子。

  1. b–a中的球的个数–>c
  2. a–属于左边放b，否则放c–>b,c
  3. b，c–原来在a的–>a
  4. c–剩下的（原来是b的）–>b

现在我们有了r-l+1个相对有序的柱子，现在问题转化为如何将同色的一堆连续球放在一边。为方便表述z表示未完全分类的柱子左端点，同理y表示右端点。初始z=l，y=r

  1. 若zy上属于左边的多，则利用空柱子几次反转使左边颜色在zy顶上。总之要把少的颜色放在顶上。假设这时左边颜色少。
  2. z–左边颜色球–>c
  3. y–左边颜色球–>c
  4. z–剩下的且不超过y最大–y
  5. –y
  6. c---->z

这样y就缩小了，如此反复直至z==y-1==m

  1. f(l,m) f(m+1,r)

这样问题就解决啦，复杂度大概为\(mnlog^n\)

code

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define frep(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
#define fdrep(i,a,b) for(int i=(a);i>(b);--i)
using namespace std;
int zhu[110][510];
int ci[510];
int bz[820010][2];
int name[60];
int endd=0;
int n,m;
int kong;
void print(int x,int y){
	zhu[name[y]][++zhu[name[y]][0]]=zhu[name[x]][zhu[name[x]][0]--];
	if(endd>0&&bz[endd-1][0]==name[y]&&bz[endd-1][1]==name[x]){
		--endd;
		return;
	}
	if(endd>0&&bz[endd-1][1]==name[x]){
		bz[endd-1][1]=y;
		return;
	}
	bz[endd][0]=name[x];
	bz[endd++][1]=name[y];
	return;
}
void mymove(int a,int b,int c,int l,int r){
	int con=0;
	rep(i,1,zhu[name[a]][0]){
		if(zhu[name[a]][i]>=l&&zhu[name[a]][i]<=r)++con;
	}
	rep(i,1,con){
		print(b,c);
	}
	drep(i,zhu[name[a]][0],1){
		if(zhu[name[a]][i]>=l&&zhu[name[a]][i]<=r)print(a,b);
		else print(a,c);
	}
	rep(i,1,con){
		print(b,a);
	}
	rep(i,1,m-con){
		print(c,a);
	}
	rep(i,1,con){
		print(c,b);
	}
	return;
}
void solve(int l,int r){
	if(l==r)return;
	int temp=(l==1)?2:1;
	int mm=(l+r)>>1;
	rep(p,l,r){
		if(p==temp)temp=1;
		mymove(p,temp,kong,l,mm);
	}
	int z=l,y=r;
	while(z<y){
		int con1=0,con2=0,con3=0,con4=0;
		rep(i,1,zhu[name[z]][0]){
			con1+=zhu[name[z]][i]<=mm?1:0;
			con2+=zhu[name[z]][i]<=mm?0:1;
		}
		rep(i,1,zhu[name[y]][0]){
			con3+=zhu[name[y]][i]<=mm?1:0;
			con4+=zhu[name[y]][i]<=mm?0:1;
		}
		if(con1+con3<con2+con4){
			if(zhu[name[z]][zhu[name[z]][0]]>mm){
				drep(i,zhu[name[z]][0],1){
					print(z,kong);
				}
				swap(name[z],name[kong]);
			}
			if(zhu[name[y]][zhu[name[y]][0]]>mm){
				drep(i,zhu[name[y]][0],1){
					print(y,kong);
				}
				swap(name[y],name[kong]);
			}
			while(zhu[name[z]][0]&&zhu[name[z]][zhu[name[z]][0]]<=mm)print(z,kong);
			while(zhu[name[y]][0]&&zhu[name[y]][zhu[name[y]][0]]<=mm)print(y,kong);
			while(zhu[name[z]][0]&&zhu[name[y]][0]<m)print(z,y);
			--y;
			while(zhu[name[kong]][0])print(kong,z);
		}
		else{
			if(zhu[name[z]][zhu[name[z]][0]]<=mm){
				drep(i,zhu[name[z]][0],1){
					print(z,kong);
				}
				swap(name[z],name[kong]);
			}
			if(zhu[name[y]][zhu[name[y]][0]]<=mm){
				drep(i,zhu[name[y]][0],1){
					print(y,kong);
				}
				swap(name[y],name[kong]);
			}
			while(zhu[name[z]][0]&&zhu[name[z]][zhu[name[z]][0]]>mm)print(z,kong);
			while(zhu[name[y]][0]&&zhu[name[y]][zhu[name[y]][0]]>mm)print(y,kong);
			while(zhu[name[y]][0]&&zhu[name[z]][0]<m)print(y,z);
			++z;
			while(zhu[name[kong]][0])print(kong,y);
		}
	}
	solve(l,mm);
	solve(mm+1,r);
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		name[i]=i;
		zhu[i][0]=m;
		for(int j=1;j<=m;++j){
			scanf("%d",&zhu[i][j]);
		}
	}
	n++;
	kong=n;
	name[n]=n;
	solve(1,n-1);
	printf("%d\n",endd);
	for(int i=0;i<endd;++i){
		printf("%d %d\n",bz[i][0],bz[i][1]);
	}
	return 0;
}

构造题 Special Judge
#省选/NOI-
NOIP2020 移球游戏
http://yoursite.com/2020/12/12/NOIP2020-移球游戏/
作者
99_wood
发布于
2020年12月12日
许可协议