BZOJ 1258([CQOI2007]三角形tri-模拟)

1258: [CQOI2007]三角形tri

Time Limit: 5 Sec   Memory Limit: 162 MB

Submit: 287  

Solved: 165

[​​Submit​​][​​Status​​][​​Discuss​​]

Description

画一个等边三角形，把三边的中点连接起来，得到四个三角形，把它们称为T1,T2,T3,T4，如图1。把前三个三角形也这样划分，得到12个更小的三角形：T11,T12,T13,T14,T21,T22,T23,T24,T31,T32,T33,T34，如图2。把编号以1，2，3结尾的三角形又继续划分…最后得到的分形称为Sierpinski三角形。

 图1. 图2. 如果B不包含A，且A的某一条完整的边是B的某条边的一部分，则我们说A靠在B的边上。例如T12靠在T24和T4上，但不靠在T32上。给出Spierpinski三角形中的一个三角形，找出它靠着的所有三角形。

Input

输入仅一行，即三角形的编号，以T开头，后面有n个1到4的数字。仅最后一个数字可能为4。

Output

输出每行一个三角形编号，按字典序从小到大排列。

Sample Input

T312

Sample Output

T314
T34
T4

HINT

50%的数据满足：1<=n<=5
100%的数据满足：1<=n<=50

Source

在纸上画画发现，

Txxxx4: Txxxx1 Txxxx2 Txxxx3

TxxxxK: T..1 T..2 T..3 （可能没有）

flag表示当前方向是否连通

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define MAXN (50+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}

char s[MAXN];
void pri(int len,int x) {
putchar('T');
Rep(i,len) printf("%c",s[i]);
printf("%d\n",x);
}
bool flag[10]={0};

int main()
{
// freopen("bzoj1258.in","r",stdin);
// freopen(".out","w",stdout);

scanf("T%s",s);
int n=strlen(s);

if (s[n-1]=='4') {
For(i,3) pri(n-1,i);
return 0;
}
flag[s[n-1]-'0']=1;
pri(n-1,4);
RepD(i,n-2) {
if (!flag[s[i]-'0'])
{
flag[s[i]-'0']=1;
pri(i,4);
}
}



return 0;
}