UC知道杭电ACM2510题怎么解
来源：百度知道 编辑：UC知道 时间：2024/09/24 22:11:31
请大牛告诉我方法和思路
关于举办杭州电子科技大学第八届大学生程序设计竞赛暨2009年浙江省大学生程序设计竞赛集训队选拔赛的通知
符号三角形
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 74 Accepted Submission(s): 39
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
关于举办杭州电子科技大学第八届大学生程序设计竞赛暨2009年浙江省大学生程序设计竞赛集训队选拔赛的通知
符号三角形
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 74 Accepted Submission(s): 39
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
想法:
1.三角形的变化以最上面那一条资料串决定共有2^n种变化
2.+,-符号合并的动作为xor的运算
3.基於2.以直接数值一个bit(0,1)取代+,-符号(题目最多为24bit);
4.向下合并动作就等同於 数值像左位移 1 再 xor 原数值
5.在合并过程中计算出含1的数量做比较即可
下面范例只做一次,要达上面功能小改就可以了
int cal_pix_line(long up ,int n,int dsize){
int i , j , count ;
long cmp ;
for( i = 0 , count = 0 ; i < n ; n-- ){
cmp = up ;
for( j = 0 ; j < n ; j++ , cmp >>= 1 ){
count += ( cmp & 1 ) ;
}
up = (up >> 1) ^ up ;
}
if( (count << 1) == dsize )
return 1 ;
return 0 ;
}
int main(){
int i , test_size , dsize , n , all ;
scanf("%d",&n);
dsize = ( ( n + 1 ) * n ) >> 1 ;
test_size = 1 << n ;
all = 0 ;
for( i = 0 ; i < test_size ; i++ ){
all += cal_pix_line( i , n , dsize );
}
printf("%d\n",all);
}