题解
「国家集训队」聪聪可可-点分治
· ✏️ 932 words · ☕ 2 mins read

有一颗 $n$($n<20000$)个节点的树,每条边都有边权。接下来由聪聪和可可分别随即选一个点,如果两点之间简单路径上的边权和是 $3$ 的倍数,则判聪聪赢,否则可可赢。

聪聪非常爱思考问题,希望知道对于这张图自己的获胜概率是多少。


「NOI2015」软件包管理器-树链剖分
· ✏️ 1215 words · ☕ 3 mins read

你决定设计你自己的软件包管理器。如果软件包 A 依赖软件包 B ,那么安装软件包 A 以前,必须先安装软件包 B 。同时,如果想要卸载软件包 B ,则必须卸载软件包 A 。现在你已经获得了所有的软件包之间的依赖关系。除 $0$ 号软件包以外,所有软件包都会依赖一个且仅一个软件包,而 $0$ 号软件包不依赖任何一个软件包。依赖关系不存在环。

现在有一些安装或卸载软件包的操作,需要求出这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包)。


「SDOI2011」工作安排-费用流
· ✏️ 1025 words · ☕ 3 mins read

你的公司需要提供 $n$ 类产品,其中第 $i$ 类产品共需要 $C _ {i}$ 件。公司共有 $m$ 名员工。员工能够制造的产品种类有所区别,我们用一个由 $0$ 和 $1$ 组成的 $m\times n$ 的矩阵 $\mathbb {A}$ 来描述每名员工能够制造哪些产品。

对于员工 $i$ ,给出 $S_i$ 。定义他的愤怒值与他制作的产品数量之间的函数是一个 $S_i+1$ 段的分段函数。设 $T _ {i,0}=0$,$T _ {i,S _ {i+1}}=+\infty$ ,那么当他制造第 $[T _ {i,j-1}+1,T _ {i,j}]$ 件产品时,每件产品会使他的愤怒值增加 $W _ {i,j}$ , $1\leq j\leq S _ {i+1}$ 。保证 $0<W _ {i,j} < W _ {i,j+1}, ; 0 < T _ {i,j} < T _ {i,j+1}$ 。

你的任务是制定出一个产品的分配方案,使得订单条件被满足,并且所有员工的愤怒值之和最小。


「NOI2014」动物园-KMP
· ✏️ 737 words · ☕ 2 mins read

给定一个字符串 $S$ ,求出 $num$ 数组——对于字符串 $S$ 的前 $i$ 个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作 $num[i]$ 。

特别地,为了避免大量的输出,你不需要输出 $num[i]$ 分别是多少,你只需要输出所有 $(num[i]+1)$ 的乘积,对 $10^9+7$ 取模的结果即可。


「ZJOI2010」网络扩容-网络流-费用流
· ✏️ 949 words · ☕ 2 mins read

给定一张有向图,每条边都有一个容量 $C$ 和一个扩容费用 $W$ 。这里扩容费用是指将容量扩大 $1$ 所需的费用。

现在请你编写一个程序求出:

  1. 在不扩容的情况下, $1$ 到 $N$ 的最大流;
  2. 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。

「国家集训队」数颜色-带修改莫队
· ✏️ 494 words · ☕ 1 mins read

墨墨购买了一套 $N$ 支彩色画笔(其中有些颜色可能相同)。墨墨会向你发布如下指令:

  1. Q L R 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。

  2. R P Col 把第 $P$ 支画笔替换为颜色 $Col$ 。


「Violet」蒲公英-分块
· ✏️ 1455 words · ☕ 3 mins read

给定一个数列 ${a_n}$ ,$m$ 次询问在 $[l,r]$ 区间内的最小众数。
强制在线。


「AHOI2008」紧急集合-LCA
· ✏️ 1435 words · ☕ 3 mins read

给出一颗 $n$ 个节点的无权树, $m$ 次询问,每次给出三个点编号为 $a$ ,$b$ , $c$ ,询问到这三个点距离最小的点的编号以及其距离和。


「SDOI2011」染色-树链剖分+线段树
· ✏️ 1240 words · ☕ 3 mins read

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作,操作有两类:

  • 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$ ;
  • 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量(连续相同颜色被认为是同一段),

如“112221”由3段组成:“11”、“222”和“1”。

请你写一个程序依次完成这 $m$ 个操作。


「ZJOI2008」树的统计-树链剖分
· ✏️ 1230 words · ☕ 3 mins read

给定一颗 $n$ 个节点的树,节点编号为 $1$ 到 $n$ ,每个节点都有一个权值 $w_i$ 。

有以下三种操作或询问:

I. CHANGE u t : 把结点 $u$ 的权值改为 $t$

II. QMAX u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值

III. QSUM u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和


「ZJOI2007」时态同步-树形dp
· ✏️ 761 words · ☕ 2 mins read

给定一棵由 $n$ 个节点构成的树。

在树上存在一个“激发器”,标号为 $s$ 。当激发器工作后,电流会延边传向每一个相邻节点。而中间节点接收到电流后,会将该电流传向与它连接并且尚未接收到电流的节点。对于每条边 $e$ ,电流通过它需要的时间为 $t_e$ ,电流的转发可以认为是在瞬间完成的。最终,激电流将到达一些“终止节点”――接收电流之后不再转发的节点。

使用一次道具可以使得电流通过某条边的时间增加一个单位。请问最少使用多少次道具才可达到每一个“终止节点”同时收到电流?


「ZJOI2007」报表统计-平衡树
· ✏️ 1202 words · ☕ 3 mins read

有一个长度为 $n$ 的整数序列,并且有以下三种操作:

  • INSERT i k :在原数列的第 $i$ 个数后面添加一个新数 $k$ ;如果原数列的第 $i$ 个数已经添加了若干数,则添加在这些数的最后

  • MIN GAP:查询相邻两个数的之间差值(绝对值)的最小值

  • MIN SORT GAP:查询所有数中最接近的两个数的差值(绝对值)


「NOI2005」维护数列-非旋Treap
· ✏️ 1513 words · ☕ 4 mins read

维护一个数列,给定初始的 $n$ 个数字。

现有六种命令:

  • 在第 $pos$ 个数后插入 $tot$ 个数
  • 翻转从第 $pos$ 个数开始的 $tot$ 个数
  • 删除从第 $pos$ 个数开始的 $tot$ 个数
  • 查询从第 $pos$ 个数开始的 $tot$ 个数的和
  • 设定从第 $pos$ 个数开始的 $tot$ 个数设定为 $c$
  • 查询整个数列中和最大的连续子区间的和

「NOI2002」银河英雄传说-并查集
· ✏️ 724 words · ☕ 2 mins read

初始时,第 $i$ 号战舰处于第 $i$ 列 $(i = 1, 2, …, 30000)$ 。

有两种指令:

合并指令为 M i j ,含义为将第 $i$ 号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第 $j$ 号战舰所在的战舰队列的尾部。

询问指令为 C i j 。该指令意思询问第 $i$ 号战舰与第 $j$ 号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。