标签 莫队 下的文章
- 首页
- 莫队
CQOI2018简要题解
破解D-H协议$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ，然后答案就是 $g^{ab}\bmod P$ 。代码社交网络【模板】有向图矩阵...
CF375D Tree and Queries
CodeForcesLuogu分析如果在序列上这个问题非常的好做：设 $num[i]$ 为 $i$ 颜色的数量， $sum[i]$ 表示颜色数量 $\geq i$ 的颜色数。那么直接跑莫队即可。现在放到了树上变成了子树询问，那么直接在 dfs 序上跑就好了。当然 dsu on tree 也是可...
洛谷4688 [Ynoi2016]掉进兔子洞
LuoguBZOJ分析莫队+ $\mathrm{bitset}$。显然一个询问 $(l_1,r_1,l_2,r_2,l_3,r_3)$ 的答案是 $(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\times size$ ，这里的 $size$ 表示三个区间内出现了...
洛谷5268 [SNOI2017]一个简单的询问
LuoguBZOJLOJ分析$\begin{aligned} \sum_{i=0}^{\infty} get(l_1, r_1, x) \times get(l_2, r_2, x) = &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0,...
洛谷4462 [CQOI2018]异或序列
LuoguBZOJ分析记 $s[i]=a[1]\oplus a[2]\oplus ... \oplus a[i]$ 。问题变为 $[l-1,r]$ 中，有多少对 $(x,y)$ 满足 $s[x]\oplus s[y]=k$ 。莫队即可。代码//It is made by M_sea #incl...
洛谷3245 [HNOI2016]大数
LuoguBZOJ分析莫队 Day2两个莫队题海星。首先考虑怎么判断 $[l,r]$ 能被 $P$ 整除。设 $num[i]$ 表示 $i\sim n$ 所构成的数。如果 $[l,r]$ 能被 $P$ 整除，那么有 $\frac{num[l]-num[r+1]}{10^{r-l+1}}\equ...
洛谷3246 [HNOI2016]序列
LuoguBZOJ分析莫队。重点是两个状态怎么 $O(1)$ 的转移。先来考虑从 $[l+1,r]$ 转移到 $[l,r]$ 的情况。这样子会多出来 $[l,l],[l,l+1],...,[l,r]$ 这些区间，我们来考虑这些区间的答案。先找到这段区间的最小值 $p$ ，那么右端点在 $[p,...
洛谷1494 [国家集训队]小Z的袜子
LuoguBZOJ分析莫队。假如第$i$种袜子有$cnt[i]$个，那么抽到一双的概率是然后总的方案数是$C_{len}^2$。概率就是：$\frac{\sum\limits_{i=1}^n\,cnt[i]\cdot(cnt[i]-1)}{len(len-1)}$莫队维护一下分子就行。考虑一下...
洛谷1903 [国家集训队]数颜色 / 维护队列
LuoguBZOJ算法带修改莫队的板子（调了半年qwq）但是我写的常数巨大，吸口氧才能过qwq然而BZOJ都A了在标准莫队的操作上加上一个延时间轴的移动就行了。代码#include <bits/stdc++.h> #define re register using namespac...
洛谷2709 小B的询问
Luogu算法莫队。考虑cnt增加或减少时答案发生了什么。显然有：$(k+1)^2=k^2+2k+1$$(k-1)^2=k^2-2k+1$所以增加时，答案增加了$2k+1$；减少时，答案减少了$2k-1$。细节见代码。代码#include <bits/stdc++.h> #defi...