符號三角形
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<stdio.h>
#include<string.h>
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<stdio.h>
#include<string.h>
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 <iostream>
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<<n<<" "<<result[n-1]<<endl;
cin>>n;
}
return 0;
}
#include <iostream>
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<<n<<" "<<result[n-1]<<endl;
cin>>n;
}
return 0;
}
