题解 P2790 【ccj与zrz之积木问题】
本蒟蒻第一次发题解
日本的蒟蒻还没有吃过呢
先说下本题思路
首先用n个动态队列vector
然后先将每个数先存入这n个动态队列中
分别在这n个队列中经过四个操作，最后输出（后面细讲）
0.findd函数
用暴力先搜索出某个值的位置，方便以后的函数调用
代码如下
void findd(int a,int &p,int &h){//查找原值的位置（"&"可改变原值）
for(int i=0;i<n;i++){
for(int j=0;j<v[i].size();j++){
if(v[i][j]==a)p=i,h=j;//p为队列的指针，h为该数在队列中的位置
}
}1.move_onto函数
先定义p，h然后用以上的findd函数找到a的位置；
将a的高度h以上的木块全部归位
v[p][i]就是v[p][i]的原位，归位即为把v[p][i]放到队列v[v[p][i]]里，然后弹出队列v[p]中的尾位（指针一定要从队尾开始，因为队列中的元素只能从队尾弹出）
void move_onto(int a,int b){
int p,h;
findd(a,p,h);
for(int i=v[p].size()-1;i>h;i--){
v[v[p][i]].push_back(v[p][i]);//把v[p][i]放到队列v[v[p][i]]里
v[p].pop_back();//弹出队列v[p]中的尾位
}
v[p].pop_back();//弹出a
findd(b,p,h);
for(int i=v[p].size()-1;i>h;i--){
v[v[p][i]].push_back(v[p][i]);//把v[p][i]放到队列v[v[p][i]]里
v[p].pop_back(); //弹出队列v[p]中的尾位
}
v[p].push_back(a);//在b的上方推入a
}2.move_over函数
与move_onto函数类似
void move_over(int a,int b){
int p,h;
findd(a,p,h);
for(int i=v[p].size()-1;i>h;i--){
v[v[p][i]].push_back(v[p][i]);//把v[p][i]放到队列v[v[p][i]]里
v[p].pop_back();//弹出队列v[p]中的尾位
}
v[p].pop_back();//弹出a
findd(b,p,h);//找到b的位置
v[p].push_back(a);//在b的上方推入a
}3.pile_onto函数
归位类似move_onto函数
将a上方的木块移至b上面的操作如下：
在b所在的队列v[pb]里按 正序 推入队列v[pa]中a以上的元素
这里有几点容易错的地方：
（1）注意不能像原来一样倒序推入，题目要求a及上面的木块 整体 摞在b上面，如果倒序推入，则顺序颠倒，这里我也错了好几次
（2）不能同时一边弹出v[pa]队列中的数,一边将v[pa]的数推入v[pb]（如第一个for循环中），因为一个是按倒序弹出，一个是正序推入v[pb],会出错
（3）还有最后单独弹出v[pa]中的数时，一定要先用一个变量记录v[pa]的长度，因为随着v[pa]中数的弹出，v[pa]的长度也会缩短（当然此时i倒序时就不用考虑这个问题，即
for(int i=v[pa].size()-1;i>ha;i--)）
void pile_onto(int a,int b){
int pa,ha,pb,hb;
findd(a,pa,ha);
findd(b,pb,hb);
for(int i=v[pb].size()-1;i>hb;i--){
v[v[pb][i]].push_back(v[pb][i]);
v[pb].pop_back();
}
for(int i=ha;i<=v[pa].size()-1;i++)
v[pb].push_back(v[pa][i]);//按正序推入队列
int u=v[pa].size()-1;
for(int i=ha;i<=u;i++)
v[pa].pop_back();//弹出队列
}4.pile_over函数
类似于pile_onto函数
void pile_over(int a,int b){
int pa,ha,pb,hb;
findd(a,pa,ha);
findd(b,pb,hb);
for(int i=ha;i<=v[pa].size()-1;i++)
v[pb].push_back(v[pa][i]);//按正序推入队列
int u=v[pa].size()-1;
for(int i=ha;i<=u;i++)
v[pa].pop_back();//弹出队列
}5.out函数（输出函数）
很简单吧，就不多说了
接下来是完整代码
#include<bits/stdc++.h>//万能头
using namespace std;
#define MAXN 26
vector<int>v[MAXN];
int n;
void findd(int a,int &p,int &h){
for(int i=0;i<n;i++){
for(int j=0;j<v[i].size();j++){
if(v[i][j]==a)p=i,h=j;
}
}
void move_onto(int a,int b){
int p,h;
findd(a,p,h);
for(int i=v[p].size()-1;i>h;i--){
v[v[p][i]].push_back(v[p][i]);
v[p].pop_back();
}
v[p].pop_back();
findd(b,p,h);
for(int i=v[p].size()-1;i>h;i--){
v[v[p][i]].push_back(v[p][i]);
v[p].pop_back();
}
v[p].push_back(a);
}
void move_over(int a,int b){
int p,h;
findd(a,p,h);
for(int i=v[p].size()-1;i>h;i--){
v[v[p][i]].push_back(v[p][i]);
v[p].pop_back();
}
v[p].pop_back();
findd(b,p,h);
v[p].push_back(a);
}
void pile_onto(int a,int b){
int pa,ha,pb,hb;
findd(a,pa,ha);
findd(b,pb,hb);
for(int i=v[pb].size()-1;i>hb;i--){
v[v[pb][i]].push_back(v[pb][i]);
v[pb].pop_back();
}
for(int i=ha;i<=v[pa].size()-1;i++)
v[pb].push_back(v[pa][i]);
int u=v[pa].size()-1;
for(int i=ha;i<=u;i++)
v[pa].pop_back();
}
void pile_over(int a,int b){
int pa,ha,pb,hb;
findd(a,pa,ha);
findd(b,pb,hb);
for(int i=ha;i<=v[pa].size()-1;i++)
v[pb].push_back(v[pa][i]);
int u=v[pa].size()-1;
for(int i=ha;i<=u;i++)
v[pa].pop_back();
}
void out()
{
for(int i=0;i<n;i++)
{
cout<<i<<":";
if(v[i].empty())
{
cout<<endl;
continue;
}
for(int j=0;j<v[i].size();j++)
cout<<" "<<v[i][j];
cout<<endl;
}
}
char s1[10],s2[10];
int a,b;
signed main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
{
v[i].push_back(i);
}
while(1)
{
scanf("%s",s1);
if(strcmp(s1,"quit")==0)break;
scanf("%d%s%d",&a,s2,&b);
int wa,wb,ha,hb;
findd(a,wa,ha);
findd(b,wb,hb);
if(wa==wb)continue;
if(strcmp(s1,"move")==0&&strcmp(s2,"onto")==0)move_onto(a,b);//判断字符串是否相等
if(strcmp(s1,"move")==0&&strcmp(s2,"over")==0)move_over(a,b);
if(strcmp(s1,"pile")==0&&strcmp(s2,"onto")==0)pile_onto(a,b);
if(strcmp(s1,"pile")==0&&strcmp(s2,"over")==0)pile_over(a,b);
}
out();
return 0;
}望洛谷通过