分析 可以考虑到 为 结尾的最长的序列。那么 。所以其实这个是个四维偏序。所以我们考虑 来做。时间复杂度为 。但是有几个非常重要的减枝条件。可以参照代码。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f=1;ch = getchar();} while(isdigit(ch)) {x = x*10+ch-'0';ch=getchar...

分析 因为我们要维护，删边，加边。所以我们考虑使用 。那么现在就是求问一条边是否被所有路径经过。所以我们考虑用子集异或。那么我们 之后，节点 的子树中的异或和必须等于 。所以我们还有维护虚子树。如果能分析到异或。这道题就不难了。 代码 #include<bits/stdc++.h> using namespace std; #define ull unsigned long long const int N = 610000; ull rnd[N],val[N],s1[N],s2[N]; int ch[N][2],L[N],R[N],fa[N],n,m; bool r[N]...

分析 一次过，非常爽。考虑 上的最近邻查询。虽然有人已经证明 上的最近邻查询时间复杂度会被构造数据卡到 。但是多数情况下是非常快的。那么这道题，只是把最近邻换成第 大距离。我们只需要用个堆来动态维护一下就好了。注意因为有编号的问题，所以要注意查询的小细节。 代码 #include<bits/stdc++.h> using namespace std; #define int long long int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-...

分析 我们对于字串匹配，考虑 和 自动机。但是 对于删除操作不太好维护。所以我们考虑原串在 自动机上匹配。用栈保存路径，如果一旦发现该节点有一个标记，那么我们就往后退 步，之后继续匹配，直到原串匹配完毕，总的时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 5e6 + 100; int fail[N],ch[N][26],XZC[N],size,n; char S[N],T[N],ans[N]; int top,son[N]; void insert(char *s) { ...

分析 发现这个是与字串有关系的，就考虑后缀自动机和 自动机。我们发现对于这个问题后缀自动机使用会非常的不自然，因为我们并没有一个原串。我们就考虑如何用 自动机解决。我们可以把所有的目标串插入自动机。因为 所以结尾并没有太多状态，可以考虑状压 。令 为考虑到节点 ，现在状态为 的最小串。那么我们就只需要在 自动机上做转移就可以了，在构建 指针时，因为 指向的是当前串的最大后缀。所以我们有了第一个转移 。那么我们做一次 就可以满足长度最短，从小到大枚举字母就可以满足字典序最小这个条件。那么当我们找到第一个 其中 。那么证明它满足了所以串，这个时候递归输出就好了。每个节点...

分析 开始学 了，先来做一个模板题。个人感觉 其实就是一个高维的二叉搜索树。其实可以像替罪羊树一样重构来保证平衡，为了偷懒就没写了。 代码 #include<bits/stdc++.h> using namespace std; // #define int long long const int N = 1e7 + 100; int read() { int x = 0;char ch = getchar(); while(!isdigit(ch)) {ch = getchar();} while(isdigit(ch)) {x = x * 10 +...

分析 求第 大的大于等于 且与 互质的数，那么我们先考虑如果我们枚举第 大是谁，其实并不好做。这样时间复杂度的的下限至少为 。那么我们考虑二分一个值 ， 与 互质的数的总个数求出来，这样二分的值就具有单调性了，也可以很好的处理大于等于 这个条件，做一次差分就好了。那么现在算法的主要问题就是如何求出 有几个数与 互质。如果我们学习过 ，那么我们可以很快从这里找到相似点， 的定义为 中有几个数与 互质。而 的求解方式为 ，我们发现并不能很好的拓展到 ，但是我们不要忘了 最根本的求解方法，容斥。 。我们发现这个的定义其实比较简单，我们先去掉 的倍数，再加上 ...

写在前面的 好久没有写这样令人心旷神怡的题目了。 分析 在区间 中选取一个字典序严格大于 的且字典序尽量小的字串 。我们先考虑如何让 的字典序严格大于 ，那么必然存在一个 使得 并且 。既然是要让字典序最小，所以考虑从大到小枚举 ，找到第一个可行的 就退出，就可以保证字典序的最小。那么现在就是询问这个 区间中，是否有这样的一个字串 。这让我们想到了后缀自动机，后缀自动机可以根据 等价类来处理这个串是否出现。我们先在后缀自动机上根据转移边匹配 ，匹配的最长长度为 。那么我们就由小到大枚举字母，如果有这样一条转移边。我们就查询转移节点的 集合中，是否有一个 是属于...

分析 我们可以先写出暴力转移方程 表示 节点到子树中某个叶子节点的最小代价。那么转移方程为 可以看出这个是类似 的直线方程的，但是斜率并不单调，所以考虑李超线段树，但是从一个子树转移到另一个子树不能暴力转移，否则时间复杂度为 。所以我们考虑线段树合并，处理完子树后进行线段树合并。这样时间复杂度为 ，有大佬通过势能分析，时间复杂度为 。最后跑的还是挺快。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const LL N = 2e6 + 100,M = 1e5,inf = 0x3...

分析 联系一下基础卷积。 ，虽然这个不是最基本的卷积形式，但是我们可以通过，令 ，那么原式变为 而 是一个常数，所以我们成功的构造了卷积形式。做一次 就好了。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}...

分析 背包 题。因为朴素的 的时间复杂度为 应该过不去。那么换种思路，先考虑没有个数限制，令 为考虑前 种物品，体积为 时，总的方案数。发现我们对个数的限制可以考虑子集容斥。考虑到，恰好选 个的方案数是等于至少选 个的方案数减去至少选 的方案数。那么现在是让我们求恰好选 到 个的方案数，左式求个和，那么右式错位相消，那么至多选 的方案数为 ，最后考虑下一种的时候直接递归，要注意容斥系数也要变符号，时间复杂度为 。 计算时可以滚动数组优化一下空间。 要想到恰好选 个的方案数是等于至少选 个的方案数减去至少选 的方案数。这道题就不难了。代码 #include&...

分析 找来的 分数规划模板题。我们要求的是 ，所以直接二分 ，那么贪心的选取最大的 个 ，最后再判断 就好了。 代码 // #include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define LL long long using namespace std; LL read() { LL x = 0,f = 0;char ch = getchar(); while(!i...