蓝桥杯2015年第六届真题-机器人塔 （C语言代码）大量解释

解题思路:

题意：A的下面只能AA或BB，B的下面只能是AB或BA（各位想到二进制的异或没有）；

如果：有1个A和2个B，那么有三种方案：

那么就可以用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;
}