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

HK酋长 lv.1

发布时间：2022-10-27 02:09:20 365

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;
}

文章来源： https://blog.51cto.com/u_15724837/5792634

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。