2014：【20NOIP提高组】移球游戏-创新互联

【题目描述】

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

常宁网站制作公司哪家好，找创新互联建站！从网页设计、网站建设、微信开发、APP开发、自适应网站建设等网站项目制作，到程序开发，运营维护。创新互联建站从2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联建站。

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

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

1. xx 号柱子上至少有一个球；

2. yy 号柱子上至多有 m−1m−1 个球；

3. 只能将 xx 号柱子最上方的球移到 yy 号柱子的最上方。

小 C 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用的操作次数不能超过 820000820000。换句话说，小 C 需要使用至多 820000 次操作完成目标。

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

【输入】

第一行两个用空格分隔的整数 nn，mm。分别表示球的颜色数、每种颜色球的个数。

接下来 nn 行每行 mm 个用单个空格分隔的整数，第 ii 行的整数按自底向上的顺序依次给出了 ii 号柱子上的球的颜色。

【输出】

本题采用自定义校验器（special judge）评测。

你的输出的第一行应该仅包含单个整数 kk，表示你的方案的操作次数。你应保证0≤k≤8200000≤k≤820000。

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

【输入样例】

2 3
1 1 2
2 1 2

【输出样例】

6
1 3
2 3
2 3
3 1
3 2
3 2

【提示】

【样例解释】

柱子中的内容为：按自底向上的顺序依次给出柱子上每个球的颜色。

操作	1号柱子	2号柱子	3号柱子
初始	1 1 2	2 1 2
1 3	1 1	2 1 2	2
2 3	1 1	2 1	2 2
2 3	1 1	2	2 2 1
3 1	1 1 1	2	2 2
3 2	1 1 1	2 2	2
3 2	1 1 1	2 2 2

【数据范围】

对于所有测试点，保证 2≤n≤502≤n≤50，2≤m≤4002≤m≤400。

【校验器】

为了方便选手测试，我们下发了checker.cpp文件，选手可以编译该程序，并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。

编译命令为：g++ checker.cpp −o checker。

checker 的使用方式为：checker，参数依次表示输入文件与你的输出文件。

若你输出的数字大小范围不合法，则校验器会给出相应提示。若你的输出数字大小范围正确，但方案错误，则校验器会给出简要的错误信息：

1. A x，表示进行到第 x 个操作时不合法。

2. B x，表示操作执行完毕后第 x 个柱子上的球不合法。

若你的方案正确，校验器会给出OK。

作者超懒，直接上代码！

#include#include#include#include#include 
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int x){
	if(x >9) writeint(x/10);
	putchar((x-x/10*10)^48);
}
inline int ABS(const int &x){
	return x< 0 ? -x : x;
}

const int MaxN = 55;
const int MaxM = 405;
int a[MaxN][MaxM], n, m;
int count(int x,int mid){
	int s = 0; rep(i,1,m) s += (a[x][i]<= mid); return s;
}
# define TOP(x) a[x][a[x][0]]

vector< pair>ans;
# define CMD(x,y) do{ ans.push_back(make_pair(x,y));\
a[y][++ a[y][0]] = a[x][a[x][0] --]; } while(false)
int pos[MaxN]; // pos[0] is empty
inline void create(int x,int s){
	rep(i,1,s) CMD(x,pos[0]);
}
inline void pourOut(int x,int y,int k){
	for(; k; --k) CMD(x,y);
}
inline void moveUp(int x,int want,int helper,bool sgn=1,bool f=1){
	int s = count(x,want), lost = 0;
	if(!sgn) s = m-s; // >want
	bool wxk = false; // if it's swapped
	if((m>>1)< s && f){
		wxk = 1; create(helper,m-s);
		swap(helper,pos[0]); // temporary
	} else create(helper,s);
	for(int work=s; work; )
		if((TOP(x)<= want) == sgn){
			CMD(x,helper); -- work;
		} else { CMD(x,pos[0]); ++ lost; }
	pourOut(pos[0],x,lost); // normal balls
	if(!f) return ; // keep %want% in register
	pourOut(helper,x,s); // put %want% on the top
	if(wxk){ // restore
		swap(helper,pos[0]);
		pourOut(pos[0],helper,m-s);
	} else pourOut(pos[0],helper,s);
}
void solve(int l,int r){
	if(l == r) return ; // already done
	if(l+1 == r){ // n = 2
		moveUp(pos[l],l,pos[r]);
		moveUp(pos[r],l,pos[l]);
		pourOut(pos[l],pos[0],count(pos[l],l));
		pourOut(pos[r],pos[0],count(pos[r],l));
		pourOut(pos[l],pos[r],a[pos[l]][0]);
		swap(pos[0],pos[l]); return ;
	}
	int mid = (l+r)>>1;
	for(int i=l+1; i<=r; ++i){
		int s1 = count(pos[i-1],mid);
		int s2 = count(pos[i],mid);
		bool sgn = (s1+s2 >= m); // want
		if((sgn && (m>>1)< m-s1)
		|| (!sgn && (m>>1)< s1)) // fill pos[i-1]
			swap(pos[i],pos[i-1]), s1 = s2;
		if(!s1 || s1 == m) continue; // well...
		int aid = (i == r) ? pos[l] : pos[i+1];
		moveUp(pos[i],mid,aid,sgn); // extract i
		moveUp(pos[i-1],mid,aid,sgn^1,false);
		pourOut(pos[i],pos[i-1],m-a[pos[i-1]][0]);
		pourOut(aid,pos[i],m-a[pos[i]][0]);
		pourOut(pos[0],aid,a[pos[0]][0]);
	}
	for(int i=l,j=r; imid; --j);
		swap(pos[i],pos[j]);
	}
	solve(l,mid), solve(mid+1,r);
}

int main(){
	n = readint(), m = readint();
	rep(i,1,n) rep(j,1,m)
		a[i][j] = readint();
	rep(i,1,n) // init
		pos[i] = i, a[i][0] = m;
	pos[0] = n+1; solve(1,n);
	writeint(ans.size());
	putchar('\n');
	for(auto it : ans){
		writeint(it.first);
		putchar(' ');
		writeint(it.second);	
		putchar('\n');
	}
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：2014：【20NOIP提高组】移球游戏-创新互联
当前URL：http://scjbc.cn/article/dechcg.html