三角形打表

本文参考自：https://blog.csdn.net/hcx11333/article/details/54727036
https://blog.csdn.net/silenceneo/article/details/47776555

题目：链接：http://acm.hdu.edu.cn/showproblem.php?pid=2510

符号三角形

Problem Description
符号三角形的 第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同 。 n=7时的1个符号三角形如下:

Input
每行1个正整数n <=24,n=0退出.

Output
n和符号三角形的个数.

Sample Input
15
16
19
20
0

Sample Output
15 1896
16 5160
19 32757
20 59984

Source
ECJTU 2008 Autumn Contest

Recommend
lcy

思路：思路：观察规律，相同得‘+’，不同得‘-’，跟异或运算很相似，可用0代表‘+’，1代表‘-’。第一层有n位，n不大于24，因此可用n位二进制数来表示当前一层的状态，数位上的0和1分别代表相应的符号，求下一层的状态时只需要当前层的各位数字两两异或即可组成下一层的状态，每向下一层，位数就减一。

由于n位二进制数共有2的n次方种情况，先求出最大的一种即2^n-1，然后依次-1枚举到0即可。二进制不熟练，还有多重循环，写的时候晕头转向，还好写对了。

原文：https://blog.csdn.net/hcx11333/article/details/54727036

打表代码：

#include<cmath>
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define scac(x) scanf("%c",&x)
#define sca(x) scanf("%d",&x)
#define sca2(x,y) scanf("%d%d",&x,&y)
#define sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scl(x) scanf("%lld",&x)
#define scl2(x,y) scanf("%lld%lld",&x,&y)
#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define pri(x) printf("%d\n",x)
#define pri2(x,y) printf("%d %d\n",x,y)
#define pri3(x,y,z) printf("%d %d %d\n",x,y,z)
#define prl(x) printf("%lld\n",x)
#define prl2(x,y) printf("%lld %lld\n",x,y)
#define prl3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
#define ll long long
#define LL long long
#define read read()
#define pb push_back
#define mp make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(1.0)
#define eps 1e-6
#define inf 1e17
#define INF 0x3f3f3f3f
#define N 205
const int maxn = 1e5+5;
int ans[25],a[25];//一个记录结果，一个记录中间状态
int main(){
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=24;++i){//最外层决定顶层位数
        a[1]=(1<<i)-1;//最大值
        while(a[1]>=0){//最大值开始往下枚举每一层
            for(int j=2;j<=i;++j){
                a[j]=0;
                for(int k=0;k<(i-j+1);++k){
                    a[j]|=((((a[j-1]>>k)&1)^((a[j-1]>>(k+1))&1))<<k);
                }
            }
            int cnt1=0,cnt2=0;//计数
            for(int j=1;j<=i;++j){//遍历每一层的状态
                for(int k=0;k<i-j+1;++k){//统计当前层
                    if((a[j]>>k)&1)++cnt1;
                    else ++cnt2;
                }
            }
            if(cnt1==cnt2) ++ans[i];
            --a[1];
        }
    }
    for(int i=1;i<25;++i)
        printf("%d\n",ans[i]);
}

真正的场上代码:

#include<bits/stdc++.h>
using namespace std;
#define INF  0x3f3f3f3f
typedef long long  LL;
int main(){
    int n,ans[25]={0,0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};
    while(scanf("%d",&n),n){
        printf("%d %d\n",n,ans[n]);
    }