杰拉斯的博客

今天在做项目的时候需要用到JavaScript农历转换算法，从网上搜索并整理了一下，重新写出一个JavaScript农历转换类，不敢独占，特此与大家分享。

(阅读全文…)

九宫格是在81个格子中，要满足以下条件：（1）每个横行和竖列中的9个格子都包含数字1至9，不重复；（2）每个黑色粗实线围住的9个格子都包含数字1至9，不重复。如下表所示：

7 6 1 9 3 4 8 2 5
3 5 4 6 2 8 1 9 7
9 2 8 1 5 7 6 3 4
2 1 9 5 4 6 3 7 8
4 8 3 2 7 9 5 1 6
5 7 6 3 8 1 9 4 2
1 9 5 7 6 2 4 8 3
8 3 2 4 9 5 7 6 1
6 4 7 8 1 3 2 5 9

要求找出给定数字的九宫格。

【输入形式】

输入9行9列81个数字，其中0表示要填的数字。

【输出形式】

输出满足条件的九宫格。

【输入样例】

0 6 1 0 3 0 0 2 0
0 5 0 0 0 8 1 0 7
0 0 0 0 0 7 0 3 4
0 0 9 0 0 6 0 7 8
0 0 3 2 0 9 5 0 0
5 7 0 3 0 0 9 0 0
1 9 0 7 0 0 0 0 0
8 0 2 4 0 0 0 6 0
0 4 0 0 1 0 2 5 0

【输出样例】

7 6 1 9 3 4 8 2 5
3 5 4 6 2 8 1 9 7
9 2 8 1 5 7 6 3 4
2 1 9 5 4 6 3 7 8
4 8 3 2 7 9 5 1 6
5 7 6 3 8 1 9 4 2
1 9 5 7 6 2 4 8 3
8 3 2 4 9 5 7 6 1
6 4 7 8 1 3 2 5 9

代码及思路如下：

#include<stdio.h>

bool canFill(int a[9][9], int k, int n){
	int i, j, row = k / 9, col = k % 9;
	for(i = 0; i < 9; ++i){
		if(a[i][col] == n){
			return false;
		}
	}
	for(j = 0; j < 9; ++j){
		if(a[row][j] == n){
			return false;
		}
	}
	for(i = row - row % 3; i < row - row % 3 + 3; ++i){
		for(j = col - col % 3; j < col - col % 3 + 3; ++j){
			if(a[i][j] == n){
				return false;
			}
		}
	}
	return true;
}

void fill(int a[9][9], int k = 0){
	int i, j;
	if(k == 81){
		for(i = 0; i < 9; ++i){
			for(j = 0; j < 9; ++j){
				printf("%d ", a[i][j]);
			}
			printf("\n");
		}
		return;
	}
	int row = k / 9, col = k % 9;
	if(a[row][col] == 0){
		for(i = 1; i <= 9; ++i){
			if(canFill(a, k, i)){
				a[row][col] = i;
				fill(a, k + 1);
				a[row][col] = 0;
			}
		}
	}else{
		fill(a, k + 1);
	}
}

int main(){
	int i, j, a[9][9];
	for(i = 0; i < 9; ++i){
		for(j = 0; j < 9; ++j){
			scanf("%d", &a[i][j]);
		}
	}
	fill(a);
	return 0;
}

2013年5月4日3点温习重写代码如下：

#include<stdio.h>

int square[9][9];

int isEnabled(int k, int num){
	int row = k / 9;
	int col = k % 9;
	for(int i = 0; i < 9; ++i){
		if(square[row][i] == num || square[i][col] == num){
			return false;
		}
	}
	int m = row - row % 3;
	int n = col - col % 3;
	for(int i = m; i < m + 3; ++i){
		for(int j = n; j < n + 3; ++j){
			if(square[i][j] == num){
				return false;
			}
		}
	}
	return true;
}

void fill(int k = 0){
	int row = k / 9;
	int col = k % 9;
	if(k >= 81){
		for(int i = 0; i < 9; ++i){
			for(int j = 0; j < 9; ++j){
				printf("%d ", square[i][j]);
			}
			printf("\n");
		}
		return;
	}
	if(square[row][col] > 0){
		fill(k + 1);
		return;
	}
	for(int i = 1; i <= 9; ++i){
		if(isEnabled(k, i)){
			square[row][col] = i;
			fill(k + 1);
			square[row][col] = 0;
		}
	}
}

int main(){
	for(int i = 0; i < 9; ++i){
		for(int j = 0; j < 9; ++j){
			scanf("%d", &square[i][j]);
		}
	}
	fill();
	return 0;
}

整数划分问题（算法分析与设计 P12）：将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数和方案。例如正整数6有如下11种不同的划分：

6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1

(阅读全文…)

只需一小句代码，如下：

printf("%d\n", ~(unsigned int)0 / 2);

分析：

当无符号0以二进制储存在内存中的时候，每一位都为0，以32位int为例，(unsigned int)0的二进制为：

00000000000000000000000000000000

按位取反（~）后，变成：

11111111111111111111111111111111

此时的十进制为：

4294967295

除以2（因为int类型中有一半表示负数且比正数多一个）之后为：

2147483647

即为32位int类型最大值。

Crixalis's Equipment

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1350 Accepted Submission(s): 543

Description

Crixalis - Sand King used to be a giant scorpion(蝎子) in the deserts of Kalimdor. Though he's a guardian of Lich King now, he keeps the living habit of a scorpion like living underground and digging holes.

Someday Crixalis decides to move to another nice place and build a new house for himself (Actually it's just a new hole). As he collected a lot of equipment, he needs to dig a hole beside his new house to store them. This hole has a volume of V units, and Crixalis has N equipment, each of them needs Ai units of space. When dragging his equipment into the hole, Crixalis finds that he needs more space to ensure everything is placed well. Actually, the ith equipment needs Bi units of space during the moving. More precisely Crixalis can not move equipment into the hole unless there are Bi units of space left. After it moved in, the volume of the hole will decrease by Ai. Crixalis wonders if he can move all his equipment into the new hole and he turns to you for help.

Input

The first line contains an integer T, indicating the number of test cases. Then follows T cases, each one contains N + 1 lines. The first line contains 2 integers: V, volume of a hole and N, number of equipment respectively. The next N lines contain N pairs of integers: Ai and Bi.
0

Output

For each case output "Yes" if Crixalis can move all his equipment into the new hole or else output "No".

Sample Input

2

20 3
10 20
3 10
1 7

10 2
1 10
2 11

Sample Output

Yes
No

Source

HDU3177

(阅读全文…)