加载中…
个人资料
依然
依然
  • 博客等级:
  • 博客积分:0
  • 博客访问:379,781
  • 关注人气:191
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
搜博主文章
好友
加载中…
访客
加载中…
评论
加载中…
留言
加载中…
博文
置顶: (2013-08-02 21:08)
    已经很久没来看新浪博客,此博客以后也不会再更新,各位ACMer的评论和问题请原谅我没能答复。新建了一个CSDN博客:http://blog.csdn.net/yyyiran,开始写一些后台开发相关的文章。
    由于今年7月已经毕业参加工作,有新的生活和梦想,也是时候离开了。ACM占据了大学1/2的时光,说离别甚难,回顾这4年的ACM之路,我很庆幸自己大学期间一直坚持自己热爱的事...

依然
2013年8月02日
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
题意:n个顶点,m条有向边的图,求出起点s到终点t的第k最短路。

思路:spfa+A*。如果用普通的bfs,很可能会因为过多的回路,而导致存放节点的队列内存爆掉,时间也很难控制。所以在搜索的时候需要结合图的启发式信息,比较自然地就想到用A*。先通过spfa或者dijkstra求出各个点到终点的最短路径长度minDis[i],然后用这个长度来作为后面A*算法时的启发式信息h`(i)。

源代码:(9936K,954MS)
#include<iostream>
#include<queue>
using namespace std;
const int NMAX = 1050;
const int MMAX = 100050;

struct Node {
    int u, dis, val;
    bool operator < (const Node &a) const
    {
        return val > a.val;
    }
}node, newNode;
struct Edge {
    int v, w, nxt;
}e
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

poj

pku

2251

a

dungeon

master

校园

分类: POJ搜索

题意:3维迷宫,求从起点到终点最少要走的时间,若不能走到,则输出“Trapped!”。

 
思路:A*,基本的启发式搜索。

源代码:(636K,32MS)
#include<iostream>
#include<queue>
using namespace std;
const int MAX = 35;

struct Node {
    int l, r, c, dis, val;
    bool operator < (const Node &b) const 
  
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

poj

pku

2778

dna

sequence

校园

分类: POJ数据结构
题意:给出一些病毒DNA序列,问一个长度为n的DNA如果不包含所给的任意一个病毒,最多有几种可能。

思路:矩阵乘法+AC自动机。(摘自Matrix67大牛:)我们以ATC,AAA,GGC,CT这四个病毒片段为例,说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀,把n位DNA分为以下7类:以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”,它可以是任一字母,只要这个字母不会让它所在的串成为某个病毒的前缀。显然,这些分类是全集的一个划分(交集为空,并集为全集)。现在,假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数,我们需要求出长度为n时各类DNA的个数。我们可以根
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
题意:已知一个DNA串和一些病毒DNA序列,求出最少改变DNA串中多少个字符,能使得串中不包含任意一个病毒序列。

思路:DP+AC自动机。多串的匹配,自然先联系到AC自动机。其次也符合DP的最优子结构思想,难就
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

poj

pku

3613

cow

relays

校园

分类: POJ数学
题意:一个无向图,求点s到点t经过k条边的最短路(边可以重复)。

思路:floyd的DP思路,用矩阵乘法来求。解题报告听说在2008年国家集训队论文,俞华程《矩阵乘法在信息学中的应用》中有。

ps:矩阵最大为100*100(最多100个点:100条边且每个点至少连2条边),时间复杂度为0(100^3*lg(1e6))。长度最长不会超int,可以不用__int64(N*length<=1e9)。
ps:我的VC++6.0,Matrix内的int v[MAX][MAX],好像当MAX定义大于100就会溢出,一开始还以为是别的地方出错了,交上去却AC,囧...
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

poj

pku

3256

cow

picnic

校园

分类: POJ搜索
题意:有k只牛,n个牧场,m条连接牧场的路(有向边)。已知各只牛初始所在的牧场,问如果一些牛沿着路移动,最多有几个牧场可能包含全部的k只牛。

思路:dfs。由于floyd的复杂度为 O(n^3)太大,固不能用邻接矩阵存边。所以用临界表来存,枚举各点用dfs求任意两点的连通性。

源代码:(267K 175MS)
#include<iostream>
using namespace std;

struct
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

poj

pku

3233

matrix

power

series

校园

分类: POJ数学
题意:已知一个n*n的矩阵A,和一个正整数k,求S A A2 A3 + … + Ak

思路:矩阵快速幂。首先我们知道 A^x 可以用矩阵快速幂求出来(具体可见poj 3070)。其次可以对k进行二分,每次将规模减半,分k为奇偶两种情况,如当k = 6和k = 7时有:
      k = 6 有: S(6) = (1 + A^3) * (A + A^2 + A^3) = (1 + A^3) * S(3)。
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

poj

pku

3070

fibonacci

校园

分类: POJ数学
题意:求第n个斐波那契数。

思路:矩阵快速幂。利用可化为矩阵快速幂,即:由于矩阵乘法具有结合律,因此对于矩阵A,有A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论:当n为偶数时,A^n = A^(n/2) * A^(n/2);当n为奇数时,A^n = A^(n/2) * A^(n/2) * A (其中n/2取整)。

源代码:(164K,16MS)
#include<iostre
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
标签:

acm

矩阵乘法

校园

分类: 学习资料
转载自Matrix67大牛的博客:http://www.matrix67.com/blog/archives/276/

    好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人,今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识,只介绍矩阵乘法和相关性质。
    不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中,一个矩阵说穿了就是一个二维数组。一个
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
题意:给出一些关键字和一篇文章,问这些关键字有几个出现在文章中。

思路:AC自动机。模板题了,裸的AC自动机,注意下关键字有可能是重复的。

源代码:(27419K 187MS)
#include<iostream>
using namespace std;

struct Node
{
    int cnt;
    Node *nxt[26], *fail;
}*rt, qq[500005], *que[500005];
int k;
char key[55];
char msg[1000005];

void insert(char *str)
{
    int i, idx;
    Node *p = rt;
    for(i = 0;
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
  

新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有