F Gcd Product 题意很短。主要介绍一种和 std 不同、比 std 思维量更低一些的做法。 定义 ，即 是三元组的集合。 定义 ，即两个三元组集合的积为另一个三元组的集合。 那么：通过打表可以发现， 具有积性。即对于互质的 有 。且当 为质数的幂次时，容易直接求出 。 于是只需要按线性筛的方法算出所有的 然后统计即可。实际上不需要保存所有的 ，只需要保存所有质数幂次的 的 即可（不然 MLE）。 时间复杂度应该是 。 #include <bits/stdc++.h> #define MOD 998244353 using namespace std; typ...

题意 给定一正整数序列 ，问有多少个非空子序列使得其中所有数的 为 1。 题解 容斥，设 为 为 的倍数，的非空子序列个数。那么如果 中有 个数是 的倍数那么 。 设 为 恰为 的非空子序列个数。那么 。 时间复杂度 ，其中 。 #include <bits/stdc++.h> #define MOD 1000000007 #define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp) #define REPR(temp, init_val, e...

D 偶数 手算几下会发现：实际上不用处理整个串，只需要关注一半的串即可。并且串的构成遵循一定规律。 我们先用 KMP 算出一半的串（记为 ）的 border，记其长度为 。记 的长度为 。 如果这是个周期串就很好办，下面考虑非周期串的情况。 考虑把扩展到足够长的串切分成若干段，如下所示。 即：第 段完全由前 段复制而来。第 1 段为 ，第 2 段为 。 然后会发现第 段的长度为 ，其中 是斐波那契数列，。 由于 的斐波那契数不超过 100 个，因此可知这样的段数不会很多，故可以先预处理出每一段的前缀和，然后每次询问时暴力累加贡献，详细见代码。 #include <bits...

给一个 T3 的不用主席树的简易做法。 建线段树，对每个点维护一个值 和一个有序 pair 列表，表示这个点对应的区间做完合并后，可以覆盖的区间为 ，且剩余的待合并的数为 。 这个列表的意义是：如果 增大到某个不小于 的 ，那么新的可覆盖区间会变成 ，但这时仍然有 。 对于 的定义类似：如果 增大到某个不小于 的 ，那么新的可覆盖区间会变成 ，但这时仍然有 。对于 之类的可以类似定义下去。 这样定义之后，容易发现一个列表的长度至多是 ，因为 是两倍两倍增长的。而合并两个点的信息也只需要归并两个列表的信息。因此总的时间复杂度为 。 使用这个框架的另一个好处在于其可以方便地处理在线...

F 题意 第一部分：给定 ，其中 ，求 。 第二部分：多组询问 ，求 ，其中 是斐波那契数列。 题解 第一部分：矩阵快速幂，记录 这七个值的转移即可。转移矩阵可以通过简单计算得出。 第二部分：利用 即可。 #include <bits/stdc++.h> #define MOD 998244353 using namespace std; inline int modadd(int x, int y){ return (x + y >= MOD ? x + y - MOD: x + y); } char s[50]; int a1, a2, a3, x, y, ...

C 牛牛的无向图 题意：给定一个无向图，定义 表示在无向图中点 能到达点 的所有路径中权值最小的路径的权值。多次询问，每次给出 ，问有多少无序点对的 不超过 。 由定义， 等于最小瓶颈生成树上， 到 路径上权值最大的边。而最小生成树是最小瓶颈生成树。所以问题就转化为：对于某个 ，有多少最小生成树上的点对，满足点对路径上权值最大的边的权值不超过 。 由于生成森林至多有 条边，权值至多有 种，因此可以按照树上边权从小到大的顺序维护点对个数的前缀和。这个可以用并查集统计，即在跑 Kruskal 的时候维护联通块的大小，如果要用权值为 的边把 两个联通块合并，那么 中的每个点和 ...

A 牛牛的mex 题意：给一个 到 的长为 的排列 ，多次询问，每次给出 ，问 。 做一个前缀最小值和后缀最小值，每次询问比一下即可。 #include <bits/stdc++.h> using namespace std; int read(){ int f = 1, x = 0; char c = getchar(); while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();} while (c >= '0' && c <=...

