JOI

JOI刷题笔记

NOI考完了, 挂分80还有没打完的30遗憾打铁

另一方面也发现自己观察性质, 思维题, dp方向差很多啊

看到身边人都刷穿JOI, 板刷CF, 就从这里开始了.

写这篇博客时hexo爆炸换成了qyc的jekyll, 主要是省心不用配置, 并增加了折叠功能, 就把题目都粘过来提高阅读体验了.

「JOI 2017 Final」T1 焚风现象

给定序列 $a$ , 构造序列 $b$ :

• 若 $a_i=a_{i-1}, b_i=b_{i-1}$ .
• 若 $a_i>a_{i-1}, b_i=b_{i-1}-(a_i-a_{i-1})t$
• 若 $a_i<a_{i-1}, b_i=b_{i-1}+(a_{i-1}-a_i)s$

$q$ 次对 $a$ 区间加一个数, 询问 $b_n$ .

$n, q\le 2\times 10^5$

一脸差分, 差分后变成单点修改, 那么直接维护 $b$ 的差分就好了, 树状数组单点修改区间求和.

「 JOI 2017 Final」T2 准高速电车

JOI 铁路公司是 JOI 国唯一的铁路公司.

在某条铁路沿线共有 N 座车站, 依次编为 $1\ldots N$ 号. 目前, 正在服役的车次按照运行速度可分为两类:高速电车(简称快车)与普通电车(简称慢车).

• 慢车每站都停. 乘慢车时, 对于任意一座车站  $i(1\leqslant i<N)$ , 车站  $i$  到车站  $i+1$  用时均为  $A$ .
• 快车只在车站  $S_1, S_2, \ldots, S_M$  停车  $(1=S_1<S_2<\cdots<S_M=N)$ . 乘快车时, 对于任意一座车站  $i(1\leqslant i<N)$ , 车站  $i$  到车站  $i+1$  用时均为  $B$ .

JOI 铁路公司现拟开设第三类车次:准高速电车(简称准快车). 乘准快车时, 对于任意一座车站  $i(1\leqslant i<N)$ , 车站  $i$  到车站  $i+1$  用时均为  $C$ . 准快车的停站点尚未确定, 但满足以下条件:

• 快车在哪些站停车, 准快车就得在哪些站停车.
• 准快车必须恰好有  $K$  个停站点.

JOI 铁路公司希望, 在  $T$  分钟内(不含换乘时间), 车站  $1$  可以抵达的车站(不含车站  $1$ )的数量 尽可能多. 但是,「后经过的车站的编号」必须比「先经过的车站的编号」大.

求出在  $T$  分钟内, 可抵达车站的最大数目.

保证 $A\le C\le B$

交换着证明一下发现对任意一座车站按高速, 准高速, 慢速顺序一定不劣.

于是高速列车把数轴分成若干段.

对于一段, 按照每次从当前能到的最后一个车站往后一个位置建设准快车站一定不劣.

同时, 每一段是独立的并且每一段是不严格上凸的, 所以每次选增益最大的一段增加一个车站一定不劣.

「JOI 2017 Final」T3 JOIOI 王国

JOIOI 王国是一个  $H$  行  $W$  列的长方形网格, 每个  $1\times 1$  的子网格都是一个正方形的小区块. 为了提高管理效率, 我们决定把整个国家划分成两个省 JOI 和 IOI .

我们定义, 两个同省的区块互相连接, 意为从一个区块出发, 不用穿过任何一个不同省的区块, 就可以移动到另一个区块. 有公共边的区块间可以任意移动. 我们不希望划分得过于复杂, 因此划分方案需满足以下条件:

• 区块不能被分割为两半, 一半属 JOI 省, 一半属 IOI 省.
• 每个省必须包含至少一个区块, 每个区块也必须属于且只属于其中一个省.
• 同省的任意两个小区块互相连接.
• 对于每一行/列, 如果我们将这一行/列单独取出, 这一行/列里同省的任意两个区块互相连接. 这一行/列内的所有区块可以全部属于一个省.

现给出所有区块的海拔, 第  $i$  行第  $j$  列的区块的海拔为  $A_{i, j}$ . 设 JOI 省内各区块海拔的极差(最大值减去最小值) 为  $R_{\text{JOI}}$ , IOI 省内各区块海拔的极差为  $R_{\text{IOI}}$ . 在划分后, 省内的交流有望更加活跃. 但如果两个区块的海拔差太大, 两地间的交通会很不方便. 因此, 理想的划分方案是 $ \max(R_{\text{JOI}}, R_{\text{IOI}}) $ 尽可能小.
你的任务是求出  $\max(R_{\text{JOI}}, R_{\text{IOI}})$  至少为多大.

对于所有数据, $2\leqslant H, W\leqslant 2000, A_{i, j}\leqslant 10^9(1\leqslant i\leqslant H, 1\leqslant j\leqslant W)$

首先看出划分是一个三角形.

那么考虑全局极差, 答案要么是全局极差, 要么全局最大值最小值分属不同省.

那么把最大值在的省叫 $A$ , 另一个叫 $B$ .

求极差时一定是全局最大值最小值和另一个什么东西相减.

容易想到二分答案.

那么二分完之后一些点被标记成不能是 $A$ , 求出满足这个情况下 $A$ 最大的情况, 然后看 $B$ 是否满足条件即可.

「JOI 2017 Final」足球

你是 JOI 联赛中一所声名卓著的足球俱乐部的经理.

俱乐部有 N 名球员, 编号为  $1\ldots N$ . 球员们每天都刻苦地进行训练, 剑指联赛冠军. 足球场可视为一个底为 $ W$  米, 高  $H$  米的长方形, 底平行于东西方向, 高平行于南北方向. 如果某个点向北走  $i$  米, 再向西走  $j$  米恰好到达球场的西北角, 这个点可用坐标  $(i, j)$  来表示.

练习结束后, 你要回收练习用的足球. 开始回收时, 所有球员都在足球场上, 球员  $i (1\leqslant i\leqslant N) $ 位于  $(S_i, T_i)$ , 球在球员  $1$  脚下. 你正和球员  $N$  一起站在  $(S_N, T_N)$ , 并准备回收球. 球员们把球传到  $(S_N, T_N)$  时, 你才会回收球.

你可以指挥球员, 但某些操作会提升球员的疲劳度. 一个球员不能同时进行多项操作. 你可以指挥控球的球员进行如下操作:

-踢球. 在东西南北四个方向中任选一个, 并指定一个正整数  $p$ , 该球员将球朝指定方向踢出恰好  $p$  米.假定球滚动时可以穿过其他球员. 该球员不会移动, 且自动停止控球, 疲劳度上升  $A\times p+B$ .
-运球. 在东西南北四个方向中任选一个, 该球员带球, 朝指定方向移动  $1$  米. 该球员仍然控球, 疲劳度上升 $C$ .
-停止控球. 该球员的疲劳度不改变.

你可以指挥没有控球的球员进行如下操作:

-移动. 在东西南北四个方向中任选一个, 该球员朝指定方向移动  $1$  米, 疲劳度上升  $C$ .
-控球. 如果该球员所在的位置恰好有球, 且没有其他球员控球, 该球员才能控球. 该球员的疲劳度不改变.

球员和球有可能跑出场外, 一个位置上可能有多个球员.
一天的训练结束后, 球员们非常疲惫. 你想知道在回收球的过程中, 所有球员的疲劳度之和至少会上升多少.

对于所有数据, $1\leqslant H, W\leqslant 500, 0\leqslant A, B, C\leqslant 10^9, 2\leqslant N\leqslant 10^5, 0\leqslant S_i\leqslant H, 0\leqslant T_i\leqslant W(1\leqslant i\leqslant N), (S_1, T_1)\neq(S_N, T_N)$

首先肯定观察策略的性质, 发现球并不一定始终朝着目标走, 可能传球走出奇怪折线之类的.

真正的性质是每个人只会接球一次, 否则它可以直接带着球走到第二次的位置. 所以每个人接球的位置是固定的–每个位置的球由初始位置最近的人接.

数据范围不大, 估计是 $HW$ 相关的.

因为球的路径想不到什么好性质可以联想到试着建图, 那么每个点相邻连边权值为 $C$ , 然后对每一行, 每一列单独建立一排点表示这一行列上踢球, 每个点向这一行上对应点连边权为 $B$ , 然后这一排点之间相邻两个连边权为 $A$ , 最后从这一排回来的位置连离它最近的球员的距离(球员跑过来).

但我们并没有显式禁止一个人接两次球, 在这个模型下相当于一个人第一次把球踢出去只会又无代价瞬移回原来的位置然后再接第二次, 但发现这样是不优的.

于是建图最短路就做完了.

「JOI 2017 Final」绳

JOI 小宝宝正拿着一根绳子玩. 绳子可视为一条长度为  $N$  的左右延伸的线段. 绳子由  $N$  根线连接而成, 每根线的长度为  $1$ , 厚度为  $1$ . 绳子上的线共有  $M$  种颜色, 左数第  $i$  根线 ( $1\leqslant i\leqslant N$ ) 的颜色为  $C_i(1\leqslant C_i\leqslant M)$ .绳子的左端点意为左数第  $1$  根线的左端点,绳子的右端点意为右数第  $1$  根线的右端点. 显然左数第  $i$  根线  $(1\leqslant i\leqslant N)$  的右端点 到 绳子的左端点 的距离为  $i$ .

JOI 把绳子的长度缩短了. 具体来说, JOI 反复地进行以下过程, 直到绳长缩短至  $2$ .

