雨羊的博客

Trie树（Prefix Tree）介绍

什么是 Trie 树 Trie 树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。如下图：上图是一棵 Trie 树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出 Tr

树

拓扑排序最短工期 PTA

题目：一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。输入格式：首先第一行给出两个正整数：项目里程碑的数量 N（≤）和任务总数 M。这里

图

约瑟夫环

n 个人中每数到 m 出队一人，第 k 次出队人的编号 //约瑟夫环// #include<stdio.h> //返回的是第K次出队的人的编号// int ysfh(int n, int m, int k) { if (k == 1) return (n + m - 1) %

递归

背包模板

模板 /** * 多重背包： * 有N种物品和一个容量为 V的背包。第i种物品最多有 num[i]件可用， * 每件耗费的空间是C[i]，价值是W[i]。 * 求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。 */ #include <iostream> #in

动态规划

莫队算法

莫队算法我早有耳闻。。可惜前不久才去学习。但是自己看了看论文，也就 1h 左右，就能够全部理解了。也就是说其实这个算法不难。。好了，让我们进入正题。我们首先来看一道例题： Description 有n个数字，给出k，以及m个查询。每次查询的格式是L，r，求L~r（左右包含）这个区间内数字的

算法

最短距离模板

dijkstra算法：求指定两点间的距离（不适用负边权），O(n^2) #include<iostream> #include<vector> #include<cstdio> using namespace std; const int INF = 0x3fffffff; const

图

最小生成树模板

prim 算法按点算，适合于点少的情况邻接矩阵，时间复杂度 o(n^2) //PTA公路村村通 #include<iostream> #include<cstdio> using namespace std; const int INF = 0x3fffffff; const int MAXV

图

二叉树遍历

已知先序中序构树 #include <cstdio> #include <iostream> using namespace std; const int N = 50; int pre[N], in[N], post[N]; //存放先序，中序，后序的数组 int n;//树中元素

树

a^b%c

利用二进制来写，提供一种新思路，也更加简洁，迅速 //res=ab%c //将b转化为二进制，1即为有这一个数，0即没有 //例如9的二进制1001 即 23+20 //则a9=a8*a1; a23和a20 的乘积 //求a的b次方对c取模 //(ab)%c==(a%c)(a%b) int fun(

数学问题

并查集模板

const int MAXN=1005; int father[MAXN]; int find(int x)//寻找根结点 { if(x==father[x])return x; return father[x]=find(father[x]); //压缩路径 } void merge

树