待更新

2018年12月2日 0条评论 1点热度 阅读全文

题目传送门 做法:在尺取的过程中用树状数组查询区间最值。复杂度O(2*n*log^2(n)) AC代码: #include<bits/stdc++.h> #define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define pb(x) push_back(x) #define sz(x) (int)(x).size() #define sc(x) scanf("%d",&x) #define pr(x) printf("%d…

2018年9月27日 0条评论 2点热度 阅读全文

图论中,用来求最短路的方法有很多,适用范围和时间复杂度也各不相同。 本文主要介绍的算法的代码主要来源如下: Dijkstra: Algorithms(《算法概论》)Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani;《算法竞赛入门经典—训练指南》刘汝佳、陈峰。 SPFA (Shortest Path Faster Algorithm): Data Structure and Algorithms Analysis in C, 2nd e…

2018年9月7日 0条评论 3点热度 阅读全文

前缀树,又叫字典树,主要用于字符串(不限于字符串)查询、统计、排序的一种数据结构 比如,给定n个字符串,进行m次查询,每次查询给定一个字符串 t,问t 是否存在于那给定的n个字符串里 这里,我们用到了前缀树,即将每个字符串看作一条链,把拥有相同前缀的字符串的链的相同前缀给合并,形成一棵棵子树。如给定三个字符串his,her,hit,得到前缀树: 上图很清晰了,在右边的树里面从根出发,一直到叶子结点,可以找到his,hit,her三个单词 那么问题来了,如果再来一个字符串it,怎么插入到这棵Trie里?显然这是无法接…

2018年8月29日 0条评论 2点热度 阅读全文

Wormholes Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 64151   Accepted: 23944 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar becau…

2018年8月28日 0条评论 2点热度 阅读全文

图的遍历之 深度优先搜索和广度优先搜索 本章会先对图的深度优先搜索和广度优先搜索进行介绍,然后再给出C/C++/Java的实现。 目录 1. 深度优先搜索的图文介绍 1.1 深度优先搜索介绍 1.2 深度优先搜索图解 2. 广度优先搜索的图文介绍 2.1 广度优先搜索介绍 2.2 广度优先搜索图解 3. 搜索算法的源码 转载请注明出处:http://www.cnblogs.co…

2018年8月18日 0条评论 10点热度 阅读全文

思路:求最大最小表示的位置,直接模板,求次数的话,先用KMP求出循环节的大小,再判断一下,最大最小表示出现次数相同,具体看代码注释。 AC code: #include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> using namespace std; const int maxn = 1e6 + 10; string str; int…

2018年8月15日 0条评论 3点热度 阅读全文

两个算法区别不是很大,一个是处理单源最短路径,一个是处理多源最短路径。 先总结下Dijkstra算法。从若干个节点中,找每次最小的提取出来,看经过最小的点的路径到达终点是否比原来小,本质上是贪心的思想。 不多说,放代码。题目来自洛谷P1339 题目描述 The good folks in Texas are having a heatwave this summer. Their Texas Longhorn cows make for good eating but are not so adept at cre…

2018年8月6日 0条评论 15点热度 阅读全文

dfs 1 void dfs(int x) { vis[x] = 1; for(int i = head[x];i;i = next[i]) { int y = ver[i]; if(vis[y]) continue; dfs(y); } } 2 VI e[maxn]; void dfs(int u) { vis[u] = 1; for(auto &v:e[u]) { if(!vis[v]) { dfs(v); } } } 树的dfs序 就是递归后和回溯前记录一次该点的编号 1 void dfs(int x…

2018年7月31日 0条评论 22点热度 阅读全文

链接:https://www.nowcoder.com/acm/contest/142/J 来源:牛客网   题目描述 Chiaki has just learned hash in today's lesson. A hash function is any function that can be used to map data of arbitrary size to data of fixed size. As a beginner, Chiaki simply chooses a hash t…

2018年7月28日 0条评论 8点热度 阅读全文