• 假设此时绳子的长度为  $L$ . 指定一个整数  $j(1\leqslant j<L)$ , 使绳子左数第  $j$  根线成为绳子的左端点(最左的线), 并折叠绳子. 也就是说,
  • 如果  $j\leqslant \cfrac{L}{2}$ , 则将左数第  $i$  根线  $(1\leqslant i\leqslant j)$  与左数第  $(2j-i+1)$  根线拧成一股. 此时, 绳子原本的右端点仍是右端点, 绳长变为  $L-j$ .
  • 如果  $j> \cfrac{L}{2}$ , 则将左数第 i 根线  $(2j-L+1\leqslant i\leqslant j)$  与左数第  $(2j-i+1)$  根线拧成一股. 此时, 绳子原本的左端点变为右端点, 绳长变为  $j$ .
• 两条线的颜色相同才能拧成一股. 在将两条线拧成一股前, 可以任意改变线的颜色. 将线染成其他颜色所需的费用 等于 线的厚度. 颜色匹配后, 两条线将被拧成一股, 新的一股线的厚度 将为 两条线的厚度之和.

我们把绳长缩短至  $2$  的绳子称为最终的绳子. JOI 希望使得将绳长缩短至  $2$  所需的费用尽可能小. 对于每种颜色, JOI 都想知道, 在最终的绳子中包含这种颜色的情况下, 将绳长缩短至  $2$  所需的最小费用.

你的任务是帮 JOI 解决这个问题.

感觉一边折叠一边改颜色好玄学啊.

考虑一个颜色只会被改一次, 所以每一个颜色其实可以一开始就决定好.

可以考虑当最终长度为 $1$ 时一定是上来全部染成众数的颜色.

为2时可能有两个颜色, 我们一开始把他染成若干颜色段.

那么考虑什么时候一种方案合法, 发现除了第一段和最后一段每一段长度都是偶数, 所以每一段左端点奇偶性相同, 枚举留下的一个颜色和奇偶性, 就能确定当前情况. 即对于当前每一个已有的颜色段把他首尾位置染色成和当前枚举的情况相同的.

而剩下的颜色一定是这样修改完后的众数.

「JOI 2016 Final」T1 橙子装箱

JOI 社决定将收获的  $N$  个橙子分装进一些箱子内. 在 JOI 社的工厂中, 橙子排列在输送带上, 依次编号为  $1\ldots N$ . 橙子  $i, (1\leqslant i \leqslant N)$  的大小为  $A_i$ . 由于分拣不方便, 同一个箱子内, 橙子的编号必须连续.
一个箱子内最多可以装  $M$  个橙子. 在一个箱子内装一些橙子的成本为  $K + s × (a − b)$ . $K$  是箱子本身的成本, 所有箱子的成本一样. $s$  是该箱子中橙子的数目. $a$  是该箱子中最大橙子的大小, $b$  是该箱子中最小橙子的大小.
求包装这  $N$  个橙子所需的最小成本.

对于所有数据, $1\leqslant N\leqslant 2\times 10^4, 1\leqslant M\leqslant 1000, 0\leqslant K\leqslant 10^9, 1\leqslant A_i\leqslant 10^9(1\leqslant i\leqslant N), M\leqslant N$

$O(n^2)$ dp冲了.

「JOI 2016 Final」T2 集邮比赛 2

JOI 商店街有  $N$  家商店, 这些商店从入口到出口依次编为  $1, 2, \ldots, N$  号. 商店街是单向通道, 只能从入口进去, 向出口走.

为了振兴小镇, 小镇将要举行集邮比赛. 在集邮比赛上, 每家商店都会准备  $\texttt{J, O, I}$  三种邮票中的一种, 在该商店中购物的顾客即可获得一张邮票.
在比赛中, 参赛选手从入口进入商业街后, 需要依次进入三家商店. 每位选手在入口处会得知他需要依次进入哪三家商店. 保证这三家商店依次提供邮票  $\texttt{J}$ , 邮票  $\texttt{O}$  和邮票  $\texttt{I}$ . 选手到出口时凭赛时收集的这三张邮票领取购物券.

这  $N$  家商店已经决定了自己要准备哪种邮票. 不过, 在赛前, 我们决定在商业街上新增一家店铺. 这家店开张的地点可在店铺  $i$  和店铺  $i+1 (1\leqslant i\leqslant N-1)$  之间, 或者是入口与店铺  $1$  之间, 异或是店铺  $N$  与出口之间. 这家新建的店铺也会参赛, 并准备  $\texttt{J, O, I}$  三种邮票中的一种.

选手获得礼品券的方式越多, 邮票拉力赛就越热烈. 如果两名选手进入的店铺不完全相同(比如三者都不同, 或是两者相同剩下一家不同), 那么这两名选手获得购物劵的方式不同.
我们想通过合理安排新店铺的开张地点, 使得选手获得购物券的方式尽可能多. 求在理想安排下, 选手最多有多少种获得购物劵的方式.
$N\le 10^5$

对于一个静态问题计数时, 可以考虑枚举 $\texttt{O}$ , 那么使用这个 $\texttt{O}$ 的方案数就是左边 $\texttt{J}$ 的数量乘右边 $\texttt{I}$ 的数量.

那么现在要在间隙中添加一个, 考虑是 $\texttt{J}, \texttt{I}$ 的情况, 当添加位置移动一格的时只有当中间的那个是 $\texttt O$ 时才会有影响, 可以直接对这个 $\texttt{O}$ 重新计算贡献.

如果添加的是 $\texttt O$ , 那么更简单: 直接计算左右数量即可.

「JOI 2016 Final」T3 铁路票价

给出一个包含  $N$  个点, $M$  条无向边的图, 点的编号为  $1\ldots N$ , 边的编号为  $1\ldots M$ .
$i$  号边  $(1\leqslant i\leqslant M)$  连接结点  $U_i$  和  $V_i$ . 开始时, 每条边的长度为  $1$  .
接下来有  $Q$  次修改, 第  $j$  次修改  $(1\leqslant j\leqslant Q)$  会将  $R_j$  号边的长度由  $1$  修改为  $2$  . 保证每条边最多只修改一次.
每次修改后, 试求: 与原图(未作任何修改的图)相比, 有多少结点到结点  $1$  的最短路变长了.

对于所有数据, $2\leqslant N\leqslant 10^5, 1\leqslant Q\leqslant M\leqslant 2\times 10^5; 1\leqslant U_i, V_i\leqslant N, U_i ≠ V_i(1\leqslant i\leqslant M); 1\leqslant R_j\leqslant M, R_j ≠ R_k(1\leqslant j<k\leqslant Q)$ , 保证图连通, 无重边.

要点在于从一点出发所有最短路形成的DAG中从这一点出发的所有走法都是最短路. 因为所有的边必然都连接距离差 $1$ 的两部分, 感性理解.

剩下就是简单问题, 直接倒过来加边看从1出发能到几个即可.

「JOI 2016 Final」T4 领地

有一个平面直角坐标系. JOI 君位于  $(0, 0)$  .
JOI 君每天**都按照一个固定的程序移动一轮. 该程序有  $N$  个步骤, 用一个长度为  $N$  的字符串  $S$  描述. 这个字符串仅由大写字母  $\texttt{E, N, W, S}$  构成.
左数第  $i$  个字符  $C_i (1\leqslant i\leqslant N)$  表示 JOI 君会移动到哪里. 如果在执行步骤  $i$  前, JOI 君位于  $(x, y)$ :

• $C_i=\texttt{E}$ : JOI 君将移动到  $(x+1, y)$ ;
• $C_i=\texttt{N}$ : JOI 君将移动到  $(x, y+1)$ ;
• $C_i=\texttt{W}$ : JOI 君将移动到  $(x-1, y)$ ;
• $C_i=\texttt{S}$ : JOI 君将移动到  $(x, y-1)$ .

次日 JOI 君会从他前一天停止的位置开始执行程序.
JOI 君会把  $(0, 0)$  以及每个步骤结束后到达的点作标记. 开始时 JOI 君没有标记任何点. $K$  天后, 对于任意整数  $a, b$ , 如果  $(a, b), (a+1, b), (a, b+1), (a+1, b+1)$  这四个点都被标记了一次或以上, 以这四个点为顶点的  $1\times 1$  的正方形就属于 JOI 君的领地.
请问  $K$  天后, JOI 君有多少个领地.

对于所有数据, $1\leqslant N\leqslant 10^5, 1\leqslant K\leqslant 10^9$ .

首先把每天的位移向量记作 $v$ . 也就是说第 $i$ 天他在 $vi$ 的位置

考虑如果路径全部在 $v$ 框成的矩形内, 也就是说两天之间的不相交, 那么很好, 求一天的然后乘 $k$ 就好.

然后发现只有一维在 $v$ 框出的区间即可, 即若以 $(0, 0)$ 为起点移动, 只要所有点 $p$ 满足 $p_x\in [0, v_x]$ 就可以.

核心在于, 我们可以通过调整轮数把这个点移动到这个框里, 就是若 $p_x=v_x+1$ 我们就让他变成下一轮的 $p_x=1$ .

于是现在就成了不交的问题了, 只要遍历这一轮的每个点判断以其为一角的格子的其他三个角点出现时间和自己的取交就是这个位置的格子被占有的次数.

要特判 $v_x=v_y=0, v_x=0\ne v_y$ 等情况哦.

「JOI 2016 Final」T5 断层

