JOISC 2020 记录

Day1 T1 Building 4

首先有一个 \(O(n^2)\) 的 DP：记 \(f_{i,j,0/1}\) 表示已经填了前 \(i\) 位，其中有 \(j\) 位选择了 A 序列，当前第 \(i\) 位是选自 A 序列还是 B 序列是否可行。

通过打表或推理发现，对于 \(f_{i,j,0/1}\) 中的每一个 \((i,0/1)\)，为 \(1\) 的 \(j\) 是一个连续段，这样就只需要维护这个 DP 的左右边界即可，复杂度 \(O(n)\)。

Day1 T2 Hamburg Steak

由于 \(k\) 很小，同时题目保证有解，所以考虑随机化。

我们选择 \(k\) 个矩形为基准矩形，其他的矩形 \(j\) 都选择和之前的矩形中“影响”最小的基准矩形相交，具体的，就是 \(\dfrac{|R\cap R_j|}{|R|}\) 最大的基准矩形 \(R\)，然后将 \(R\) 替换成 \(R\gets R\cap R_j\)。

考虑如果当前矩形和任何一个矩形都没有交了，我们就希望将这个矩形的决策提前。我们就将其和之前的一个矩形随机交换。感觉跑起来很快。

Day1 T3 Sweeping

对于一个点 \((x,y)\) 我们将其考虑成区间 \([x,n-y]\)。然后考虑每一次操作会发生什么。

一次 H 操作，如果 \(x\le N-l,y\le l\) 则将 \(x\gets N-l\)，也就是如果 \(N-l\in[x,N-y]\)，则 \([x,N-y]\to [N-l,N-y]\)。

一次 V 操作，如果 \(x\le l,y\le N-l\) 则将 \(y\gets N-l\)，也就是如果 \(l\in[x,N-y]\)，则 \([x,N-y]\to [x,l]\)。

也就是说，每一次操作都是一个参数 \(x\)，将所有满足 \(x\in[l,r]\) 的变成 \([l,x]\) 或者变成 \([x,r]\)。

考虑如何维护这个操作，先只考虑 \([l,r]\to [x,r]\) 的操作，另一个同理。假如所有的区间都包含了值 \(p\)，则 \(x\le p\) 的操作可以用一个所有 \(l\) 对 \(x\) 取 \(\max\) 的操作代替。而对于 \(x\ge p\) 的操作，会使得所有 \(r\ge x\) 的区间变成 \([x,r]\)，实时维护 \(r\) 最大的区间，就可以依次找到这些区间了。而这些区间必然不再满足 \(p\in[l,r]\) 的要求了。

我们建立一棵线段树，每一个区间挂在包含它的最小区间那里 \([L,R]\)，这样必然有 \(\dfrac{L+R}{2}\in [l,r]\)，可以用上面说的方法维护，而一个区间因为上面的第二类操作而改变了这样的最小区间，这样的操作也只会出现 \(O(\log n)\) 次，所以可以直接下传。使用平衡树维护当前节点的所有区间，时间复杂度为 \(O(n\log^2n)\)。

Day2 T1 Chameleon's Love

首先考虑询问每一对 \((x,y)\)，如果返回值为 \(1\)，就在它们之间连一条无向边，则每个点的度数为 \(1\) 或者 \(3\)，具体的，如果 \(x\) 喜欢的变色龙也喜欢 \(x\)，则它只会连向与它颜色相同的变色龙；否则，\(x\) 会连向与它颜色相同的，喜欢它的，和它喜欢的三条变色龙。

我们想要知道每一对颜色相同的变色龙，则我们就是要对于度数为 \(3\) 的点 \(x\)，区分出这三条变色龙，我们记其为 \(y,z,w\)。不妨令 \(y\) 为与 \(x\) 颜色相同的，\(z\) 为 \(x\) 喜欢的，\(w\) 为喜欢 \(x\) 的。

则询问 \((x,y,z)\) 得到的结果为 \(2\)，\((x,z,w)\) 的结果为 \(2\)，\((x,w,y)\) 的结果为 \(1\)，也就意味着我们可以得到 \(z\) 是那一条，也就可以得到所有 \(x\) 喜欢的 \(z\)，这样就可以删去所有的 \(z\) 和 \(w\) 而保留 \(y\) 了。这一部分需要 \(3n\) 的询问。

而现在的问题就是如果得到前面的无向边，显然用 \(O(n^2)\) 次询问时不合理的。所以我们考虑先找到一个极大独立集，然后二分询问每一个不在独立集里的点和这个独立集内点的连边，然后就可以将独立集删去了，由于每一个点的度数最多为 \(3\)，我们每一次都可以找到至少 \(\dfrac{1}{4}n\) 大小的独立集，每一次处理了之后规模都会缩小为原来的 \(\dfrac{3}{4}\) 也就是 \(O(n\log n)\) 次询问，而对于每一条边我们需要进行一次二分，也是 \(O(n\log n)\) 次询问。

在每一次找独立集之前 shuffle 一下以减小常数。

Day2 T2 Making Friends on Joitter is Fun

我们相当于不断进行这样的操作：如果两个点之间相互有边，则将这两个点合并成一个点，更行一下与它有关的贡献计算。

而每一次有合并的时候，我们使用启发式合并，将出度加入度较小的那一边的所有边重新加入到较大的那边，这个过程由于可能导致更多的边的合并，所以需要使用队列维护，使用 set 维护边集，时间复杂度 \(O(n\log^2n)\)。

Day2 T3 Ruins 3

（主要是我也不太记得怎么做了）

