A 三位出题人如果我们画一张 的表，会发现题目要求等价于，在这张表每个位置填 或 ，需要满足每列都不全是 且都不全是 ，每列相互独立，于是答案为 。B 数数对 ~ 之内的数进行筛质数（埃式筛或线性筛），对于所有质数 找出小于 的 的个数 ，答案为 。C 和天下枚举 的前缀二进制 ，按位与不严格小于其运算的两个数，可以将所有 的数全部用并查集合并。D 搬家我们可以发现，如果一个收纳箱从第 个物品开始装入物品，一定会有一个固定的结束点 ，这与前面的物品无关，于是我们可以考虑用倍增优化上述过程，复杂度 。E Alice and Bod由于询问一个字符串是否对称，可以使用 维护，对于第二种操作，可以将...

A 生不逢七签到题，按照题目模拟即可。官方提交代码B 交换数字由于我们交换任意位置的数字， 的值恒为定值，只会改变 的值，而我们知道 ，于是我们最大化 的值即可最小化 的值。官方提交代码C 老虎机概率和组合数学的基础，我们可以用 计算，概率可以将问题情形分成若干相等概率的情况，用满足条件的情况数，除以总情况数得到概率。有一个简单的小技巧，我们可以很容易发现图案均不相同的情况以及图案全部相同的情况计数很方便，一对图案的方案数可以用总方案数减去上述情况数计算得来。官方提交代码D 幻兽帕鲁我们跟踪某个数他是怎么移动到最终的位置的，可以发现每个数都是类似于在线段树上移动，而移动的方向取决于他二进制下从...

https://www.cnblogs.com/zrzring/p/NC55994D.html  将图上恰好 nnn 个点染成黑色，使得图上相邻的黑白点对数量恰好为 mmm  考虑 nnn 个黑点如果不相邻，则两个点的贡献互不影响 考虑相邻的情况，我们把相邻的点连边，则贡献为每一个连通块的贡献的和，我们用一个二元组表示一个连通块的大小和贡献 (x,y)(x, y)(x,y) 若一个连通块大小为 nnn，则其贡献最大为 2n+22n + 22n+2，如果初始的 m>2n+2m > 2n + 2m>2n+2，我们可以从中分出一个单独的块 (1,4)(1, 4)(1,4)，最后一定...

用一个bool数组表示每个数是否能被表示，初始化把Q所有元素设为1，然后跑一个高维前缀和算出所有的子集，类似多源最短路，这个过程可以同时多源进行 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 1e7 + 10, M = 2e6 + 10, inf = (1 <&am...

考虑数的唯一分解 f(px)=p,f(∏pixi)=1f(p^x) = p, f(\prod p_i^{x_i}) = 1f(px)=p,f(∏pixi​​)=1 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 1e7 + 10, M = 2e6 + 10, inf = 0x3f3...

按边权排序后并查集维护在一个连通块的点，bitset维护出现的颜色集合，对于询问求一个前缀和来回答询问就行了 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #include <bitset> #define int long long using namespace std; const int N = 1e6 + 10, M = 2e...

更好的阅读体验 原题 - 【FJOI2016】神秘数 如果只有一次全局询问，可以排序之后扫一遍数组，每次和比较，更新答案，直到不能更新为止 区间询问不能排序，但是如果不排序的话，进行上述操作，最多扫次就能得出答案 考虑每次更新时，可以更新的数一定比上一次更新时的大(否则在上一次更新就计入里了)，于是我们最多会更新次 于是我们就有了一个主席树的做法去优化找小于某个值的做法，复杂度 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include &l...

更好的阅读体验 考虑如何利用差分的思路，即知道起始状态和目标状态如何求出过程量 我们并不关心具体过程，只关心一步到位的过程，于是去找相对位置的位移即可，记录这组位移，再用一个原始序列去进行这样的位移即可 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 1e6 + 10, M = 2...

更好的阅读体验 裴蜀定理的推广，若，则，负数可以转化为正数处理 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #define int long long using namespace std; const int N = 1e6 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f; inline int read() { i...

更好的阅读体验 这种题一般都需要用到容斥 因为操作可以改变顺序，原题就变成了  将到的排列分成两个集合，，对于每个元素，都最多有个，求划分方案数  考虑枚举集合的大小，为了满足条件，时可以选择任意的数放入，时只能在从到里选择个 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 1e6...

更好的阅读体验  题意：求从1出发经过给定的条关键路径回到1的最短路，  注意到条边的两个端点，再加上起点1，只有这些点是关键点，其他的点都无关紧要 预处理出每两个关键点之间的最短路，然后类似于旅行者问题跑一个状压dp，讨论一下每个关键路径的两个端点转移即可 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #define mp(x, y) make_...