地面是由无限多无限长的地层堆叠成的, 画到平面上, $y=0$ 为地面, 现在有 $q$ 变化, 每次给出三个参数 $d, x, l$ 表示画一条穿过 $(x, 0)$ 的, 斜率为 $d\in{1, -1}$ 的直线把地层切开, 之后这条直线上方的地层向上移动 $l$ 层. 求所有变化结束后所有位置 $i\in [1, n]$ 的地层一开始是第几层.

$n, q\le 2\times 10^5$

所有地层都是斜着移动的, 十分诡异, 此时要想到旋转坐标轴, 将坐标轴顺时针旋转45°后就是每次把一个矩形向右或向下移动.

第二, 我们维护所有地层的点显然是困难的, 要想办法聚焦一层或一层的点, 光看第一层显然是不行的, 正确做法是倒着做, 每次将地层下降, 那么只用聚焦于最后询问的时候一层都下沉到哪里.

然后我们惊喜的发现, 实际上将地层下降还带来一个好处: 原来我们上升的时候会改变点的相对顺序, 但下降是不会的.

于是现在问题变成了, 平面上有若干点, 每次选择一个前缀或后缀(两维前后缀都一样)平移一段, 求最后点的坐标.

那么你发现此时两维坐标很独立, 开两个树状数组分别维护即可.

「JOI 2018 Final」T1 寒冬暖炉

JOI 的家里有一个暖炉. JOI 君比较耐寒, 所以他独自在家里时不用开暖炉, 但是有客人的时候就必须要开暖炉了.

这一天, JOI 有  $N$  个客人, 第  $i$  位客人  $(1\le i\le N)$  到达的时间是时刻  $T_i$ , 并在时刻  $T_i+1$  离开. 不会有多位客人同时到访.

JOI 可以在任何时刻开启暖炉, 不过在每次开启暖炉的时候会消耗一根火柴. JOI 只有  $K$  根火柴, 所以最多只能开启暖炉  $K$  次. 在这一天伊始, 暖炉是关着的.

暖炉开着的时候需要燃料. 为了节省燃料, JOI 想最小化暖炉工作的总时间.

给出 JOI 的客人们到访的时间以及 JOI 拥有的火柴根数, 你需要编写一个程序计算暖炉最少需要工作多长时间.
对于所有输入数据, 有 $1 \le N \le 10^5, 1 \le K \le N, 1 \le T_i \le 10^9 (1 \le i \le N), T_i<T_{i+1} (1 \le i \le N-1)$

看着像wqs二分, 是对的, 不过可以更简单.

把空闲的位置设为 $1$ , 有客人的地方减去 $-inf$ , 则要在序列上选 $k$ 段使得和最小.

每次选最小子段和一定不劣吧.

等价于每次选择没人的最长的一段, 在这里断开一段.

复杂度1log.

「JOI 2018 Final」T2 美术展览

JOI 国将举行美术展, 在美术展中将展出来自全国各地的各种美术品.

现在有  $N$  件候选美术品, 编号为  $1$  至  $N$ . 每件艺术品有描述其尺寸与价值的两个整数, 第  $i$  件艺术品的尺寸为  $A_i$ , 其价值为  $B_i$ .

美术展至少有一件美术品被选中并展示, 并且举办美术展的展览馆足够大, 所以展出所有的  $N$  件美术品也是可行的. 为了符合 JOI 国人民的审美, 我们想使得参展的美术品之间的尺寸之差不能太大. 并且, 我们想使得参展的美术品价值之和尽量大. 因此, 我们决定按照以下方式选定参展的美术品:

在参展美术品中, 令  $A_{max}$  为所选美术品中最大的尺寸, $A_{min}$  为所选美术品中最小的尺寸. 令  $S$  为所有参展美术品的总价值之和. 给出候选美术品的数量以及其尺寸与价值, 求  $S-(A_{max}-A_{min})$  的最大值.

对于所有输入数据, 有 $2 \le N \le 5\times 10^5, 1 \le A_i \le 10^{15} (1 \le i \le N), 1 \le B_i \le 10^9 (1 \le i \le N)$

首先把 $A$ 排序, 发现选择的一定是一段连续的区间. 因为最大最小值确定后中间的当然全加进来.

设 $b$ 前缀和数组为 $s$ , 就是 $\max_{i>j} (s_i-s_{j-1})-(a_i-a_j)$

于是扫一遍就结束了.

「JOI 2018 Final」T3 团子制作

你是一个制作团子的师傅, 现在, 你正想用竹签把团子串成一串.

团子被放置在长为  $N$  行, 宽为  $M$  列的隔开的格子里, 每个格子里都放着一个团子. 每个团子的颜色是红、绿与白中的一种.

你可以选择三个从左到右, 或者从上到下的连续的格子, 把格子中的团子串成一串, 按照这个顺序, 一串团子串上正好会有三个团子.

现在, 你希望尽可能多做些颜色按照红绿白顺序的团子串, 并且团子在串上的顺序必须与从格子中取出的顺序相同. 需要注意的是, 同一个团子只能被串在一串团子串上.

你最多能制作多少串团子串呢?

给出放置在每个格子上的团子的颜色, 你需要计算最多能制作的团子串的数量. 团子串的颜色必须按照红、绿、白的顺序.
$N, M\le 3000$

肯定考虑中间的那个.

上来先觉得是不是建图网络流, 然后似乎看起来是二分图, 但 $3000\times 3000$ 咋看都跑不过啊.

画图发现,只有同一反对角线的绿色团子才会相互影响!.

那么每一个反对角线单独做, dp即可. 是设 $f_{i, 0/1/2}$ 表示前 $i$ 个, 最后一个是横着, 竖着或不串的答案.

「JOI 2018 Final」T4 月票购买

JOI 所住的城市有  $N$  个车站, 分别编号为  $1 \dots N$ . 有  $M$  条铁路, 编号为  $1 \dots M$ . 第  $i$  条铁路双向连接车站  $A_i$  与车站  $B_i$ , 乘车费用为  $C_i$ .

JOI 住在车站  $S$  附近, 而 JOI 所在的 IOI 高中在车站  $T$  附近. 他打算买一张月票往返这两个车站. 当他买这张月票时, 他需要选择一条在车站  $S$  与车站  $T$  之间的乘车费用最小的路径. 有了这张月票, JOI 可以无需额外费用, 双向通过任意所选路径包含的铁路.

JOI 经常去在车站  $U$  与车站  $V$  附近的书店, 因此他希望能买一张月票使得从车站  $U$  到车站  $V$  的花费最小.

当他要从车站  $U$  去往车站  $V$  时, 他会选择一条从车站  $U$  到车站  $V$  的路径. 对于路径上的每段铁路, 如果这段铁路在月票指定的路径范围内, 则费用为  $0$ , 否则费用为  $C_i$ . 每段铁路的费用和为 JOI 从车站  $U$  到车站  $V$  的总费用.

他想要知道, 如果他买月票时选择了一条合适的路线, 从车站  $U$  到车站  $V$  的最小费用是多少.

你需要编写一个程序计算最小费用.
对于所有输入数据, 有 $2 \le N \le 100000, 1 \le M \le 200000, 1 \le C_i \le {10}^9$ .
保证 $1 \le S, T, U, V \le N, S \ne T, U \ne V, S \ne U 或 T \ne V, 1 \le A_i < B_i \le N$ , 图中无重边.

两条路径的交是一个区间, 否则直接把两次相交之间的部分也在买月票的那条路径上跑一定更好.

这时候想到最短路DAG倒是不困难的, 发现只要统计出 $s\to t$ 最短路DAG上每个点能到的点中离 $v$ 最近的, 这个可以DAG上dp, 那么就结束了. 注意要把 $u$ 和 $v$ 换一换再来一遍.

还是要多锻炼发现性质.

「JOI 2018 Final」T5 毒蛇越狱

给出长 $2^L$ 的序列 $v$ 表示每个 $0\ldots 2^L$ 中每个数的权值, $q$ 个询问, 每次给定一个字符串, 第 $i$ 个字符表示限制二进制第 $i$ 位为0, 1或任意, 求满足条件的数的权值和.

$L\le 20, q\le 10^6$ .

最简单的暴力当然是每次暴力枚举合法的数复杂度 $2^L$ .

另外这个东西让人联想FMT/FWT, 因为不看必须为1就是子集前缀和啊.

那么有了1之后可以加上一个容斥, 先做FMT求子集前缀和, 那么拿若干前缀和容斥出这个, 那么设 $S$ 的前缀和 $v_S$ , 算的就是 $\sum_{S\subseteq T} v_S\times (-1)^{\vert S\vert-\vert T\vert }$ , 这里 $T$ 是强制为 $1$ 的位的集合.

折腾完复杂度好像还是 $2^L$ ?

然而你发现, 设强制位0, 1, 任意的个数为 $a, b, c$ , 实际上第一个是 $2^c$ , 这个是 $2^b$ .

那么把0和1的角色互换用FWT+容斥就能得到 $2^a$ .

注意 $a+b+c=20$ , 所以现在复杂度就成了 $2^6q=64q$ .

「JOI Open 2017」T2 推土机

平面上有  $N$  个点, 点  $i: (1\le i\le N)$  位于  $(X_i, Y_i)$ , 点  $i: (1\le i\le N)$  的权值为非零整数  $W_i$ (可能为负数).
在平面上画两条平行线, 所得的总价值为平行线之间(压线也算)所有点的权值之和. 求总价值至多不超过多少.

