Deep_Dark_FAntasy♂

分类

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 未归档(176) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

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

2020/7/8 VJ contest 8 比赛

7篇文章 722人学习

2020/7/10 VJ contest 9 比赛

4篇文章 590人学习

2020牛客暑期多校训练营（第二场）

3篇文章 899人学习

2020牛客暑期多校训练营（第一场）

1篇文章 1194人学习

2020牛客暑期多校训练营（第三场）

4篇文章 596人学习

2020牛客暑期多校训练营（第四场）

3篇文章 603人学习

2020牛客暑期多校训练营（第六场）

5篇文章 723人学习

2020牛客暑期多校训练营（第五场）

4篇文章 639人学习

2020牛客暑期多校训练营（第七场）

3篇文章 622人学习

2020牛客暑期多校训练营（第九场）

1篇文章 708人学习

2020牛客暑期多校训练营（第十场）

2篇文章 577人学习

2020 CCPC网络赛

2篇文章 657人学习

SDNU Contest 10.15

0篇文章 0人学习

愿早日绿名

0篇文章 0人学习

全部文章（共235篇）

修复dna

#include<bits/stdc++.h> using namespace std; const int N=55,S=22,M=1002,INF=0x3f3f3f3f; int n,m; int tr[N*S][5],dar[N*S],idx; char str[M]; in...

2021-10-07

0 484

修复密码(kmp+状态机dp)

构造的密码位置i和j+1进行匹配，如果i确定，j+1在kmp中的转移是确定的。f[i][j]表示密码构造到i位置，状态是j的方案,枚举i+1位置处放哪个字母，固定后，就可以知道当前状态可以连向哪些状态。dp的复杂度NM26，因为里面现找它的转移到的状态，所以应该再乘M，复杂度为26*N^3 #inc...

2021-10-07

0 629

AC自动机

ac自动机是kmp在trie上的推广，kmp适用于单模式串匹配，而ac自动机适用于多模式串的匹配。既然是kmp在trie上的推广，我们不妨先来回忆一下kmp的核心：求next数组的过程。next[i]是与模式串前缀匹配的后缀最长的长度(也可以理解为与最长后缀匹配的前缀的下标)此处说的都是非平凡的前缀...

2021-10-06

0 602

(hdu多校)Function

固定g(x)后，就变成了二次函数求极值问题。分情况讨论一下即可. #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1000002,INF=0x3f3f3f3f; int a...

2021-09-29

0 537

多校第六场 J.Defend Your Country

n个点m条边，n<=1e6,初始的时候是连通的。第i个点权值是ai，现删掉一些边使得剩余连通分量的总权值最大。定义连通分量的权值，如果连通分量的包含奇数个点，则为-\sum ai,如果包含偶数个点，则为\sum ai. 首先初始n是偶数个点，则不用删边。若n是奇数个点，则可以分成若干奇数个点...

2021-09-29

0 465

多校第二场League of Legends

题目描述:n<=5000的人分成k组打游戏，[ai,bi)是每个人的空闲时间，每组至少有一个人，每个人都加入一组，每组至少玩一个单位时间，求所有组玩游戏时间总和最大。相当于把n个区间分成k组，每组求交集，k个交集之和最大。对于区间我们可以先按左端点排序，对于"大区间"（覆盖...

贪心单调队列优化dp

2021-09-08

0 468

多校1 Hash Function

ai % seed != aj %seed,那么|ai-aj|%seed != 0，|ai-aj|的集合中元素可以用fft组合出来，既然|ai-aj|不能整除seed，同时也说明seed不是任何一个|ai-aj|的因子,因此我们还要筛出每个数的因子,筛因子可以做到O(nlogn) #include ...

FFT

2021-09-01

0 495

区间最大公约数

存一个最大公约数，整个区间的最大公约数可以由左右两个子区间的最大公约数得到。但(a,b,c)和(a+x,b+x,c+x)的最大公约数没有关系。如果修改一个数的最大公约数，修改完，直接回溯就可以了，所以同时修改一个区间非常难，修改一个数easy。有没有办法变成单点修改，那么将整个区间修改可以转化为差分...

线段树

2021-08-18

0 676

对线段树Node中保存信息的学习

245. 你能回答这些问题吗1.首先是单点修改，直接pushup2.查询区间内的最大子段和一道题所有要维护的信息：考虑当前信息，能否被算出来，如果不能，增加信息，再考虑增加的信息能否被算出来，直到完备性 struct Node { int l, r;// 区间左右端点 int ...

线段树

2021-08-16

0 509

学习笔记：可持久化线段树(主席树)：静态

前置知识：权值线段树：相当于将线段树当成一个桶，其中的每一个点所代表的区间相当于一段值域。维护的值为这段值域中的一些信息。可持久化概念：可持久化实质上就是存储该数据结构所有的历史版本，以达到高效的处理某些信息的目的。可持久化线段树：假设当前线段树是这样的，修改如图的路径那么可持久化线段树会把这些点...

可持久化线段树主席树

2021-08-14

0 592