A 认为树以 为根。 显然，牛牛和路由器均以最优策略移动时，两者会在某个叶子处相遇，且牛牛会从 一直往下，追到这个叶子。那么我们就要求所有可能到达的叶子中最深的那个。 我们写下从 到 ，一路向上经过的节点序列。设其长度为 。那么路由器在不会被抓住的情况下，向上走最高能到达的点就是这个序列的第 个点。设它为 ，则 的子树内的所有叶子，路由器都能到达。 因此用一次 DFS 即可求出答案。 int to[200005], nxt[200005], at[100005], cnt; int lst[100005], fa[100005], maxdep[100005]; void dfs(i...

E 题目大意 给定 个点，第 个点有权值 。如果对于 有 不为 ，那么 间有无向边，边权为 。问从 到 的最短路。 题解 想了一个很憨的做法：依次考虑每一个位，对当前位建立一个新点，设为 。遍历所有点，如果点 满足这一位上为 ，那么连一条从 到 的边，边权为这一位对应的二进制数；再连一条从 到 的边，边权为 。 然后跑 Dijkstra 即可。时间复杂度很高，但居然能过，我也是没想到的。 #include <bits/stdc++.h> #define REP(temp, init_val, end_val) for (int temp = init_val...

题目大意 给定一张无向图，每条边有费用，每走 条边会有额外费用 ，至多走 条边。问从点 到点 的最小费用路。 题解 把每一个点拆成 个点，相当于对点记录一下时间即可直接套用 Dijkstra 算法。 #include <bits/stdc++.h> #define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp) #define REPR(temp, init_val, end_val) for (int temp = init_val; temp >...

题目大意 有 天，每天可购买 个糖，不同时间、不同的糖有不同价格。每天购买 个糖有额外代价 。须保证第 天结束时累计购买数达到 。问最小代价。 题解 写了一个朴素的二维 DP，预先对每一天的糖价格排序，然后设 为第 天结束时买了 个糖的最小代价。则 其中 表示前 天最小的 个糖的价格和。 这么做是 的。当然由于后面整个都是只和 相关的函数，因此应该也可以用单调队列维护，时间复杂度降为 。 #include <bits/stdc++.h> #define REP(temp, init_val, end_val) for (int temp = init_val...

A 由题意，设 b 的前两个数为 。那么公差最多有 9 种，即 。因此暴力枚举并判断即可。 B 可以用树形 DP，更简单的做法是发现答案等于所有边权和的两倍减去树的直径。 C 考虑固定右端点 ，计算可行的区间左端点数目。发现区间最大值随着左端点左移单调不减，区间最小值随着左端点左移单调不增。这表明如果对于某个左端点 ，区间 符合条件，那么对任意 ， 也满足。 因此预先建立 ST 表，然后枚举右端点，二分出最靠右的可行左端点即可统计答案。 int f[100005][18], g[100005][18], logg; void build_ST(int *a, int n){ for(...

题目大意 给定 ，求从 中任取两个数（可以相同）异或的最大值。多组数据。 题解 首先如果 就直接返回 ，下面均讨论 的情况。 然后看 的最高二进制位是否相同，如果相同就表明 中所有数这一位都是相同的，这一个二进制位不会对答案造成任何影响，因为异或后一定会消掉。从而可以把最高那位减掉，对新的 继续求解。 如果不相同呢？设最高位代表 ，那么由于 ，就可得到 且 。此时最优方案为令 与 异或，得到 。这就是结果。 一次求解的时间复杂度为 。 #include <bits/stdc++.h> #define REP(temp, init_val, end_val) for...

题目大意 定义 为树上编号为 两点路径上的点权异或和。求所有 的异或和。 题解 由于都是异或和，因此只需要对每一个点考虑其在所有路径中出现的次数即可。将出现分成三个部分：点出现在其子树内点和外部点的路径上、点连接其子树内点的路径上、点出现在其子树内点之间的路径上。分别统计即可。时间复杂度为 。可以一次 DFS 实现，我这里用了两次。 #include <bits/stdc++.h> #define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp) #define...