JOISC 2023

· · 个人记录

Day 1

currencies

有一棵边权是 w_i 的树，询问在路径 u \rightarrow v 上，要么花费 (1,0) 要么花费 (0,w_i)，在总花费不超过 (x,y) 的前提下最小的第一类花费次数。

在主席树上二分即可。

festival2

考虑将 [2n] 匹配形成的 n 个区间。某个人希望找出一个最大的无交区间集，他采取的方式是按照左端点排序贪心。问在多少种匹配方式下这个做法是错误的。

passport

在 [1,n] 上每个点提供访问 [l_i,r_i] 的通行证。从一个点出发，如果获得这个点的通行证即可更新可访问范围，然后可以获得更多的通行证。问从每个点出发，访问所有点最少需要多少通行证。

假设从起点出发，不会拿到一个通行证，它完全偏序了之前的通行证。否则用线段树优化建图松弛一下即可。

那么一个位置可以分为向左更新和向右更新两类。我们可以令 lm(i,j) 表示拿 2^j 个向左的通行证可以走到的最左端点，令 rm(i,j) 表示拿 2^j 个向右的通行证可以走到的最右端点，转移用 BIT/线段树优化一下。

然后可以求出每个点的答案，再跑一个最短路即可。

Day 2

conveyor

有一棵边的方向未知的树，一次询问可以在一些点集上放一个物品，将一个边集反向，然后交互库会进行一次操作：对于每个有物品的点，如果有出边，则将这个物品移向某一条出边（由交互库决定），否则不进行操作，最后返回每个点上有没有物品。需要求出每条边的方向。n \leq 10^5，询问次数不能超过 30。

一开始就在想一个错误的方向（把规模除2），导致一直没有爬出来。

考虑把和某条无向边相邻的点按深度 mod 3 分类，取最大的点集询问，调整相邻的有向边方向使得物品不可能从这条边走出去。

那么每次至少确定 1/3 个剩余边的状态，可以在规定次数内解决问题。

有一个细节是两个深度相同的点的物品可能走向同一个点（公共父亲），所以应该先在儿子中寻找物品。

council

n$ 个人给 $m$ 个议项投票，要选一个主席和一个副主席出来让他们的选票作废，如果某个议项的票数至少是 $\lfloor{n\over 2}\rfloor$ 则通过。问固定主席的情况下最多通过多少议项。$n\leq 3\times 10^5, m \leq 20

每个议项有4种状态，我们可以跑一个类似 FWT 的东西求出每种 mask 的答案。复杂度 O(n + m2^m)。

mizuyokan2

给出一个正整数序列，将其分成一些段使得一段的和的大小关系形如 <><>... 或 ><><...。多次询问，对一个区间求答案。n \leq 250000,q \leq 50000,a_i \leq 10^9

Day 3

chorus

有一个长度为 2n 的 AB 序列，AB 个数相同，可以进行一些交换，使得得到的序列可以分成 k 个子序列，每个子序列形如 x 个 A 和 x 个 B。最小化操作次数。n \leq 10^6，时限 6s。

最终序列无论如何都是合法括号序列，所以先贪心地将原序列调整为合法括号序列（每一步都取到答案下界）。

令 A_i,B_i 为第 i 个 A，B。那么 [A_i,B_i] 形如左右端点递增的区间。

最终方案一定是将一段区间分为一个子序列。考虑 [A_{[l,r]},B_{[l,r]}] 的代价，可以发现它就是 l \leq i < j \leq r, B_i < A_j 的对数，划分出来的每个区间是互不影响的。

于是带权二分后可以得到一个 1D1D 的dp。有一些做法：

显然这个dp有决策单调性，直接上分治是 O(n \log ^3 n) 的，有87分。

其实这个代价函数可以预处理后 O(1) 计算，于是把分治换成二分队列可以 O(n \log^2 n)，可以通过。

其实这个代价函数可以分成两半，一半斜优另一半直接单调队列，可以 O(n \log n)。

因为单 log 写起来比较恶心于是写了第二种做法。

cookies

有 n 种饼干，数量为 a_i，需要放在一些盒子里，每个盒子不能放多个同一种类的饼干，最终所有盒子都需要填满。盒子的大小取值范围是一个集合，问最少需要多少盒子。n, \sum a \leq 15000

将 a 从大到小排序，令 b_1,b_2,\cdots,b_c 为最终的盒子集合，那么有解当且仅当 \sum a = \sum b 且 \forall x, \sum_{i=1}^x a_i \leq \sum_{i=1}^c \min(b_i,x)。

令 f_{i,j,S} 表示考虑完了 \gt i 的盒子部分，有 j 个盒子 \geq i，\sum \min(b_k,i) = S 是否有解。因为前两维总共只有 O(\sum a \ln \sum a) 种，用 bitset 优化总复杂度 O({(\sum a)^2 \ln a \over w})。

输出方案可以倒着跑一遍，求出来 b，然后贪心。

tourism

给出一棵树，询问区间点集的虚树一共覆盖多少点。

典中典问题。先求 [l,r] \cup {1} 的答案然后容斥减去 lca 上方的部分。前者枚举右端点，用 LCT + BIT 维护即可。

Day 4

battle

主持人会给 A 一个长度为 n(n \leq 43) 的 AB 字符串以及 (X,Y)。A 可以给一个 8 \times 8 网格涂上两种颜色，然后主持人会把网格的第 X 行与第 Y 列任意涂色。然后网格和 n 会交给 B，B 需要说出原本的字符串是什么。

guard

travel

数轴上有 n 个特殊点。一个人从某个位置出发走遍所有点，每次他会选择还未选择的较近点（如果左右距离相同选左边），问他走的距离和。

容易看出只会拐弯 O(\log W) 次。于是倍增求出什么时候拐弯即可。复杂度 O(n \log n + q \log n \log W)。