注意到 ，于是我们可以将每一个条件当作一条边建立无向图（ 可以转为 并建立自环）。目标为将每一个点匹配一条边。第一步，不断寻找度数为 的点并将其唯一邻边和此点匹配；第二步，对于剩余的点，如果度数为 ，则无解，否则此时图必然为若干个环，对于每一个环，按同一方向匹配环上的边和点即可。维护点的度数，在度数变为 时直接处理这个点，总时间复杂度 。 #include <iostream> #include <vector> using namespace std; using pii = pair<int, int>; int n; vector<vector&...

Hack: ```python3 n = 100000 print(n) for i in range(1, n + 1):     k = 2     p = [min(n, n + 2 - i), max(1, n - i)]     print(k, *p) ```

考虑枚举最终的列数，显然固定列数检查答案时间复杂度是 。枚举时进行一个简单的剪枝：从 开始分别向左右枚举列数，保证列数始终小于当前最优解。正确性显然。考虑复杂度：首先答案至多为 。所以向左枚举的数量至多为 ，最坏情况此值为 。向右枚举同理故最坏时间复杂度为 。 #include <climits> #include <iostream> using namespace std; int n; int m; int k; int a[200000]; int res; int Change(int base) { int res = INT_MAX; for (int i...

直接暴力做所有操作即可实测即使区间全卡满也只跑不到三秒，对于测试用例跑的比自己写的分块还要快upd: 不到三秒是错的，因为操作二开销要比操作一更大，会超过三秒。不过全操作二仍然不到四秒，还是稳稳通过。 #include <iostream> using namespace std; using ll = long long; int n; int q; ll a[100001]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 1;...

只需要一组数据： 数组 和 交替，操作全都是 ，因为只记录最大以及最小值时询问一定会递归到所有叶子，单次询问时间复杂度 ，故即可将时间复杂度卡为 。附如下分块 + 排序 + 二分做法。如何选取块长：根据代码中的做法，设块长为 ，则初始化复杂度为 ，修改复杂度为 ，查询复杂度为 ，选取 最优，此时总时间复杂度为 。upd: 因为排序开销非常大，所以将块长减小可以很大程度优化运行时间，代码中设为了 。 #include <array> #include <cstring> #include <iostream> #include <algorithm&gt...

目前两个题解都有问题第一篇题解：1000000 可以作为根 1 -1000000 1000000000000 -1000000000000000000 第二篇题解：出题人应能够想到从小到大枚举的做法并且刻意将其卡超时，不存在“通常的假设是测试数据不会极端地将所有小数都设置为解”的说法正解一：显然根最多 600000 个，不断随机取 x，期望大约 2.5 次出答案可能的不取决于随机化的正解二：真的把每个方程不管用什么方法解出来所有在范围内的根，不过可能比较麻烦 #include <chrono> #include <iostream> #include <rando...

同小红升装备 #include <deque> #include <iostream> #include <vector> using namespace std; int n; int x; int y; int t; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> x >> y >> t; vector<vector<int>> dp(n + 1, vector<int>(t ...

初始化全，操作视为区间与，之后区间查或看是否满足条件以上操作都可以使用线段树 #include <iostream> using namespace std; int n; int m; struct Lrv { int l; int r; int v; }; struct Node { // int sum = (1 << 30) - 1; // int tag = (1 << 30) - 1; int sum; int tag; Node(): sum((1 << 30) - 1), tag((1 << 30) - 1) {} v...

A 略 B 答案  C 发现 ，于是答案为  减去  最大频数 DE 倍增预处理，倍增找步数时保持 ，如果最终  则  可以变成 ，反之亦然 F set 维护所有的非零元素位置，维护总体异或和，询问在 set 上寻找需要操作的下标然后暴力除，如果变成零就从 set 中移除 G 令  距离为 。记度数大于二的位置为关键点，如果  和  之间有关键点，答案为 ，否则找到离  或  最近的关键点，距离记为 ，则答案为 。倍增维护 LCA 和关键点数量，以及以关键点为起点的多源 BFS 即可。

参考铺设道路，我们对于每一个 x 计算 cnt[x]-cnt[x-1] 就做完了使用哈希表可以避免排序复杂度__gnu_pbds::gp_hash_table 比 std::unordered_map 快，并使用 splitmix64 防造数据卡 #include <cctype> #include <chrono> #include <cstdio> #include <iostream> #include <ext/pb_ds/assoc_container.hpp> using namespace std; struct cus...

朴素做法：对每一个起点跑一遍，用一个布尔数组记录是否访问过，时间复杂度。优化：找出所有的环，答案为最近的环上点。时间复杂度。 #include <iostream> #include <vector> using namespace std; int n; vector<int> p; vector<int> res; void Dfs(int x) { res[x] = -1; int y = p[x]; if (res[y] == -1) { res[y] = y; while (y != x) { y = p[y]; res[y] = y;...

考虑二十六个字母拆成二十六位，先使用 a 串，同时将变化插入异或线性基，然后用线性基将权值消到 0 #include <array> #include <iostream> #include <valarray> #include <vector> using namespace std; int n; string a; string b; array<int, 26> xxj; array<int, 26> xxjp; array<int, 26> xxjMask; void Insert(int x, i...

考虑 sum hash给每一个 n/2 以内的数一个随机权值，预处理所有双排列 sum hash 以及前缀 sum hash，根据长度判断是哪个双排列即可 #include <chrono> #include <iostream> #include <random> using namespace std; using ull = unsigned long long; mt19937_64 myRand64(chrono::steady_clock::now().time_since_epoch().count()); int n; int q; ull ...

两行用分号可以一行 from math import gcd print(int(input()) * gcd(*map(int, input().split())))