各国OI
「POI2015」Kinoman-线段树
· ✏️ 521 words · ☕ 2 mins read

共有 $m$ 部电影,编号为 $1$ 到 $m$,第 $i$ 部电影的好看值为 $w[i]$。在 $n$ 天之中(从 $1$ 到 $n$ 编号)每天会放映一部电影,第 $i$ 天放映的是第 $f[i]$ 部。你可以选择 $l,r(1 \leq l \leq r \leq n)$ ,并观看第 $l,l+1,\dots , r$ 天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。


「POI2015」Myjnie-区间dp
· ✏️ 1098 words · ☕ 3 mins read

有 $n$ 家洗车店从左往右排成一排,每家店都有一个正整数价格 $p_i$ 。有 $m$ 个人要来消费,第 $i$ 个人会驶过第 $a_i$ 个开始一直到第 $b_i$ 个洗车店,且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 $c_i$,那么这个人就不洗车了。

请给每家店指定一个价格,使得所有人花的钱的总和最大。


「BOI2007」Mokia-CDQ分治套CDQ分治
· ✏️ 1503 words · ☕ 3 mins read

在定位系统中,世界被认为是一个 $W \times W$ 的正方形区域,由 $1 \times 1$ 的方格组成。每个方格都有一个坐标 $(x,y)$ , $1 \leq x,y \leq W$。

有三种命令,意义如下:

  • 0 W 初始化一个全零矩阵。本命令仅开始时出现一次。
  • 1 x y A 向方格 $(x,y)$ 中添加A个用户。A是正整数。
  • 2 X1 Y1 X2 Y2 查询 $X1 \leq x \leq X_2$ , $Y_1 \leq y \leq Y_2$ 所规定的矩形中的用户数量
  • 3 无参数 结束程序。本命令仅结束时出现一次。

「POI2012」Cloakroom-类背包dp
· ✏️ 605 words · ☕ 2 mins read

有 $n$ 件物品,每件物品有三个属性 $a[i], b[i], c[i]$ , $(a[i] < b[i])$ 。

再给出 $q$ 个询问,每个询问由非负整数 $m$ , $k$ , $s$ 组成,问是否能够选出某些物品使得:

  • 对于每个选的物品 $i$ ,满足 $a[i] \leq m$ 且 $b[i]>m+s$ 。

  • 所有选出物品的 $c[i]$ 的和正好是 $k$ 。


「POI2014」Salad Bar-瞎搞
· ✏️ 504 words · ☕ 2 mins read

有一个长度为 $n$ 的字符串,每一位只会是 $\text{p}$ 或 $\text{j}$ 。求一个最长子串,使得不管是从左往右还是从右往左取,都保证每时每刻已取出的 $\text{p}$ 的个数不小于 $\text{j}$ 的个数。


「POI2013」Price List-图论
· ✏️ 1103 words · ☕ 3 mins read

给定一个 $n$ 个点,$m$ 条边的无向联通图,每条边的权值均为 $a$。

原图所有满足 $u$ 节点和 $v$ 节点间最短路为 $2 \times a$ 的点对 $(u,v)$ 间建立一条无向边,边的权值均为 $b$。

给定一个起始节点$k$,求在上述操作后,$k$到所有节点的最短路径。


「POI2006」Periods of Words-KMP
· ✏️ 578 words · ☕ 2 mins read

一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串 $P$ 是串 $A$ 的前缀, 当且仅当存在串 $B$ , 使得 $A = PB$. 如果 $P \neq A$ 并且 $P$ 不是一个空串,那么我们说 $P$ 是 $A$ 的一个 $proper$ 前缀. 定义 $Q$ 是 $A$ 的周期, 当且仅当 $Q$ 是 $A$ 的一个 $proper$ 前缀并且 $A$ 是 $QQ$ 的前缀(不一定要是 $proper$ 前缀).

比如串 $abab$ 和 $ababab$ 都是串 $abababa$ 的周期. 串 $A$ 的最大周期就是它最长的一个周期或者是一个空串(当 $A$ 没有周期的时候), 比如说, $ababab$ 的最大周期是 $abab$ . 串 $abc$ 的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.


「POI2010」Antisymmetry-后缀数组
· ✏️ 790 words · ☕ 2 mins read

对于一个 $0/1$ 字符串,如果将这个字符串 $0$ 和 $1$ 取反后,再将整个串反过来和原串一样,就称作“反对称”字符串。比如 $00001111$ 和 $010101$ 就是反对称的, $1001$ 就不是。

现在给出一个长度为 $n$ 的 $0/1$ 字符串,求它有多少个子串是反对称的。


「POI2000」病毒-AC自动机
· ✏️ 463 words · ☕ 1 mins read

二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。


「POI2011」Tree Rotations-线段树合并
· ✏️ 1677 words · ☕ 4 mins read

现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 $n$ 个叶子节点,满足这些权值为 $1…n$ 的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换,使得最终所有叶子节点的权值按照前序遍历序写出来,逆序对个数最少。


「POI2014」PTA-单调队列
· ✏️ 471 words · ☕ 1 mins read

给定 $n$ 个点的高度,规定从 $1$ 点出发,跳到比高度小于当前点的点不消耗体力,否则消耗一点体力,最后到达 $n$ 点。

$q$ 次询问,每次询问有一个步伐限制 $k$ ,求最少耗费的体力。


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

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