分析 我们考虑 上的 ，定义 为，匹配了 个字符，当前在 节点的最大价值。那么转移为 那么，现在的问题就在于如何求出 数组。由于 指针指向的是最长后缀，所以有 的转移，这个可以在构造 指针时就构造好。那么总的复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e3 + 100; int f[N][N],fail[N],ch[N][3],val[N],size; int n,m; void insert(char *S) { int len = strlen(S +...

分析 我们发现难点其实是在如何处理距离为 的节点也可以匹配的问题。我们可以把四个字符拆开，一样的我们定义一个新的距离函数就可以了 。那么按照套路反转 或者 。我们就得到了一个卷积形式，那么最后的时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 8e5 + 100,P = 998244353; int limit = 1,R[N],L = 0,K,n,m; char A[N],B[N]; int cnt[N],g[N],f[N]; int ksm(int a,int b) { ...

分析 由于混合位运算并不具备结合律，所以我们应该是不能强制将式子化简的。但是我们考虑位运算的本质。举一个例子 运算，我们如果完整的写出表达式为 我们可以发现，其实位运算的结果只取决于每一位，而并不是整个数字的值。那么我们可以按位考虑每一位，其实按位考虑也是解决关于位运算问题的一种常见方法。我们可以令 表示一个数第 位是 最后经过一系列位运算后变为的答案。那么我们考虑最后的答案就可以贪心考虑了。我们按大到小枚举每一位。 当 这时候我们显然应该让答案 ，因为我们对于 是有大小限制的，如果第 为 都不影响答案，我们显然使 这样才有可能满足更多的条件。 当 这时候我们需要...

分析 做法非常多，有 的。好像复杂度都是 的。这里提供一种广义后缀自动机的做法。这里采用了绝对没有空节点的在线做法，空间为线性 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; char ch[210][N]; int fa[N<<1],si[N<<1],len[N<<1],nxt[N][26],last,size; int insert(int c) { if(nxt[last][c]) { int p = last,q...

分析 有一道加强版的题解 这里 。那道题要求有多个模板串。而这道题只有一个，那么我们可以通过 来解决。考虑用栈储存路径，遇到完美匹配就返回 步。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; char ch[N],S[N],ans[N]; int top = 0,nxt[N],f[N]; int main() { scanf("%s%s",ch + 1,S + 1); int n = strlen(S + 1); for(int i = 2...

分析 我们有一个性质，树的任意一个点到树另外一个点的最长距离，一定是由某一个直径的端点和该点构成的。有了这个性质。我们只需要对这几个特殊的建一个虚树。然后找到直径的端点，那么答案为 这个做三次 就好了。代码非常简单，因为我们不用真正的建出虚树。 关于定理的证明，下文全选自 网站。 引理：在一个连通无向无环图中， 、 和 是三个不同的结点。当 到 的最短路与 到 的最短路不重合时， 到 的最短路就是这两条最短路的拼接。 证明：假设 到 有一条不经过 的更短路 ，则该路与 、 形成一个环，与前提矛盾。 定理：在一个连通无向无环图中，以任意结点出发所能到达...

分析 我们可以先定义状态 为在第 列，第 行所需要的最小点击次数。那么我们有如下转移 这个是如果选择点击的转移。 这个是不点的转移。那么我们通过滚动数组的技巧，第一种的转移优化到 。然后对于 的时候特判一下就好了。时间复杂度为 。对于障碍物我们直接赋值 。 代码 #include<bits/stdc++.h> using namespace std; int read() {int x;scanf("%d",&x);return x;} const int N = 21000,inf = 0x3f3f3f3f; struct Node { int...

引入 给你两个字符串 。询问 是否匹配。其中 含有通配符 。 可以匹配任意一种字符。 分析 如果我们使用最常见的字符串匹配算法 我们发现，对于 的处理是非常复杂度的。这个我们引入一个函数 。叫做字符串 的距离函数。那么我们定义 。这样如果我们把 看做完全匹配的话，如果 我们就把他定义为 。这样就完美的解决了通配符的问题。但是由于引入了一个二元函数。我们计算上式子需要的时间复杂度为 。考虑函数展开 如果我们定义 这样我们得到了一个卷积形式。通过 或者 优化。总的复杂度变为 。 代码 #include<bits/stdc++.h> usin...

引入 求出多项式是 满足 系数对一个数取模。 推导 还是利用牛顿迭代 。那么代入牛顿迭代的公式为 然后没有学习过牛顿迭代的朋友可以看我上一篇。 当然这下面这份代码不能解决 的情况。那个时候应该使用二次剩余。 代码 #include<bits/stdc++.h> using namespace std; const int N = 4e6 + 100,P = 998244353; int limit,r[N],L; int ksm(int a,int b) {int x=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)x=1LL*...

引入 求出满足 的多项式 。 做法 既然可以快速幂求 ，其实多项式也是可以的。那么总的复杂度为 其实这个好写，常数也小，一般不会被卡。 我们可以对一个多项式求 和 。那么 求出 。之后在做一次 就可以了。记住，如果 下面给出的代码并不能通过。 代码 #include<bits/stdc++.h> using namespace std; const int N = 4e6 + 100,P = 998244353; int limit,r[N],L; int ksm(int a,int b) {int x=1;for(;b;b>>=1,a=1LL...

引入 求解 系数对一个数取模 。 前置知识 泰勒展开， 这个相信学习过高数的朋友都知道。 牛顿迭代，我们可以通过牛顿迭代找出一个函数的零点，当然这个是有一定限制的，这个可以百度搜一下。换句话就是已知 ，要求求出满足 的多项式 。考虑倍增，如果我们已经知道 。那么根据泰勒展开 因为 的前 项为 ，那么在 的意义下前 项为 。所以 变形之后 。 如此我们就得到了牛顿迭代法的公式。推导 。先做一些简单的变形 那么定义 那么其实我们就是要求出这个函数的零点。代入上面的牛顿迭代的式中可以得到 代码 #include<bits/stdc++.h> usi...

分析 直接贪心，没有什么思维难度。主要是考虑到贪心的选取更少的元素。那么元素个数为 其中 。那么考虑 如果分解完后 仍然这一位有 ，那么 。 代码 #include<bits/stdc++.h> using namespace std; int a[100],n,L,Ans; int ksm(int a,int b){ int x=1;for(;b;b>>=1,a=a*a)if(b&1)x=x*a;return x; } int main() { cin>>n; while(n){a[++L]=n%10;n/=1...

题意 分析 开放式求和 推导之后 。因为偷懒，直接上 了。 代码 T=int(input()) for i in range(T): n=int(input()) b= ((n*(2*n+1)*(n+1))//6 + (n*(n+1))//2)//2 print(b**2)