OI
「SDOI2008」洞穴勘测-LCT
· ✏️ 624 words · ☕ 2 mins read

辉辉热衷于洞穴勘测。

辉辉有一台监测仪器可以实时将通道的每一次改变状况,并在辉辉手边的终端机上显示:

Connect u v代表监测到洞穴u和洞穴v之间出现了一条通道,Destroy u v代表监测到洞穴u和洞穴v之间的通道被毁。Query u v,代表向监测仪询问此时洞穴u和洞穴v是否连通。

保证无论通道怎么改变,任意时刻任意两个洞穴之间至多只有一条路径。

已知在第一条指令显示之前,洞穴群中没有任何通道存在。


「Luogu2617」Dynamic Rankings-树状数组-可持久化线段树
· ✏️ 817 words · ☕ 2 mins read

给定一个含有 $n$ 个数的序列 ${a_n}$ ,回答询问或执行操作:

  • Q i j k ($1\leq i\leq j\leq n, 1\leq k\leq j-i+1$)表示询问$a[i],a[i+1]……a[j]$中第 $k$ 小的数。

  • C i t ($1 \leq i \leq n,0\leq t \leq 10^{9}$)表示把 $a[i]$ 改变成为 $t$ 。


「SDOI2013」直径-树的直径
· ✏️ 1700 words · ☕ 4 mins read

定义一棵树上最长的路径为树的直径。树的直径可能不唯一。

给定的一棵 $n$ 个结点的树,求其直径的长度,以及有多少条边满足所有的直径都经过该边。


「POI2014」KUR-Couriers-主席树
· ✏️ 451 words · ☕ 1 mins read

给一个数列 ${a_n}$ ,每次询问区间 $[l,r]$ 内有没有一个数出现次数超过一半。如果有,输出这个数,如果没有,输出 $0$ 。


「NOI2012」美食节-费用流
· ✏️ 1099 words · ☕ 3 mins read

美食节共有 $n$ 种不同的菜品,每个同学都点了一份在这 $n$ 个菜品中的菜。总共有 $m$ 个厨师来制作这些菜品。厨师们会按照要求的顺序进行制作,并且每次只能制作一人份。第 $j$ 个厨师制作第 $i$ 种菜品的时间记为 $t _ {i,j}$ 。每个同学的等待时间为所有厨师开始做菜起,到自己那份菜品完成为止的时间总长度。总等待时间为所有同学的等待时间之和。

已知共有 $n$ 种菜品,第 $i$ 种菜品需要做 $p_i$ 份,共有 $m$ 个厨师。请计算出最小的总等待时间是多少。


「NOI2009」二叉查找树-区间dp
· ✏️ 1050 words · ☕ 3 mins read

给定 $n$ 个结点的数据值 $V_i$ ,权值 $P_i$ ,访问频度 $T_i(T_i \geq 0)$ 。对于 $\forall i,j \in V$ 且 $i \neq j$ ,有 $V_i \neq V_j, P_i \neq P_j$ 。

现令这 $n$ 个点组成一颗二叉树,且满足 $\forall , i \in V$ ,若 $p$ 为 $i$ 的左子节点, $q$ 为 $i$ 的右子节点,则 $V_p < V_i < V_q$ 且 $P_i < P_p,; P_i < P_q$ 。可以证明,这样的二叉树是唯一的。点$i$ 在树中的深度 $D_i$ 定义为它到根的距离加 $1$ 。定义结点 $i$ 的访问代价 $E_i = T_i \times D_i$ 。可以修改每个点的权值为任意实数,其代价均为给定的正整数 $K$ ,但需保证任两点权值仍互不相同。

现求上文所述二叉树中,其 $\sum^n _ {i = 1}{E_i} + \sum K$ 的最小值。


「SCOI2010」连续攻击游戏-二分图匹配
· ✏️ 549 words · ☕ 2 mins read

lxhgww 最近迷上了一款游戏,在游戏里,他拥有 $n$ 个装备( $n \le 1000000$ ),每种装备都有 $2$ 个属性,这些属性的值用 $[1,10000]$ 之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。

游戏进行到最后, lxhgww 遇到了终极 boss ,这个终极 boss 很奇怪,攻击他的装备所使用的属性值必须从 $1$ 开始连续递增地攻击,才能对 boss 产生伤害。现在lxhgww想知道他最多能连续攻击 boss 多少次?


「Luogu3765」总统选举-平衡树-线段树
· ✏️ 1285 words · ☕ 3 mins read

秋之国共有 $n$ 个人,分别编号为 $1,2,…,n$ ,一开始每个人都投了一票,范围 $[1,n]$ ,表示支持对应编号的人当总统。共有 $m$ 次预选,每次选取编号 $[l_i,r_i]$ 内的选民展开小规模预选,在该区间内获得超过区间大小一半的票的人获胜,如果没有人获胜,则由小 C 钦定一位候选者获得此次预选的胜利(获胜者可以不在该区间内),每次预选的结果需要公布出来,并且每次会有 $k_i$ 个人决定将票改投向该次预选的获胜者。全部预选结束后,公布最后成为总统的候选人,没有候选人的话输出 $-1$ 。


「CQOI2012」交换棋子-费用流
· ✏️ 974 words · ☕ 2 mins read

有一个 $n$ 行 $m$ 列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第 $i$ 行第 $j$ 列的格子只能参与 $m _ {i,j}$ 次交换。

输出仅一行,为最小交换总次数。如果无解,输出 $-1$ 。


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

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

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


点分治学习笔记
· ✏️ 1326 words · ☕ 3 mins read

点分治是一种主要在树上的分治,可以在解决一些树上特定条件的路径的问题。其复杂度与大部分分治类似,大概是 $O(K ; \log{n})$( $K$ 为除分治步骤之外的时间复杂度的多项式)。


BJOI2018游记
· ✏️ 1977 words · ☕ 4 mins read

爆零滚粗。


「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}$ 。

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


AC自动机学习笔记
· ✏️ 97 words · ☕ 1 mins read

Aho–Corasick算法,常叫做AC自动机。是一种字符串多模式串匹配算法。能在线性时间内完成多个模式串对一个查询串的匹配。

能自动AC哦。