题解 P4536 【[CQOI2007]三角形】

· · 题解

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}