一只橘橘猫

分类

coderforces(20) dp动态规划(3) icpc(8) KMP算法(3) leetcode(1) STL(1) 人工智能(2) 优先队列(1) 图论(3) 字符串(5) 搜索(2) 数学(4) 日记(1) 最短路(3) 未归档(29) 杭电多校(7) 牛客多校(11) 牛客寒假训练营2020(6) 牛客练习赛(8) 线段树树状数组(2) 贪心(4) 题解(25)

/ 注册

TA的专栏 27篇文章 0人订阅

acm菜鸡日常

20篇文章 2413人学习

7篇文章 1165人学习

0篇文章 0人学习

全部文章（共149篇）

字符串最短公共祖先

题意：求包含a，b两字符串的最小字符串的长度。题解： a，b两字符串互相进行两次kmp，满足以下三个条件：a的后缀与b的前缀重合a的前缀与b的后缀重合a在b内或b在a内代码： #include <bits/stdc++.h> using namespace std; #define...

最短公共祖先字符串

2019-08-30

0 609

KMP和扩展KMP

kmp算法：模式串在主串中出现首次位置以及出现次数 //模式串在主串中出现首次位置以及出现次数 #include <bits/stdc++.h> using namespace std; const int maxx = 100010; int next[maxx]; char s1...

扩展kmp 字符串 kmp

2019-08-30

0 642

字符串编辑距离（Levenshtein距离）算法

介绍：Levenshtein距离是一种计算两个字符串间的差异程度的字符串度量（string metric）。我们可以认为Levenshtein距离就是从一个字符串修改到另一个字符串时，其中编辑单个字符（比如修改、插入、删除）所需要的最少次数。例子：从字符串“kitten”修改为字符串“sittin...

字符串

2019-08-30

0 965

icpc 2018南京L-Magical Girl Haze

题意：给出一个无向图有n个点和m条边，问你从1走到n，可以至多将k条路的长度变为0，问你最短路的长度题解：分层最短路代码：#include <bits/stdc++.h> using namespace std; #define ll long long const int ma...

dijkstra 分层最短路

2019-08-29

0 564

icpc 2018 焦作L-Poor God Water

题意：有N个小时，有三种食物（用1 ，2 ，3代替好了），每个小时要吃一种食物，要求任意连续三个小时不能出现111，222，333，132，231，313，323的方案数题解：对于 n 来说，我们只关注后两位，因为若 n - 1 的所有方案解决的话，我们在 n - 1 的方案添加0, ...

矩阵快速幂

2019-08-28

0 556

icpc 2018 沈阳 D-Made In Heaven

题意：就是给出一个有向图，问你从起点到终点的第k短路。题解：用到第k短路+A*启发式搜索代码： #include <bits/stdc++.h> using namespace std; const int MAXN = 1005; const int INF = 0x3...

A* 第k短路

2019-08-28

0 535

Codeforces Round #579 (Div. 3)

题意：给出一个序列，问你是否能构成1-n的环或者n-1的环。题解：处理一下序列，取模就行了。代码： #include <bits/stdc++.h> using namespace std; #define ll long long int a[205]; int mai...

2019-08-27

0 509

spfa单源最短路

题意：给出一个无向图和每条边的权值，给出一个点s，问你s点到任意点的最短距离，就是dij，但是dij要开二维数组，如果节点的个数大于等于1e5，dij绝对爆内存。题解： spfa算法。代码：#include <bits/stdc++.h> using namespace std; ...

spfa算法

2019-08-25

0 576

STL 来自专栏

set 和 multiset set<int> s; multiset<int> ms; set<int>::iterator it; s.insert(n); //set的首位的迭代器表示 s.begin(),s.end(); //set 可以使用lower_b...

STL

2019-08-24

0 726

2019CCPC网络赛 H

题意：给出每条鱼烤制的时间，抓捕每条鱼的时间是相同的，问你最少花费多少时间才能将所有的鱼抓完并烤完。题解：贪心策略，就是要让自己的空闲时间越小越好，处理好每个烤鱼的时间，排序完后直接相加就好了，确实是想复杂了，贪心策略越简练越容易a，想麻烦可就事大了。代码：#include <bits...

贪心

2019-08-24

0 573