$1\le N\le 2000, \vert X_i \vert , \vert Y_i \vert \le 10^9, 1 \le \vert W_i \vert \le 10^9(1\le i\le N) . (X_i, Y_i)\ne(X_j, Y_j): (1\le i<j\le N) $

平行线定角度的话相当于最大子段和啊.

那么枚举角度, 就是分块旋转扫描线不分块, 就是考虑两个点在线上的投影在转一圈的过程中只会变 $O(1)$ 次, 所以转一圈暴力去交换的复杂度是 $n^2$ 的.

那么就用线段树维护投影形成的序列的最大字段和, 会 $n^2$ 次交换相邻两个(单点修改), 复杂度 $n^2\log n$ .

「JOI Open 2017」T3 高尔夫

平面的第一象限上有  $N$  个矩形障碍, 矩形的两组对边分别平行于 x 轴和 y 轴. 矩形  $i(1\le i\le N)$  的左下角是  $(A_i, C_i)$ , 右上角是  $(B_i, D_i)$ . 任意两个矩形(包括边界)不相交.
JOI 君需要将一个高尔夫球从  $(S, T)$  打到  $(U, V)$ , 保证这两点不同, 保证这两点不在障碍内或障碍的边界上.
JOI 君只能朝平行于 x 轴或平行与 y 轴的方向击球(JOI 君可以跟着移动). 球可以经过边界, 但不能进入障碍物内部. 球撞进障碍物后会停下(JOI 君仍然可以朝远离障碍物的方向击球).
求最少要击球多少次, 才能将高尔夫球打进  $(U, V)$ .
$1\le S, T, U, V\le 10^9, 1\le N\le 10^5, 1\le A_i<B_i\le 10^9, 1\le C_i<D_i\le 10^9, (S, T)\ne (U, V)$

用你丰富的语文功底体会出, 球可以半路停下来而不是必须撞到障碍. (qyc)

路径一定要么是矩形边线的延长线, 要么能直接连到起点终点上.

于是把所有矩形边线作为点拿出来建图, 发现一条横线可能会连向一个区间的竖线(为什么不是全局? 因为有障碍. )于是用线段树优化建图跑最短路.

「JOI 2015 Final」T1 铁路旅行

过于简单.

「JOI 2015 Final」T2 分蛋糕 2

JOI 君和 IOI 酱是双胞胎兄妹. JOI 君最近闲暇时常常会做甜点. 今天 JOI 君也烤了蛋糕吃, IOI 酱立马嗅到了蛋糕的香气于是跑来想分着吃.
蛋糕是圆形的, 从蛋糕中某点开始将蛋糕放射状切为  $N$  块, 按逆时针顺序编号为 1 到  $N$  . 切了之后的第 i 块蛋糕的大小为  $A_i$  . 由于切蛋糕的人刀功很不好, 所以  $A_i$  互不相同.

JOI 君和 IOI 酱按照以下的方法分这  $N$  块蛋糕:

1. 首先 JOI 君从这  $N$  块蛋糕中任选一块取走;
2. 然后, 从 IOI 酱开始, IOI 酱和 JOI 君交替地从剩下的蛋糕中选出一块取走. 不过, 当且仅当一块蛋糕两旁的蛋糕至少有一块已经被选择, 这块蛋糕才能被选择. 如果可供选择的蛋糕有多个, IOI 酱会选择最大的一个, 而 JOI 君可以任选一个.

JOI 君想让自己所得到的蛋糕大小的合计值最大.

$N\le 2000$

选走的蛋糕是环上的一个区间.

于是考虑序列上区间dp, $f_{i, j, 0/1}$ 表示该谁选了并且已经选完区间 $[i, j]$ 的代价, 转移显然.

然后套路复制两倍就结束了.

「JOI 2015 Final」T3 JOI 公园

时值 20XX 年, 为了给办奥赛做准备, IOI 国将要修缮 JOI 公园. JOI 公园里有  $N$  个广场, 这些广场从  $1$  到  $N$  编号. 有  $M$  条道路连接各个广场, 这些道路从  $1$  到  $M$  编号. 第  $i(1 \leq i \leq M)$  条道路是一条连接第  $A_i$  和第  $B_i$  个广场的双向边, 长度为  $D_i$  . 任意两个广场间一定有道路(直接或间接)相连.

修缮计划如下: 首先, 选择一个自然数  $X$  , 将和第一个广场距离等于  $X$  或在  $X$  以下的所有广场(含第一个广场)相互之间连结一条地下通道. 广场  $i$  和广场  $j$  的距离指, 从广场  $i$  到广场  $j$  经过的道路长度总和的最小值. 定义  $C$  为一个与修筑地下通道花费有关的量(  $C$  是整数). 修筑所有地下通道的花费为  $C\times X$  .

接下来, 撤去已经通过地下通道连接的广场之间的道路. 撤去道路的花费不计.

最后, 将没有被撤去的道路进行修补, 长为  $d$  的道路修补的花费为  $d$  .

修缮计划实施之前, JOI 公园没有地下通道. 请求出 JOI 公园修缮花费总和的最小值.
$N\le 10^5, M\le 2\times 10^5, D_i\le 10^5$

dij之后我们知道了对于一个 $x$ 会删去总长位多少的边, 那么枚举一下就好了. 枚举要离散化.

「JOI 2015 Final」T4 舞会

IOI 王国为了庆祝 JOI 公主的生日, 举行了舞会. 预定有  $N$  位贵族要参加舞会.  $N$  是奇数. 将贵族们从  $1$  到  $N$  编号. 每个贵族有一个由整数表示的舞蹈熟练度 . 贵族  $i(1 \leq i \leq N)$  舞蹈熟练度为  $D_i$ . 舞会中, 含 JOI 公主在内的  $N+1$  人两两一组跳舞. $IOI$ 王国遵循老手帮新手的传统, 按以下方法决定跳舞的分组.

• 开始时,  $N$  个贵族排成一列.
• 直到队列中只剩下一个贵族为止, 不断进行以下操作.
• 调查最前面  $3$  个贵族的舞蹈熟练度.
• 这  $3$  个人中舞蹈熟练度最大的贵族称为  $A$  . 如果存在多个人, 从中选出序号最小的称为  $A$  .
• 这  $3$  个人中舞蹈熟练度最小的贵族称为  $B$  . 如果存在多个人, 从中选出序号最大的称为  $B$  .
• $A$  和  $B$  离开队列并组成一组.
• 这三人中没有被选择的一个人移动到队列最后.
• 最后剩下的一个人和 $JOI$ 公主一组.

从第  $1$  个贵族到第  $M(1 \leq M \leq N-2)$  个贵族的  $M$  个贵族已经决定了自己开始时排在队列的第几个. 剩下的  $N-M$  个贵族的排列方式可以由国王自由决定.

因为 JOI 公主才刚开始学跳舞, 国王想知道和 JOI 公主组队的贵族的舞蹈熟练度的最大值.

任务

给出每个贵族的舞蹈熟练度, 和  $M$  个贵族开始时在队列中的位置. 请编写程序求出和 JOI 公主一组的贵族的舞蹈熟练度的最大值.

哦, 原题, 这个就是二分答案, 求出让每个位置熟练度满足二分店答案至少需要几个人, 这个过程用队列模拟.

「JOI 2015 Final」T5 城墙

历史学家 JOI 教授对曾经存在过的 IOI 王国进行了研究.

根据过去的调查, IOI 王国的形状为由  $H$  行, $W$  列的格子组成的长方形. IOI 王国的首都为了防卫外敌入侵而修筑了一座城墙.

围住 IOI 王国首都的城墙形状如以下叙述: 城墙形状由城墙的大小决定. 大小为  $s(s\ge 3)$  的城墙, 指  $s\times s$  的正方形的最外一圈, 也就是除去此正方形中心  $(s-2)\times (s-2)$  的小正方形剩下的区域.

据调查, 围住首都的城墙的大小在  $L$  或以上. 而且已知 IOI 王国中的一些格子不存在城墙.

JOI 教授为了进一步研究, 想要知道城墙有多少种可能的情况.

任务

给出 IOI 王国的大小, 城墙的大小的最小值, 和一些已知不存在城墙的格子, 请编写程序求出城墙可能的情况数.

$N, W\le 4000$

有三个不确定量: 左上角坐标和边长.

时间内可以枚举两个.

那么如果枚举边长 $s$ 和左上角横坐标 $x$ , 我们需要求在 $x$ 和 $x+s$ 间有多少条没有障碍的路, 并且还要处理纵向有障碍的情况.

如果枚举 $x$ 和 $y$ , 那么要求这个点开始的对角线上有多少点 $P(x+a, y+a)$ 能向左, 向上延伸超过 $a$ .

于是, 求出所有点向左向上延伸的最小值, 记为 $len$ , 然后枚举每一条对角线, 维护所有 $len-i$ , $i$ 表示是对角线上的第几个, 那么就是求若干个区间大于一个数的个数, 离线扫描线BIT即可.

「JOI Open 2016」T1 JOIRIS

JOIRIS 的游戏区域名叫「井」, 是一个宽度为  $N$ , 高度足够大的矩形网格. 位于左数第  $i$  列, 从下往上数第  $j$  列的格子记作  $(i, j)$ . 游戏过程中, 每个格子要不有一个方块, 要不没有方块.
开始时, 在第  $i$  列有且仅有  $(i, 1), (i, 2), \dots, (i, A_i)$  有方块.
接下来, $10^4$  个  $1×K$  的骨牌一个个下落, 玩家要依次放置骨牌. 每次放置骨牌按照如下方式进行:

