博文
[置顶] 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......
(原创)用矩阵连乘解决公式推导(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); ......