显然 \(N\) 次地震之后必然无法再发生地震，所以可以将 \(N\) 次看作是无数次，而每一次石柱是否变化都是与后缀有关的，所以考虑从后往前考虑。

设计 DP \(f_{i,j}\) 表示后 \(i\) 个柱子，出现了高度为 \(1\sim j\) 的固定的柱子，而没有出现高度为 \(j+1\) 的柱子。

前面已经有 \(c_0\) 个柱子消失了，还有 \(c_1\) 个柱子存在。

如果当前位置的柱子消失了，必然有 \(h_i\le j\)，而只剩下 \(j-c_0\) 个可选。

如果当前位置的柱子没有消失，则要么 \(h_i=j+1\) 要么 \(h_i> j+1\)，对于第二种情况，我们不好确定 \(h_i\) 的选择，所以我们先不计算贡献。

对于 \(h_i=j+1\) 它可能也同时激活了，前面某些 \(h_{i'}>j+1\) 的柱子，构成了连续段，我们假设拓展到了 \(k\)，我们记需要再前面 \(c_1-j\) 个没有确定的存在柱子中选择 \(k-j-1\) 个，而当前柱子可能是从 \(j+1\sim k\) 中的任何一个位置降到 \(j+1\) 的，也就是有 \(k-j+1\) 中选择。然后就是剩下的那些柱子的排布，这个可以用另一个 DP 预处理出来。

时间复杂度 \(O(n^3)\)。

Day3 T1 Constellation 3

不存在星座就是不存在两个星星作为对角的矩形内没有被阻挡。

从低到高考虑每一层，是一个反悔贪心的过程，每一次在删去自己和删去所有和自己冲突的点中选择一个代价最小的，同时如果删去了和自己冲突的所有点，自己的权值要更新为 \(c_i-\sum c_j\)。

而每一个点可能冲突的星星是一个接下来的区间，使用树状数组维护区间加，单点查即可。

时间复杂度 \(O(n\log n)\)。

Day3 T2 Harvest

由于成熟时间 \(C\) 是全局的，这也就意味着某一个人采摘了一个苹果之后，这颗苹果树下一次被谁采摘是固定的，我们可以通过二分直接找到，下一个人 \(nxt_i\) 以及需要等待的时间 \(tim_i\)。

同样初始的时候每一个苹果第一次被谁摘也是可以二分计算出来的。

考虑所有 \(i\to nxt_i\) 的边，构成了一个基环内向树，我们考虑如何计算询问：

对于非环上点，每一个苹果他最多在某一个时刻采摘依次，可以用平衡树维护苹果集合，需要支持全局加，查询 rk 和启发式合并。

对于非环上的点，我们可以断掉一条环边 \(u\to nxt_u\)，这样就可以把苹果拆成两类：第一类为没有经过环边的，和上面的哪一种类似处理即可；第二类是在经过环边之后，再消耗 \(\sum tim_i\) 的时间被采摘到了。

对于第二种，相当于询问在前 \(T-\sum tim_i\) 时刻内 \(u\) 节点采摘了多少个苹果，我们记环长为 \(L\)，则每一个苹果被 \(1\) 采摘的时刻形如 \(kL+h,k=0,1,2\dots\)，我们记 \(T=qL+r\)，则我们可以通过 \(r\) 和 \(h\mod L\) 的大小关系讨论出贡献，对于 \(\mod L\) 的余数建立树状数组即可。

时间复杂度的瓶颈在于前面的启发式合并，时间复杂度 \(O(n\log^2n)\)。

Day3 T3 Stray Cat

整理数据范围之后发现就是要解决两个问题：\(A=3,B=0\) 的一般图，\(A=3,B=6\) 的树。

对于第一种情况，我们只能走一条最短路，先考虑从 \(0\) BFS 依次得到每一个点的距离 \(dis\)，然后将每一条边的权值赋成 \(\min(dis_u,dis_v)\mod 3\)，这样，每一个点只可能对应两种权值的边，同时走哪一种也是可以直接得到的。

对于第二种情况，考虑先从 \(0\) 开始将每层的边黑白交替染色，这样如果我们初始确定的走的方向，就可以走到 \(0\) 了，但这样唯一的问题就是如果初始是在一个二度点，就不知道应该往哪里走了。所以考虑在每一条链上面建立一个标识串，而 \(B=6\) 刚好可以看到这条链上 \(2+\dfrac{B}{2}=5\) 个字符，我们就需要用这 \(5\) 个字符判断这个标识串的正反，发现 \((001101)^{\infty}\) 满足要求。

Day4 T1 Capital City

考虑如果要联通一种颜色，其构成的虚树上的每一个点的颜色都与要与之合并，这个是构成若干有向边的支配关系的，考虑用树剖线段树优化建图来维护这个支配关系，然后跑 Tarjan 缩点之后找到权值最小的闭合子图即可。

Day4 T2 Legendary Dango Maker

把所有可能的方案抽象成点，在冲突的点对之间连边，也就是要在这张 \(O(RC)\) 量级的图上找尽可能大的独立集，显然是没有确定性算法的，所以考虑模拟退火，提交答案题，调一调参数就跑出来了。

Day4 T3 Treatment Project

每一次治疗能够彻底清除的部分是一个斜 \(45^\circ\) 正方形，我们要阻挡任何一条从下到上的路径，可以发现能够转移到的方向是一个 \(\dfrac{1}{4}\) 平面，使用 KDT 优化 Dijk 即可，时间复杂度 \(O(n\sqrt{n})\)。