差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest11 [2021/08/06 13:41]
王智彪
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest11 [2021/08/08 14:06] (当前版本)
jxm2001
@@ 行 4: / 行 4: @@
 ^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
-|  B  |  2  |  0  |  0  |
+|  B  |  2  |  1  |  0  |
-|  D  |  0  |  0  |  0  |
+|  D  |  2  |  0  |  1  |
-|  E  |  2  |  0  |  0  |
+|  E  |  2  |  0  |  1  |
 |  G  |  0  |  0  |  0  |
 |  I  |  0  |  0  |  0  |
@@ 行 100: / 行 100: @@
 	}
 	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== D. Dancing Disks =====
+==== 题意 ====
+给定一个 $6\times 6$ 的栈，每次可以从栈 $(r,c)$ 顶部取若干个元素放入栈 $(r+1,c)$ 或栈 $(r,c+1)$ 的顶部。
+初始时所有元素都在栈 $(1,1)$，自底向上分别是 $a_1,a_2\cdots a_n$，其中 $a_1,a_2\cdots a_n$ 构成 $1\sim n$ 的一个排列。
+要求构造一个方案将所有元素转移到栈 $(6,6)$，且栈 $(6,6)$ 自底向上分别是 $n,n-1\cdots 1$。其中 $n\le 40000$。
+==== 题解 ====
+设 $f(r,c)$ 表示从 $f(r,c)$ 出发至少可以将多少个元素转移到 $(6,6)$ 且最终 $(6,6)$ 上元素有序。
+显然 $f(6,6)=1$。而对 $f(6,5)$，假设元素自底向上为 $1,2$，考虑先移动 $2$，再移动 $1$。假设元素自底向上为 $2,1$，则同时移动 $2,1$。
+如果有三个元素自底向上为 $3,1,2$，显然没有合法方案，所以 $f(6,5)=2$，同理 $f(5,6)=2$。
+对其他情况，可以先将栈 $(r,c)$ 的元素从小到大排序，然后依次分配 $f(i,j)$ 个元素给栈 $(i,j)$ 处理 $(i\ge r,j\ge c,i+j\gt r+c)$，于是有
+$$
+f(r,c)=\sum_{i\ge r,j\ge c,i+j\gt r+c}f(i,j)
+$$
+最后有 $f(1,1)\ge 40000$，所以一定存在合法方案。方案构造按上述方法即可。
+每个元素最多移动 $10$ 步，所以最多出现在 $10$ 个栈，所以总元素个数为 $O(10n)$，算上排序复杂度，总时间复杂度为 $O(10n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=4e4+5,N=6;
+int dp[N+1][N+1];
+int dfs1(int r,int c){
+	if(dp[r][c])return dp[r][c];
+	_rep(i,r,N)_rep(j,c,N){
+		if(i!=r||j!=c)
+		dp[r][c]+=dfs1(i,j);
+	}
+	return dp[r][c];
+}
+int a[MAXN],temp1[MAXN],temp2[MAXN],b[N+1][N+1];
+pair<int,int> p[MAXN];
+stack<int> st[N+1][N+1];
+void Move(int r1,int c1,int r2,int c2,int cnt){
+	while(r1<r2){
+		printf("%d %d D %d\n",r1,c1,cnt);
+		r1++;
+	}
+	while(c1<c2){
+		printf("%d %d R %d\n",r1,c1,cnt);
+		c1++;
+	}
+}
+void dfs2(int r,int c,int n){
+	if(n==0||(r==6&&c==6))return;
+	_for(i,0,n){
+		temp1[i]=temp2[i]=st[r][c].top();
+		st[r][c].pop();
+	}
+	if(r+c==11){
+		if(n==1)
+		Move(r,c,6,6,1);
+		else{
+			if(temp1[0]<temp1[1]){
+				Move(r,c,6,6,2);
+				st[6][6].push(temp1[1]);
+				st[6][6].push(temp1[0]);
+			}
+			else{
+				Move(r,c,6,6,1);
+				Move(r,c,6,6,1);
+				st[6][6].push(temp1[0]);
+				st[6][6].push(temp1[1]);
+			}
+		}
+		return;
+	}
+	sort(temp1,temp1+n);
+	int lpos=0;
+	_rep(i,r,N)_rep(j,c,N){
+		if(i==r&&j==c)continue;
+		int rpos=min(lpos+dp[i][j],n);
+		_for(k,lpos,rpos)
+		p[temp1[k]]=make_pair(i,j);
+		b[i][j]=rpos-lpos;
+		lpos=rpos;
+	}
+	_for(i,0,n){
+		int r2=p[temp2[i]].first,c2=p[temp2[i]].second;
+		Move(r,c,r2,c2,1);
+		st[r2][c2].push(temp2[i]);
+	}
+	for(int i=N;i>=r;i--)for(int j=N;j>=c;j--){
+		if(i==r&&j==c)continue;
+		dfs2(i,j,b[i][j]);
+	}
+}
+int main(){
+	int n=read_int();
+	_rep(i,1,n)
+	st[1][1].push(read_int());
+	dp[6][6]=1,dp[6][5]=dp[5][6]=2;
+	dfs1(1,1);
+	dfs2(1,1,n);
+//	while(!st[6][6].empty()){
+//		space(st[6][6].top());
+//		st[6][6].pop();
+//	}
 	return 0;
 }

CVBB ACM Team

用户工具

站点工具

差别

页面工具