P2522 [HAOI2011]Problem b
Description 题目链接:P2522 有 $T$ 组数据,求 $$\sum\limits_{i=x}^n\sum\limits_{j=y}^m[gcd(i,j)=k]$$ $1\leq T,x,y,n,m,k\leq 5\times 10 ^4$。 Solution 可以根据容斥原理,原式可以分成四个子问题,每个子问题的式子为: $$\su…
浅谈莫比乌斯反演
浅谈莫比乌斯反演 那些各种各样的性质与定理,大多是前人几年甚至几十年才得出来的,哪里是你几天就能理解并证明的。 简介 莫比乌斯反演是数论中的重要内容。对于一些函数 $f(n)$,如果很难直接求出它的值,而容易求出其倍数和或约数和 $g(n)$,那么可以通过莫比乌斯反演简化运算,求得 $f(n)$ 的值。--OI Wiki 莫比乌斯函数 定义 $$\…
P4587 [FJOI2016]神秘数
Description 题目链接:P4587 一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}, 1 = 1 2 = 1+1 3 = 1+1+1 4 = 4 5 = 4+1 6 = 4+1+1 7 = 4+1+1+1 8无法表示为集合S的子集的和,故集合S的神秘数为8。 现给定n个正整数a[1…
P2523 [HAOI2011]Problem c
Link 题目链接:P2523 Solution 设 $f[i][j]$ 表示剩余 $n - m$人中编号 $\ge i$ 的人,其中 $j$ 个人的编号已经确定的方案数 $$f[i][j] = \sum \limits_{k = 0}^j f[i + 1][j - k] \times C_j^k (0 \le j \le n - s[i] - i…
P3516 [POI2011]PRZ-Shift
Description 题目链接:P3516 给定一个长度为 $n$ 的排列,有两种操作: (a) 将最后一个数移到最前面。(b) 把第三个数移到最前面。 连续 $k$ 个操作可以合并成一块,表示为 $ka$ 或 $kb$,要求输出一个长度小于 $n^2$ 操作序列使得进行操作后排列变为 $1,2,3,\dots,n$。 无解输出 NIE。 $1\…
P3792 由乃与大母神原型和偶像崇拜
Description 题目链接:P3792 给定一个长度为 $n$ 的序列 ${a_i}$,有 $m$ 个操作: 单点修改查询区间 $[l,r]$ 是否可以重排成值域上连续的一段。 $n,m\leq 5\times 10^5,a_i< 2.5\times 10^7$ Solution 可以考虑记录某个点之前第一个权值相同的数的位置 $p_i…
P4581 [BJOI2014]想法
Description 题目链接:P4581 给定 $m$ 个集合,其中 $A_i={i}$,之后 $n-m$ 个集合,每个集合是之前两个集合的并集,问之后 $n-m$ 个集合的大小。 有一定容错范围。 $1\leq m \leq 10^5,1\leq n\leq 10^6$ Solution 题面提醒的很到位,这题要用随机化。 但是如何随机化?之…
bzoj2122 工作评估
Description 题目链接:bzoj2122 利用空闲时间,BX希望外出工作,工作开始之前,公司就会给BX一个评估值 $X_0$,之后每天BX的评估值都是根据上一天的评估值和当天公司的运行状况得出,即 $X_i=X_{i-1}+D_i$,但是每天的评估值有一个上限,也就是说完整的评估公式应该是 $X_i=\min{X_i-1+D_i,L_i}…
CF819B Mister B and PR Shifts
Description 题目链接:CF819B 给定一个长度为 $n$ 的全排列 ${p_i}$,定义其偏移值为 $\sum_{i=1}^{n}|p_i-i|$,你可以将 $k\in[0,n-1]$ 个数从后面移到前面,使全排列的偏移值最小,输出最小偏移值和此时的 $k$,如果有多个符合输出任意一个。 $1\leq n \leq 10^6$ Sol…
CF803G Periodic RMQ Problem
Description 题目链接:CF803G 一个序列 ${a_i}$ 由 $k$ 个长度为 $n$ 的序列 ${b_i}$ 拼接而成,支持 $q$ 个操作: 1 l r x,区间赋值2 l r求区间最小值 $1\leq n\leq 10^5,1\leq k \leq 10^4,1\leq q \leq 10^5,1\leq b_i\leq 10…
CF1045G AI robots
Description 题目链接:Luogu CF1045G 给定 $N$ 个点,每个点的位置为 $X_i$,覆盖半径为 $R_i$,能覆盖 $[X_i-R_i,X_i+R_i]$,权值为 $Q_i$,询问能互相覆盖到并且权值之差不大于 $K$ 的点对的数量。 $1\leq N\leq 10^5,1\leq K\leq 20,1\leq X_i,R…
LuoguP2542 [AHOI2005] 航线规划
Description 题目链接:P2542 给定一个 $n$ 个点 $m$ 条边的无向图,定义 $u,v$ 的关键边为从 $u$ 到 $v$ 的所有路径都必须经过的边,给定 $q$ 个操作: 查询 $u,v$ 两点间的关键边数量。删除边 $u,v$,保证合法。 保证任意时刻任意两点联通,不可能出现重边和自环。 $1\leq n\leq 3\tim…
LuoguP3604 美好的每一天
Description 题目链接:P3604 给定一个长度为 $n$ 的字符串(仅包含小写字母),有 $m$ 个询问区间 $[l,r]$,求区间的子区间重排能成为一个回文串的个数。 $1\leq n,m\leq 6\times 10^4$ Solution 数据范围较小,考虑莫队。 一个字符串重排能成为回文串的条件是出现次数最多有一个是奇数。 由于…
LuoguP3793 由乃救爷爷
Description 题目链接:P3793 给定一个 $n$ 个数的序列,有 $m$ 个询问,每次询问区间最大值。 $1\leq n,m\leq 2\times 10^7$,保证数据随机。 Solution 考虑分块。 如果朴素分块肯定是不能过的 $O(N\sqrt{N})$,但是这题并没有修改操作,所以考虑先预处理出第 $l$ 个块到第 $r$…
LuoguP3710 方方方的数据结构
Description 题目链接:P3710 给定一个长度为 $n$ 的序列,一开始序列的数全是 $0$,有 $m$ 个操作。 区间加区间乘单点查撤销第 $p$ 个操作(保证为加、乘操作) $1\leq n,m\leq 150000$,时间限制 $4s$,保证数据随机。 Solution 首先如果只有前 $3$ 个操作可以使用线段树。 然后考虑第 …
P4117 [Ynoi2018] 五彩斑斓的世界
Description 题目链接:P4117 给定一个长为 $n$ 的序列,有 $m$ 个操作: 区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。查询区间 $[l,r]$ 中 $x$ 的出现次数。 $1\leq n \leq 10^6,1\leq m \leq 5\times 10^5,1\leq l \leq r\leq n,0\leq …
LuoguP4168 [Violet]蒲公英
Description 题目链接:P4168 给定一个长度为 $n$ 的序列,$m$ 次询问,每次询问输出区间众数,如果出现次数相同,输出编号小的。 强制在线。 $1\leq n\leq 4\times 10^4,1\leq m \leq 5\times 10^4,1\leq a_i\leq 10^9$ Solution 看到区间众数,自然而然就想…
LuoguP5071 [Ynoi2015] 此时此刻的光辉
Description 题目链接:P5071 给定一个长为 $n$ 的序列,有 $m$ 次查询,每次查询一段区间的乘积的约数个数 $\bmod 19260817$ 的值。 $1\leq n,m \leq 10^5,1\leq a_i \leq 10^9$ Solution 乍看题目,不难想到一种很暴力的做法:先对每个数质因数分解,然后利用约数和定理…
LuoguP5356 [Ynoi2017] 由乃打扑克
Description 题目链接:P5356 一个长为 $n$ 的序列 $a$,需要支持 $m$ 次操作,操作有两种: 查询区间 $[l,r]$ 的第 $k$ 小值。区间 $[l,r]$ 加上 $k$。 $1\leq n,m\leq 10^5,-2\times 10^4\leq$ 每次加上的数和原序列的数 $\leq 2\times 10^4$。 …
LuoguP4119 [Ynoi2018] 未来日记
Description 题目链接:P4119 一个长为 $n$ 的序列 $a$,有 $m$ 次操作。 把区间 $[l,r]$ 内所有的 $x$ 变成 $y$。查询区间 $[l,r]$ 内第 $k$ 小值。 $1\leq n,m,a_i\leq 10^5$ Solution stO 陈指导 Orz,陈指导码了一个下午就做完了,蒟蒻我竟然写了3天。 首…