各省省选
「SDOI2008」递归数列-矩阵快速幂
· ✏️ 672 words · ☕ 2 mins read

一个由自然数组成的数列按下式定义:

对于 $i \leq k$ :$a_i = b_i$

对于 $i > k$ : $a_i = c_1a _ {i-1} + c_2a _ {i-2} + … + c_ka _ {i-k}$

其中 $b_j$ 和 $c_j$ ( $1 \leq j \leq k$)是给定的自然数。写一个程序,给定自然数 $m \leq n$, 计算 $a_m + a _ {m+1} + a _ {m+2} + … + a_n$, 并输出它除以给定自然数 $p$ 的余数的值。

对于 100% 的测试数据:

$1 \leq k \leq 15,1 \leq m \leq n \leq 10^{18},0 \le b_1, b_2,… b_k, c_1, c_2,…, c_k \leq 10^9,1 \leq p \leq 10^8$


「HEOI2016/TJOI2016」树-线段树
· ✏️ 628 words · ☕ 2 mins read

在2016年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树(根为 $1$),有以下两种操作:

  1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)

  2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖先)

你能帮帮她吗?


「JLOI2011」飞行路线-分层图最短路
· ✏️ 517 words · ☕ 2 mins read

Alice 和 Bob 现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在 $n$ 个城市设有业务,设这些城市分别标记为 $0$ 到 $n-1$,一共有 $m$ 种航线,每种航线连接两个城市,并且航线有一定的价格。

Alice和Bob现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多 $k$ 种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少?


「HNOI2014」世界树-虚树+树形dp
· ✏️ 1637 words · ☕ 4 mins read

世界树的形态可以用一个数学模型来描述:世界树中有 $n$ 个种族,种族的编号分别从 $1$ 到 $n$,分别生活在编号为 $1$ 到 $n$ 的聚居地上,种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连,道路的长度为 $1$。保证连接的方式会形成一棵树结构,即所有的聚居地之间可以互相到达,并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度;例如,若聚居地 $a$ 和 $b$ 之间有道路,$b$ 和 $c$ 之间有道路,因为每条道路长度为 $1$ 而且又不可能出现环,所以 $a$ 与 $c$ 之间的距离为 $2$。

出于对公平的考虑,第 $i$ 年,世界树的国王需要授权 $m_i$ 个种族的聚居地为临时议事处。对于某个种族 $x$($x$ 为种族的编号),如果距离该种族最近的临时议事处为 $y$($y$ 为议事处所在聚居地的编号),则种族 $x$ 将接受 $y$ 议事处的管辖(如果有多个临时议事处到该聚居地的距离一样,则 $y$ 为其中编号最小的临时议事处)。

现在国王想知道,在 $q$ 年的时间里,每一年完成授权后,当年每个临时议事处将会管理多少个种族(议事处所在的聚居地也将接受该议事处管理)。 现在这个任务交给了以智慧著称的灵长类的你:程序猿。请帮国王完成这个任务吧。


「SHOI2014」概率充电器-树形dp
· ✏️ 832 words · ☕ 2 mins read

著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品—— 概率充电器:

“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”

SHOI 概率充电器由 $n-1$ 条导线连通了 $n$ 个充电元件。进行充电时,每条导 线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率 决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行间接充电。

作为 SHOI 公司的忠实客户,你无法抑制自己购买 SHOI 产品的冲动。在排 了一个星期的长队之后终于入手了最新型号的 SHOI 概率充电器。你迫不及待地将 SHOI 概率充电器插入电源——这时你突然想知道,进入充电状态的元件个数的期望是多少呢?


「ZJOI2007」仓库建设-斜率优化
· ✏️ 555 words · ☕ 2 mins read

L 公司有 $N$ 个工厂,由高到底分布在一座山上。工厂 $1$ 在山顶,工厂 $N$ 在山脚。

由于地形的不同,在不同工厂建立仓库的费用可能是不同的。第 $i$ 个工厂目前已有成品 $P_i$ 件,在第 $i$ 个工厂位置建立仓库的费用是 $C_i$ 。

对于没有建立仓库的工厂,其产品应被运往其他的仓库进行储藏,而由于 L 公司产品的对外销售处设置在山脚的工厂 $N$ ,故产品只能往山下运(即只能运往编号更大的工厂的仓库),当然运送产品也是需要费用的,假设一件产品运送 $1$ 个单位距离的费用是 $1$ 。

假设建立的仓库容量都都是足够大的,可以容下所有的产品。你将得到以下数据:

  • 工厂 $i$ 距离工厂 $1$ 的距离 $X_i$(其中 $X_1=0$ );
  • 工厂 $i$ 目前已有成品数量 $P_i$ ;
  • 在工厂 $i$ 建立仓库的费用 $C_i$ ;

请你帮助 L 公司寻找一个仓库建设的方案,使得总的费用(建造费用+运输费用)最小。


「SHOI2013」发牌-fhq Treap
· ✏️ 516 words · ☕ 2 mins read

在一些扑克游戏里,如德州扑克,发牌是有讲究的。一般称呼专业的发牌手为荷官。荷官在发牌前,先要销牌。所谓销牌,就是把当前在牌库顶的那一张牌移动到牌库底,它用来防止玩家猜牌而影响游戏。

