牛妹的游戏 题目描述 给定一个无向图，问这个图中是否存在三元环，或者这个图的补图中是否存在三元环。 正解 三元环计数有一个很经典的根号分治的做法，这里不详细讲，网上博客讲得很清楚。 补图的边是 级别的，就不能三元环计数了，怎么办？ 由于边很多，随机三个点找到三元环的概率很大，直接随他大概 次就行。 时间复杂度 。（） 代码 #include <bits/stdc++.h> #define N 50005 using namespace std; int n, m; int x[N], y[N], deg[N]; int p[N], tot; vector<int&...

子序列 题目描述 给定一个序列，问有多少子序列满足 。 正解 这种子序列里面元素不独立的题一般不好做，考虑如何将元素的值独立。 现在 和 的值独立了，发现原问题就是求一个上升子序列个数。 用树状数组单点加，区间求和可以做到 。 注意到 并不是整数，但其实只要知道相对大小就行，即还需要离散化。 代码 #include <bits/stdc++.h> #define N 105 using namespace std; const int mod = 1e9 + 7; const double eps = 1e-10; int n; int a[N]; namespa...

边的染色 题目描述 给定一个无向图，边权为 0 / 1。 给定一些边的权，然后要你去把剩下的边权给定了。 要求对于图中每一个环,边权异或和为 0。 求方案数对 998'244'353 取模。 正解 先给出一个构造解的方法：将每一个点随便定一个点权，然后令边权等于两端点权异或和。 这样一定是合法的，因为一个环内每个点恰好出现了（被异或）两次（环内每一个点的度数都为 2）。 发现这样子给定点权的方案可以唯一对应一种给定边权的合法方案。 现在考虑题目中的边有什么用 —— 限制点权。 不考虑 -1 的边，因为 -1 的边对于点权并没有限制。 那么在一个联通块内，选择了一个点，那么联通块内所有的点的选...

牛牛与序列 先口胡一下做法，明天再来补充一下吧。 主要问题其实是求单调不降的序列个数。 考虑把原序列转化成差分序列。 然后就是一个插板的事情了。 #include <bits/stdc++.h> #define N 1000005 using namespace std; const int mod = 998244353; int n, k; int fac[N + 3], ifac[N + 3]; inline int perm(int x, int y) { return 1LL * fac[x] * ifac[x - y] % mod; } inline int...

密码系统 题目描述 给定一个长度为 的环状字符串。 将这个字符串划分成 段，每段长度为 ，这个划分的代价为字典序最大的划分子段。 求所有划分方案下，字典序最小的划分代价。 题目太难描述了自己看题吧。 正解 环状字符串按照套路先倍长，然后枚举起始位置就能枚举到所有的划分了。 现在问题就是如何快速求出一个划分的代价。 考虑后缀排序，求出每一个后缀的排名。 然后一个划分的代价其实就是区间（并不连续，类似于区间 ）的排名取 max。 这个可以用线段树或者单调队列做，时间复杂度 / 。 总复杂度 。 吐槽 这题后缀排序怎么卡二分 + 哈希啊，让我这种不会 SA 的人怎么活啊。（我的 SA 是直接...

牛牛的数学题 题目描述 辣鸡多项式板子题不配拥有描述。 正解 先来康康三道模板题。 子集卷积 多项式乘法 快速沃尔什变换 题目中那个一坨，其实相当于分别按顺序做上面的三个东西。 这题真的很没有营养，会就会，不会怎么想都写不了。 #include <bits/stdc++.h> #define N 262144 using namespace std; const int mod = 998244353, inv2 = 499122177; int n; int rev[N], lim, hib; int A[N], B[N], C[N], D[N], popc[...

最短路变短了 题目描述 给定一个有向带权图，每次询问将一条边反向会不会使 的最短路变短。 正解 先以 1 号点为源点在正图跑最短路，第 个点的距离记为 。 再以 号点为源点在反图跑最短路，第 个点的距离记为 。 设 号边为有序三元组 。（题目给定的） 修改 号边，最短路变短当且仅当 。 为啥呢？ 如果不走 号边，那么最短路显然不会变短。 如果走 号边，那么最短路一定是 。 #include <bits/stdc++.h> #define N 200005 using namespace std; int n, m, q; int u[N], v[N], w[...

相似的子串 题目描述 给定一个字符串，询问出现次数大于等于 的最长子串的长度（子串不相交）。 正解 二分 + 哈希。 首先答案显然满足单调性。 二分长度 后，如何判断答案可行？ 设 表示以 为开头，长度为 的子串，到 为止，在不相交的情况下，最多出现了多少次。 更新 数组的时候有个比较显的然贪心，即记录从左往右扫的时候，最右出现的与 相同的子串（且与当前子串不相交）出现位置的开头。 查找子串的时候利用哈希表查询相同的哈希值即可。 如何做到不相交？ 一个子串的 数组记录在开头，而在子串的尾巴位置插入哈希表，就可以做到不相交。 时间复杂度 。 一开始交了一发 map 的，多了个...

苹果树 题目描述 给定一棵大小为 的树，每一个点上有一个物品，物品的属性 。 有 次操作，操作分两类，修改和询问。 修改给定 , ，表示点 新增了一个属性为 的物品。 询问给定 , , ，询问距离节点 最近的一个 "带有属性的物品" 的节点（下面称这种节点为关键节点）。 正解 如果是随机树的话，那么有一个小 trick，在两个点的 lca 计算贡献。 每一个点 维护一个动态开点的线段树，区间 维护的是距离点 最近的关键节点。 修改每一个点的时候暴力往上跳父亲（树高为 ），然后在祖先修改线段树。 查询的时候同样是暴力往上跳父亲，在祖先查询最近的关键节点。 复杂度为 。...

环球旅行 题目描述 给定一棵大小为 的树，让你断一条边，使得树上距离最大值最小。 正解 先求出树直径的两个端点 ，，最后断的边肯定是直径上的边。 考虑枚举这条边，然后快速统计答案。 先可以预处理出直径这一条链，然后求出链上前缀的直径和后缀的直径就可以 统计答案了。 断掉直径上的边后，两边联通块的直径肯定分别是 （考虑树直径的性质，反证法可以证明）。 那么好办，对于直径上的每一个点，求出它挂出去的链的最远距离即可。 时间复杂度 。 出题人不给大样例还得自己打对拍，差评。 #include <bits/stdc++.h> #define N 1000005 #define in...

回到过去 题目描述 给定 给物品，第 个物品的大小为 ，如果两个物品大小相同，则这两个物品为一类。 要求选出一些物品总大小为 ，对于所有类别的物品，询问它是否必须被选至少一个。 不同类的物品，总大小不超过 ，且保证存在一种方案可以选出总大小为 的物品。 正解 暴力想法是对于每一类物品，不选它，然后跑背包看能不能凑出总大小为 的物品。 有一个特别优美的性质就是不同类的物品总大小不超过 ，这说明了最多只有  种物品。 但是暴力跑背包时间复杂度还是不对，是 的，就算用 bitset 优化还是跑不了。 但只要预处理出前缀的背包状态，和后缀的背包状态，对于一个类 ，就只需要 的时间复杂度就...