#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]; int q[N*S],ne[N*S]; int f[M][N*S]; map<char,int> ch; void insert() { int p=0; for(int i=0;str[i];i++) { int t=ch[str[i]]; if(!tr[p][t]) tr...

构造的密码位置i和j+1进行匹配，如果i确定，j+1在kmp中的转移是确定的。f[i][j]表示密码构造到i位置，状态是j的方案,枚举i+1位置处放哪个字母，固定后，就可以知道当前状态可以连向哪些状态。dp的复杂度NM26，因为里面现找它的转移到的状态，所以应该再乘M，复杂度为26*N^3 #include<bits/stdc++.h> using namespace std; const int N=55,mod=1e9+7; int n,m; char str[N]; int f[N][N]; int main() { cin>>n>>str+...

ac自动机是kmp在trie上的推广，kmp适用于单模式串匹配，而ac自动机适用于多模式串的匹配。既然是kmp在trie上的推广，我们不妨先来回忆一下kmp的核心：求next数组的过程。next[i]是与模式串前缀匹配的后缀最长的长度(也可以理解为与最长后缀匹配的前缀的下标)此处说的都是非平凡的前缀后缀。 next[0]=next[1]=0; for(int i=2;i<=n;i++) { j=next[i-1]; while(j&&p[j+1]!=p[i]) j=next[j]; if(p[j+1]==p[i]) j++; next[i]=j; } 推广到t...

固定g(x)后，就变成了二次函数求极值问题。分情况讨论一下即可. #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1000002,INF=0x3f3f3f3f; int a,b,c,d,n; LL A,B; vector<int> g[55]; LL f(int x) { return A*x*x+B*x; } int main() { for(int i=1;i<N;i++) { int tmp=i,sum=0; while(tm...

n个点m条边，n<=1e6,初始的时候是连通的。第i个点权值是ai，现删掉一些边使得剩余连通分量的总权值最大。定义连通分量的权值，如果连通分量的包含奇数个点，则为-\sum ai,如果包含偶数个点，则为\sum ai. 首先初始n是偶数个点，则不用删边。 若n是奇数个点，则可以分成若干奇数个点+若干偶数个点。 我们发现奇数个点的连通块大小必然不超过1，原因在于假设3个点的连通块，分成2+1会更优。 因此n是奇数个点，目标是分成若干个孤立点+若干偶数个点。 再想想看，这些孤立点是什么。 第一种情况：可以变成一个非割点+(n-1)个点的偶图 第二种情况: 若非割点都很大怎么办，那么就要把割点...

题目描述:n<=5000的人分成k组打游戏，[ai,bi)是每个人的空闲时间，每组至少有一个人，每个人都加入一组，每组至少玩一个单位时间，求所有组玩游戏时间总和最大。相当于把n个区间分成k组，每组求交集，k个交集之和最大。对于区间我们可以先按左端点排序，对于"大区间"（覆盖小区间的区间）可以单独自己在一组，或是和小区间在一起(此时有大区间和没大区间对答案无影响，因此只需关注小区间),(而和其他区间在一起至少会使合法长度降低,因此在最优方案中没有这种)。因此我们可以把大区间单独拎出来，单独排序，选前i长的区间之和不妨设sum[i]表示上前i个最大的大区间之和,ans=m...

ai % seed != aj %seed,那么|ai-aj|%seed != 0，|ai-aj|的集合中元素可以用fft组合出来，既然|ai-aj|不能整除seed，同时也说明seed不是任何一个|ai-aj|的因子,因此我们还要筛出每个数的因子,筛因子可以做到O(nlogn) #include <bits/stdc++.h> using namespace std; const int N = 2000010, base = 500001; const double PI = acos(-1); struct Complex { double x, y; ...

存一个最大公约数，整个区间的最大公约数可以由左右两个子区间的最大公约数得到。但(a,b,c)和(a+x,b+x,c+x)的最大公约数没有关系。如果修改一个数的最大公约数，修改完，直接回溯就可以了，所以同时修改一个区间非常难，修改一个数easy。有没有办法变成单点修改，那么将整个区间修改可以转化为差分，(x,y,z)能不能转化为差分？有(x,y,z)=(x,y-x,z-y)命题:(a1,a2,a3,...,an)=(a1,a2-a1,a3-a2,...,an-an-1)证明:右大于等于左，设左边为d,d|a1,d|a2,故d|a2-a1,...,从而d|右边，左大于等于右边，d|a1,d|a2-...

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

前置知识：权值线段树：相当于将线段树当成一个桶，其中的每一个点所代表的区间相当于一段值域。维护的值为这段值域中的一些信息。可持久化概念：可持久化实质上就是存储该数据结构所有的历史版本，以达到高效的处理某些信息的目的。 可持久化线段树：假设当前线段树是这样的，修改如图的路径那么可持久化线段树会把这些点重新复制一遍，然后修改一些信息，所有新点里面只有改变的儿子变了，另外一个儿子还指向原来的节点。每一个版本线段树结构都是完全一样的，只不过信息不一样，因此对于每一个节点来说在不同版本的对应节点在原来树里面对应同一个位置。由于可持久化线段树不能用堆的方式来存了，而应该用指针的方式来存： struct ...

相交矩形的左下是两个左下的最大，右上是两个矩形右上的最小如果相交构不成矩形，返回false class Solution { public: bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) { int minx = max(rec1[0], rec2[0]); int miny = max(rec1[1], rec2[1]); int maxx = min(rec1[2], rec2[2]); int max...

此题新颖之处在于二进制的数位dp，平常见的都是十进制数位dp因为要统计0的数量，所以前导零会有影响，那么当dp也只在没有前导零的时候才记忆化。抄自洛谷：由于我们要搜的数可能很长，所以我们的直接最高位搜起 举个例子：假如我们要从 [0,1000] 找任意相邻两数相等的数 显然 111,222,888 等等是符合题意的数 但是我们发现右端点 1000 是四位数 因此我们搜索的起点是 0000 ，而三位数的记录都是 0111,0222,0888 等等 而这种情况下如果我们直接找相邻位相等则 0000 符合题意而 0111,0222,0888 都不符合题意了 所以我们要加一个前导0标记 如果当前位 l...

常规想：dp[pos][sum],这状态是基本的。a是题目给定的，f(a)最大也就4600的样子，如果用memset优化，需要加一维dp[pos][4600][4600]来存f(a)的不同值。这个数组显然不合法。这个时候就要用减法了，dp[pos][sum]是枚举到pos位，小于等于sum的个数，这个状态是和a无关的可以用memset优化。这道题没有直接按照题目要求设置dp，而是进行了优化，使得多组样例都能用，这一点是一个数位特点，使用的条件是：约束条件是每个数自身的属性，而与输入无关。 #include<bits/stdc++.h> using namespace std; in...

https://vjudge.net/contest/419200#problem/B拓扑序从后往前，每次选最少时间就行这里用一个优先队列就能搞，有模板来着模板：https://www.cnblogs.com/atmacmer/p/5178666.html(要分清输入的是谁是谁的前继以反向拓扑)模板： struct node{ int id; int val; node(int _id,int _val){ id=_id; val=_val; } friend operator < (const node& ...