蓝桥杯2015年第六届真题-机器人塔

题目

题目链接

题解

DFS+二进制枚举。

经典dfs之一。

好像比较经典的那个同型dfs题叫“符号三角形”？

可以看出上面一行的安排方式均由下面一行的安排方式决定，因此我们只要定好最后一行，那么上面的安排方式均可以由下行推出，且最后一行固定则整个三角形安排方式唯一。

我们用 0 0 0表示 A A A， 1 1 1表示 B B B，这是由 A A A和 B B B出现的条件导致的，当两个字母一致时可以放 A A A，当两个字母不一样时放 B B B，这与异或运算不谋而合，因此 0 0 0表示 A A A， 1 1 1表示 B B B时有，A^A = B^B = A、B^A = A^B = B； 我们二进制枚举最后一行的状态，再通过dfs得到上面三角形的安排方式，若能到达第一行且 A A A和 B B B的个数满足输入，则说明找到一种方案，方案数+1； dfs中我们还可以适当剪枝以降低时间复杂度。当已经安排好的几行的 B B B的总数已经超过了输入的要求，则可以直接返回，无需继续以此状态深搜下去了；又或者，当已经安排好的几行的 B B B的总数过少，少到什么程度呢？少到即使上面未被搜索到的小三角形全填 B B B也无法达到输入的要求，则也可以直接返回无需深搜。

代码

#include
using namespace std;
const int N = 1010;

int a, b, n, ans, arr[N][N]; // a[i][j]表示第i行第j个是A还是B，0表示A，1表示B。AB是由哪个数字表示主要是由二者出现的条件决定。 

void dfs(int row, int sumb) {
	
	if(row == 1) {
		if(sumb == b) ans ++; 
		return ;
	}
	
	for(int i = 1;i  b || (row-2)*(row-1)/2 + sumb >a>>b;
	n = sqrt(a+b