• 玩家先选择骨牌是横向放置还是纵向放置.
• 若选择纵向, 玩家还需再选择一个整数  $x (1 \le x \le N)$ . 一个骨牌会下落到第 x 列最上方方块的上面一行. 若第  $x$  列没有方块, 骨牌会下落到井底.
• 若选择横向, 玩家还需再选择一个整数  $x (1 \le x \le N-K+1)$ . 一个骨牌会下落到第  $x$  列至第  $x+K-1$  列最上方方块的上面一行. 若第  $x$  列至第  $x+K-1$  列没有方块, 骨牌会下落到井底.
• 每个骨牌停止下落后, 系统将从井底往上逐行检查, 如果有一行格子被方块填满, 该行的所有方块都会消失, 且上方的所有方块向下移动  $1$  格.
• 此时检查井中是否有方块, 如果井中没有方块, 游戏结束, 玩家胜利, 否则玩家开始放置下一个骨牌.

保证开始时最底下一行没有被方块填满. 请判断玩家能否胜利, 如果可能, 则输出一种方案.

对于所有数据, $2\le N\le 50, 1\le K\le N, 0\le A_i \le 50.$

设 $b_i=\sum_j a_{jK}$

那么纵向放置不会改变什么, 而横向放置会让所有 $b_i\to b_i+1$

最后的时候前 $n\bmod k$ 个 $b_i$ 相等, 后 $k-n\bmod k$ 个相等. 所以一开始满足这个性质是必要条件.

同时也是充分的, 通过构造证明:

1. 首先竖着做是不会影响答案的, 所以可以先通过竖着加把他变成单增的.

2. 然后胡乱不断放横的使得后 $n-k+1$ 列(留下前 $k-1$ 列)都堆到 $a_n$ 的高度, 前 $k-1$ 列不管成什么样(可能有一些悬空).

3. 然后在左边不断放竖的就可以把右边 $n-k$ 都消掉. 此时左边也不会有悬空的了.

4. 考虑此时 $b_{n\bmod k+1\ldots k}$ 是相等的, 因为 $b_k=a_k=0$ , 所以 $a_{n\bmod k+1\ldots k-1}=b_{n\bmod k+1\ldots k-1}=b_k=0$ . 只有前 $n\bmod k$ 列有值了.

5. 而另外 $b_{1\ldots n\bmod k}=a_{1\ldots n\bmod k}$ , 因为一开始他们是相等的, 且我们做的操作不会改变 $\mod k$ 意义下的值, 所以现在他们 $\bmod k$ 相等, 可以通过放竖条让他们一样高, 最后在右边不断放横条就可以胜利了.

于是也是充分的了.

「JOI Open 2016」T2 销售基因链

基因库中有  $N$  个字符串, 这些字符串仅由 A, G, U, C组成(保证每个字符串都包含四种字母).
$M$  组查询, 每组查询包含两个字符串  $P$ , $Q$ , 试求: 基因库中有多少个字符串同时存在前缀  $P$  和后缀  $Q$ .
举个例子, GAC 存在前缀 G, GA, GAC, 存在后缀 C, AC, GAC, 那么我们可以说: GAC 同时存在前缀 GA 和后缀 AC.

$N\le 10^5, \sum \vert P \vert , \sum \vert Q \vert$

按字典序排序后相同前缀的是一个区间, 同理反过来相同后缀的也是一个区间, 那么前后分别排序后每个字符串对应到一个点 $(a, b)$ , $a, b$ 分别为正着和倒着的顺序, 而询问就是矩形点个数. 复杂度 $n\log n$ .

但还有更牛逼的, 如果建可持久化字典树, 就是询问出现在一个时间段内且在某一子树的字符串个数了, 直接每个子树维护子树内结束标记个数减一减就做完了. 排序用字典树+dfs序, 就可以优化成线性了啊.

「JOI Open 2016」T3 摩天大楼

将互不相同的 $N$ 个整数 $A_1, A_2, \dots, A_N$ 按照一定顺序排列.
假设排列为 $f_1, f_2, \dots, f_N$, 要求: $\vert f_1 − f_2 \vert + \vert f_2 − f_3 \vert + \dots + \vert f_{N−1} − f_N \vert \le L$.
求满足题意的排列的方案数 $\bmod (10^9+7).$
$1\le N\le 100, 1\le L\le 1000, 1\le A_i\le 1000$ .

序列上 $dp$ 是不可能的, 你不知道你还有哪些数没插入. 而且数的位置其实不是关键.

那么在值域顺序dp, 这种dp模型大概是考虑从小到大不断插入数, 行成若干个连续段(一个区间都已经被插入). 这样做的好处是一方面不用记已经插入了哪些数, 一方面一个数的贡献其实只和它前后是否比他大有关, 而不和到底是几有关.

于是设 $f_{i, j, k, 0/1/2}$ 表示已经插入了前 $i$ 小的数, 形成了 $j$ 个连续段, 当前贡献是 $k$ , 序列两端点被插入了几个, 转移是枚举是否新创建段, 就是插入一个数 $a$ 时如果两边都已经被插入贡献 $2a$ (比左右俩数都大), 如果一个被插入了贡献 $0$ , 否则贡献 $-2a$ , 复杂度是 $n^3V$ ( $V=\max A_i$ ).
考虑优化状态, 现在只有 $k$ 这一维看起来不太卡满, 如果我们让 $k$ 单调递增那么这一维实际大小是 $L$ , 但因为可能上去很大再下来所以出问题, 所以这里把一个数的贡献一点一点计算: 对于所有连续段端点我们不再减去 $a$ (一边领居没插入)或 $2a$ (两边都没数), 而是假装每一个连续段左右两边都有数 $i$ , 相当于把这一个数的贡献按值域维分成若干段一段一段的雷佳进答案, 这样就让 $k$ 变成单调的了, 复杂度 $n^2L$

「JOI 2014 Final」T1 JOI 徽章

实际是个模拟暴力

「JOI 2014 Final」T2 IOI 馒头

有 $M$ 种互不相同的馒头各一个, 第 $i$ 个馒头卖 $P_i$ 元.
有 $N$ 个包装盒, 第 $j$ 个包装盒最多能装 $C_j$ 个馒头, 买第 $j$ 个包装盒的花费为 $E_j$ 元. 要求只能将一些馒头放进包装盒中打包出售, 不能零售, 当然也可以不出售某些馒头(卖剩的馒头被出题人吃了, 出题人还吃得津津有味~). 售出一盒馒头得到的利润为盒内所有馒头的价格减去包装盒的价格.

现在买下(这 $N$ 个包装盒)其中的一些包装盒(也可以不买, 还可以全买), 将馒头打包出售, 求最大可能利润.

对于全部数据, $1\le M\le 10^4, 1\le N\le 500, 1\le P_i, C_j, E_j\le 10^4$ .

馒头其实可以先不管, 因为若当前能装 $k$ 个我们买的一定是前 $k$ 大.

所以就设 $f_{i, j}$ 表示考虑前 $i$ 种包装盒, 现在手里有 $j$ 元能买几个馒头. 是个背包.

很遗憾 $j$ 这一维爆炸了. 但值域这一维很小.

于是经典的互换他们, 设 $f_{i, j}$ 表示前 $i$ 种包装盒买 $j$ 个馒头的最小代价.

「JOI 2014 Final」T3 年轮蛋糕

JOI 君马上要和妹妹 JOI 子和 JOI 美一起吃小吃. 今天的小吃是他们三个人都很喜欢的年轮蛋糕.

年轮蛋糕是像下图一样呈圆筒形的蛋糕. 为了把蛋糕分给三个人, JOI 君必须沿着半径方向切 $3$ 刀, 从而把蛋糕分成三块. 然而, 由于年轮蛋糕硬得像实木一样, 要让刀切进去并不简单. 因此, 这个年轮蛋糕上事先准备了 $N$ 个切口, 而 JOI 君只能在有切口的位置下刀. 切口按顺时针顺序编号为 $1$ 到 $N$, 对于 $1\le i\le N-1$, 第 $i$ 个切口和第 $i+1$ 个切口之间部分的大小是 $A_{i}$. 第 $N$ 个切口和第 $1$ 个切口之间部分的大小是 $A_{N}$.

妹控的 JOI 君在把蛋糕切成 $3$ 块之后, 自己选走最小的一块吃掉, 把剩下两块分给两个妹妹. 而另一方面, JOI 君太喜欢年轮蛋糕了, 只要能吃到的时候就会想吃很多很多. 试求: JOI 君吃掉的蛋糕的大小至多不超过多少.

给出切口个数 $N$ 和表示各部分大小的整数 $A_{1}, \cdots , A_{N}$, 请求出把年轮蛋糕切成 $3$ 块之后最小一块大小的最大值.
$N\le 10^5, A_i\le 10^9$

最小值最大, Umnik.

然后枚举一个切口, 找到剩下两个切口, 显然是随着这个切口移动单调的, 三指针.

「JOI 2014 Final」T4 飞天鼠

飞天鼠 $JOI$ 君住着的森林里长着编号为 $1$ 到 $N$ 的 $N$ 棵桉树. 第 $i$ 棵树的高度是 $H_{i}$ 米.

JOI 君能在其中的 $M$ 对桉树之间直接飞行, 在各对树木之间飞行所需的时间是固定的. 当 $JOI$ 君在树木之间飞行的时候, 他离地面的高度会每秒下降 $1$ 米. 也就是说, 如果 $JOI$ 君现在离地高度是 $h$ 米, 在树木之间飞行需要 $t$ 秒, 那么飞行之后的离地高度就会变成 $h-t$ 米. 当 $h-t$ 小于 $0$ 或大于目标树木的高度时则不能飞行.

