咖啡


私信TA

用户名:Tianxn

访问量:13797

签 名:

人一我百,人十我万

等  级
排  名 14
经  验 8591
参赛次数 1
文章发表 124
年  龄 22
在职情况
学  校 西安航空学院
专  业 软件工程

  自我简介:

解题思路:

题意:A的下面只能AA或BB,B的下面只能是AB或BA(各位想到二进制的异或没有);

如果:有1个A和2个B,那么有三种方案:

 


                     A(0 =1 ^ 1)
                                       B(1)                     ^B(1)

                     B(1 = 0 ^ 1)
                                       A(0)                     ^B(1)

                     B(1 = 1 ^ 0)
                                       B(1)                     ^A(0)

那么就可以用0代表A,1代表B;

还要一点要说,题目的意思是从下向上摆(下面多上面少),为了写程序方便(二维数组从一行开始),我们从从上向下摆,显然结果是一样的。

注意:下面是按反过了的模型说的(倒三角型))

那么只要知道第一行的数据,就可以依次更新下面的数据(反对角线方向从上向下);也就是说只用枚举一行的所有可能就可以了,第2行开始的结果都是根据上一行来的。

如何枚举一行:第一行每一个位置不是1就是0,每一个位置每次从0开始枚举,到1结束;枚举方向从左到右;

例如:拿样例来说吧:1个A,2个B也就是1个0,2个1;

(注意:这里枚举0,1是在第一行,其他行都是根据第一行来更新的)

0              // 第一行第一个位置为0,此时不用更新


0 0           // 第一行第二个位置为0,此时更新第二行

1              // 不合格(约束:1个0)


0 1           // 第一行第二个位置为1,此时更新第二行

1              // 合格,方案数加一


1             // 第一行第一个位置为1,此时不更新


1 0          // 第一行第二个位置为0,此时更新

1             // 合格,方案数加1


1 1         //  第一行第二个位置为1,此时更新                                

0            // 合格,方案数加1

此时已经枚举完毕,总方案数为3。

(注意:一直都是枚举的第一行的每一种方案,其他行都是根据第一行更新得到的)


如何统计A,B的个数(也就0,1的个数):加入用cnt计数,每次枚举的时候直接cnt+=枚举的那个位置上的数,如果是1那就加上了,是0就相当于没加,那这不就是统计了1的个数吗!! 0的个数用当前规模的总个数减去1的个数就可以了。


注意事项:


题目中提到:测试数据都合法。也就是说可以算出一行都多少个数字;

*    *    *     *

*    *    *

*    * 

*

上面的这个图,就是每次更新的范围,所有*的总个数就是A,B的总和;

在知道了A,B的个数之和,就可以算出第一行有几个数(人);

怎么算?? ::: 等差数列求和,公差为1;前n项和就是 (1 + n)* n / 2 

假设第一行只有一个数(x=1),计算以边前n项和看是否相等,如果相等那么第一行就有x个数,如果不x+1

,然后看是否相等,最后就得到了第一行能放几个数(x)。



注意:题目的要点就是枚举第一行有多少种可能,每种情况用来去更新其他行。

参考代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 510;

int m; // A的个数(即0的个数)
int n; // B的个数(即1的个数) 
int p[N][N]; // c存放当前的摆放方案 
int cnt; // 当前B的个数(即1的个数) 
int x = 1; // 第一行最多有多少个人 
ll ans; // 总的方案数 

void dfs(int cur) {
        // 0和1的个数大于给定的个数,直接返回上一层
	if(cnt > n || cur * (cur + 1) / 2 - cnt > m) return ;
	if(cur == x) {
		ans++;
		return ;
	}
	for(int i = 0; i < 2; ++i) {
		p[0][cur] = i;
		cnt += i; // 加号的数量
		for(int j = 1; j <= cur; ++j) { // 更新受影响的位置
			p[j][cur - j] = p[j - 1][cur - j] ^ p[j - 1][cur - j + 1];
			cnt += p[j][cur - j];
		}
		dfs(cur + 1); // 去下一个位置
		for(int j = 1; j <= cur; ++j) cnt -= p[j][cur - j]; // 回溯
		cnt -= i; // 回溯
	}
}

int main() {
	scanf("%d%d", &m, &n);
	while(x * (x + 1) / 2 != m + n) x++; // 第一行有多少个数字(题目中的人)
	dfs(0);
	printf("%lld\n", ans);
	return 0;
}


C语言网提供「C语言、C++、算法竞赛」在线课程,全部由研发工程师或ACM金牌退役选手亲自授课,以视频+配套题目的学练同步模式教学,强化动手,并提供增值服务!

  评论区