JOI

学习：连续端 dp。 目标：最优化 \(F(S) = \sum_{i=1}^{n-1} w(A_{S_i}, A_{S_{i+1}})\)，或者说，重排序列以最优化相邻两个元素产生的贡献。 考虑拆开贡献，拆成类似 \(L(a_i) + R(a_{i+1})\) 的形式。连续端 dp 通过以下两个操作 ......

洛谷。 题意 应该好理解的。 分析 我们的所有雪球在同一时间之间的距离都是相同的，因此一段雪，要么是它左侧的第一个所取，要么右侧第一个所取，要么不被取，并且，我们每一个雪球所占有的雪是连续的一段。 我们令 \(L_i\) 表示第 \(i\) 步前所能走的最左点，\(R_i\) 表示第 \(i\) 步 ......

题面 Link 说实话这题看懂题面就做出来一半了，所以本题不提供简化题面 分析 题目描述很具有迷惑性，我们发现其实所谓“房门”的一系列操作，其实就是人物只能竖着走或者横着走。相当于我们要从左下角出发，一开始只能竖着走，图中分散着一些“节点”，人物只能在“节点”上才能改变方向，并付出一单位代价。 于是 ......

\(\color{violet}{\text{P7219[JOISC2020]星座3}}\) 笛卡尔树的题还是写得少了。建笛卡尔树，然后考虑从下向上合并答案。由于每行只会保留一颗星星，所以可以用 \(f_{x,y}\) 表示第 \(x\) 行保留了第 \(y\) 列的星星的最有答案。合并上是简单的， ......

[JOI 2016 Final]オレンジの出荷 题面 \(f_i\) 表示 \(1\sim i\) 的都放完的最小代价，数据范围支持 \(O(nm)\) dp。 点击查看代码 #include<bits/stdc++.h> #define ull unsigned long long #define ......

洛谷。 题意 应该显然，注意最多只能翻转一条边，并且可以不翻转。 分析 首先观察数据范围 \(2\le N \le 200\)，\(1\le M \le 5\times 10^4\)，可以发现我们的 \(N\) 和 \(M\) 并不是同级的，因此，在众多的最短路算法中，我们应当选择不加堆优化的 di ......

传送门。 前置知识 区间 dp。 题意 一个周长为 \(L\) 的圆，在初始点的顺时针方向依次排列着 \(N\) 物品，第 \(i\) 个物品在顺时针 \(X_i\) 米处，可以在 \(T_i\) 前收集到这个物品。 此时，从初始点出发，时间为 \(0\)，允许顺时针或逆时针移动，问最多可以收集到多 ......

