用户工具

站点工具


2020-2021:teams:legal_string:组队训练比赛记录:contest11

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:legal_string:组队训练比赛记录:contest11 [2021/08/06 11:54]
jxm2001
2020-2021:teams:legal_string:组队训练比赛记录:contest11 [2021/08/08 14:06] (当前版本)
jxm2001
行 4: 行 4:
  
 ^  题目 ​ ^  蒋贤蒙 ​ ^  王赵安 ​ ^  王智彪 ​ ^ ^  题目 ​ ^  蒋贤蒙 ​ ^  王赵安 ​ ^  王智彪 ​ ^
-|  B  |  2  |  ​ ​| ​ 0  |  +|  B  |  2  |  ​ ​| ​ 0  |  
-|  D  |  ​ ​| ​ 0  |  ​ |  +|  D  |  ​ ​| ​ 0  |  ​ |  
-|  E  |  2  |  0  |  ​ ​| ​+|  E  |  2  |  0  |  ​ ​| ​
 |  G  |  0  |  0  |  0  |  |  G  |  0  |  0  |  0  | 
 |  I  |  0  |  0  |  0  |  |  I  |  0  |  0  |  0  | 
-|  J  |  2  |  0  |  ​ |  +|  J  |  2  |  0  |  ​ |  
-|  L  |  2  |  0  |  ​ ​| ​+|  L  |  2  |  0  |  ​ ​| ​
  
 ====== 题解 ====== ====== 题解 ======
行 100: 行 100:
  }  }
  enter(ans);​  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;  return 0;
 } }
2020-2021/teams/legal_string/组队训练比赛记录/contest11.1628222070.txt.gz · 最后更改: 2021/08/06 11:54 由 jxm2001