义乌中学暑假集训 2021.07.09 D
Description 给定一棵 $n$​ 个节点的树 $T$​,有 $m$​ 个询问,每次询问给定 $l,r$​,问存在多少个 $k\in Z$​,使从树上编号为 $l$​ 的点沿着 $l\rightarrow r$​ 的简单路径走 $k$​ 步恰好到达 $k$​。 $1\leq n\leq 3\times 10^5,1\leq m\leq 3\…
CF765F Souvenirs
Description 题目链接:CF765F 给定一个长度为 $n$ 的序列 $a_i$,有 $m$ 个询问,每次询问给定 $l,r$,求对于 $i,j\in[l,r]$,且满足 $i\not = j$,$|a_i - a_j|$ 的最小值。 $1\leq n\leq 10^5,1\leq m\leq 3\times 10^5,0\leq a_i…
义乌中学暑假集训 2021.7.8 D
Preface 见到 lxl 小姐姐真的好好好兴奋!!! 果然好可爱 Description 给定一个序列 $A$,求所有 $1\leq l \leq r \leq n$ 的区间 $[l,r]$ 的最大子段和的和,答案对 $2^{64}$ 取模。 $1\leq n\leq 10^5,-10^9\leq A_i\leq 10^9$ Solution …
升学e网通 倍速播放
准备 请使用电脑网页端以进行。(手机其实也可以,不过本文不着重提) 安装 安装 Tampermonkey 可以在浏览器的**插件商店**中下载,也可以从其他渠道获取Tampermonkey的crx文件,然后解压提取出来。 然后进入浏览器设置→扩展程序,进入后再打开右上角的开发者模式并保持该窗口的开启。之后找到被解压后的tampermonkey.cr…
P2508 [HAOI2008]圆上的整点
Description 题目链接:P2508 求一个给定的圆($x^2+y^2=r^2$)的圆周上有多少个点的坐标是整数。 $r\leq 2\times 10^9$ Solution $$\begin{align}x^2+y^2=r^2 & \Leftrightarrow y=\sqrt{r^2-x^2}\& \Leftrighta…
P5298 [PKUWC2018]Minimax
Description 题目链接:P5298 给定一棵 $n$ 个节点的根节点为 $1$ 的有根树,每个节点最多有两个子节点。 定义节点 $x$ 的权值为: 若 $x$ 没有子节点,则其权值为 $a_i$。若 $x$ 有子节点,则它的权值有 $p_x$ 的概率为其子节点的权值的最大值,有 $1-p_x$ 的概率为其子节点的权值的最小值。 假设 $1…
YbtOJ LCM计数
Description 题目链接:YbtOJ 给定 $T$ 组数据,每组数据给定 $n,m$,求$$\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)[\forall n>1,n^2\not |\gcd(i,j)]$$$1\leq T\leq 10^4,1\leq n,m\leq 4\times 1…
YbtOJ 最小数
Description 题目链接:YbtOJ 109-8 给定一个正整数 $n$,求满足只由 $8$ 组成且被 $n$ 整除的最小数。 有多组数据。 Solution 题目即求满足 $n|88\dots8(k\text{个}8)$ 的最小的 $k$ 值。 转换一下:$$\begin{align}n|88\dots8(k\text{个}8) &…
bzoj4173 数学
Description 题目链接:bzoj4173 设 $S(n,m)$ 为满足 $m \bmod k + n\bmod k \ge k$ 的所有正整数 $k$ 组成的集合,求$$\phi(n)\times \phi(m)\times \sum_{k\in S(n,m)}\phi(k)\bmod 998244353$$$n,m\leq 10^{15…
P3302 [SDOI2013]森林
Description 给定一个 $N$ 个节点的森林,每个点有权值 $v_i$,初始有 $M$ 条边,有 $T$ 个操作: Q x y k 查询点 $x$ 到点 $y$ 路径上的点权种第 $k$ 小,保证合法。L x y 在点 $x$ 和点 $y$ 之间连一条边,保证合法。 强制在线 $1\leq N,M,T \leq 8\times 10^4,…
浅谈 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…