2023年天梯赛复盘（剪切复制、分寝室、堆宝塔）_天梯赛分寝室

剪切复制（字符串）

 思路：此题需要掌握一定的字符串的函数的使用。erase函数、substr函数、find函数、insert函数

AC代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
string s,s1,s2,s3;
int n,a,b;
int main(int argc, char** argv) {
	cin>>s>>n;
	while(n--)
	{
		cin>>a>>b>>s1>>s2;
		s3=s.substr(a-1,b-a+1); //在字符串s中的a位置开始复制b-a+1的长度的子串
		s.erase(s.begin()+a-1,s.begin()+b);//s字串从a-1到b删除 
		int len=s1.length();
		s1+=s2;//拼接字串s1和s2赋值给S1，合在一起珊 
		int pos = s.find(s1);//在字符串s中寻找S1
		if(pos!=-1)  s.insert(pos+len,s3);//找到了，相应位置插入子串S3
		else s.insert(s.length(),s3);//没有找到，在末尾插入子串3 
	}
	cout<<s;
	return 0;
}

分寝室（暴力法）

思路：先将可能的寝室人数写入一个数组（因为要求相同性别的寝室人数都要一致，所以总人数/寝室人数一定是整除的），再遍历某个性别可能的寝室人数数组，二层遍历另一个性别可能的寝室人数，判断是否满足刚好分完寝室的要求即可，在二层遍历中用一个minn标记不同性别寝室人数之差，记录最小的，最终遍历结束答案也就出来了。
注意有可能没有答案，所以用来记录最小寝室人数之差的字符也可以作为有没有答案的标记。也就是ans1=0和ans2=0的时候，是没有答案的。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
int a[N],b[N];
int n0,n1,n;
int main(int argc, char** argv) {
	cin>>n0>>n1>>n;
	int p1=0,p2=0;
	for(int i=2;i<=n0;i++) //存储每间寝室可能住的人数
	{
		if(n0%i==0)
		{
			a[p1++]=i;
		}
	}
	for(int i=2;i<=n1;i++)
	{
		if(n1%i==0)
		{
			b[p2++]=i;
		}
	 } 
	int minn = 1000000000;
	int ans1=0,ans2=0;
	//暴力法 
	 for(int i=0;i<p1;i++)
	 {
	 	if(n0/a[i]<=n)
	 	{
	 		for(int j=0;j<p2;j++)
	 		{
 
	 				if(n0/a[i]+n1/b[j]==n)
	 				{
	 					if(minn>abs(a[i]-a[j]))
	 					{
	 						ans1=a[i];
	 						ans2=b[j];
	 						minn=abs(a[i]-b[j]);
						 }
					 }
			 }
		}
	 }
	 if(ans1==0&&ans2==0)  cout<<"No Solution";
	 else  cout<<n0/ans1<<" "<<n1/ans2;
	return 0;
}

堆宝塔（模拟栈）

堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小，按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下：

首先准备两根柱子，一根 A 柱串宝塔，一根 B 柱用于临时叠放。
把第 1 块彩虹圈作为第 1 座宝塔的基座，在 A 柱放好。
将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下，如果比最上面的小，就直接放上去；否则把 C 跟 B 柱最上面的彩虹圈比一下：
    如果 B 柱是空的、或者 C 大，就在 B 柱上放好；
    否则把 A 柱上串好的宝塔取下来作为一件成品；然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上，最后把 C 也放到 A 柱上。

重复此步骤，直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品，B 柱上剩下的彩虹圈被逐一取下，堆成另一座宝塔。问：宝宝一共堆出了几个宝塔？最高的宝塔有多少层？
输入格式： 

输入第一行给出一个正整数 N（≤103），为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数，对应每个彩虹圈的直径。
输出格式：

在一行中输出宝宝堆出的宝塔个数，和最高的宝塔的层数。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：

11
10 8 9 5 12 11 4 3 1 9 15

输出样例：

4 5

样例解释：

宝宝堆成的宝塔顺次为：

10、8、5
12、11、4、3、1
9
15、9
思路：就是用栈模拟上述过程即可，size是栈的长度，push是进栈，pop弹出栈顶，empty判断栈是否为空。

AC代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
stack<int> a,b;
int maxn;
int main(int argc, char** argv) {
	int n,c;
	cin>>n>>c;
	a.push(c);
	int cnt=0;
	for(int i=1;i<n;i++)
	{
		cin>>c;
		if(a.top()>c) a.push(c);
		else if(b.empty()||c>b.top()) b.push(c);
		else
		{
			cnt++;
			maxn=max(maxn,(int)a.size());
			while(!a.empty()) a.pop();
			while(!b.empty()&&b.top()>c) a.push(b.top()),b.pop();
			a.push(c);
		}
	}
	cnt++;
	maxn=max(maxn,(int)a.size());
	if(!b.empty()) cnt++,a.push(b.top()),b.pop();
	maxn=max(maxn,(int)a.size()); 
	cout<<cnt<<" "<<maxn;
	return 0;
}