首页 > ACM题库 > HDU-杭电 > HDU 3545-Board Coloring[解题报告]HOJ
2014
11-05

HDU 3545-Board Coloring[解题报告]HOJ

Board Coloring

问题描述 :

HH is painting a board of size 4 * N. You can assume the color of square (X, Y) on the board is Ax,y which is an integer between 0 and 255. For the beauty of the board, HH decide to paint the board following the rules :
1) Ax,y >= Ax,y-1.
2) For some given pairs of (X1, Y1) (X2, Y2), AX1,Y1 = AX2,Y2
Your task is to calculate how many ways there are to paint the board.

输入:

There are multiple test cases, the first line of input contains a single integer denoting the number of test cases.
For each test case, the first line contains an integer N and M, denoting the length of the board and the number of additional rules. (1 <= N <= 15, 0 <= M <= 100)
For next M lines, each line contains four integers X1, Y1, X2, Y2 denoting one additional rule for the painting. (1 <= X1, X2 <= 4, 1 <= Y1, Y2 <= N)

输出:

There are multiple test cases, the first line of input contains a single integer denoting the number of test cases.
For each test case, the first line contains an integer N and M, denoting the length of the board and the number of additional rules. (1 <= N <= 15, 0 <= M <= 100)
For next M lines, each line contains four integers X1, Y1, X2, Y2 denoting one additional rule for the painting. (1 <= X1, X2 <= 4, 1 <= Y1, Y2 <= N)

样例输入:

3
1 0
1 3
1 1 2 1
1 1 3 1
4 1 3 1
2 6
1 1 2 1
1 1 3 1
1 1 4 1
1 2 2 2
1 2 3 2
1 2 4 2

样例输出:

Case 1: 67296
Case 2: 00256
Case 3: 32896

//+option:-ansi -Wall -Wextra -pedantic
//+source:http://acm.hdu.edu.cn/showproblem.php?pid=2405
//press <F7> to update the source to mark file.
//press <S-F7> to open the page
#include "iostream"
#include "algorithm"
#include "cstdio"
#include "cstdlib"
#include "cstring"
using namespace std;
#define _ASSERT(a) ({fprintf(stderr,"%s:%d: %s\n", __FILE__, __LINE__, #a); exit(-1);})
#define _FOREACH(a, b) for(__typeof(b.begin())a=b.begin(), a##ed__=b.end(); a!=a##ed__; a++)
#define _FOREACHC(a, b, cond) for (__typeof(b) a=b;(cond); b++, a=b)
#define _QUEUEPROC(cond, U, V) \
	for(int u=(U);cond;u=(U))\
		_FOREACH(v, V) 
#define _STACKPROC(cond, U, V) \
	for (int u=(U); cond; u=(U))\
		for (bool child=false; !child; child=true)\
			_FOREACHC(v, (V), !child)
#define _INCREMENT(over, ...)\
 do\
 {\
 static int over = 0;\
 (over)++;\
 __VA_ARGS__;\
	}while(0)
#define rangedo(i, s, t)\
 i=s; i!=t; i++
#define each(a, b)\
 __typeof(b.begin())a=b.begin(), a##ed__=b.end(); a!=a##ed__; a++
 

int T;
int N, M;
int f[16][16][16][16];
int vst[16][16][16][16];
struct Save{
	int x1, y1, x2, y2;
}sav[1001];
const int modulo = 100000;
int iter[4];
int main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d", &N, &M);
		memset(vst, 0, sizeof(vst));
		for (int i=0; i<M; i++)
			scanf("%d%d%d%d", &sav[i].x1, &sav[i].y1, &sav[i].x2, &sav[i].y2);
		for (rangedo(iter[0], 0, N+1))
		for (rangedo(iter[1], 0, N+1))
		for (rangedo(iter[2], 0, N+1))
		for (rangedo(iter[3], 0, N+1))
		for (int rangedo(i, 0, M))
			if ( (iter[sav[i].x1-1] < sav[i].y1)!=
			 (iter[sav[i].x2-1] < sav[i].y2) )
			{
				vst[iter[0]][iter[1]][iter[2]][iter[3]]=true;
				break;
			}
		memset(f , 0, sizeof( f));
		f[0][0][0][0]=1;
		for (int rangedo(color, 1, 257))
		{
			for (int rangedo(colum, 0, 4))
			for (rangedo(iter[0], 0, N+1))
			for (rangedo(iter[1], 0, N+1))
			for (rangedo(iter[2], 0, N+1))
			for (rangedo(iter[3], 0, N+1))
				if (iter[colum])
				{
					int &dp = f[iter[0]][iter[1]][iter[2]][iter[3]];
					iter[colum]--;
					dp += f[iter[0]][iter[1]][iter[2]][iter[3]];
					iter[colum]++;
					if (dp>=modulo) dp-=modulo;
				}
			for (rangedo(iter[0], 0, N+1))
			for (rangedo(iter[1], 0, N+1))
			for (rangedo(iter[2], 0, N+1))
	 		for (rangedo(iter[3], 0, N+1))
				if (vst[iter[0]][iter[1]][iter[2]][iter[3]])
					f[iter[0]][iter[1]][iter[2]][iter[3]]=0;
		}
		_INCREMENT(ncase,
				printf("Case %d: %05d\n", ncase, f[N][N][N][N]));
	}
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1