Deep_Dark_FAntasy♂

未归档

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

/ 注册

全部文章 / 未归档（共176篇）

修复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 332

修复密码(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 458

AC自动机

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

2021-10-06

0 433

(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 390

多校第六场 J.Defend Your Country

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

2021-09-29

0 321

多校第二场League of Legends

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

贪心单调队列优化dp

2021-09-08

0 336

多校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 375

区间最大公约数

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

线段树

2021-08-18

0 496

矩形重叠

相交矩形的左下是两个左下的最大，右上是两个矩形右上的最小如果相交构不成矩形，返回false class Solution { public: bool isRectangleOverlap(vector<int>& rec1, vector<int>&...

2021-05-21

1 373

Round Numbers(数位dp)

此题新颖之处在于二进制的数位dp，平常见的都是十进制数位dp因为要统计0的数量，所以前导零会有影响，那么当dp也只在没有前导零的时候才记忆化。抄自洛谷：由于我们要搜的数可能很长，所以我们的直接最高位搜起举个例子：假如我们要从 [0,1000] 找任意相邻两数相等的数显然 111,222,888 ...

数位dp

2021-01-27

1 437