joisc

洛谷传送门 LOJ 传送门 很妙的题。但是我今天才补/ll 发现苹果生长的间隔是定值，也就是说，第 \(i\) 个人在某个时刻摘了一棵树上的苹果，那么下一个摘到这个苹果的人确定。设其为 \(p_i\)，连边 \(i \to p_i\)，就构成了一个内向基环森林。还可以顺便给这条边赋一个边权，意义是这 ......

洛谷传送门 LOJ 传送门 为了方便，设 \(a_0 = a_{n + 1} = \infty\)。 考虑拎出来所有区间 \([l, r]\) 使得 \(\sum\limits_{i = l}^r a_i < \min(a_{l - 1}, a_{r + 1})\)。那么 \([l, r]\) 中的 ......

[JOISC 2016] 雇佣计划 题解 这里补充一篇自己的 \(n \log n\) 做法。 本蒟蒻打了两棵线段树，并且进行了繁琐的分类讨论，完全被标算的树状数组吊打 qwq 题意： 给定一个序列 \(a\)，有两种操作： 将 \(c\) 位置权值改为 \(d\)； 给定一个权值 \(b\)，定义 ......

记录一下 JOISC 2023 的做题记录 Day1 T1 Two Currencies 给定一棵树，在边上有总计 \(m\) 个检查站，经过一个检查站需要叫 \(1\) 枚金币或者若干枚银币。\(Q\) 次询问，问一个人有 \(X\) 枚金币和 \(Y\) 枚银币，能否从 \(u\) 走到 \(v ......

[洛谷传送门](https://www.luogu.com.cn/problem/P9520 "洛谷传送门") [LOJ 传送门](https://loj.ac/p/3685 "LOJ 传送门") 观察可得，若存在合法解，则一定存在一种解，使得每个人都不停顿地从起点走到终点。 因为如果一个人走到一半 ......

[洛谷传送门](https://www.luogu.com.cn/problem/P9528 "洛谷传送门") [LOJ 传送门](https://loj.ac/p/3693 "LOJ 传送门") [UOJ 传送门](https://uoj.ac/problem/730 "UOJ 传送门") 神题。 ......

[AtCoder 题目链接](https://atcoder.jp/contests/joisc2022/tasks/joisc2022_b) [Luogu 题目链接](https://www.luogu.com.cn/problem/AT_joisc2022_b) 观察题目，不自觉地想到了 dp， ......

## 题面 给定 $n$ 个点 $m$ 条边的无向图。 现在要对每个点黑白染色。 若能够使一条边连接的两点颜色相同，其他边连接的两点颜色不同，则这条边合法。 求合法的边数。 $ 2 \leq n \leq 10^5,1 \leq m \leq 2 \times 10^5$。 图可能不连通，不保证没有 ......

## 题面 JOI 社为了扩大业务而开始了新社员招募。社员有 $N$ 名候补者，编号从 $1$ 到 $N$，每名候补者有称为评价值的一个确定整数。评价值高于某一个值的候补者全部都将被聘用，他们还将分为几个组别。如果 $a, b(a \lt b)$ 同时被聘用且 $c(a \le c\le b)$ 全 ......

## **[JOISC 2012](https://www.ioi-jp.org/camp/2012/2012-sp-tasks/index.html) Day2 T2「[星座](https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day2. ......

先考虑这个式子： $\sum_{j=1}^{M} |C_{k_{j}} - C_{k_{j+1}}|$ 一定是在 $C$ 有序时取到，具体证明很简单各位读者自己证明。 那么现在式子变成： $\sum{V} + 2 \times({C_{\max} - C_{\min}})$ 这个时候一个常见的技巧是 ......

# P7561[JOISC 2021 Day2] 道路の建設案 (Road Construction) 题解 ## 题目描述 JOI 国是一个 $x\times y$ 的二维平面，王国里有 $n$ 个城镇，分别编号为 $1, 2, \cdots, n \in [1,2.5 \times 10^5]$ ......

2023.7.3 [Problem Link](https://uoj.ac/problem/618) 给定一棵 $n$ 个点的树，对于一个点集 $S$，定义 $f(u,S)$ 为 $\min_u \sum_{v\in S} \mathrm{dis}(u,v)$，$g(S)$ 为使得 $f(u,S) ......

# P6891 [JOISC2020] ビルの飾り付け 4 **[题目传送门](https://www.luogu.com.cn/problem/P6891)** ## Problem 给定长度为 $2n$ （$1\le n\le5\times10^5$）的序列 $A$，$B$。要求构造一个单调不降 ......

我觉得 JOISC 的题都非常有水平！ ### P9329 [JOISC 2023 Day1] Two Currencies 简单题。因为每次尽量花银币，而且尽可能在银币花销比较小的花银币，所以整一棵主席树，二分。 复杂度 $O(n\log n)$ 非常好。 [Submission](https:/ ......

# 「JOISC 2020 Day2」遗迹 ## 题目大意： 给定长度为 $2n$ 的序列 $h_i$，满足对于所有 $k \in [1,n]$，均存在两个 $i$ 满足 $h_i = k$，定义“地震”为如下操作： - 对于所有 $i \in [1,2n]$，当且仅当 $h_i > 0$ 且对于所 ......

### Day1 监狱 首先我们感性理解：每名囚犯一定是依次走到自己的目的地的。因为如果起点或终点挡着别人的路，让他先走到目的地就行了。而在中间的话还容易挡着别人的路。 所以如果一个人的起点在另一个人的路径上，那么这个人必须先走，如果一个人的终点在别人的路径上，那么这个人必须后走。 然后就随便用树剖 ......

### **subtask 1** 因为 $1\le s_i\le2$，所以每艘船上都至少有一个保安。令 $cnt_i$ 表示第 $i$ 艘船上的保安数，可以先将所有 $cnt_i+=1$ ，所有 $s_i-=1$。经过这一次操作后，如果两艘船之间的小岛的 $s_i$ 全为 $0$，表示这两艘船可以 ......

## statement 给定 $n$ 个人，每个人从 $T_i$ 秒开始从 $a_i$ 移动到 $b_i$，每秒移动一个单位。给定 $q$ 个保镖，每个保镖从 $P_i$ 秒开始，从 $x_i$ 开始移动，每秒一个单位。如果保镖和人在同一个位置上，就可以获得 $C_i$ 的奖金，问每个保镖最多能获 ......

##### JOISC2020 Day1 建筑装饰4 Building4 我们发现 $A$ 的个数是连续的，所以我们只需要 DP 出最大的 $A$ 的个数和最大的 $B$ 的个数，若两者都 $\ge n$ 那么就有解。然后再从后往前推出方案即可。 https://qoj.ac/submission/ ......

##### JOISC2017 Day1 开荒者 Cultivation 首先进行转化，转化为对于每个点 $x,y$，将其扩成一个左上角为 $(x-a,y-c)$ 右下角为 $(x+b,y+d)$ 的矩形后覆盖整个 $R\times C$ 的大举行。首先考虑枚举 $a,b$，那么我们可以得到平面上的 ......

#### JOISC21 フードコート (Food Court) 首先我们发现我们这个删除实际上可以假删除，我们每次问询时求出这个队列目前被删了几个（维护区间加，区间 $\max(0,A-x)$）就可以把删除操作给弄掉了。 然后我们考虑对商店做扫描线！因为我们现在其实就是对商店的单点问询，我们这个加 ......

##### JOISC2022 Day1 监狱 Jail 首先我们发现操作一定是给所有人排序，然后按照顺序直接从 $s_i$ 挪到 $t_i$，要求是对于 $i$，所有在它之前挪的 $t$ 不能在 $s_i\to t_i$ 上，所有在它之后挪的 $s$ 不能在 $s_i\to t_i$ 上。有了这个 ......

## [JOISC2022]监狱 容易发现一个人一旦开始走就不会停。 因此如果一个人的开始点 $s_i$ 在另一个人的 $s_j\to t_j$ 上，那么 $i$ 的出发时间一定小于 $j$，对于 $t_i$ 在路径上同理。 因此可以建出一个图，那么合法当且仅当图是 $DAG$ 。 建图可以用倍增优 ......

JOISC 2020 D1T1 Building 4 有显然的 $O(n^2)$ DP，大力猜测状态里 A 的个数这一维对于合法的状态是一个区间，就可以 $O(n)$ 了。 不太会证，~~已经过 C++ 核实~~。 D1T2 Hamburg Steak 感觉，没啥想法，好像有很多随机化过了。 正解做 ......

T1 巴士走读 考虑在每个节点 $u$ 维护 $f_u(x)$ 表示在时刻 $x$ 到达节点 $u$ 时的最晚出发时间，显然这个函数单调递增。考虑进行转移，将所有巴士按照 $Y$ 进行排序，依次枚举每辆巴士，设巴士出发节点为 $A$ ，终止节点为 $B$ ，发车时间为 $X$ ，到达时间为 $Y$ ......

[JOISC2020] 最古の遺跡 3 题目 可以发现，第 $i$ 根柱子最后的位置在所有曾经为 $i$ 的位置中最大的。记 $T_i$ 表示最终保留高度 $i$ 的柱子编号。 考虑按照值域从大到小扫描，维护一个集合 $S$ 表示尚未留下的位置集合，每次执行： $S\gets S\cup {X_i, ......

仍然是没有做通信题。 JOISC2016 Day1 Matryoshka 俄罗斯套娃 转化错了，转化成上升子序列了，然后就变成了区间 LIS。 实际上是 LDS，那么就可以直接做了。 https://qoj.ac/submission/99648 JOISC2016 Day1 Memory2 神经衰 ......

题目 点这里看题目。 给定一张 $N$ 个点 $M$ 条边的无向连通无自环图。一条边除其连接的端点外，还有参数 $w$。 进行 $Q$ 次询问，每次询问给定 $x$，回答一条边的边权为 $|x-w|$ 时最小生成树的代价之和。 $100%$ 的数据满足：$1\le N\le 500, 1\le M\ ......

通信题还没做。 JOISC19 D1T1 試験 (Examination) 双 log 很简单。但是单 log 才是这题的本质。 我们进行一些补集转换。我们能算的是什么？我们能算一条边在边界上的直角边平行于坐标轴的直角三角形数点，我们能算长方形数点。 我们要算 1 的点数，那相当于 2 的点数减去 ......