JOI 君还能沿着树的侧面上下移动, 使得他的离地高度在 $0$ 到当前所在树木高度的范围内变化. JOI 君每使自己的离地高度增加或减少 $1$ 米都需要 $1$ 秒的时间.

JOI 君要从 $1$ 号树木上高度为 $X$ 米的位置出发, 到树木 $N$ 的顶端(高度为 $H_{N}$ 米的位置)去. 他想知道为了达成这个目标所需时间的最小值.

给出各棵树木的高度、JOI 君能直接飞行的树木对和 $JOI$ 君最初所在位置的高度, 请求出到达树木 $N$ 顶端所需时间的最小值.
全部的输入数据满足:

$2\le N\le 100000$
$1\le M\le 300000$
$1\le H_{i}\le 10^{9}(1\le i\le N)$
$1\le T_{j}\le 10^{9}(1\le j\le M)$

看起来是最短路没错, 但状态数是 $NH$ 的.

考虑我们大概非必要不上升.

如果我们一直往下走, 走到一个地方爬上来一定会经过0.

那么再求出每个位置从0高度到终点的距离就好了. 实际上相当于把路程分成从起点一直往下走, 然后从地底爬上来, 然后再走到终点.

「JOI 2014 Final」T5 裁剪线

给定平面上 $n$ 条线段, 求它把平面分成多少块.
$n\le 10^5$, 坐标值域 $10^9$.

众所周知欧拉公式 $V-E+F=C$, $C$ 为连通块个数.

于是统计交点个数, 线的个数和连通块数.

那么统计交点个数连通块个数和线的个数都是简单的, 就是对每一条线段求有多少和他垂直的线和他相交, 二维数点就好了.

能不能直接维护块数?

从左往右扫描线, 遍历到竖着的就在并查集里合并一个区间里横着的这些线, 遍历到横着的起点/终点就删掉这个区间里的点. 这个好像可以打标记.

「JOI 2013 Final」T1 彩灯

每年 JOI 高中的文化祭上, 走廊上都会有彩灯装饰. 共有 N 个彩灯, 从走廊的西侧到东侧排成一列. 每个彩灯要么亮要么不亮.

JOI 高中的仓库里沉睡着一台能够对彩灯进行操作的机器. 对于指定的连续的一段彩灯, 此机器能将这些彩灯中所有亮的变成不亮的, 所有不亮的变成亮的. 但是由于这个机器已经老化了, 所以最多只能使用一次.

JOI 高中的学生们很喜欢彩灯的交替列(亮的彩灯和不亮的彩灯交替排列的一段连续的彩灯). 他们希望能够在必要时使用一次这个机器, 使得所有彩灯中所含的最长的交替列最长.
$N\le 10^5$

套路的, 交替这种的特点是奇偶性全相同, 所以枚举所有亮的灯是奇数还是偶数, 然后就简单.

「JOI 2013 Final」T2 搭乘 IOI 火车

给定两个序列, 可以在其中各选一个区间, 然后按自己指定的顺序归并起来, 拼成一个形如101010的串(第一个是1, 后面交替), 最大化拼出的长度.
串长2000

dp它, $f_{i, j, 0/1}$ 表示第一个序列的第 $i$ 个为结尾, 第二个序列的第 $j$ 个为结尾, 所形成的串的最后一个是 $0/1$ 的最长长度即可.

「JOI 2013 Final」 T3 现代豪宅

你在某个很大的豪宅里迷路了. 这个豪宅由东西方向 $M$ 列, 南北方向 $N$ 行的正方形房间组成. 从西面开始第 $x$ 列 $(1 \leq x \leq M)$, 从南面开始第 $y$ 行 $(1 \leq y \leq N)$ 的房间用 $(x, y)$ 表示.

相邻的两个房间之间都有一扇门. 对于每扇门, 门关上表示不可通行, 门打开表示可以通行. 当门打开时, 从门一边的房间走到另一边的房间需要 $1$ 分钟. 另外, 一些房间中有一个开关, 如果连续 $1$ 分钟按住这个开关, 那么所有关上的门会打开, 所有打开的门会关闭.

现在, 连接东西两个房间的门全都是关上的, 连接南北两个房间的门全都是打开的. 你现在在房间 $(1, 1)$, 要在最短时间内移动到房间 $(M, N)$.

任务
给出豪宅的大小 $M, N$, 以及存在开关的 $K$ 个房间的位置 $(X_1, Y_1), (X_2, Y_2), \ldots, (X_K, Y_K)$. 开始时, 连接东西两个房间的门全都是关上的, 连接南北的两个房间全都是打开的. 请编写程序求出从房间 $(1, 1)$ 移动到房间 $(M, N)$ 最少需要多少时间. 不过, 当房间 $(M, N)$ 不能到达时, 请输出 $-1$.
$N, M\le 10^5, K\le 2\times 10^5$

首先平方做法是好想的, 建两层图分别表示横着有边和竖着有边的情况, 连上边, 然后所有有按钮的点把这两层连起来.

正解就是忽略掉额外的点而只保留这些会在两张图里切换的特殊点和起点终点, 复杂度 $K\log K$

「JOI 2013 Final」T4 JOIOI 塔

给定 $\texttt{J}, \texttt{O}, \texttt{I}$ 三个字母组成的字符串 $S$, 从中拿出若干的不交的 $\texttt{JOI}$ 和, $\texttt{IOI}$ 子序列, 最大化拿的数量总和.
不交是指不能选同一个字符两遍, 但 $IIOOII$ 这种是可以取出来两个的, 就是说可以跨越.
$\vert S\vert \le 10^6$

tyy讲过这个题, 十分霸气的表示不二分的做法都是假的. . . 然后qyc翻出loj线性老哥.

难点在于如何处理 $\texttt{I}$, 因为不知道是 $\texttt{IOI}$ 的第一个还是第二个.

二分数量, 判定时从前往后扫, 并且维护若干个没匹配的串, 扫到 $\texttt{J}$ 就新开一个没匹配的串, 扫到 $\texttt{O}$ 如果能匹配现在没匹配的串就直接匹配, 不然就扔掉, 对于 $\texttt{I}$ 如果当前没匹配的串和已经匹配的总和够答案了就当成末尾的 $\texttt{I}$, 否则当头部的.

线性做法是, 一定可以是一个前缀的 $\texttt{I}$ 贡献到头部, 一个后缀的贡献到尾部, 预处理前后缀然后枚举分段点即可.

「JOI 2013 Final」T5 冒泡排序

给出长为 $N$ 的数列 $A$, 对数列 $A$ 中任意两个整数进行一次交换得到数列 $A’$. 请编写程序求出对数列 $A’$ 使用冒泡排序使其升序排列的交换次数的最小值. (请注意: 开始时对数列 $A$ 中整数的交换并不需要交换相邻两个数. )
$N\le 10^5, A_i\le 10^9$

先考虑 $A_i$ 互不相同的.

冒泡排序复杂度等于逆序对个数众所周知.

交换两个 $i, j$ 位置的数的贡献是满足 $x\in (i, j), A_x\in (A_j, A_i)$ 的 $x$ 个数二倍也众所周知.

那么这个是二维数点, 用二维前缀和可以得到平方算法.

考虑如何优化, 发现这是个四维问题, 你要选一个4-side矩形.

考虑性质, 若 $a<b$ 且 $A_a>A_b$, 显然若交换 $b, c$ 肯定不如交换 $a, c$.

所以交换 $i<j, A_i>A_j$ 的时候 $i$ 是所有前缀最大值的下标, $j$ 是所有后缀最小值的下标.

于是 $A_i$ 随 $i$ 单增, 所以原来的 $A_x<A_i$ 是一个前缀, 同理对 $j$ 是一个后缀.

也就是说 $x>i$ 和 $A_x<A_i$ 合体成了下标上的一个区间, 就是先加后问的矩形加矩形max, 复杂度1log.

其实 $j$ 关于 $i$ 是有决策单调性的, 可以分治维护决策单调性做到2log, 虽然不知道为何单调? qyc说决策单调性是应该枚举的性质, 很有道理

同时是loj round #6 C. 花火

「JOI 2019 Final」T1 勇者比太郎

勇者比太郎正在面对恶魔.

为了攻击恶魔, 比太郎会在一个 $H \times W$ 的网格上放置三种道具(分别记作 J, O, I)并施放咒语. 网格上往下数第 $i$ 行($1 \le i \le H$), 左往右数第 $j$ 列($1\le j \le W$)的格子坐标记为 $(i, j)$.

现在, 比太郎在网格的每个格子中放置了三种道具中的一种, 比太郎将施放一个咒语, 其威力取决于三种道具的排列方式. 具体的, 威力大小等于满足以下条件的有序四元组 $(i, j, k, l)$, $(1 \le i < k \le H, 1 \le j < l \le W)$ 的数量.

条件: $(i, j)$ 位置的格子上的道具为 J, $(i, l)$ 位置上的道具为 O, $(k, j)$ 位置上的道具为 I.

比太郎想知道他的咒语的威力是多少.

请写一个程序, 根据三种道具在网格上的排列, 计算出咒语的威力(即满足上述条件的四元组数量).
$H, W\le 3000$

大概想象一下这个矩形的样子, 预处理每个 $J$ 上面有多少 $O$, 右边有多少 $I$ 扫一遍乘起来即可.

