月度归档: 2021年5月

18 篇文章

浅谈 rope
前言 今天做了 UVA12538 自带版本控制功能的IDE Version Controlled IDE 看了下题解发现可以用 rope 直接水过,所以发篇博客,记录一下 rope 的用法。 简介 rope 的本质就是块状链表。rope 是 C++ STL 中 pbds 的一个分支,想要引用,需要加上两行代码: #include <ext/r…
SP11444 MAXOR – MAXOR & bzoj 2741 【FOTILE模拟赛】L
Description 给定一个长度为 $n$ 的序列 $a_i$,有 $m$ 个询问,查询一段区间内的子区间的异或和最大值。 强制在线。 $1\leq n\leq 10^5$ Solution 首先肯定考虑使用 Trie 树。 然而普通 Trie 树并不能处理这个问题,所以我们考虑先使其可持久化,处理区间异或值。 然后再分块,记 $F[i][j]…
P6774 [NOI2020] 时代的眼泪
Description 题目链接:P6774 给定长度为 $n$ 的序列,其中第 $i$ 个点的权值为 $p_i$,保证 $p_i$ 为 $[1,n]$ 的排列。 有 $m$ 个询问,每个询问给定 $l,r,x,y$ 表示求出序列区间为 $[l,r]$ 的矩形的值在 $[x,y]$ 的顺序对数量。 $n\leq 10^5,m\leq 2\times…
#61. 【UR #5】怎样更有力气
Description 题目链接:#61. UR #5 大力水手问禅师:“大师,很多事情都需要用很大力气才能完成,而我在吃了菠菜之后力气很大,于是就导致我现在非常依赖菠菜。我很讨厌我的现状,有没有办法少吃点菠菜甚至不吃菠菜却仍很有力气?” 禅师浅笑,答:“方法很简单,不过若想我教你,你需先下山徒手修路。” 山下是 $n$ 座村庄从 $1$ 到 $n…
P5222 Game
Description 题目链接:P5222 给定一个 $N\times M$ 的网格,其中有 $T$ 个格子有障碍,现需要在第一列摆一定量棋子,每一次可以执行以下操作: 向上/向下移动一枚棋子一个单位,且该位置没有障碍、没有其他棋子将本列所有棋子移动到下一列,且下一列目标位置没有障碍 再给定 $Q$ 个询问,每个询问给出 $k_i$,询问最多能在…
P5481 [BJOI2015] 糖果
Description 题目链接:P5481 给定一个大小为 $n\times m$ 的表格,可以填入自然数 $1$ 到 $k$,要求每一行数字单调不减,且任意两行不能完全相同,求方案数,答案对 $p$ 取模。 $1\leq n,m\leq 10^5,1\leq k,p \leq 2\times 10^9$ Solution 由于单调不降,所以相当…
AT1984 [AGC001F] Wide Swap
Description 题目链接:AT1984[AGC001F] 给出一个元素集合为 ${1,2,\dots,N}$( $1\leq N\leq 500,000$)的排列 $P$,当有 $i,j (1\leq i<j\leq N)$满足$j-i\geq K (1\leq K\leq N-1)$ 且 $|P_{i}-P_{j}|==1∣$ 时,…
P1829 [国家集训队]Crash的数字表格 / JZPTAB
Desciption 题目链接:P1829 给定 $n,m$,求 $$(\sum\limits_{i=1}^n\sum\limits_{j=1}^mlcm(i,j)) \bmod 20101009$$ $1\leq n,m\leq 10^7$ Solution 首先抛开模数, $$\sum\limits_{i=1}^n\sum\limits_{j=…
P3327 [SDOI2015]约数个数和
Description 题目链接:P3327 设 $d(x)$ 表示 $x$ 的约数个数,有 $T$ 组数据,给定 $n,m$ 求 $$\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)$$ $1\leq T,n,m\leq 5\times 10^4$ Solution 首先你得知道: $$d(ij)=\sum\…
P2257 YY的GCD
Description 题目链接:P2557 有 $T$ 组数据,求: $$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)\in prime]$$ $T\leq 10^4,n,m\leq 10^7$ Solution 显然可以枚举质数,所以原式可以化为: $$\sum\limits_{i=1}^n\s…
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}…