BZOJ1258 [CQOI2007]三角形
2024-08-27 07:24:27
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
T34
T4
HINT
50%的数据满足:1<=n<=5
100%的数据满足:1<=n<=50
题解
如果最后一个数是4,那么直接把它改成1,2,3输出。
否则,可以发现一个三角形最多靠在三个三角形上,即每条边最多靠在一个三角形上。
从后往前看输入序列,最右面的1对应了左面那条边靠着的三角形,即把它后面的去掉,再把它改成4,如T312靠在T34上;
2和3同理。
附代码:
#include <cstdio>
#include <cstring>
int f[3], n;
char s[1000];
void outPut() {
s[n] = '\0';
printf("%s4\n", s);
}
int main() {
scanf("%s", s);
n = strlen(s);
if (s[n - 1] == '4') {
s[n - 1] = '\0';
printf("%s1\n%s2\n%s3\n", s, s, s);
return 0;
}
int a;
while (--n)
if (!f[a = s[n] - '1']) {
outPut();
f[a] = 1;
}
return 0;
}
最新文章
- IIS8 使用FastCGI配置PHP环境支持 过程详解
- Java中获取键盘输入值的三种方法
- iOS-Gdata XML解析配置和简单使用
- 百思不得骑姐的问题——难道是控件的bug?
- Linux功能-环境变量
- SPOJ TEMPLEQ - Temple Queues(二分查找+树状数组)
- Android 国际化字符串资源,各语言目录表及从字符串资源文件读字符方法
- CREATE PROCEDURE
- asp.net linq查询环境搭建
- POJ 3692:Kindergarten(最大的使命)
- 设置span 宽度的完美解决方案
- #pragma mark指令的作用
- webpack的Hot Module Replacement运行机制
- SQL Server数据库漏洞评估了解一下
- spark优化整理
- 48- java Arrays.sort和collections.sort()再次总结
- html 网页生产pdf文件
- python获取时间————前一天后一天前一小时后一小时前一分钟后一分钟
- java appium webview切换处理
- Java设计模式(3)建造者模式(Builder模式)