济南手机网站建设,大连网页建站模板,设计师导航网址,石龙东莞网站建设Codeforces Gym 101173 CERC 16 D BZOJ 4790 Dancing Disks 强烈安利这道构造题目#xff0c;非常有意思。
这里用到的思想是归并排序#xff01;
多路归并排序#xff01;
我们这样想#xff0c;假设6*6的网格中除了最后一个网格外#xff0c;其他的凡是有元素…Codeforces Gym 101173 CERC 16 D BZOJ 4790 Dancing Disks 强烈安利这道构造题目非常有意思。
这里用到的思想是归并排序
多路归并排序
我们这样想假设6*6的网格中除了最后一个网格外其他的凡是有元素的格子中这些元素都是严格有序的。
也就是说在每个rod上从栈顶到栈底是严格单调递减的那么我们可以模仿归并排序的思想从这些rods里面选取一个最大的放在最后一个网格上并把它从原rod里面删除掉然后再取这些rods里面最大的放到最后一个网格上这样的话是不是就是归并排序的思想。最后这个网格在操作完成后将是严格单调递减的。即满足了要求。
现在我们的任务是把其他的格子都变成单调递增的。那么怎么办呢
递归呀
那么我们的思路就有了。
但是这里要注意一个问题就是说(1,2)和(2,1)这两个格子实际上可以构造出size为2的有序序列。这样下去第6*6个格子足够构造40000多个数字的有序序列。
代码 #include bits/stdc.h
using namespace std;
const int MAXN 1e5;
const int INF 1e9;
stackint rods[7][7];
int arr[MAXN];
int n;
vectorint opx;
vectorint opy;
vectorchar opt;
vectorint opn;
int merge(int x,int y, int op){if(x y 3){if(rods[1][1].size() 2){int top1 rods[1][1].top();rods[1][1].pop();int top2 rods[1][1].top();rods[1][1].pop();if((top1 top2) ^ op){ //op 0 inc,op 1 decrods[x][y].push(top1);rods[x][y].push(top2);opx.push_back(1);opy.push_back(1);opt.push_back(x 1?R:D);opn.push_back(1);opx.push_back(1);opy.push_back(1);opt.push_back(x 1?R:D);opn.push_back(1);}else{rods[x][y].push(top2);rods[x][y].push(top1);opx.push_back(1);opy.push_back(1);opt.push_back(x 1?R:D);opn.push_back(2);}return 2;}else if(rods[1][1].size() 1){int top1 rods[1][1].top();rods[1][1].pop();rods[x][y].push(top1);opx.push_back(1);opy.push_back(1);opt.push_back(x 1?R:D);opn.push_back(1);return 1;}else{return 0;}}int nums[7][7];memset(nums,0,sizeof(nums));for(int i 1;i x;i){for(int j 1;j y;j){if((i ! x || j ! y) (i ! 1 ||j ! 1)){nums[i][j] merge(i,j,!op);}}}if(!rods[1][1].empty()){nums[1][1] 1;}//merge itint cur_cnt 0;int pos_x 0;int pos_y 0;int pos_max op * INF; int flag 1;while(flag){flag 0;for(int i 1;i x;i){for(int j 1;j y;j){if(i x j y) continue;if(!nums[i][j]) continue;if((pos_max rods[i][j].top()) ^ op){ // op 0 incpos_max rods[i][j].top();pos_x i;pos_y j;}}}if(pos_max ! op * INF){pos_max op * INF;flag 1;cur_cnt;rods[x][y].push(rods[pos_x][pos_y].top());rods[pos_x][pos_y].pop();nums[pos_x][pos_y]--;for(int i pos_y;i y;i){opx.push_back(pos_x);opy.push_back(i);opt.push_back(R);opn.push_back(1);}for(int i pos_x;i x;i){opx.push_back(i);opy.push_back(y);opt.push_back(D);opn.push_back(1);}}}return cur_cnt;
}
int main(){scanf(%d,n);for(int i 1;i n;i){scanf(%d,arr[i]);rods[1][1].push(arr[i]);}merge(6,6,0);for(int i 0;i opx.size();i){printf(%d %d %c %d\n,opx[i],opy[i],opt[i],opn[i]);}return 0;
}
