- 博客(62)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 （一）关于几个基本类的认识
（一）关于几个基本类的认识这个类是在看PF的ActionExtClear的初始化函数的时候，发现forcedMove（强制移动）和threholdRest（休息的阈值）的初始化的时候，突然发现没看懂是啥意思，他传进去一个name和一个defaultalue有什么用？原来在ExtClear里面是继承的ExtAction类，而ExtAction里面有很多这样的函数：**1、scenarioInf...
2020-02-26 11:42:44
199
原创 洛谷P1034 矩形覆盖
洛谷P1034 矩形覆盖这是一道简单的搜索题，但是非常难想到（据说当年的这题，全国没有一个人完全做对）。首相我们来分析下，由于题目说矩形不能相互重合，即不能相交，并且k<=4。 那么我们可以分别写出矩形的排列方式。1、当k=1时，就是一个大矩形，求所有点的左上右下的两个点。2、当k=2时，有如下两个排列方式那么怎么计算呢？对于左图，我们先将原先的点，按照y坐标升序排序，然后循环...
2020-02-16 12:30:09
301
原创 洛谷 P1021 邮票面值设计
洛谷 P1021 邮票面值设计要求一个组合，很明显是用dfs来搜索，那么怎么判断呢？用背包！！！dp[i] 表示拼凑出 i 这个数的最小邮票数，然后统计dp [i] <= n 的个数即可在dfs中有一个边界问题，就是：当你在选择下一个数的时候，会发现虽然可以知道他一定 >= 上一个数，但是其上边界却并不明了。但是经过几次尝试就会发现，其上界值一定 <= 当前最大的连续值...
2020-02-09 11:45:13
219
原创 洛谷 P1020 拦截导弹
洛谷 P1020 拦截导弹动态规划经典题今天闲着无聊刷来刷洛谷上以前做过但是没有在洛谷提交的题目，忽然发现以前的基础确实很有必要温习。首先，看下n2做法，n2的动态规划很简单，核心代码是下面的getans 函数, 可以看到两问都用同一段代码完成了，f [ maxn ] 代表的是最长不上升子序列的长度，而dp [ i ]则是第二问的答案，是可以有定理证明的就是一个最长上升子序列，但是。。。我...
2020-02-07 12:51:38
253
1
原创 倍增法求树中的LCA 洛谷 P3379模板题
倍增法求树中的LCA第一次。。我用STL中的vector，然后由两个点TLE了。。。无奈只好选择用链表存边现附上TLE代码（开O2可过）：#include <bits/stdc++.h>using namespace std;const int maxn=5e5+7;int n,m,s;int lg[maxn],fa[maxn][22],depth[maxn];//fa[...
2019-11-17 23:08:54
144
原创 洛谷 P1026 统计单词个数 字典树+动态规划
洛谷 P1026 统计单词个数 字典树+动态规划题目大意：给你一串字符串，求将这个字符串分成k块的，每块单独计算包含单词个数，他们的总和的最大值，每算一个单词之后，该单词的起点不能再被计算另一个单词。首先建立对已有单词的字典树，为之后的计算区间内的单词树做准备计算num[ i ] [ j ]，代表i到j区间内，有多少个位置能作为单词的起点然后初始化dp[ i ] [ i ]和dp[ i ]...
2019-11-04 23:51:45
327
原创 Contest #13 火鼠的皮衣 -不焦躁的内心
CometOJ Contest #13 火鼠的皮衣 -不焦躁的内心这是一道组合数学的巧妙转换的题目，极其简单，但是比赛的时候没有想出来。。嘤嘤嘤其实也不简单，因为我不会矩阵快速幂求下面这个公式对p取模的值，n,a,b,p均有 1e 18 的范围∑i=1n/2Cn2∗iaibn−2∗i\sum_{i=1}^{n/2}C^{2*i}_{n}a^ib^{n-2*i}i=1∑n/2Cn2∗i...
2019-10-28 20:17:09
141
原创 洛谷P5357 AC自动机（二次加强版）建立fail树
洛谷P5357 AC自动机（二次加强版） 建立fail树再次写AC自动机的题目，加强对其的理解首先重述对fail指针的理解：首先，初始化的时候，每一个节点的fail指针都指向root=0； 对于每一个节点，都询问其父亲节点的fail指针指向谁，再向指向的该节点询问其子节点有没有与当前节点相同的节点，如果有，则当前节点的fail指针指向与其相同的节点。 这样，每次查询时，对于每个节...
2019-10-22 17:50:43
277
原创 并查集模板 洛谷P3367
并查集模板 洛谷P3367#include <bits/stdc++.h>using namespace std;int n,m;int fa[10001];int z,x,y;int find(int a){ if(fa[a]==a) return a; return fa[a]=find(fa[a]);}int main(...
2019-10-09 19:04:54
126
原创 Python学习日记三 Pycharm的调试
Python学习日记三 Pycharm的调试在学习日记二中，我还有几个地方没有记录到第一，是bool操作符：and，or，not第二，是函数形参以及它的返回值第三，全局变量和局部变量：局部变量在局部程序完成后，就会消失以上就是不全之前的记录。接下来，记一记今天的正题：Pycharm软件对Python的调试左上角有一个爬虫一样的按钮点击即开始调试，或者使用快捷键 shift + F...
2019-09-24 00:03:26
126
原创 数据结构 单向链表 C++ 非Class实现
数据结构 单向链表 C++ 非Class实现昨天上了数据结构的课程，虽然说上个学期也上了链表（但我没认真听），而且我觉得用Class实现简单链表太麻烦了，所以直接用struct实现了一下上代码：#include <bits/stdc++.h>using namespace std;int n,m,x;struct Link{ int data; Link *...
2019-09-19 20:25:47
186
1
原创 Python学习日记 第二天
Python学习日记 第二天隔了好多天，终于又抽出时间学Python了今天写了一个简单游戏Dragon Realm大意是，你随机选择一个山洞进入，两个山洞只有一个有宝藏，选对了你就赢了这个程序使用了两个库random和time，还有函数的定义及调用，还有一个字符串的特殊输出上代码和注释：import randomimport timedef displayIntro(): #def...
2019-09-16 23:33:18
142
原创 最小生成树 Kruskal算法 Prim算法 洛谷P3366
最小生成树 Kruskal算法 Prim算法 洛谷P3366相较于Prim算法，我觉得Kruskal算法更优（因为一般情况，题目给你的边数都是正常的，Kruskal算法的时间复杂度为O(ElogE) E为边的数量），Kruskal算法是将边按权值排序之后利用并查集进行加边，直至加入边的数量为n-1时结束，而Prim算法是每一次加入一个点，使用的是邻接表进行加点，其时间复杂度为O(n^2)，n...
2019-09-16 23:16:40
307
原创 洛谷 P1012 拼数
洛谷 P1012 拼数真——手写字符串的排序比较函数这个题目，因为之前没有把更长的字符串后面剩余的字符与另一个字符串的首字母进行比较，所以最后一个点WA了#include <bits/stdc++.h>using namespace std;int n;struct op{ char st[100001];};op a[21];bool cmp(op x,op...
2019-09-16 19:21:19
223
原创 Python 初级 第一日
Python 初级 第一日嘛，Python作为最受欢迎的语言，而我现在才刚刚开始起步，今天先来记录一下基本的运算方式和一些基础的函数运用。1、基本运算：±*/ <= >= != == < > 不用太过操心，和我们数学的运算法则一样，不用太过操心,比较操作符也是一样的2、变量：变量不用定义，直接赋值即可(理解为赋值就是定义)，然后就可以直接定义了3、然后就是输入...
2019-09-02 23:52:27
121
1
原创 后缀自动机（SAM） 速成抢救blog 洛谷P3804
后缀自动机（SAM） 速成抢救blog 洛谷P3804在网上看到了一篇很好的关于后缀自动机的博客，他没有说太多的后缀自动机的原理，全篇只有一个要点——如何构建及操作后缀自动机，这是非常好的东西！所以，先附上这篇大佬的blog：https://www.cnblogs.com/sclbgw7/p/10197629.html本篇基本借助于这位大佬的理解，并加上自己的一些理解，酌情阅读后缀自...
2019-09-01 21:58:46
586
原创 牛客竞赛 字符串哈希 白兔的字符串
牛客竞赛 字符串哈希 白兔的字符串一道水题，字符串哈希，用链表结构存储，直接上代码了#pragma GCC optimize("O2")#define ull unsigned long long#include <bits/stdc++.h>using namespace std; const int maxn=2e6+7,mod=1e5+7;char str[...
2019-08-28 15:17:39
261
原创 洛谷P5410 拓展KMP 模板题
洛谷P5410 拓展KMP 模板题KMP算法大家应该都知道，拓展KMP顾名思义，就是在KMP算法上面的扩展和加难。拓展KMP的经典题型就是：给你两个串，让你求一个串的后缀子串与另一个串的最长公共前缀LCP的长度（用ex数组存下）具体理解可以参照刘雅琼前辈的扩展KMP的PPThttps://wenku.baidu.com/view/64ac5384b9d528ea81c779ed.html...
2019-08-28 11:37:40
253
原创 洛谷 P3805 manacher算法 模板题
洛谷 P3805 manacher 模板题先感谢下这篇blog（本文的两幅图是从上面截取下来的）:https://segmentfault.com/a/1190000008484167实锤模板！直接讲解下马拉车算法~~~回文串是个什么玩意大家应该都懂吧？不懂上度娘搜，一抓一大把Manacher算法，就是找出一个字符串里面的最长回文串，也就是这个题目要我们求的东西首先，马拉车有一个预处...
2019-08-28 09:38:41
176
原创 带修改主席树 洛谷P2617 Dynamic Rankings
带修改主席树 洛谷P2617 Dynamic Rankings题目大意：这道题依然是求区间第k大，但是这是求动态区间第k大的值，数组里的值可以随意修改。输入：第一行有两个正整数n(1≤n≤100000)，m(1≤m≤100000)。分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式...
2019-08-27 19:52:52
127
原创 牛客练习题 AC自动机 String (强制 离线AC自动机)
牛客练习题 AC自动机 String (强制 离线AC自动机)嘛，这题TLE了我一下午，最终在晚上终于搞出来了！！！基本思想是AC自动机，但由于题目是询问中穿插了字符串的添加，所以我们不得不将其离线（因为每次添加都需要更新fail指针，这样时间复杂度太大了），然后倒序处理询问，对之前添加进去的一一删去，得出答案后即可输出。开始的时候就是普通树状数组的操作，我交的代码TLE是因为我没有做求单词...
2019-08-25 22:34:30
233
原创 主席树介绍 ： 洛谷P3834 可持久化线段树 1（主席树）
主席树介绍 ： 洛谷P3834 可持久化线段树 1（主席树）昨天开始进入主席树的学习。。首先，主席树也是线段树的一种，但是空间比线段树更大，这是因为，他记录了每一次修改之前的状态，也就是说，他比一般的线段树有更多的节点，一开始看到有题解说，每一个节点都存了一个线段树，这把我吓了一跳，其实准确来说，应该不是这样的，下面看我讲解：主席树，是在权值线段树上发展来的，对于每一个 L == R 的节...
2019-08-24 20:07:11
128
原创 C++ STL set的使用
C++ STL set的使用今天写一道贪心题，被禧宝儿嘲讽了：“亲，这边建议您学一下set”于是就来补坑了，毕竟学这些STL，以后在数据处理方面会用很大作用首先附上另一个大佬的blog：https://blog.csdn.net/Strawberry_595/article/details/81188509set 是一个关联性容器，其他关联性的容器，像multiset, map, mult...
2019-08-22 21:54:07
321
原创 洛谷 P2292 L语言 trie树+暴力
洛谷 P2292 L语言 trie树+暴力题目大意：给你n个短串，然后再给你m个长串，让你对每一个长串求能被短串组成的最长长度这题其实是一个简单思维题，然后暴力即可首先，我们看题，给我们n个字符串，然后，建立trie树。然后我们对每一个长串进行遍历，遍历的时候，我们对每一个短串能到达的结尾位置进行标记，然后每碰到这样一个标记，就往trie树上遍历查找，一直找到新的单词结尾，然后标记。...
2019-08-22 20:53:47
133
原创 洛谷 P2322 最短母串问题 状压+AC自动机
洛谷 P2322 最短母串问题 状压+AC自动机题目大意：给你n个串，让你求包含这n个串的最短母串首先，看到多串，就大概知道要用AC自动机了。然后再想，我们怎么将每个串加入到我们所求的母串上面去。虽然n<12,但是我们无法对每一种情况进行dfs，所以这种想法需要抛弃。在trie树上，我们肯定需要遍历每一个节点，那么我们可以对每一个单词的结尾进行一个标记。怎么标记呢？（注意了，状压开始...
2019-08-22 20:24:56
186
原创 牛客练习 数学题 序列求和
牛客练习 数学题 序列求和题目链接：https://ac.nowcoder.com/acm/problem/15950?tdsourcetag=s_pctim_aiomsg&headNav=acm我是真的好久没写数学题了。。。智商已下线。。今天必须把这道题拿出来好好补点智商税这题在高中的时候我估计还能写得出来，因为知道这道题怎么做之后，我脑海里清晰的记得自己将好多数列的公式都写...
2019-08-20 22:14:17
268
原创 HDU6534 权值树状数组+莫队 Chika and Friendly Pairs
HDU6534 权值树状数组+莫队 Chika and Friendly Pairs嘛，写完这道题后最莫队和树状数组的理解更进了一步嘛，有关莫队的知识，请参考我的另一篇博客，莫队基本上写完一两道模板题后就基本理解了，很简单的这次学到了一个很实用的STL 函数 unique函数，对于权值离散化非常有用，在对一个数组排完序以后，unique函数能够将相邻的重复元素，变成一个元素，将多余的元素放在...
2019-08-20 21:30:17
151
原创 相似子串 BZOJ 3230 后缀数组模板题
相似子串 BZOJ 3230 后缀数组模板题时间2019 8 10——这题网上似乎找不到了，但是我有数据哟这道题其实非常简单，但是我场上并没有想出来。。。。现在拿出来补补智商首先我们求出后缀数组sa[] height[] Rank[] 数组，到这我们的基本条件就已经具备了然后再根据我们对后缀数组的理解：两个排名不相邻的最长公共前缀定义为排名在它们之间的Height的最小值RMQ问题当然...
2019-08-19 21:50:41
132
原创 ST表 洛谷 P3865 ST表模板题
ST表 洛谷 P3865 ST表模板题首先，来说说为什么学ST表哈。ST表类似于树状数组和线段树这两种数据结构在解决RMQ问题时，ST表和线段树的预处理时间复杂度都是O(nlogn)，两者的不同在于，在查询RMQ答案时，ST表的时间复杂度为O(1)，而线段树却有 O (logn)，这是ST表的优势就完全体现出来了。ST表实际上是一个二维数组 ST[i] [j]，含义是：从下标i 到下标 i...
2019-08-18 21:04:53
273
原创 NAIPC 2018 Prefix Free Code
NAIPC 2018 Prefix Free Code这是我和左学长精诚合作弄出的一道题（虽然我的代码后面到处有坑）字典树+dfs序(字典序大小)+树妆数组+阶乘计算答案因为保证每一个字符串都不是其他串的前缀，那么在字典树上，每一条支链的结尾有且仅代表一个串，也就是说保证扫到串的末尾时，不会有其他串在这条链上。然后用一个 tpos[ ] 数组记录当前这个字典树的节点所代表的是输入的第几个串...
2019-08-16 15:56:46
169
原创 2019 牛客多校赛 第七场 String 最小表示法
2019 牛客多校赛 第七场 String 最小表示法最开始看到这题的时候，从题目里给的样例就认为是把原串拆成n个最长的非递减序列，后来发现并不是这样，因为题目所要求的是将其拆分为最少的部分，并且所有部分都是满足在不同表示顺序中具有最小的字典序，和我的想法有那么些不同。举个栗子：对于01101111这个串，按题目要求拆开所得的串就只有01101111，而按我自己的理解，就会拆成011和0111...
2019-08-14 09:33:39
126
原创 后缀数组 模板题 HDU 3518
后缀数组 模板题 HDU 3518构造最长公共前缀——Height前提：求得rank[]数组，rank[i]表示第i个后缀的字典序排名；求得SA[]数组，SA[i]表示排名为i的后缀所在的位置Heigth[i] 表示Suffix( SA[i] )和Suffix( SA[i - 1] )的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀H[i] : 等于Height[Rank[i]]，...
2019-08-13 21:34:31
193
原创 CCPC Final 2017 Alice's Stamps
CCPC Final 2017 Alice’s Stamps和题解说得一样，一道简单的DP，dp [ i ] [ j ]代表从编号1到编号i，使用 j 个set所得的最大值初始化为0，然后就可以DP了，最后所得的dp [n] [k]就是答案（网上说是背包的变式）转移方程和思路是这样的：1、首先预处理，在输入的时候就能将每个点区间所能到的最远右端点记录下来，代码如下for(int i=1...
2019-08-13 21:26:02
241
原创 莫队算法 模板题 小Z的袜子 洛谷 P1494
莫队算法 模板题 小Z的袜子 洛谷 P1494附上题目链接 https://www.luogu.org/problem/P1494附上我的莫队启蒙链接 https://oi-wiki.org/misc/mo-algo/#include <bits/stdc++.h>using namespace std;#define ll long longconst int...
2019-08-12 18:03:12
130
原创 Survive the flood 题解
Survive the flood 题解实际上是一个简单的二分答案+bfs首先我们先用bfs得出水在不同的时间所能到达的位置，给每个位置做一个最早到达时间的记录，即step[i][j]。然后因为高度最高为1e5，那么我们开始二分这个最大跳跃高度的最小值，每次将高度传入，并以这个高度为标准再次进行rabbit在不同时间所能到达的位置，并记录rab[i][j]作为rabbit到达这个位置的时间（...
2019-08-09 07:14:40
257
原创 暑期个人赛题目 CF赛题 How many trees
暑期个人赛题目 CF赛题 How many trees?题目链接 http://codeforces.com/problemset/problem/9/D一开始看到这道题还认为世道数据结构，比完之后才发现这是一道动态规划的题目，啊啊啊，是我太菜虽然这道题左学长用了一个四维的DP，但其实只需要3个循环加一个二位DP数组即可dp [ i ][ j ]表示i个点在高度为j的情况下所得的组合数但...
2019-08-06 09:15:02
156
原创 牛客数据结构单调栈训练题 Bad Hair Day
牛客数据结构单调栈训练题 Bad Hair Day嘛，这是一道之前在比赛的时候和左学长研究过的题，多亏了左学长，现在这题能秒出。解题方法是这样的：每次在栈里放入一个高度，但放入之前，需要保证栈里面的元素是单调的，就相当于对于每一个比当前高度高的牛都做了贡献，每次答案加上单调栈里面的元素个数即可，很简单上代码：#include <bits/stdc++.h>using nam...
2019-08-06 08:55:57
169
原创 牛客优先队列训练题 NOIP2018 道路铺设
牛客优先队列训练题 NOIP2018 道路铺设虽然在牛客上分类是优先队列，但实际操作起来其实就只是一道纯贪心的题目，有点单调队列的感觉，每次找后面大于前面的，并加上后面的差值，O(n) 的时间复杂度就可过，不需要用到优先队列上代码：#include <bits/stdc++.h>using namespace std;const int maxn=1e6+7;int n,a...
2019-08-06 08:43:06
213
原创 牛客字符串训练 NOI 2014 动物园
牛客字符串训练 NOI 2014 动物园这道题应该算是一道比较简单的动态规划了，因为很容易就会发现存在递推的关系。对于每一个前缀，我们先求得其nxt数组，得出在该位置的的最长匹配，在求nxt数组的同时，我们也可以求得num数组，但此时求得的num数组并没有去重紧接着我们就可以计算答案了，但是计算答案的时候需要注意num数组的去重，这个方法很巧妙，就是利用num数组和nxt数组相似的性质，一...
2019-08-06 08:30:52
121
原创 牛客数据结构优先队列训练题 操作系统
牛客数据结构优先队列训练题 操作系统啊啊，明明一道极其简单的训练题，我想得太复杂了！！！！不说了直接上代码，就是模拟没什么好说的#include <bits/stdc++.h>using namespace std;int a,b,c,d,lastend=0;struct pro{ int id=0,at=0,ti=0,pri=0; bool operato...
2019-08-02 23:18:05
152
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人