「JOI 2019 Final」T2 画展

你将举办一个画展. 在展览中, 你需要将一些画放入一些画框中并摆放成一排.

展览有 $N$ 幅候选画, 编号从 $1$ 到 $N$. 画 $i ( 1 \le i \le N)$ 具有大小 $S_i$ 和美观度 $V_i$.

另外, 有 $M$ 个候选画框, 编号从 $1$ 到 $M$. 画框 $j ( 1 \le j \le M)$ 的大小为 $C_j$.

只有大小不超过 $C_j$ 的画才能放入画框 $j$ 中. 每个画框中最多只能放一幅画. 每幅要展出的画都必须放在一个画框中.

考虑到美观因素, 展出的画必须满足以下条件:

对于任意两幅相邻的画, 右边的画框大小不小于左边的画框
对于任意两幅相邻的画, 右边的画的美观度不小于左边的画的美观度
你需要求出你最多能展出多少幅画.
有 $1 \le N, M \le 10^5, 1 \le S_i, V_i, C_j \le 10^9 (1 \le i \le N, 1 \le j \le M)$.

LIS. . . , 和qyc倒在相同的坑里.无序的

那么分别从小到大排序, 要求选出若干两边都严格递增的对. 每个画匹配一个后缀的画框.

一脸贪心的样子, 从小到大的框每个装上能装的美观度最小的.

「JOI 2019 Final」T3 有趣的家庭菜园 3

家庭菜园专家 JOI 先生在他的家庭菜园中种植了一种叫 Joy 草的植物. 在他的菜园里, 有 $N$ 个花盆自东向西摆放, 编号分别为 $1, \ldots, N$. 每个花盆中有一株 Joy 草.

春天到了, JOI 先生注意到 Joy 草如他期望地长出了各种颜色的叶子, 但他也发现 Joy 草的生长速度没有他期望的那么快. 他查阅了书籍, 找到了草的以下特点:

Joy 草有三种品种, 分别会长出红色、绿色和黄色的叶子.

如果两株同一颜色的 Joy 草紧密相邻, 它们的生长速度就会减慢.

因此, JOI 先生决定重新摆放花盆, 使得没有两株相邻的 Joy 草颜色相同.

花盆非常沉重, 因此 JOI 先生每次只能交换相邻的两个花盆. 形式化的说, JOI 先生每次操作可以选择一个 $i (1 \le i < N)$, 然后交换花盆 $i$ 和花盆 $i+1$.

请编写一个程序, 计算最少的交换次数.
$N\le 400$

就是说找一个排列 $a$ 使得任意 $a_i, a_{i+1}$ 颜色不同, 并且最小化逆序对个数.

直接dp最终排列, $f_{i, j, k, 0/1/2}$ 表示前 $i$ 个, 有 $j$ 个R, $k$ 个Y, 最后一个是R/G/Y的最小逆序对个数. 不对.

那么扫值域吗? 也不对, 看题解.

啥? 设对了? 哦, 是可以转移的, 我们能根据这个知道当前填的这个应该是原序列中第几个R/G/Y, 然后提前计算一下费用(插入这个的时候计算上后面的和这个组成的). 结束了.

「JOI 2019 Final」T4 硬币收藏

平面上有 $2n$ 点, 求最小的代价把它们都移动进 $(1, n)\times (1, 2)$ 的矩形里, 移动的代价为两点的曼哈顿距离, 最后移动完之后要求位置互不相同.
$n\le 10^5$

怎么做?

每个点可以先移动到离矩形最近的点, 一定不劣

然后在这个矩形内贪心, 从左往右扫, 维护两行各有多少多出来的空位即可. 需要费用提前计算一下吧.

好像是某个老鼠进洞啊.

「JOI 2019 Final」T5 独特的城市

给一棵 $n$ 个点的树, 每个点有颜色 $c_i$, 对于每个点求一遍以这个点为根时, 对于所有深度, 若这个深度上只有一个点那么把这个点称为特殊点, 对每个点求所有特殊点的颜色数.
$n\le 2\times 10^5$

与 $u$ 形成特殊点的点一定在 $u$ 出发的最长链上.

那么, 找到任意一条直径, 那么所有点的最长链都可以是到直径的两端点之一.

于是从两端点开始dfs, 考虑对于当前点 $x$ 有哪些长链上的点不特殊, 发现 $x$ 到根路径上每个点规定了这条链上一个区间不能成为特殊点, 用栈维护到根路径上到所有的特殊点.

但问题在于进入一个分支的时候可能删掉了一些特殊点, 而这些点在另一个分支是不被删除的.

容易发现 $u$ 进入 $v$ 时, 被删掉的点是从 $u$ 开始向祖先走, 长度为除了 $v$ 子树外其他子树的最长链的这个区间.

那么若当前递归进入的不是最长的儿子, 贡献是相同的.

所以先递归进长儿子统计, 再进其他儿子统计. 这样就不需要复原进入一个儿子后向祖先删除的部分了.

注意由于每次删掉的是子树内最长链, 所以子树内不会删的比外面删的更多. 但 $u$ 自己不应在 $u$ 处被删且可能被子树干掉, 所以每次递归儿子要判断如果当前栈顶不是 $u$ 把 $u$ 塞进去.

复杂度是每个点被塞进去度数+1次, 所以线性.

网上资料都说是长链剖分, 但感觉并没怎么用长链的性质. 本质还是换根dp.

「JOI Open 2019」T1 三级跳

有一条很长的路, 被划分为 $N$ 段并从 $1$ 到 $N$ 编号. 每一段都一个坚固程度, 第 $i$ 段路的坚固程度为 $A_i$.

JOI 君是一位有天赋的体育明星. 他将在这条路上进行三级跳. 一次三级跳包含三次连续的跳跃动作. 设 $a, b, c$ 为 JOI 君进行三级跳时三个起跳点的所在段, 那么需要满足以下条件:

$a<b<c$. 即: 起跳点所在段需要严格递增;
$b-a\le c-b$. 即: 第一次的跳跃距离应该不大于第二次的跳跃距离.
JOI 君将进行 $Q$ 次三级跳. 第 $j$ 次三级跳的所有起跳点所在段编号都在 $L_j$ 到 $R_j$ 范围内. 换句话说, 必须保证 $L_j\le a<b<c\le R_j$.

JOI 君想在更坚固的段上起跳. 对于每次三级跳, JOI 君想知道起跳点的最大坚固程度之和.

写一个程序, 在给定路的段数和每次三级跳的信息的情况下, 计算对于每次三级跳, 起跳点的最大坚固程度之和.
对于所有数据, $3\le N\le 5\times 10^5, 1\le Q\le 5\times 10^5, 1\le A_i\le 10^9, 1\le L_j\lt L_j+2\le R_j\le N$.

构造支配对, 但是固定 $i, k$ 根本想不到支配性质.

需要固定 $i, j$, 对于任意 $(i, j, k)$ 作为答案, $i, j$ 换成区间 $[i, j]$ 的最大值和次大值一定不劣, 因为前半段是可以任意短的.

考虑每个次大直, 一个次大值只会对应2个最大值(左右各一个), 于是一共只有 $O(n)$ 个!

就开扫描线吧, 当经过对 $(a, b)$ 的 $2b-a$(最小的 $c$)时把它插入进去, 每次就是全局取max和区间最小值了.

「JOI Open 2019」T2 汇款

JOI 王国的河狸湖边有 $N$ 座房子, 按逆时针方向给房子从 $1$ 到 $N$ 编号.

站在湖所在的位置看, 每一座房子可以给它左边相邻的房子汇款, 即: 对于房子 $i\ (1\le i\le N-1)$, 它左边的房子是房子 $i+1$, 对于房子 $N$, 它左边的房子为房子 $1$. 然而, 汇一笔款的手续费等于汇款金额. 汇款金额必须是一个整数. 当你汇款的时候, 你必须交手续费, 所以汇款钱数和手续费之和不能超出房子里的钱数.

目前, 房子 $i\ (1\le i\le N)$ 里有 $A_i$ 元. 另一方面, 从收税的角度来看, 我们希望房子 $i$ 里的钱数等于 $B_i$. 因此你希望利用汇款系统使得房间 $i$ 里钱数等于 $B_i$ 元. 你不能通过除给别的房子汇款和交手续费之外的方式花掉钱.

给定每座房子目前有的钱数和期望钱数, 写一个程序判断能否使得每间房子都达到期望的钱数.
对于全部数据, $1\le N\le 10^6, 0\le A_i, B_i\le 10^9$.

震惊, 万万没想到是模拟题! 不敢相信啊.

每个房子最多汇款 $\log A_i$ 次, 于是考虑进行 $\log A_i$ 轮, 即直接看 $A_i$ 是大于还是小于目标状态然后去汇1, 弄完不对就不可能了.

「JOI Open 2019」T3 病毒实验

你知道「净是一些鬼畜发明公司」(Just Odd Inventions Co. , Ltd. )吗? 这家公司就是发明一些鬼畜玩意的. 现在我们就叫它 JOI 公司.

JOI 公司开发了一种新型病毒——「JOI 病毒」. JOI 公司想要通过用 JOI 病毒感染 IOI 岛上的居民的方式做一次病毒实验.

IOI 岛是一个矩形, 从东向西有 $R-1$ 条互相平行的街道, 从北向南有 $C-1$ 条互相平行的街道. 它们把岛划分为 $RC$ 个区域. 每个区域只住着一个居民, 我们称住在从北数第 $i$ 区域, 从西数第 $j$ 个区域的居民为居民 $(i, j)$.

