2013
11-10

Fractal

A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same “type” of structures must appear on all scales.

A box fractal is defined as below :
• A box fractal of degree 1 is simply

X
• A box fractal of degree 2 is

X X

X

X X
• If using B(n – 1) to represent the box fractal of degree n – 1, then a box fractal of degree n is defined recursively as following
B(n - 1)        B(n - 1)
B(n - 1)
B(n - 1)        B(n - 1)

The input consists of several test cases. Each line of the input contains a positive integer n which is no greater than 7. The last line of input is a negative integer −1 indicating the end of input.

For each test case, output the box fractal using the ‘X’ notation. Please notice that ‘X’ is an uppercase letter. Print a line with only a single dash after each test case.

1
2
3
4
-1

X
-
X X
X
X X
-
X X   X X
X     X
X X   X X
X X
X
X X
X X   X X
X     X
X X   X X
-
X X   X X         X X   X X
X     X           X     X
X X   X X         X X   X X
X X               X X
X                 X
X X               X X
X X   X X         X X   X X
X     X           X     X
X X   X X         X X   X X
X X   X X
X     X
X X   X X
X X
X
X X
X X   X X
X     X
X X   X X
X X   X X         X X   X X
X     X           X     X
X X   X X         X X   X X
X X               X X
X                 X
X X               X X
X X   X X         X X   X X
X     X           X     X
X X   X X         X X   X X
-

//* @author: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
import java.util.Scanner;
class Main
{
static StringBuffer sb=new StringBuffer();
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
while(true)
{
int a=in.nextInt();
if(a==-1) break;
else if(a==1) System.out.println('X');
else g("",a-1);
System.out.println("-");
}
}

static void p(int a)
{
int t=(int)Math.pow(3, a-1);
for(int i=0;i< t;i++)
sb.append(" ");
}

static void g(String s,int a)
{
if(a==0)
{
sb.delete(0, sb.length()+1);
print(s);
System.out.println(sb.toString().subSequence(0, sb.lastIndexOf("X")+1));
return;
}
g(s+"A",a-1);
g(s+"B",a-1);
g(s+"A",a-1);

}

static void print(String s)
{
int l=s.length();
char c=s.charAt(0);
if(l==1)
{
if(c=='A') sb.append("X X");
else sb.append(" X ");
return;
}
if(c=='A')
{
print(s.substring(1));
p(l);
print(s.substring(1));
}
else
{
p(l);
print(s.substring(1));
p(l);
}
}
}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

2. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

3. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

4. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。