The Blocks Problem 题解

el/2024/5/21 22:17:23

The Blocks Problem

题目传送门 UVA - 101
刷刘大爷紫书的第二天

大致思路

这道题的大致思路应该比较明显,对每根柱子上的木块进行归位和转移两种操作
我的想法是用map存每个木块的在哪跟柱子上,再进行查找,归位和移动的操作

不过要主题原文的一句话
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal
command…

因为没注意到这句话我这题WA了四发,程序重写了两次

#include <bits/stdc++.h>
using namespace std;
map<int,int>book;
vector<int>pile[30];
string s1="move",s2="pile",s3="onto",s4="over",s5="quit";
int find_block(int num){int p=book[num];for (int i = 0; i < pile[p].size(); ++i) {if(pile[p][i]==num)return i;}
}
void clear_block(int num){int p=find_block(num);int q=book[num];for (int i = pile[q].size()-1; i >=p ; --i) {int l=pile[q][i];book[l]=l;pile[l].push_back(l);pile[q].pop_back();}
}
void move_block(int x,int y){int p=find_block(x);int q1=book[x];int q2=book[y];for (int i = p; i <pile[q1].size() ; ++i) {int l=pile[q1][i];book[l]=q2;pile[q2].push_back(l);}pile[q1].erase(pile[q1].begin()+p,pile[q1].end());
}
int main(){int a,b,n;cin>>n;for(int i=0;i<n;i++) {book[i] = i;pile[i].push_back(i);}string x,y;while(cin >>x && x != s5){cin>>a>>y>>b;if(book[a]==book[b])continue;if(x==s1){if(y==s3){clear_block(a);clear_block(b);move_block(a,b);}else{clear_block(a);move_block(a,b);}}else{if(y==s3){clear_block(b);move_block(a,b);}else{move_block(a,b);}}}for (int i = 0; i < n; ++i) {cout<<i<<":";for (int j = 0; j < pile[i].size(); ++j) {cout<<" "<<pile[i][j];}cout<<endl;}
}

http://www.ngui.cc/el/5239387.html

相关文章

多重背包的拆分问题

多重背包应该算是背包问题里面比较麻烦的一种了&#xff0c;基本思路就是拆分转化为01背包&#xff0c;进而套01背包的模版 今天在洛谷刷题的时候遇到一道题,是一个多重背包和完全背包的组合型问题 题目描述 爱与愁大神后院里种了n棵樱花树&#xff0c;每棵都有美学值Ci。爱…

D. a-Good String

传送门 题意 一个字符串如果长度为1 并且为’a’ 那么就是 a -good 字符串&#xff0c; 当长度大于1时&#xff0c; 需要满足 &#xff1a; 将总区间划分成一半&#xff0c; 其中一半全是a&#xff0c;另一半必须为b-good 字符串 以此类推 分析 这道题的做法比较直观&#…

大师 洛谷P4933

大师 题目链接 大师 题目描述 建筑大师最近在跟着数学大师ljt12138学数学&#xff0c;今天他学了等差数列&#xff0c;ljt12138决定给他留一道练习题。 ljt12138首先建了n个特斯拉电磁塔&#xff0c;这些电塔排成一排&#xff0c;从左到右依次标号为1到n&#xff0c;第i个…

C. Good String

传送门 分析 给你一串字符串&#xff0c;你可以擦去一部分字符&#xff0c;剩下一个字符串t,要求最后剩下的字符串t满足这样的性质&#xff1a;字符串&#x1d461;2&#x1d461;3…&#x1d461;&#x1d45b;−1&#x1d461;&#x1d45b;&#x1d461;1和字符串 &#x…

Travel 最短路

链接&#xff1a;https://ac.nowcoder.com/acm/problem/14292 来源&#xff1a;牛客网 题目描述 精灵王国有N座美丽的城市&#xff0c;它们以一个环形排列在Bzeroth的大陆上。其中第i座城市到第i1座城市花费的时间为d[i]。特别地&#xff0c;第N座城市到第1座城市花费的时间为…

飞行路线 |分层图初步学习

链接&#xff1a;https://ac.nowcoder.com/acm/problem/15073 来源&#xff1a;牛客网 题目描述 Alice和Bob现在要乘飞机旅行&#xff0c;他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务&#xff0c;设这些城市分别标记为0到n-1&#xff0c;一共有m种航…

设计密码 —— 状态机

来源&#xff1a;acwing 题目描述 你现在需要设计一个密码 S&#xff0c;S 需要满足&#xff1a; S 的长度是 N&#xff1b; S 只包含小写英文字母&#xff1b; S 不包含子串 T&#xff1b; 例如&#xff1a;abc 和 abcde 是 abcde 的子串&#xff0c;abd 不是 abcde 的子串…

A. Remove Smallest

传送门 分析 这道题的意思大概是说有一串数字&#xff0c;你每次可以取出两个数字x&#xff0c;y&#xff0c;但要求是x和y相差不能超过1&#xff0c;然后你可以任意删去一个数字&#xff0c;这种操作可以进行无数次。 给你一个数组&#xff0c;然后让你判断能不能通过这种操…

迷宫2 ——单调队列解决bfs问题

链接&#xff1a;https://ac.nowcoder.com/acm/problem/15196 来源&#xff1a;牛客网 题目描述 这是一个关于二维格子状迷宫的题目。迷宫的大小为N*M&#xff0c;左上角格子座标为(1,1)、右上角格子座标为(1,M)、左下角格子座标为(N,1)、右下角格子座标为(N,M)。每一格都用-…

D. 505

传送门 分析 这个道题的题意是给你一个n * m的01矩阵&#xff0c;然后可以更改矩阵中的数字&#xff0c;比如把0改成1&#xff0c;或者把1改成0&#xff0c;要求最后矩阵中没有任何一个边长为偶数的子矩阵中含有偶数个1&#xff0c;如果不含偶数边长的子矩阵&#xff0c;则不…