符号三角形
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 661 Accepted Submission(s): 317
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
飞机票：
http://acm.hdu.edu.cn/showproblem.php pid=2510
一开始 我木有思路想找规律 就写了几组数据没有发现规律 后来懒的不想去搜索打表
后来百度下都是打表法
但是百度后 回来暴搜 居然也卡了 没有写出来 很多细节不会处理 后来参考了人家代码才过了
发现自己需要使劲努力啊 加油吧骚年
把-‘-’当作1，‘+’当作0时；这样正好满足题意。
我们知道1^1=0; 1^0=1, 0^1=1 , 0^0=0;
然后可以做异或运算
上暴力代码
[cpp] #include
#include
int ans[30];
int a[30][30];//用于保存每个n的第一层的状态的中间过程
int count;//记录1的个数
void DFS(int n)
{
int i,j;
if(n>24) return ;
for(i=0;i<=1;i++)
{
a[1][n]=i;//只需要暴力第一行即可
count+=i;
for(j=2;j<=n;j++)
{
a[j][n-j+1]=a[j-1][n-j+1]^a[j-1][n-j+2];
count+=a[j][n-j+1];
}
if(count*2==n*(n+1)/2)
ans[n]++;
DFS(n+1);
count-=i;
for(j=2;j<=n;j++)
{
a[j][n-j+1]=a[j-1][n-j+1]^a[j-1][n-j+2];
count-=a[j][n-j+1];
}
}
}
int main()
{
int i,j,k,n;
memset(ans,0,sizeof(ans));
count=0;
DFS(1);
while(scanf("%d",&n)!=EOF)
{
if(!n) break;
printf("%d\n",ans[n]);
}
return 0;
}
#include
#include
int ans[30];
int a[30][30];//用于保存每个n的第一层的状态的中间过程
int count;//记录1的个数
void DFS(int n)
{
int i,j;
if(n>24) return ;
for(i=0;i<=1;i++)
{
a[1][n]=i;//只需要暴力第一行即可
count+=i;
for(j=2;j<=n;j++)
{
a[j][n-j+1]=a[j-1][n-j+1]^a[j-1][n-j+2];
count+=a[j][n-j+1];
}
if(count*2==n*(n+1)/2)
ans[n]++;
DFS(n+1);
count-=i;
for(j=2;j<=n;j++)
{
a[j][n-j+1]=a[j-1][n-j+1]^a[j-1][n-j+2];
count-=a[j][n-j+1];
}
}
}
int main()
{
int i,j,k,n;
memset(ans,0,sizeof(ans));
count=0;
DFS(1);
while(scanf("%d",&n)!=EOF)
{
if(!n) break;
printf("%d\n",ans[n]);
}
return 0;
}
提交代码：
[cpp] #include
using namespace std;
int result[24]={0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};
int main()
{
int n;
cin>>n;
while(n!=0)
{
cout<
}
return 0;
}
#include
using namespace std;
int result[24]={0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};
int main()
{
int n;
cin>>n;
while(n!=0)
{
cout<
}
return 0;
}