在 IOI 岛上, 一天共有 $M$ 个时间段. 我们称第 $k$ 个时间段为时段 $k$. 风总是从东西南北四个方向吹来, 风向取决于时段. 如果时段相同, 则风向相同, 与日期无关.

每个居民都有一个抵抗力. 居民 $(i, j)$ 的抵抗力用一个非负整数 $U_{i, j}$ 表示.

如果 $U_{i, j}=0$, 表示居民 $(i, j)$ 的抵抗力很高, 并且这位居民不会感染 JOI 病毒;
如果 $U_{i, j}>0$, 表示居民 $(i, j)$ 可能会感染 JOI 病毒. 如果以下情况持续了 $U_{i, j}$ 个时段, 这位居民就将在下一个时段感染 JOI 病毒:
住在风吹来方向且与这位居民相邻的居民感染了 JOI 病毒.
注意一天最后一个时段和下一天第一个时段是连续的.
为了完成实验, 我们想要至少感染一位居民, 但是我们不想感染太多的居民. 在初始的时候, 我们选择一位居民作为第一个被感染的人, 然后使他感染 JOI 病毒. 我们不能感染抵抗力为 $0$ 的居民.

给定每一个时段的风向, 写一个程序计算在 $10^{100}$ 天之后至少会有多少居民被感染, 和达到这个最小值选择初始感染者的方案数.
对于全部数据, $1\le M\le 10^5, 1\le R, C\le 800, 0\le U_{i, j}\le 10^5$, 保证 $D$ 字符串长度为 $M$ 并且只包含 $N, S, W, E$ 四种字符, 并且保证至少有一个 $U_{i, j}\ge 1\ (1\le i\le R, 1\le j\le C)$.

读错成简单题了/qd 病毒的风可以来自不同方向但时间上连续, 所以毙掉了先建图再直接tarjanSCC的做法.

首先如果A感染后B也感染, 那直接感染B一定不劣.

所以我们选的是最小的出度为0的SCC, 但很遗憾我们不知道图的结构.

但我们仍然可以模拟: 对于一个点可以处理它周围四个点的16种情况下是否会感染, 然后枚举人bfs就可以做到 $n^2c^2$.

但其实我们只想知道关系而不是直接bfs答案, 没必要每次都到底吧?

考虑如果A可以到B, 那么所有到A的都一定不优于B了吧.

于是我们维护若干集合, 每个集合维护一个最优点, 每次从最优点出发遍历, 若遍历到其他集合的元素就合并上去.

写成别如卡就是 $RC\log RC$ 了

最后得到若干无法拓展的集合, 那么每个集合从最优点出发求一下是 $RC$ 的, 这个大小同时是这个集合的感染人数和感染方案.

「JOI 2020 Final」T1 只不过是长的领带

你知道 Just Odd Inventions 公司吗? 这个公司的业务是「只不过是奇妙的发明 / Just Odd Inventions」. 这里简称为 JOI 公司.
JOI 公司的最新发明是「只不过是长的领带」. 共有 $N+1$ 条领带, 并以 $1, \ldots, N+1$ 编号.
第 $i$ 种领带的长度为 $A_i$, 其中 $1 \le i \le N+1$.

公司聚集了他们的员工, 并准备举办一场试戴派对.
参加该聚会的员工共有 $N$ 个, 且第 $j$ 个员工一开始戴着长度为 $B_j$ 的领带, 其中 $1 \le j \le N$.
派对的流程如下:

JOI 公司的 CEO 首先选出一条领带, 它将不会在接下来的派对中使用.
然后, 每个员工从其余领带中选择一条, 且需保证没有两个员工选择了同一条领带.
最终, 每个员工取下一开始戴着的领带, 并试戴他 / 她选择的领带.
若某个员工一开始戴着的领带长度为 $b$ 而最后试戴的领带长度为 $a$, 则他 / 她会产生 $\max{a - b, 0}$ 个单位的奇怪感.
整场派对的奇怪度定义为所有员工中最大的奇怪感.

由此, 我们定义 $C_k$ 为当 CEO 选择第 $k$ 条领带时, 整场派对最后可能的最小奇怪度.

请你对于给定的 $A_1, A_2, \ldots, A_{N+1}$ 和 $B_1, B_2, \ldots, B_N 求出 C_1, C_2, \ldots, C_{N+1}$.
对于所有测试数据 $1 \le N \le 2 \times 10^5, 1 \le A_i \le 10^9, 1 \le B_j \le 10^9\ (1 \le i \le N+1, 1 \le j \le N)$.

发现自己是智障: 简单贪心发现如果匹配连出交叉一定不如换一下不交叉, 于是两个分别排序一一对应就是对的. 因为要删一个你要处理排完序后 $i$ 对应 $i$ 和 $i$ 对应 $i+1$ 的情况然后随便做.

「JOI 2020 Final」T2 JJOOII 2

比太郎收到了一个长度为 $N$ 的字符串 $S$ 作为他的生日礼物, 且这个字符串仅由 $\texttt{J}, \texttt{O}, \texttt{I}$ 组成.

对于所有正整数 $K$, 若一个字符串仅由 $K$ 个连续的 $\texttt J$, $K$ 个连续的 $\texttt O$ 和 $K$ 个连续的 $\texttt I$ 顺次连接而成, 则我们称这个字符串为 $K$ 级JOI-串.
例如, $\texttt{JJOOII}$ 就是一个 2 级 JOI-串.

比太郎热衷于构造 $K$ 级 JOI-串, 于是他打算通过以任意顺序使用以下三个操作任意次来将字符串 $S$ 构造为一个 $K$ 级 JOI-串:

1. 删除 $S$ 的开头字符.
2. 删除 $S$ 的结尾字符.
3. 删除 $S$ 的一个非开头且非结尾的字符.
   由于操作 $3$ 十分耗时, 比太郎想要尽可能少地使用操作 $3$.
   请对于给定的长度为 $N$ 的字符串 $S$ 和一个正整数 $K$, 输出将其构造为 $K$ 级JOI-串所需要的最少的操作 $3$ 的次数.
   若无解, 请输出 $-1$.

$3 \le N \le 2 \times 10^5, 1 \le K \le \frac N3$, S 是一个仅有 $\texttt J, \texttt O, \texttt I$ 组成的字符串.

枚举一下开头位置, 预处理一下每个位置往后多少有 $K$ 个 $\texttt{J}/\texttt{O}/\texttt{I}$, 结束.

「JOI 2020 Final」T3 集邮比赛 3

JOI 君生活的 IOI 国有一个著名的湖泊, 今天一场集邮大会在湖边举行.

绕湖一圈总共有 $N$ 种邮票可以收集, 编号分别为 $1\ldots N$, 收集点绕湖顺时针排列. 湖的周长为 $L$, 第 $i$ 张邮票 $(1\le i\le N)$ 的收集点在距离出发点顺时针走 $X_i$ 米的位置.

参赛者在比赛开始的时候要站在出发点的位置, 当大会开始时, 参赛者可以绕湖顺时针或者逆时针移动, 参赛者能够得到第 $i$ 张邮票 $(1\le i\le N)$ 当且仅当他到达收集点的时间在比赛开始时的 $T_i$ 秒以内(含).

JOI 君也是集邮大会的参与者. 他的移动速度是每秒钟 $1$ 米, 你可以认为只有移动才会消耗时间.

请你计算他最多能收集到多少种邮票.
对于 $100%$ 的数据, 保证 $1\le N\le 200, 2\le L\le 10^9, 1\le X_i < L, X_i < X_{i+1}, 0\le T_i \le 10^9$.

走到的一定是一个区间经典.

$f_{i, j, 0/1, t}$ 表示 $i-j$ 这一区间, 当前在 $i/j$, 时间 $t$ 拿到的最多邮票, $t$ 这一维原地爆炸, 于是直接替换 $t$ 和答案维做完了.

「JOI 2020 Final」T4 奥运公交

给一个 $n$ 点 $m$ 边有向图, 边有 $c$ 和 $d$ 两个属性表示这条边的代价和把这条边方向颠倒的代价, 求翻转至多一条边的情况下 $1\to n$ 最小代价.
$n\le 200, m\le 5\times 10^4$

$n\le 200$, 复杂度居然不是 $n^3$.

考虑枚举翻转的是边 $u\to v$, 那么贡献似乎很好算, 就 $\min(dis(1, n), dis(1, v)+dis(v, u)+dis(u, n))$ 这样.

但问题是我们翻转一条边可能导致原最短路消失. 考虑最短路必经边只有 $n$ 条(最短路树的树边才有可能)所以这些边直接重跑暴力即可.

「JOI 2020 Final」T5 火灾

给一个长 $n$ 序列 $a$ 在0时刻的状态 $a_1\ldots a_n$, 每一时刻 $a_i=\max{a_i, a_{i-1}}$(同时进行的), $q$ 次询问 $t$ 时刻区间和.
$n, q\le 2\times 10^5$

这个题是lxl在一轮省集搬的题的弱化版啊! 把树上的操作去了就行了.

具体的, 考虑所有由值相等的连续段, 每一时刻它左右端点都有可能右移, 取决于左右两个连续段与它的大小关系. 并且由若干时刻连续段会消失. 因为要求和用平衡树维护. 这个技巧是不是很经典啊?

开题解. 为啥大家不需要平衡树也不维护连续段

大致是分析了一个数的移动是平面(时间-下标)上的一个平行四边形, 在平面上做平行四边形加横线求和.