假设一开始,荷官拿出了一副新牌,这副牌有 $N$ 张不同的牌,编号依次为 $1$ 到 $N$ 。由于是新牌,所以牌是按照顺序排好的,从牌库顶开始,依次为 $1, 2, \dots$ 直到$N$ ,$N$ 号牌在牌库底。为了发完所有的牌,荷官会进行$N$ 次发牌操作,在第 $i$ 次发牌之前,他会连续进行 $R_i$ 次销牌操作, $R_i$ 由输入给定。请问最后玩家拿到这副牌的顺序是什么样的?


「SDOI2011」消耗战-虚树+树形dp
· ✏️ 973 words · ☕ 2 mins read

给定一个 $n$ 个点,以 $1$ 为根的有根树,砍断第 $i$ 条边的代价为 $c_i$。有 $m$ 次询问,每次给出 $k_i$ 个关键点(保证关键点不含 $1$ 号节点),询问能够使 $1$ 号节点不能到达任何关键点,所要砍断边的代价和最小是多少。

数据范围:$n,m \leq 250000,\sum {k_i} \leq 5 \times 10^5$


「TJOI2015」棋盘-状压dp+矩阵快速幂
· ✏️ 902 words · ☕ 2 mins read

有一个 $n$ 行 $m$ 列的棋盘,棋盘上可以放很多特殊的棋子,每个棋子的攻击范围是 $3$ 行 $p$ 列。输入数据用一个 $3 \times p$ 的矩阵给出了棋子攻击范围的模板,棋子被默认在模板中的第 [二] 行,第 [$k+1$] 列,模板中棋子能攻击到的位置标记为 1,不能攻击到的位置是 0 $(1 \leq p \leq m, 0 \leq k < p)$。输入数据保证模板中的第 [二] 行第 [$k+1$] 列是 1

打开门的密码是这样的:在要求棋子互相不能攻击到的前提下,摆放棋子的方案数。注意什么棋子都不摆也算作一种可行方案。请求出方案对 $2^{32}$ 取余的结果即可。


「SCOI2014」方伯伯的OJ-动态开点线段树
· ✏️ 1341 words · ☕ 3 mins read

方伯伯正在做他的 OJ 。现在他在处理 OJ 上的用户排名问题。 OJ 上注册了 $n$ 个用户,编号为 $1$ ~ $n$ ,一开始他们按照编号排名。

方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号 ,共有 $m$ 次操作:

  1. 操作格式为 1 x y ,意味着将编号为 $x$ 的用户编号改为 $y$ ,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证 $x$ 必然出现在队列中,同时, $y$ 是一个当前不在排名中的编号。

  2. 操作格式为 2 x ,意味着将编号为 $x$ 的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。

  3. 操作格式为 3 x ,意味着将编号为 $x$ 的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。

  4. 操作格式为 4 k,意味着查询当前排名为 $k$ 的用户编号,执行完该操作后需要输出当前操作用户的编号。

对于 $100%$ 的数据, $1 \leq n \leq 10^8,1 \leq m \leq 10^5$。

强制在线。


「HNOI2011」XOR和路径-高斯消元
· ✏️ 746 words · ☕ 2 mins read

给定一个无向连通图,其节点编号为 $1$ 到 $N$,其边的权值为非负整数。试求出一条从 $1$ 号节点到 $N$ 号节点的路径,使得该路径上经过的边的权值的 “ $\text{XOR}$ 和” 最大。该路径可以重复经过某些节点或边,当一条边在路径中出现多次时,其权值在计算 “$\text{XOR}$ 和” 时也要被重复计算相应多的次数。

直接求解上述问题比较困难,于是你决定使用非完美算法。具体来说,从 $1$ 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 $N$ 号节点为止,便得到一条从 $1$ 号节点到 $N$ 号节点的路径。显然得到每条这样的路径的概率是不同的,并且每条这样的路径的 “ $\text{XOR}$ 和” 也不一样。现在请你求出该算法得到的路径的 “ $\text{XOR}$ 和” 的期望值。


「SCOI2007」排列-状压dp
· ✏️ 371 words · ☕ 1 mins read

给一个数字串 $s$ 和正整数 $d$ , 统计 $s$ 有多少种不同的排列能被 $d$ 整除(可以有前导 $0$ )。


「SCOI2015」情报传递-树链剖分-主席树
· ✏️ 741 words · ☕ 2 mins read

给定一个 $n$ 个节点的有根树,开始时每个节点的权值都为 $0$ 。一共有 $q$ 个时刻,每个时刻可能有如下两个操作之一:

  1. 给定一个节点 $x$ ,从下一个时刻起每个时刻都给该节点的权值 $+1$(每个节点只会有一次该操作);

  2. 给定两个节点 $x,y$ 以及一个数 $C$ ,求这两个节点的简单路径上权值大于 $C$ 的节点个数,以及简单路径上的所有节点个数。


「HEOI2016/TJOI2016」序列-CDQ分治优化dp
· ✏️ 1039 words · ☕ 3 mins read

佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。

现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可 。

注意:每种变化最多只有一个值发生变化。