您正在查看 "数据结构" 分类下的文章 2010-09-26 21:32 关于构造的矩阵可以看代码，应该比较清楚。此题按思路也可以用二分+快速模取幂，不过偶试了一下，超时了..
#include <iostream>
#include <cstdio>
#include |
2010-09-25 13:28 2010-09-24 16:27 思路挺简单，不过处理的时候感觉有点麻烦，主要就是要讨论b>=1和b==0的时候, 建议先做PKU 3233再来做这道题，WA两次，传递参数的时候用了int ，导致整数越界,
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define F(i, l, r) for(int i=(l); i<=(r); i++)
#define FOR(i, l, r) for(int i=(l); i<(r); |
2010-09-21 12:30 题意：给一个有向图，求从经过k步从一点到另外一点的路径数
n<=100(点数）, m(边数）， k<=10^9（步数）
算法：如果从u->v有一条边，则把[v][u]赋值为1, 初始化矩阵，再进行矩阵快速冥乘，最后[n][1]就是答案，
#include <iostream>
using |
2010-09-20 22:19
再次练矩阵乘法
#include <iostream>
#include <cstdio>
#include <string>
|
2010-09-20 21:56 题意：给定'f'和'm'两种字符，两种字符组成长度为L的字符串，求字符串中不包括"fmf"或"fff"的字符串的总数:
算法：写出递推公式再用矩阵乘法进行快速模取冥
#include <iostream>
#include <cstdio>
|
2010-09-20 18:00 经典的题，偶一直不敢敲矩阵的题，虽然有一个模板，但觉得总看模板的话对能力提高不大，于是决定自己写一写，刚开始写得很搓，RE几次，WA几次，后来慢慢完善了一下，感觉还是很不错，能不看模板的情况还是不要看模板好...
#include <iostream>
#include |
2010-09-03 16:57
/* PKU 2778 AC自动机+矩阵递推
题意：求长度为n不包括给定模式串的字符串数量。
解法：Aho-Corasick自动机(前缀树) + 矩阵快速乘法
*/
#include <iostream>
#include <queue>
|
2010-09-03 0:07
/*此题参考了大牛的代码，自已无能啊, 不过总算明白了
题意：求长度为n不包括给定模式串的字符串数量。
转移方程：dp[i][j] = dp[i][j] + dp[i-1][k] (k为j的父节点), 且必须满足条件 flag[j]不能为危险节点（即模式串的结尾）
此代码G++AC， C++WA， 不知何故
*/
|
2010-08-29 16:27
/*题意：求n个字符串的最长的一个子串，满足该子串在超过一半以上的字符串中出现过，并输出该子串，如果有多个子串满足要求，则按字典序输出所有的子串；
算法：二分长度+后缀数组，需牢记*/
#include <iostream>
#include |
2010-08-28 22:09
Tire图+DFS
题意:给出m个字符串由小写和*?组成,给n个纯字母的单词,?可以代表一个字母,*可以代表任意多个字母包括0,对每个单词,从m个模板中找出所有可能的匹配
思路:?作为26,*作为27 AC代码:
#include <iostream |
2010-08-28 22:08
Zoj 后缀数组+线段树 求一个字符串的最长的子串,条件为该子串在原字符串中出现的次数不小于m.求并输出最右边出现该字符串的位置
#include <iostream>
#include <algorithm>
#include |
2010-08-22 2:01
/* PKU 3690 二维串匹配
题意：给定一个模式矩阵只包含'*'和'0'，再给T个矩形，求有多少个矩形在模式矩形中出现
解法：对给定的T个矩形，构建一个trie图，然后枚举模式矩阵的子矩阵，看在trie图中是否
匹配,
*/
#include <iostream>
using |
2010-08-17 16:30 题意：已知一棵树的前序和中序遍历，输出后序遍历，
dfs即可
#include <queue>
#include <cstdio>
#include <iostream>
|
2010-07-21 0:17 题目大意：给定一些硬币，这些硬币中有一个是假硬币，注意的是假硬币有可能比真硬币的重量小，也有可能比真硬币的重量大，给出对这些硬币的一些称重，称重为天平两边的硬币数相等，然后给出称重后的结果，即哪边重，判断对于给定的称重情况，判断最后是否能找出那枚假硬币
算法：
用枚举的思想枚举每颗硬币，然后所有的称重方法中进行判断，判断所有的称重是否成立， 如果不成立， 说明该枚硬币肯定不是假硬币，最后判断所有不能判定出是否是假硬币的硬币数量，如果数量大于1，则表示无法判断出，否则则可以判断说 |
| | |