好久没写题解，水一篇。 题意 题意显然。 分析 看到这道题，我们就应该进行一个小贪心，对于最左边某一字符，直到最右边的这一字符，我们不会在中间删除同样的字符，不然则可以保留这一字符，将两边往内缩。 也就是说，我们确定了最左边的 J 后，那么留下最后一个 J 必然是当前这个 J 的后面的第 \(K-1 ......

Description 一根长度为 \(10^9\) 的直杆从左到右水平放置。你可以忽略这根杆的重量。共有 \(N\) 个砝码挂在这根杆上，每个砝码的质量为一单位。这 \(N\) 个砝码的位置两两不同。第 \(i(1 \leq i \leq N)\) 个砝码的位置为 \(A_i\) 。即，第 \(i ......

loj3469. 「JOI 2021 Final」雪球 发现 \(i\) 的答案只和相邻的两个数有关，且两边是独立的，不妨假设 \(a_i=0\)，\(a_{i+1}=d\)。那么假设第 \(j\) 次操作 \(a_{i+1}\) 到达的最小位置是 \(d-mn_j\)，\(a_i\) 到达最大位置 ......

LOJ #3470. 「JOI 2021 Final」集体照 设最终操作成的序列为 \(b\)，由于其满足 \(b_i \le b_{i+1}+1\)，我们可以得知它相当于把 \(1,2,\cdots, n\) 划分成若干个区间，每个区间翻转所得到的排列。 要求最小化 \(N(b\circ a^{- ......

交配 / Crossing 令 J 为 \(0\)，O 为 \(1\)，I 为 \(2\)，杂交相当于是 \(c\equiv -(a+b)\pmod 3\) 可以发现最后的状态数不会超过 \(27\) 种，直接暴力线段树维护即可。 #include<iostream> #include<cstdio ......

バブルソート 2 / Bubble Sort 2 可以发现，答案即为 \(\max\limits_{i=1}^n \sum\limits_{j=1}^{i-1}[a_j>a_i]\)。 因为是 \(\max\)，所以可能成为答案只有后缀最小值，可以把式子改写成 \(\max\limits_{i=1} ......

怎么这么难！ 写 BCDE。 loj3663.「JOI 2022 Final」自学 tag：二分，贪心。 先不妨假设 \(A_i\geq B_i\)。二分，然后考虑怎么选。 发现方案一定是：如果能上课就先上课把需求填满，然后空出来的时间用来自学上课上不满的课程。 如何证明。只需要证明： 不存在上课能 ......

洛谷P9349 题意 一种区间覆盖操作，可以考虑直接无脑线段树,复杂度为\(O(nlog_n)\)。 但是观察后发现可以开一个桶，记录这个数在序列中出现的最后一次的下标。循环扫一遍原序列，从小到大对于每一个a[i]，使得下标i到m[a[i]]的区间全部覆盖为a[i]。每次覆盖一个小区间后，因为前面的 ......

<template> <div> <div class="bg-white rounded-lg font-light w-96 shadow p-4"> <div class="text-center text-lg mb-4">后台管理系统</div> <form @submit.prevent ......

T2 怎么 std 9k。 ### *loj3985. 「JOI Open 2023」古代机器 2 tag：交互，字符串，线性代数。 感觉很厉害。 **解法一：**$m=n+2$。 考虑按位确定，那么确定第 $i$ 位的时候建立如下自动机：对于 $j<i$，$a_j=b_j=j+1$，$a_i=i+ ......

[传送门](https://www.luogu.com.cn/problem/P9197) 为了规避绝对值，我们可以先将$a_i$从小到大排序 考虑$DP$：假如我们计算到$a_g$，则$f_{i,j,0/1,0/1}$定义为当前阶段有$i$段，这$i$段数全用$a_g$连接的值为$j$，是否有左端 ......

### 题目大意 在一个数轴上有 $n$ 个人，第 $i$ 个人位于坐标 $X_i$，权值为 $E_i$。我们要送给一些人书，当 $i$ 收到了一本书，那么对于所有 $j$，满足 $\left | X_i-X_j \right | \le E_i-E_j$，那么 $j$ 会去买一本书。问最少送几个人 ......

## 题解 JOI 王国有 $N$ 位居民，从 $1$ 到 $N$ 编号。居民 $i$（$1\le i\le N$）居住在数轴上坐标 $X_i$ 处，其**影响力**为 $E_i$。同一个坐标可能住了多于一位居民。居民的影响力越高，广告效应也越高，但买书也越谨慎。 Rie 出版了一本关于信息学的书。 ......

# [稻草人](https://loj.ac/p/2880) 按 $x$ 排序，可以将问题转化为寻找点对 $(i,j)$，使得 $y[i]h[i]$ 的点，任何满足 $h[k] > h[j]$ 的点应该会在 $j$ 处被统计一次，因此 $i$ 处不能被统计。二分得到 $k$ 的分界点，用单调栈总点数 ......

上午下午模拟赛。 期望得分 100 + 12 + 30，实际得分 100 + 12 + 60 第一题用时过长导致没有时间看第二题和第三题。 二分图太弱了！ # [疑案追凶](https://www.luogu.com.cn/problem/P7968) 我们将相邻的，互不相交的身高区间放到一个询问里 ......

## 题面 给定一个长为 $N$ 的序列 $S_i$，刚开始为时刻 $0$。 定义 $t$ 时刻第 $i$ 个数为 $S_i(t)$，那么： $$\left\{ \begin{array}{ll} S_0(t)=0\\S_i(0)=S_i\\S_i(t)=\max\{S_{i-1}(t-1),S_i ......

T1：注意到 $i,i+1$ 间的间隔如果选上会增加 $a_{i+1}-a_i-1$ 的时间，然后消耗一根火柴。那不取最大的 $k-1$ 个即可。（$-1$ 是因为一开始用了一根。） T2：按 $A$ 排序，算 $B$ 的前缀和 $S$，选一个区间 $[l,r]$ 显然比不是区间更优，代价 $S_r ......

[洛谷传送门](https://www.luogu.com.cn/problem/P8161) ## 1.题意简述： 一个学期有 $N$ 天 $N*M$ 节课，每天的第 $i$ 节课可以选择效果 $a_i$ 的学习与 $b_i$ 的自习。问应如何安排每节课，使所有功课最小值最大？ ## 2.思路： ......

# Description 给定一个由 `J`、`O`、`I` 组成的字符串，求最多能拆分成多少 `JOI` 或 `IOI`。 对于所有数据，$1\leq \vert S\vert\leq 10^6$。 # Solution 先处理出 $\text{pre}_i$ 为前缀 `J` 和 `I` 的数量 ......

# Description 给定 $n$ 条鱼，每条鱼有长度和颜色。你可以选出若干条鱼，需要满足最大长度小于最小长度的两倍。定义两种养鱼方案不同仅当它们三种颜色之一的出现次数不同，求不同的养鱼方案数。 对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5$。 题目链接：[ ......

# Description 有 $n$ 个套娃，每个套娃都有外体积与内体积，内体积严格小于外体积。你可以把一个娃套到另一个内体积比它的外体积大的娃里面，并且需要套到不能再套为止。求出有多少种套娃方案。 题目链接：[JOI](https://www2.ioi-jp.org/camp/2012/2012 ......

好神奇的做法，我称其为猪猪（猪笼原理）分治。 记 $0,1,?$ 的个数分别为 $a,b,c$。有一个显然的 $O(2^c)$ 做法，对每个 $?$ 枚举其为 $0/1$ 即可。 然后我们考虑只有 $?,1$ 的情况，把所有 $?$ 当成 $0$，答案就是一个超集和；同理，对于只有 $?,0$ 的情 ......

# [JOI 2015 FInal 舞会](https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_d) ## 题意 IOI 王国为了庆祝 JOI 公主的生日，举行了舞会。 预定有 $ N $ 位贵族要参加舞会。 $ N $ 是奇数。将贵族们从 $ ......