扩展kmp 这题只能用扩展kmp做了 我们求一下next就好了，然后直接统计 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 2e5+100; int net[max_n], extend[max_n]; void getnext(char p[]) { register int a = 0;register int b = 0; int nn = strlen(p); net[0] = nn...

kmp轻改 我的思路是，直接在s1中kmps2然后，当匹配到s2的最后时，直接return j就可以了 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 5e4+100; char s[max_n],p[max_n]; int net[max_n]; void getnext(){ int n = strlen(p);p[n]=1;net[0]=-1; for (int i=0,j=-1;i<n;...

kmp next数组 这题莽一看似乎是用扩展kmp做的。事实上确实，我们可以利用扩展kmp完成但是其实我们利用kmp就可以做出来了 我们已经知道了kmp中的next数组的意义next[n]意义为最长的公共前缀和后缀然后我们想知道下一个公共前缀和后缀了一点就透答案是next[next[n]]循环就好了，直到为0 #include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int max_n = 4e5+100...

最小循环节问题 #include<cstdio> #include<cstring> using namespace std; const int max_n = 1e6 + 100; char s[max_n]; int net[max_n]; int n; void get_next(char* p) { net[0]=-1; for (int i = 0, j = -1;i < n;) { if (j == -1 || p[i] == p[j])net[++i] = ++j; else j = net[j]; ...

循环节问题 其实和上一题差不多。关键都是如何判断循环节罢了 我们求出next数组后，取遍历索引求出当前数组的循环节i-next[i]然后如果cyc==i就没有循环节如果i%cyc!=0就不是完整循环节 然后输出就好了 #include<iostream> #include<algorithm> using namespace std; const int max_n = 1e6+100; int n; int net[max_n]; char p[max_n]; void getnext(){ net[0]=-1;net[n]=500; for (in...

循环节问题 经典的利用kmp算法解决。n-net[n]就是最小循环节cyc。如果n%cyc==0那么我们可以说正好，不用加否则就得加后缀但是有一个需要判断的地方，当cyc==n的时候没有循环节，那么我们要特殊判断了 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 1e5+100; int net[max_n]; void getnext(char p[],int size) { int i = 0;int j...

kmp轻改 这里有一个条件就是我们在kmp匹配时，匹配的子串不能交错。很简单稍微改一下就可以了。当我们匹配成功时，直接让j=0从头开始匹配就好了。 #include<iostream> #include<algorithm> #include<cstring> using namespace std; int net[1100]; void getnext(char p[],int size) { int i = 0;int j = -1; net[0] = -1;net[size]=(char)500;//绝对不会出现的数 whil...

kmp模板题 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 1e6+100; int net[11000]; void getnext(int p[],int psize){ net[0]=-1;p[psize]=500; for (int i=0,j=-1;i<psize;){ if (j==-1||p[i]==p[j]){ ++i;++j; ...

kmp模板题 上模板就行了 #include<iostream> #include<algorithm> #include<string> #include<vector> using namespace std; const int max_n = 1e5+100; int net[max_n]; void getnext(int p[],int size) { int i = 0;int j = -1; net[0] = -1; while (i < size) { if (j == -1 || ...

数学，结论题 告诉大家一个结论。求解任意区间的gcd中，gcd的变化最多只有log2(max(num))次 为什么这样说呢？现在假设我们求解从L到后面任意一个前缀的gcd我们想想哈，这个gcd值一定是<=a[L]的我们想想这个gcd的变化，每次变化最小还是得/2那么最多log2(a[L])次实际上变化的还会更少！！！ 那么依据这个理论，我们可以做出这题。时空复杂度其实是很小的。 #include<iostream> #include<algorithm> #include<map> using namespace std; typedef long l...

**题目，出题人说的什么G2玩意 还是有收获的 目前的斜率dp问题大致分为两类1.总结公式后，进行线性规划求解2.数形结合，与凸包相似。 本题属于第二种。我们可以求一个前缀和。然后我们可以知到，对于目前的节点j其实就是在0->j-k中找一个点，使得(sum[j]-sum[i])/(j-i)最大。我们如果硬是用dp的话，那么就是n^2级。很明显这个形式让我们想到了斜率优化。首先我们维护的是一个下凸包。为什么是这样的呢？建议看这篇博客的分析，他对斜率dp的凸包分析方法，我觉得十分有用，精辟！！！！那么我们就维护下凸包就行了。关键的第二弹：如何在O(1)的时间内得到答案？在上面的博客中，他说可...

sb问题，出题人题意说的什么G2玩意 #include<iostream> #include<algorithm> #include<vector> #include<bitset> #include<set> #include<map> using namespace std; int n,m,f; bitset<110> G[110]; bitset<110> F[110]; bitset<110> E; int par[110]; int find(int x){ retu...

状态压缩+最大流 首先我们可以很明显的看出这是一个最大流问题。其实我们也是可以将这题看成一个匹配问题，用hk算法可能能过。我没有试。 我们给出最大流做法。我们发现这里的点数实在是太多了，直接使用最大流算法肯定会超时。那么，我们分析题目。发现，行星m最多只有10颗。这意味着什么呢？意味着，对于一个人她对行星的适应性最多只有2^11-1种情况！！即2048种情况，那么我们可以一口气将点数减少很多。 #include<iostream> #include<algorithm> #include<vector> #include<functional> ...

最短路、邻接矩阵 这题拿到手里，我很是迷茫。我不知道这道题该怎么做？刚开始认为是构造，看不出来图论模型。 原来，如果我们把给的矩阵看成图的邻接矩阵的话，那么我们就可以建立图论模型了。正如题解所说。condition1：节点1有一个出度condition2：节点n有一个入度condition3：节点2->n-1出度与入度相等 我们仔细想想哈，这不就是一条最短路吗！！！！！！1->n关键的还有：如果形成环，就是形成一个以1为首尾的环和以n为首尾的环。这也是满足上述条件的。那么分这两种情况取小就可以了。 #include<iostream> #include<algor...