题解 由于给定序列，o的概率一定是1，x的概率一定是0. ?的期望实际上是0.5 我们要求的是E_{x^2},令dp_i代表到第i位时E_{x^2i}，l_i为到达i位置时的期望长度。根据上述条件，o时l_i = l_{i-1} + 1,x时l_i = 0,而x的时候l_i = 0.5 \times (l_{i-1} + 1) 根据l，观察E_i - E_{i-1},可以发现x^2 - (x - 1)^2 = 2x + 1 因此dp_i = dp_{i - 1} + 2 \times l_{i - 1} + 1 d…
题意 给定n和 a[i] b[i], 已知FWT(a[i]) * FWT(ans[i]) = FWT(b[i]),求ans[i] (XOR) 题解 FWT板题，赛后学习了一个 AC代码 #include <iostream> using namespace std; using ll = long long; ll MOD = 1e9+7; ll inv2; int n; const int maxn = (1 << 20) + 5; ll a[maxn],b[maxn]; ll qpow(…
题意 略 题解 由于这是一个不用维护原有序列的操作，我们可以考虑维护一个ST表进行RMQ查询。 这个RMQ是用来干什么呢？ 根据题目数据范围，我们知道这道题不能容忍\mathcal O(n^2)及以上的算法 我们必须要在\mathcal O(nlogn)的时间复杂度下完成所有的操作。 维护一个dp数组，dp[cur] = dp[first_greater_than_cur] + 1 这个时候就需要我们用RMQ了。二分[cur,n]，找到第一个比当前元素大的元素的位置，这时dp值就可以加1. 贪心预处理原序列的选择情…
题解 注意 这和数独不一样，是要求子矩阵中每一行 或 每一列的字符只出现一次 这个问题坑了不少人 剩下的按照官方题解就完成 • 注意到52种字符，子矩形最多52行，52列。 • 一个5252nm的做法是显然的，可以优化到52*nm。 • 枚举上下边界(最多差52) • 当左端点确定后，右端点的范围是连续的一段，并且单调 • 扫一遍即可，可以使用位运算降低复杂度。 AC代码 #include <iostream> #include <vector> #include <algorithm…
题意 初始长度2^n的01序列，要从^&|中选择n个运算符。 • 序列长度:(2^n)\to (2^{n-1})\to ... \to 16\to 8\to 4\to 2\to 1。 • 问有多少个可能，使得运算后剩下的一个字符为1。 题解 事实上这道题暴力就是标准做法，但是dfs的过程一定是3^n的，会超出题目要求时间。我们必须考虑剪枝或者对小范围数据进行优化。 官方题解解答 • 暴力的复杂度是3^n的，只需要再优化一点点! • 如果剩下了16个变量，可能性只有65536个。 • 预处理他们，得到一个3^…
题解 题目可以转化为插板法求解。考虑当x + y + z
题解 利用数学方法中的“隔板法”，不难知道结果就是 \displaystyle\sum_{k=0}^{n-1}{{n-1}\choose{k}} 这是二项式定理的展开式。所以，这道题就转换为求解2^{n-1} \mod (10^9+7) AC代码 #include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <array> using namesp…
题意 对于一个字符串s 有q个询问，对于每个询问有l,r，问的是在区间[l,r]中字典序最小子串的个数。 题解 易证字典序最小子串一定是一个字母，于是只需要统计在[l,r]范围内最小的字母出现的次数。 由于没有更新操作，我们可以直接处理出26个字母的前缀和。 时间复杂度\mathcal O(26 * |S|) 如果用离线维护查询的最大最小值来减少前缀和的维护次数，在该题的数据范围还可以省下一部分时间 用fastio可以省部分输入输出时间，前缀和用short代替int可以省一部分空间和时间 AC代码 #pragma …
题意 给定长为n的数组，初始值均为0 执行m个操作，每次操作的行为 如原题面 题解 很多人用线段树弄过去了，但是这个非常考验模板的水平，如果常数比较大这个方法就GG了 官方题解的解法说的不是很清楚，而根据官方标程的实现方式，实际上就是一个标准的RMQ逆向的过程。 首先对于RMQ 我们要学习什么是ST表。附录:ST表 然后我们在m次操作中，把一个区间分成两份: 令 d 等于 \left \lfloor \log_2(r - l + 1) \right \rfloor，我们可以用两个操作 (l, l + 2^d - 1…
题意 n个点，m1条边的图E1，n个点，m2条边的图E2。求图E2有多少子图跟图E1同构。 题解 由于题目数据范围不大考虑暴力枚举n!范围的所有结果。 答案除以自同构数。 AC代码 #include <iostream> #include <cstring> #include <algorithm> #include <numeric> using namespace std; int n, m1, m2, u[100], v[100], g1[10][10], g2…
