博文
构造n阶魔方阵(2008-05-31 10:31:00)
摘要：构造n阶魔方阵
何谓魔方阵？
4 9 2
3 5 7
8 1 6
定义：由n*n个数字所组成的n阶方阵，具有各对角线，各横列与纵行的数字和都相等的性质，称为魔方阵。而这个相等的和称为魔术数字。若填入的数字是从1到n*n，称此种魔方阵为n阶正规魔方阵。
1. n = 2k + 1(奇数时)
(1) 1放在第一行的中间位置上；
(2) 下一个数放在当前位置的上一行、下一列；
(3) 若当前位置是第一行，下一个数放在最后一行；若当前位置是最后一列，下一个数放在第一列；
(4) 若下一个数要放的位置上已经有了数字，则下一个数字放在当前位置的下一行，相同列。
根据此规则填充的3阶魔方阵如下：
8
1
6
3
5
7
4
9
2
2. n = 4k(4的整数倍时)
(1) 先将整个方阵划分成k*k个4阶方阵，然后在每个4阶方阵的对角线上做记号
(2) 由左而右、由上而下，遇到没有记号的位置才填数字，但不管是否填入数字，每移动一格数字都要加1
(3) 自右下角开始，由右而左、由下而上，遇到没有数字的位置就填入数字，但每移动一格数字都要加1
（2）后： (3）后：
3. n = 4k + 2
本法填制魔方阵时，先将整个方阵划成田字型的四个2 k + 1阶的奇数阶小方阵，并以下法做注记：
1,右半两个小方阵中大于k+2的行。
2，左半两个小方阵中( k + 1 , k + 1 )......
PKU题目分类,开始写解题报告(2008-05-31 10:09:00)
摘要：PKU题目分类,开始写解题报告
对于思路的扩展以及应用都是具有好处的
初期:
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
pku3508 一个有趣的小学算术题(2008-05-22 09:39:00)
摘要： 题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=3508
/*
一开始想用1n 2n到9n直接看能否整除11，结果TLE。
很纳闷，看别人才89ms，纸上一画才发现不就是小学算术题吗?
a b c 0
+ a b c
---------- (a>0)
3 5 3
*/
#include <stdio.h>
#include <string.h>
#define MAXSIZE 1000000
char h1[MAXSIZE+2],h2[MAXSIZE+2];
int len;
int main()
{
int i,jin;
int t=0;
while(1)
{
scanf("%s",h1+1);
len = strlen(h1+1);
if(len==1 && h1[1]=='0')
break;
for(i=1;i<=len;i++)
h1[i] -= '0';
h2[len+1] = 0;
for(jin=0,i=len;i>=1;i--)
{
h2[i] = h1[i] - h2[i+1] - jin;
if(h2[i]<0)
{
h2[i] += 10;
jin = 1;
}
else
jin = 0;
}
if(h2[1]==0)
printf("%d. IMPOSSIBLE\n",++t);
else
{
printf("%d. ",++t);
for(i=1;i<=len;i++)
printf("%d",h2[i]);
printf("\n");
}
}
return 0;
}
......
pku1351 动规——记忆化搜索(2008-05-22 09:35:00)
摘要：题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1351
/**********pku1351************
* 动规——记忆化搜索
* a[n][p][k][u]
* n: 统计了几个slot
* p: 当前取道那些值 按位存储p=7(0111)表示已经取到1,2,3
* k: 最后一个值
* u: 是否满足条件1
* 注意答案会超过32位整数
******************************/
#include <stdio.h>
#include <memory.h>
__int64 a[20][16][5][2];
int flag[5] = {0,1,2,4,8};
void init()
{
int i;
memset(a,-1,sizeof(a));
for(i=0;i<=15;i++)
{
a[1][i][1][1] = a[1][i][2][1] = a[1][i][3][1] = a[1][i][4][1] = 0;
a[1][i][1][0] = a[1][i][2][0] = a[1][i][3][0] = a[1][i][4][0] = 0;
}
a[1][1][1][0] = 1;
a[1][2][2][0] = 1;
a[1][4][3][0] = 1;
a[1][8][4][0] = 1;
}
__int64 ado(int n,int p,int k,int u)
{
int t;
if(n<=0) return 0;
if(a[n][p][k][u]!=-1) return a[n][p][k][u];
a[n][p][k][u] = 0;
if((p&flag[k])==0) return 0; /*p不包含k，直接返回0*/
t = p&~flag[k];
if(u==0)
{
if(k==1)
{
a[n][p][k][u] += ado(n-1,p,1,0) + ado(n-1,p,2,0) + ado(......