博文
[置顶] pku题目分类，以后可以照着来练(2009-07-30 13:02:00)
摘要：主流算法：
Ø 1.搜索 //回溯
Ø 2.DP（动态规划）
Ø 3.贪心
Ø 4.图论 //Dijkstra、最小生成树、网络流
Ø 5.数论 //解模线性方程
Ø 6.计算几何 //凸壳、同等安置矩形的并的面积与周长
Ø 7.组合数学 //Polya定理
Ø 8.模拟
Ø 9.数据结构 //并查集、堆
Ø 10.博弈论
1、 排序
1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,
1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 223......
PKU2418 二叉搜索树(2009-10-16 16:24:00)
摘要：http://acm.pku.edu.cn/JudgeOnline/problem?id=2418
二叉搜索树的典型题....
很久没做ACM了,感觉有一个月那么多了吧.
现在来打这些也感觉生疏咯...
BST用到这题目很合适,也有人说用qsort可以过,应该是题目时间太宽的缘故.
上代码...BST
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct BSTNode
{
char name[100];
int times;
struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
int count;
void BSTInsert(BSTree &t,char str[])
{
BSTree p,f;
p = t;
while(p)
{
if(strcmp(str,p -> name) == 0)
{
p -> times++;
return;
}
f = p;
p = (strcmp(str,p -> name) < 0) ? p -> lchild : p -> rchild;
}
p = (BSTree) malloc (sizeof(BSTNode));
p -> lchild = p -> rchild = NULL;
strcpy(p -> name,str);
p -> times = 1;
if(t == NULL) t = p;
else
{
( strcmp(p -> name,f -> name) < 0 ) ? (f -> lchild = p) : (f -> rchild = p);
}
}
void InOrderTravel(BSTree &t)
{
if(t != NULL)
{
InOrderTravel(t -> lchild);
printf("%s %.......
(原创)用矩阵连乘解决公式推导(2009-08-02 13:40:00)
摘要：前些天做了比赛，学到了矩阵连乘，直到今天才真正弄懂了。
TJU3318 Chinese rings，这就是简单的矩阵连乘的应用。
当然，学习这个首先要知道二分求幂。
我构造的矩阵是这样的，矩阵A:
1 2 1
1 0 0
0 0 1
起始矩阵是，矩阵B:
f(2)
f(1)
1
目标矩阵是矩阵C:
f(n+1)
f(n)
1
这样矩阵A*B就可得到矩阵
f(3)
f(2)
1
A*（A*B）又可得到
f(4)
f(3)
1
.
.
.
.
.
我感觉很巧妙，也是今天才刚刚体会的。
这样的话 A*A*A....*A*B就可以得到C，然后就得到我们的答案f(n)
我们可以先把前面n-1个A求出来，这里用到二分求幂的方法。
关于二分求幂，我刚开始也不懂。后来去网上搜了下才知道。
话不多说，上代码。
#include <stdio.h>#include <string.h>#define M 200907
void mulmatrix(__int64 a[][3],__int64 b[][3]){ int i,j,k; __int64 c[3][3]; memset(c,0,sizeof(c)); for(i = 0;i < 3;i++) for(j = 0;j < 3;j++) for(k = 0;k < 3;k++) c[i][j] = ( c[i][j] + ( ( a[i][k] * b[k][j] ) % M) ) % M; &nbs......
转自matrix67 十个利用矩阵乘法解决的经典问题(2009-08-01 17:13:00)
摘要：十个利用矩阵乘法解决的经典题目 from Matrix67
2009-07-15 16:48
好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人，今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识，只介绍矩阵乘法和相关性质。 不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中，一个矩阵说穿了就是一个二维数组。一个n行m列的矩阵可以乘以一个m行p列的矩阵，得到的结果是一个n行p列的矩阵，其中的第i行第j列位置上的数等于前一个矩阵第i行上的m个数与后一个矩阵第j列上的m个数对应相乘后所有m个乘积的和。比如，下面的算式表示一个2行2列的矩阵乘以2行3列的矩阵，其结果是一个2行3列的矩阵。其中，结果的那个4等于2*2+0*1： 下面的算式则是一个1 x 3的矩阵乘以3 x 2的矩阵，得到一个1 x 2的矩阵： 矩阵乘法的两个重要性质：一，矩阵乘法不满足交换律；二，矩阵乘法满足结合律。为什么矩阵乘法不满足交换律呢？废话，交换过来后两个矩阵有可能根本不能相乘。为什么它又满足结合律呢？仔细想想你会发现这也是废话。假设你有三个矩阵A、B、C，那么(AB)C和A(BC)的结果的第i行第j列上的数都等于所有A(ik)*B(kl)*C(lj)的和（枚举所有的k和l）。经典题目1 给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转 这里的操作是对所有点同时进行的。其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。如果对每个点分别进行模拟，那么m个操作总共耗时O(mn)。利用矩阵乘法可以在O(m)的时间里把所有操作合并为一个矩阵，然后每个点与该矩阵相乘即可直接得出最终该点的位置，总共耗时O(m+n)。假设初始时某个点的坐标为x和y，下面5个矩阵可以分别对其进行平移、旋转、翻转和旋转操作。预先把所有m个操作所对应的矩阵全部乘起来，再乘以(x,y,1)，即可一步得出最终点的位置。 ......
01背包与完全背包的心得(2009-07-31 21:36:00)
摘要：用一维写的代码。
01背包: for(j = 1;j <= n;j++)
for(i = v;i <= 0;i++)
f[i] = max(f[i],f[i-c[j]]+d[j]);
完全背包: for(j = 1;j <= n;j++)
for(i = 0;i <= v;i++)
f[i] = max(f[i],f[i-c[v]]+d[i]);
两个背包只差在内循环的顺便。因为如果是正着数的话，f[j][i]的状态就会由f[j][i-c[j]]来推导得。
显然f[j][i-c[j]]是已经进入第j种物品的子结果，这是不符合01背包的，而应该是无限背包的。......
简单的并查集 hdu1272(2009-07-27 15:00:00)
摘要：今天去杭电做了两道题，主要是看了杭电并查集的讲义。
感觉他讲得非常棒，纯入门了。
也在今天又学了一个新的知识，并查集，感到很高兴。
HDU1272
题目意思是找到判断是不是连通无环的图。
判断成环的时候，只要判断输入边的两个点。有一个共同的父节点，那么这两个点就成环。
判断连通的时候，只要判断根节点数为1即可。
不多说，简单题，上代码。
上代码。
#include <stdio.h>#include <string.h>int k,flag[100005],bin[100005];int find(int x){ if(bin[x] == x) return x; return bin[x] = find(bin[x]);}void merge(int x,int y){ int fx,fy; fx = find(x); fy = find(y); if(fx != fy) bin[fx] = fy; else k = 0;}int main(){ int i,j,n,m,cnt,p; while(scanf("%d%d",&n,&m) != EOF && n != -1) { if(n == 0) { puts("Yes"); &nb......
prim算法(2009-07-27 10:24:00)
摘要：昨天做了ZOJ1372，挺开心的，又学了一个算法——最小生成树的prim算法。
其实这个算法跟最短路径算法差不了多少，只是其中改了一点点条件。
这样说吧。比如最短路的起点是1号点，那么数组每次更新的都是到1号点的最短距离。
而最小生成树则是到已选的当前点集的最短距离。
两个都是贪心算法的经典。
学的不多，不过每天都在快乐地进步。
上代码：#include <stdio.h>
#include <string.h>
int mat[55][55],used[55],min[55];
int p;
int prim()
{
int i,j,k,q,ret = 0;
for(i = 1;i <= p;i++)
min[i] = 1000000000,used[i] = 0;
min[1] = 0;
for(i = 1;i <= p;i++)
{
k = -1;
for(j = 1;j <= p;j++)
if(!used[j] && (k == -1 || min[j] < min[k]))
k = j;
used[k] = 1;
ret += min[k];
for(j = 1;j <= p;j++)
if(!used[j] && mat[k][j] && mat[k][j] < min[j])
min[j] = mat[k][j];
}
return ret;
}
int main()
{
int i,j,n,r,a,b,c;
while(scanf("%d%d",&p,&r) != EOF && p != 0)
{
memset(mat,0,sizeof(mat));
for(i = 0;i < r;i++)
......
今天学了优先队列(最大堆)(2009-07-20 10:06:00)
摘要：昨天去做了浙大的月赛。身为ACM菜鸟中的菜鸟的我，简直是被虐。
一个下午只看了一题。ZOJ3230，想了一下午只能想到M*N算法，还想了N种剪枝。
后来想想真是异想天开了吧。哎，一百万次的循环已经够呛，还想要有10000*100000的循环。
第二天看了一下最大堆的，又想到昨天Nineright所讲的C++中有优先队列的模版。
于是用了一下，对a排了个序，Ac了。
代码如下:
#include <stdio.h>#include <queue>#include <stdlib.h>#include <algorithm>using namespace std;
struct s{ int a; int b;}pr[100005];
int cmp1(struct s a,struct s b){ return a.a < b.a;}
int main(){ int n,m,i,j,k,p; while(scanf("%d%d%d",&n,&m,&p) != EOF) { for(i = 0;i < n;i++) scanf("%d%d",&pr[i].a,&pr[i].b); sort(pr,pr+n,cmp1); priority_queue <int> q; q.push(0); ......