自动搬运

查看原文

来自洛谷，原作者为

	RedreamMer 一拍桌子，两眼放光，三十分钟，四百分贝，五指指天，六重积分，七次反演，八维凸包，九只 log，十种做法，全部假啦！！！

搬运于2025-08-24 22:01:06，当前版本为作者最后更新于2020-02-29 12:15:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P4536题解

思路：模拟

Solution

因为三角形只有三边，所以与它相邻的三角形的个数不会大于3，那或许有人会问，图2中"T4"不是靠在周围的6个三角形上吗？

题目中说：如果B不包含A，且A的某一条完整的边是B的某条边的一部分，则我们说A靠在B的边上。

也就是说，三角形只能靠在比自己大的三角形上。

然后我们可以这样来考虑：

如果是以三角形编号为"T...4"，那与他相邻的一定是"T...1"、"T...2"、"T...3"。

否则，我们首先可以保证这个三角形的编号里不会出现"4"，我们可以从编号的第一位（不是"T"）开始：

1. 如果这一位上的数字为"1"，则它靠下面的三角形就是"T...4";

2. 如果这一位上的数字为"2"，则它靠右边的三角形就是"T...4"；

3. 如果这一位上的数字为"3"，则它靠左边的三角形就是"T...4"；

如果没有更新靠在某一边上的三角形，那原靠在那条边上的三角形就一直靠在边上。

不断一位一位更新靠在这个三角形边上的三角形，最后即为答案。

Code

#include<bits/stdc++.h>
using namespace std;
string s,ss[3];
int len;
int main() {
	cin>>s;
	len=s.size()-1;
	if(s[len]=='4') {//特判末尾是不是特殊的三角形 
		cout<<s.substr(0,len)<<1<<endl<<s.substr(0,len)<<2<<endl<<s.substr(0,len)<<3;
		return 0;
	}
	for(int i=1; i<=len; i++) {
		if(s[i]=='1')
			ss[0]=s.substr(0,i)+"4";//更新靠在下面的三角形 
		else if(s[i]=='2')
			ss[1]=s.substr(0,i)+"4";//更新靠在左边的三角形 
		else if(s[i]=='3')
			ss[2]=s.substr(0,i)+"4";//更新靠在右边的三角形 
	}
	sort(ss,ss+3); 
	for(int i=0; i<=2; i++)
		if(ss[i][0]=='T')//判断这条边上有没有三角形靠着 
			cout<<ss[i]<<endl;
	return 0;
}

$\color{blue}\text{My Blog}$