主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
JOISC 补完计划
最后更新于 2025-08-28 09:44:29
作者
加藤惠
分类
个人记录
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
从去年联赛后就感觉自己颓过头了...甚至连 wzp 都在婊我太颓了... 开个 blog，~~假装~~督促一下自己。 之前写过的题就不写了。 ~~如果没补完，或者进度太慢我可能又会把这篇 blog 删了~~ ## 2.23 ##### 「JOISC 2017 Day 2」门票安排 神仙题。 首先有一个结论，所有翻转的区间的并不为空。 然后就有了一个多项式做法。 枚举一个点 $x$ ，表示所有翻转的区间都覆盖了 $x$。 二分答案，枚举需要被翻转的区间 $t$。 从左往右考虑每个点 $i$，假设之前共翻转了 $y$ 个区间，$i$ 被覆盖了 $z$ 次，当前点 $i$ 还需要翻转 $now$ 个区间。 推下不等式可以得到 $now \ge \lceil \frac{z+t-y-ans}{2} \rceil$。 考虑贪心选择所有左端点在 $i$ 的左边，覆盖了 $x$，且没有被翻转的区间中，右端点最大的 $now$ 个进行翻转，可以用堆维护。 最后再对所有点 check 一遍。 复杂度是 $O(n^3\log^2n)$ 的。 考虑减少 $x,t$ 的枚举量。 然后是一堆神仙结论，最终得出了： 令 $a_i$ 表示所有区间都选择不翻转的情况下，$i$ 覆盖了几次。 设 $a_l,a_r$ 满足 $a_l=a_r=\max\limits_{i=1}^{n} a_i$，且 $l,r$ 分别是最右端和最左端的两个。 最优的答案中存在一种使得 $x$ 取到了 $l$ 或者 $r$，$t$ 取到了 $a_l-mid$ 或者 $a_l-mid+1$，其中 $mid$ 是当前二分的答案。 具体证明可以看[这里](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2-arranging_tickets-review.pdf)。 然后再套用上面的做法就行，复杂度 $O(n \log^2 n)$。 ##### 「JOISC 2017 Day 2」火车旅行 每个点往左右第一个比它大的点连边，问题转换为多次求两点的最短路。 预处理 $L_{i,j},R_{i,j}$ 表示从 $i$ 出发走 $j$ 步，最左和最右分别能走到哪里。转移是 easy 的。 设 $A<B$，考虑先找到从 $A$ 出发走 $k$ 步使得 $R_{i,k} < B \le R_{i,k+1}$，然后再从 $B$ 走到 $R_{i,k}$。 这样是 $O(n^2)$，可以倍增加速，复杂度 $O(n \log n)$。 ##### 「JOISC 2017 Day 3」长途巴士 我自闭了，感觉自己就是个弱智。 插入斜率递增的直线，如何线性维护下凸包想了一万年。 有一个非常容易观察到的性质，如果第 $i$ 个人在到 $j$ 个服务站前 GG 了，那么在到达第 $j$ 个服务站前，第 $i$ 个人后面喝水的人都会 GG，也就是 GG 的人是一段区间，且右端点是某个服务站前最后一个喝水的人。 考虑根据这个东西 DP。 设 $F_i$ 表示做完前 $i$ 个人的最小费用。 转移考虑第 $i$ 个人有没有 GG。 令 $cost(i,j,k)$ 表示区间 $[i,j]$ 内的人在从第 $k$ 个服务站往 $k+1$ 个服务站移动的时候 GG 的费用。 $F_i=\min(F_{i-1}+w\times(\left \lfloor \frac{x}{t} \right \rfloor+[D_i \le x \bmod t]),\min\limits_{j,k} F_j+cost(j+1 ,i,k))$ 具体写出式子后发现如果 $j$ 转移到在它后面的 $i$ 时 $j$ 的贡献是一个一次函数。 考虑 CDQ 分治，每次插入斜率递增的直线，维护一个下凸包。 然后我tm真就在想插入斜率递增的直线怎么维护，想了半年还是只会李超树，虽然复杂度都是一个 $\log$ 的。 后来去 UOJ 群问了一下，发现和斜率递减是一样的，这tm只是插入的位置不同，为什么我就觉得不能这样维护了呢？？？ 不愧是我，丢人.jpg ## 2.24 ##### 「JOISC 2017 Day 3」幽深府邸 ~~之前做 HNOI 的时候做过了~~ 本来想写一个靠谱的做法，还没写完突发奇想，感觉稍微改一点地方就能过了。 然后发现这个乱搞它过了，就不管了。 考虑预处理出每个点能到的区间 $[l_i,r_i]$。 考虑扫描线，开一个单调栈维护能到当前点的点，栈里面的点的 $l_i$ 递增。 每次先弹出栈头不能到当前点的点。 然后更新栈里面每个点的 $l_i$，如果两个点的 $l_i$ 长一样了就合并在一起。 复杂度是 $O(n^2)$ 的... 但是过了... 复杂度靠谱的话就考虑把栈改成 set，每次更新的时候不是每个点更新，而是考虑多了几个钥匙会让哪些位置可能产生更新，这个总的是 $O(n)$ 的，又因为相同的合并了，所以总共只有 $O(n)$ 次更新。复杂度是 $O(n \log n)$ 的。 HNOI 那个题当时写了个另外的靠谱的 $O(n \log n)$ 的做法。 每次不断往左走直到不能走，再往右走直到不能走，重复这个过程直到往左往右都不能走。 但是不知道为什么少了几个限制，我觉得原来的做法复杂度不太对了... 通过观察 lych 的题解，我发现好像其实还是对的... 不愧是我，丢人.jpg ##### 「JOISC 2017 Day 3」自然公园 ~~补了罗小黑战记~~ 看不懂 lych 的题解...去膜了一发 supy 的代码... 考虑每次加入一个一个点 $x$。 如果直接已经找到的图有点直接连到了 $x$，就直接加入 $x$，每次爆出一个连通块的 bfs 序，二分找到最后一个和 $x$ 有连边的点，然后删去这个点，继续在分裂出来的连通块里找直到找不到一个点和 $x$ 有连边，因为有度数限制，询问次数是对的。 如果没有点直接连到 $x$，考虑二分出 $x$ 到已经找到的图的链上的编号最大的点 $y$，先递归加入 $y$。 ## 2.25 今天这种天气真的不想动脑子啊。。所以可能就鸽了。。 ##### 「JOISC 2017 Day 4」绑架 2 ~~我终究还是做题了~~ 显然有一个非常傻逼的 $O(nm)$ 的求出每个点答案的 DP。 然后看到 $Q \le 100$ 那不就大力猜想这个 DP 的如果确定起点的话状态是非常少的，直接记忆化一波。 然后就过了。 证明可以看 lych 在 ZJOI2018 的讲课。 ##### 「JOISC 2016 Day 1」俄罗斯套娃 ~~先跳计算几何~~ ~~司机模拟赛搬过这个题~~ 根据 wzp 对我的教导，最小链覆盖等于最长反链。 直接扫描线树状数组维护就完事了。 ## 2.26 颓了好久。。 ##### 「JOISC 2016 Day 1」棋盘游戏 屑题。 写出状态后直接大力分类讨论就行。 转移写的仔细一点就行。 ##### 「JOISC 2016 Day 2」雇佣计划 ~~普及题~~ 是在太傻逼了，不想说了。 ## 2.27 ~~从起床颓到一点半~~ 把计算几何那个题填了。 ##### 「JOISC 2017 Day 4」Dragon 2 相信 $O(qn \log n)$ 大家都会。 然后众所周知如果每次询问的复杂度是 $O(\min(siz(F_i),siz(G_i)) \times \log n)$（$siz(x)$ 表示种族 $x$ 的龙的个数）的，记忆化一波复杂度是可以随便跑 $n=3 \times 10^4,q=5 \times 10^4$的。 所以再讨论一种情况就做完了。 写的比较浪，代码喜提 LOJ 最长 AC 代码。 ~~震惊，主席树竟比树状数组跑得快~~ ## 2.28 ##### 「JOISC 2016 Day 2」三明治 好题。 首先有一个非常菜的做法。 bfs 从外往里拿，每个点搞两个 bitset 分别表示是拿这个点靠拿这个点上面的三明治还是拿靠下面的三明治 需要拿的三明治。 时空复杂度都是 $O(\frac{n^4}{w})$。 从外往里不行就考虑从里往外，对于每个点考虑如果靠拿这个点上面/下面的三明治而拿这个点，需要拿的三明治是固定的，这个可以直接 dfs 找。 直接做复杂度是 $O(n^4)$ 的。 但是我们如果对于每一列从上往下做，每个点可以继承上一个点搜索的结果，因为前一个点肯定要拿。 复杂度优化为 $O(n^3)$。 ##### 「JOISC 2016 Day 2」女装大佬 ~~这个题让我回忆起了 PKUWC 当时 D2T1 做了 1h 的绝望~~ ~~然后这个题我又做了毛 1h~~ ~~我tm思考了半年其实根本不存在的细节，不愧是我，丢人~~ 显然原问题可以转化为一个匹配问题。 考虑可以在 $n$ 分钟内领完的条件是 $\left \lfloor \frac{\max(preF_i-preM_i)}{2} \right \rfloor \le \frac{preF_n-preM_m}{2}$ $preF_i$ 表示前 $i$ 个人中 'F' 的个数，$preM_i$ 表示前 $i$ 个人中 'M' 的个数。 可以把 $\max$ 去掉，考虑对于每个 $i$ 求要满足这个条件最少要把几个后面的 'M' 移到 $i$ 前面。 推下不等式就做完了。 不太懂我为什么想了这么久。 ## 2.29 今天模拟赛... ##### 「JOISC 2016 Day 3」回转寿司 ~~之前在去恰饭的路上似乎听过zyy说过类似的题~~ ~~以为是神仙题，想了一下发现是傻逼题~~ 考虑分块。 边角直接暴力重构，重构考虑第 $i$ 个点就是之前塞进来的点和 $i$ 前面的点的最小值，这个可以通过分析那个代码得到。 中间的块随便搞搞就行了。 复杂度可以做到 $O(q\sqrt{n}\log n)$。 ##### 「JOISC 2016 Day 3」电报 ~~普及题~~ 对于每个点保留连向它的边中边权最大的那条边，如果保留整个环再随便搞搞就行了。 ## 3.1 三月了呢。 ##### 「JOISC 2016 Day 4」危险的滑冰 ~~总感觉 JOISC 6102 的题做起来不得劲啊~~ 首先有一个性质，对于两个原本就有的冰块中间的那块区域只会到一次。 考虑根据这个东西建图，对于每个点 $(i,j)$ 向它四个方向两点中间没有冰块的点连边，边权为从 $(i,j)$ 出发所需的来回走的步数。 直接建边数是 $O(n^3)$ 的。 考虑优化建图，歪比歪比，歪比巴卜（这部分挺 easy 的懒得写了）可以优化到 $O(n^2)$。 复杂度 $O(n^2\log n)$。 ##### 「JOISC 2016 Day 4」最差记者 2 ~~LOJ 上有的 JOISC 6102 的题补完辣~~ 首先有一个贪心，考虑从小到大考虑每个第二轮的成绩，能匹配到第一轮的成绩就匹配掉，并且应该匹配尽量大的。 但是这显然有一个小小的问题，这样子搞可能会让某个人没东西可以匹配。 举个栗子： ``` 3 1 1 1 2 5 3 5 2 1 3 1 4 ``` 按照上面的贪心，第二轮的第 $2$ 个和第 $3$ 个和第一轮的第 $1$ 个和第 $2$ 个配，第二轮的第 $2$ 个并不能和第一轮的第 $3$ 个配。 所以还要判一下如果当前点匹配了某个点会不会使得某个点没得配了。 线段树维护即可。 复杂度 $O(n \log n)$。 ##### 「JOISC 2018 Day 1」道路建设 LCT 模板题。 ## 3.4 跳计算几何。 ##### 「JOISC 2018 Day 1」帐篷 考虑 DP。 设 $dp_{i,j}$ 表示已经有 $i$ 行和 $j$ 列填了的方案数。 转移考虑最上面一行怎么填，这样就不会算重了。 ##### 「JOISC 2018 Day 2」修行 转载自：[zsy 的博客](https://blog.csdn.net/abcyan1235/article/details/101608634/) 相当于是要求有多少排列 $p$ 满足 $p_i>p_{i+1}$ 的 $i$ 的个数恰好为 $k-1$。 转化为求期望。这个期望等价于 $n$ 个 $[0,1)$ 随机变量 $a$ 满足 $a_i>a_{i+1}$ 的 $i$ 的个数恰好为 $k$ 的概率，而这样的 $a$ 又可以一一对应为 $n$ 个 $[0,1)$ 随机变量 $b$ 的前缀和的小数部分，其中当 $a_i \le a_{i+1}$ 时前缀和整数部分不变，否则整数部分 $+1$。 于是变成了求 $k-1 \le \sum b_i < k$ 的概率。 先把 $b_i \in [0,1)$ 的限制容斥掉，然后就变成了求 $n$ 个 $[0,+\infty)$ 随机变量之和 $<k$ 的概率。这个概率实际上等于 $\frac{k^n}{n!}$。 ## 3.5 先跳个提答。 ##### 「JOISC 2018 Day 2」最差记者 3 ~~为什么这个题当时现场有 16 个人过啊~~ 设 $b_i$ 表示 $i$ 移动一次会和 $i+1$ 拉开多少距离。 可以用 $b_{i-1}$ 推出 $b_i$。 $b_i=\left \lceil \frac{a_i}{b_{i-1}} \right \rceil \times b_{i-1}$ 不难发现 $b_i$ 的值只有 $\log$ 种，$b_i$ 相同的点显然任意时刻都是靠在一起的。 询问的时候直接算出每段区间的左右端点，和询问的区间取交求和就行。 ##### 「JOISC 2018 Day 3」比太郎的聚会 ~~为什么这个题当时现场只有 3 个人过啊~~ ~~经典套路题~~ 直接按询问 $Y_i$ 大小分类就行。 ## 3.6 摸了。 ##### 「JOISC 2018 Day 4」糖 经典题。 ## 3.10 摸了几天鱼，补了几部一直鸽着的片子。 ##### 「JOISC 2014 Day1」巴士走读 直接按 $Y_i$ 从大到小加入 $1$ 连出去的边，更新到每个点的最早的时间。 因为每条边最多只会更新一次，所以复杂度是对的。 询问的时候二分一下就行了。 ##### 「JOISC 2014 Day1」有趣的家庭菜园 显然 $ans=\sum\limits_{i=1}^{n} \min(\sum\limits_{j=1}^{i-1}[a_j>a_i],\sum\limits_{j=i+1}^{n}[a_j>a_i])$。 拿 jio 做一下就行了。 ##### 「JOISC 2014 Day1」历史研究 分块，然后就做完了。 ## 3.11 ##### 「JOISC 2014 Day1」拉面比较 每次取出两个数，小的和 $\min$ 比，大的和 $\max$ 比。 ##### 「JOISC 2014 Day2」水壶 写了一个乱搞。 问题本质就是求一个网格图两个的最小瓶颈路。 考虑 Boruvka，每次从一个集合内的点开始 bfs，如果 bfs 到一个另外集合的点就直接结束。 复杂度不会算，至少是 $O(H \times W \log n)$ ，但是感觉最多再只会乘一个常数。 然后根据这个东西我又想到了一个[问题](https://www.zhihu.com/question/378582977)。 zyy 说大概是 $O(20n^2)$ 的。 欢迎神仙来回答。 ##### 「JOISC 2014 Day2」交朋友 如果一个点的出度为 $2$，显然这个点能到达的点相互之间都会有连边。 dfs一遍，并查集维护就行。 ## 3.12 ##### 「JOISC 2014 Day2」邮戳拉力赛 考虑如果对于每个打卡点经过的方式确定的话，就是一个下行到上行和上行到下行匹配的过程。 考虑根据这个东西 DP。 设 $dp_{i,j}$ 表示做到 $i$，之前两者差为 $j$ 的最优解。 转移的时候注意下一个点可以匹配多次就行了。 没想到一个点匹配多次可以直接记到第二维状态，而是需要再加一维记录前面最佳匹配，最后看别人代码都只有两维才发现的我是个傻逼。 ##### 「JOISC 2014 Day3」JOIOJI 随便推推式子，开个 map，然后扫一遍就行。 ##### 「JOISC 2014 Day3」稻草人 一往分治方向想就直接会了... 考虑分治。 从大到小加入当前分治的区间的点，维护两个单调栈，单调栈里记录的是下标，然后询问的时候在一个单调栈里二分下就行了。 想了半年才往分治方向想的我是个傻逼。 ##### 「JOISC 2014 Day3」电压 先搞出原图的一个生成森林。 非树边合法的条件是只有一个奇环，并且那个奇环经过这条边。 树边合法的条件是所有奇环都经过这条边，且没有偶环经过这条边。 树上差分一下就行了。 ## 3.13 ##### 「JOISC 2014 Day4」两个人的星座 首先有一个性质：两个不交的三角形存在两条公切线使得两个三角形分别在公切线的两侧。 考虑根据这个性质统计，后面这部分其实是很 easy 的。 枚举一个点，对另外点极角排序后，two pointers 就行了。 具体实现的时候可以用前缀和，这样巨好调。 这个题让我找到了我计算几何板子的一个大锅... ##### 「JOISC 2014 Day4」挂饰 直接 DP 就行。 ##### 「JOISC 2015 Day1」复制粘贴 2 从后往前做就行。 ##### 「JOISC 2015 Day1」愉快的标志设计 可以发现一个合法的字符串，unique 后长度只有 $\log$，暴力算一算就行了。 ##### 「JOISC 2015 Day1」有趣的家庭菜园 2 首先有一个 $O(n^2)$ 的 DP。 数据结构随便维护一下就行了。 ## 3.16 ##### 「JOISC 2015 Day 1」卡片占卜 区间修改感觉有点难处理，差分一下序列改成两个单点改。 现在就是每次可以改两个点，最终要使四个点的值改变。 对于每个操作两个点之间连边，那么答案四个点两两匹配的最短路之和。 ##### 「JOISC 2015 Day2」Building 3 考虑怎么 check 一个序列 $A$ 是否合法。 可以证明如果对于每个 $i$ 都满足存在一个 $j\ (j<i)$ 使得 $A_j=A_j+1$，则这个序列是合法的。 统计答案是 easy 的，注意判一下 $0$ 和只能插一个位置的情况就行。 ##### 「JOISC 2015 Day2」Keys 考虑对于每个间隔分类讨论两端点具体是什么情况这个间隔才会对答案有贡献。 可以发现只有一种情况是和两端的点都有关，按这种情况给 $n$ 个人重新排列 DP 就行。 ##### 「JOISC 2015 Day2」Road Development 树剖模板题。 ## 3.18 ##### 「JOISC 2015 Day 3」AAQQZ 屑题。 写了个 $O(n^3)$ 过了就懒得改成 $O(n^2\log n)$ 了。 具体的话就是考虑分回文串的中点是否在选择要 sort 的区间内。 在 sort 区间内的话考虑枚举修改的区间，中点肯定在最小的数中间或这最大的数中间。 不在的话考虑，枚举中点，然后找到左边和右边第一个不匹配的点，然后从这个点开始拓展就行了。 ##### 「JOISC 2015 Day 3」Card Game Is Great Fun 直接 DP 就行。 ##### 「JOISC 2015 Day 4」Inheritance 考虑按边权对边 sort 后对每条边算答案，开 $k$ 个并查集维护第 $k$ 人的连通的情况，显然这条边会在第一个出现这条边的两个点还没连通的人那边被删，二分一下就行了。 ##### 「JOISC 2015 Day 4」Limited Memory 先判掉 $n$ 是奇数，左括号的数量不为 $\frac{n}{2}$ 的情况。 考虑对于每个右括号找与之匹配的左括号，因为是从前往后匹配的，所以之前的肯定合法，从后往前扫的时候只要记左括号与右括号的差就行。 算一下会发现刚好 22 位够用。 ## 3.19 ##### 「JOISC 2015 Day 4」防壁 以前和小猪讨论过一道 csa 的和这题长的差不多的一个题，当时就觉得有点细节就没去写，终于还是要写的。 考虑把同方向移动缩起来，每次移动就是右边贴着一个点往左移或者左边贴着一个点往右移，当一次移动的间隙没有当前块长，那么这次移动是不存在的，可以把这次移动缩起来，所以按长度从小到大算每个块，每次缩掉长度小于当前块的移动。 关于维护可以用 set 和 链表。 具体的细节其实主要在第一次的移动。 我一开始觉得第一次移动不太能缩起来，但是通过观察过的人的代码，好像都没管这个东西，经过一波分析后，发现好像是不用管的，然后第一次的移动再单独拿出来算一下就行了，具体可以看我 LOJ 上的代码。 ##### 「JOISC 2019 Day1」考试 三维偏序板题。 ## 3.20 ##### 「JOISC 2019 Day1」馕 对于每个人求出把一块馕平均分成 $n$ 段的切割点。 对于第 $i$ 段给第 $i$ 个切割点最靠前的人。 可以证明这样构造一定是存在且合法的。 需要比较精细的实现，写的比较浪分数可能会炸 ll。 ##### 「JOISC 2019 Day2」两个天线 憨批数据结构题。 4k代码一发过编译然后直接过了还蛮爽的。 ##### 「JOISC 2019 Day2」两道料理 考虑扫描线，维护第二维。 每次移动第一维，第二维转移形如 $f_i=\max(f_{i-1}+b,f_i+a)$ 这样的形式。 直接维护不太容易维护，考虑维护这个 DP 数组的差分数组。 后面那个东西，相当于一个前缀都加上一个数，可以看做是两个单点插入。 前面那个东西，相当与是一个单点插入。 同一个位置插入多次注意要先插入正的再插入负的。 另外如果一个位置不管怎么走都要算，不要插入直接记到答案里（我tm被这个东西续了半年，后来看到 mayaohua 一开始和我错的一样，然后他后面判了这个东西才注意到）。 ##### 「JOISC 2019 Day3」指定城市 在模拟赛里做到两次类似的题了。 大力猜想每次选最长的链就是对的。 随便 set 或者堆维护一下就行了。 ## 3.21 ##### 「JOISC 2019 Day3」开关游戏 有一个非常重要的性质：一个点最多只会被覆盖两次。 根据这个性质 DP 就行。 令 $F_{i,j,k}$ 表示做到第 $i$ 个点，两次操作是 $j,k$ 的最少操作数。 直接转移就行。 ##### 「JOISC 2019 Day4」矿物 卡常卡的我心力交瘁，从 200w，到 140w，到 120w，到 102w 再到 99w。 考虑先对所有点做一次，分成两个集合，使得每一对点的两个点分别在不同的集合内。 然后考虑分治，每次把一个集合的一半的点塞进去，询问另外一个集合中和塞进去的点匹配的点。 递归下去做。 实现精细一点，卡卡常就过了。 ## 3.23 ##### 「JOISC 2019 Day3」穿越时空 Bitaro xsj 模拟赛题。 当时只会 $q\sqrt{n \log n}$ /kk。 首先把每次要 +1 这个东西转化掉。 考虑线段树维护这个东西。 有一个性质，如果这段区间的 $\max{l_i}$ 比 $\min{r_i}$ 大，那么这个区间的行走路线可以唯一确定。 那么考虑可以用一个三元组 $(l,r,c)$ 来表示一段区间的答案，即一定要从 $l$ 高度的位置进，从 $r$ 高度的位置的地方出，需要的费用为 $c$。 另外如果路劲不唯一的时候就记一下 $\max{l_i}$ 和 $\min{r_i}$。 合并讨论下就行。 ##### 「JOISC 2019 Day4」蛋糕拼接 3 一眼以为是凸优化，写完过不去第一个样例才发现是假的。 首先显然最优排列方案的美观度是 $\sum V_i-2 \times (\max {C_i}-\min{C_i})$。 那么首先可以先把蛋糕按 $C_i$ 排序。 枚举选的右端点，可以证明选取的最优的左端点单调不减。 直接分治+主席树做就行了。 ##### 「JOISC 2019 Day4」合并 zyy 模拟赛题..我当时现场过了来着.. 因为太傻逼，鸽了。 ##### 「JOISC 2018 Day 1」栅栏 考虑对于每两个栅栏和正方形的四个顶点连边，问题转化为求一个最小环且包含这个正方形。 判包含可以考虑从原点引出一条射线，包含的条件可以转化为这条射线经过了环上的奇数条边。 建边的话判一下两条线段的四个顶点分别与另一条线段的距离就行。 ## 3.24 ##### 「JOISC 2018 Day 2」路网服务 注意到把附加的边全都连到同一个点上比较优。 爬山爬了半年还是只有80+，自闭了。 去问了一波 xpp，他说他退火挂着跑了一会就跑出来了，于是我也把爬山改成了退火挂着跑了一会，然后就跑出来了。 ##### 「JOISC 2018 Day 3」安全门 可以看 [myh 的博客](https://blog.csdn.net/qq_38609262/article/details/86750729)。 ## 3.25 ##### 「JOISC 2018 Day 4」野猪 LOJ 上 2019 及以前的 JOISC 题终于补完了... 然而最近 LOJ 又上传了 JOISC 2020 的题.../kel 第一反应不走最短肯定走次短，但是显然是假的。 然后冷静了好久，发现再记一条不经过最短出发的边和次短抵达的边的最短 和一条不经过次短出发的边和最短抵达的边的最短好像就可以了。 这个东西可以把边当点跑 Dij 在 $O(m^2\log m)$ 的时间内处理出来。 资瓷单点修大家都会，线段树维护矩阵就行。 因为时限开的比较宽，窝写的时候偷了点懒，矩阵合并的复杂度是四次，不知道为什么总的时间比 xsj 合并是两次的少。 ## 3.26 ##### 「JOISC 2020 Day1」建筑装饰 4 先考虑朴素的DP。 $dp_{i,j,0/1}$ 表示第 $i$ 个数选 A/B，选的 A 的个数为 $j$ 是否可行。 可以证明对于 $dp_{i,?,j}$ 为 1 的值的地方是一个区间。 DP 这个区间就行。 ##### 「JOISC 2020 Day1」汉堡肉 写了个乱搞，没想到过了。 考虑 random_shuffle，每次矩形放到某个集合能使这个集合减小的面积最小的那个集合。 直到找到合法的解。 正经做法可以看 [zyy 的博客](https://blog.csdn.net/zhouyuyang233/article/details/105010508)。 ##### 「JOISC 2020 Day2」变色龙之恋 首先有一个 $O(n^2)$ 的做法。 先对于每个变色龙 $i$ 求出有多少个 $j$ 在询问 $\{i,j\}$ 时返回的答案是 $1$。 可以发现对于每个变色龙合法的 $j$ 要么只有 1 个要么只有 3 个，一个说明和它一样的就是那个，三个的话可以先通过两个询问得到这个变色龙喜欢的变色龙编号，在做一遍。 复杂度瓶颈在对于每个 $i$ 找合法的 $j$。 考虑一个一个变色龙扫过去，因为与一个变色龙有关的变色龙最多只有 3 个，可以把之前的变色龙分为 4 个集合使得一个集合内的任意两个变色龙没有任何关系，然后一个一个集合二分过去就行。 需要比较精细的实现和比较优秀的常数。 ## 3.27 ##### 「JOISC 2020 Day2」有趣的 Joitter 交友 考虑给出一个有向图怎么算最后的边数。 如果两个点 $u,v$ 之间如果既存在 $(u,v)$ 也存在 $(v,u)$，这两个点可以缩起来。 最终答案就是缩完点后的图每个点的 $siz\times (siz-1)+siz\times \text{入度}$。 考虑对于每个点分别维护四个 set，启发式合并就行。 ##### 「JOISC 2020 Day2」遗迹 可以看 [xyx 的博客](https://blog.csdn.net/qq_39972971/article/details/105074251)。 ##### 「JOISC 2020 Day3」星座 3 考虑按最大值分治，维护一个 DP，启发式合并或者线段树合并就行。 ## 4.1 草，我居然鸽了这么久了。 看起来这个寒假又被续了半个月，所以一些颓废相关的东西被我提上日程了，所以最近大概都会这么鸽。 不过本来 LOJ 上有的题就快补完了。 ##### 「JOISC 2020 Day4」首都城市 考虑点分治，从当前根的颜色开始拓展，如果有颜色满足所有是当前颜色的点并没有全在当前子树中，那么这个答案肯定是不优的，可以直接舍去。 ##### 「JOISC 2020 Day3」迷路的猫 首先 $A=3,B=0$ 的 sub。 可以考虑搞出一棵 bfs 树，按层给边染色即可。 $A=2,B=6$ 的 sub。 如果一个点的度数大于 2，与父亲的连边和与儿子的连边颜色不同就能分辨哪个是父亲。 问题在于链上怎么在 6 步之内区分上下。 考虑到要往返，所以其实就只有 3 步。 3 步一共可以得知 5 条边的信息，那么可以构造一个 01 字符串 $S$，使得可以通过一个长度为 5 的字符串是否在 $S$ 的循环中存在得到方向。 随便手玩构造一下就行。 ##### 「JOISC 2020 Day3」收获 垃圾数据结构题。 每个点往前一个和它距离至少为 $C$ 的点连边，可以得到一个基环树森林，考虑树上的询问和环上的询问分开做。 树上直接线段树合并一波就行。 环上考虑破环为链，则可以用两个前缀和的差 $pre_i-pre_j$ 表示 $j$ 到 $i$ 需要的时间，设一棵树 $i$ 要跑到环上要 $dep_i$ 的时间，则一个询问的答案为 $\sum_{pre_j-pre_i+dep_k \le T,j \in [i,i+n)} \lfloor \frac{T-(pre_j-pre_i+dep_k)}{len} \rfloor +1$，其中 $len$ 表示环长，$n$ 表示环的节点个数。 因为有个下取整还要拆开，所以这是一个三维偏序的问题。 考虑转化为两个二维偏序问题的和，$(\sum_{pre_j-pre_i+dep_k \le T,j \in [n+1,2 \times n]} \lfloor \frac{T-(pre_j-pre_i+dep_k)}{len} \rfloor +1) +(\sum_{j \in [i,n]} [pre_j-pre_i+dep_k \le T])$。 ## 4.8 ##### 「JOISC 2020 Day1」扫除 还没写过，先胡着。 先考虑第三个包的做法，显然每次修改肯定是一个区间，线段树维护就行。 第四包考虑被修改操作动过的点肯定是满足第三个包的性质的，于是只要一颗线段树维护没动过的点和一颗平衡树维护动过的点就行。 动态插点的话在在外面套一层分治就行了。 4.9 upd: 已经写好了，大概团子那个题就鸽了，懒得改成退火或者加上点贪心再去跑了，假装自己在寒假结束之前补完了。 ##### 「JOISC 2020 Day4」传奇团子师傅 wzp 说每次随 $3 \times 3$ 的矩阵，清空原先的匹配然后在随意配就行了。 但是我就是这样写的，只爬了 70pts，wzp 说他就这样爬出来了，可能这就是神仙吧。 ##### 「JOISC 2020 Day4」治疗计划 考虑 DP，令 $f_i$ 表示 $T_i$ 时刻 $[1,R_i]$ 的人都好了的最小花费。 转移顺序考虑每次取出没转移过的最小的 $f_i$ 转移就行。 一个点 $j$ 如果能被转移到，且之前没被转移过，这个点的值就是 $f_i+C_j$，因为每次取出的是最小的且 $i$ 转移到 $j$ 再加上的值都之和 $j$ 有关。 所以考虑线段树维护还没被转移的点，每次暴力找出能转移到且还转移到的点更新就行。 具体怎样才能从 $i$ 转移到 $j$ 直接分类讨论推不等式就行。 --- LOJ 上有的就填完辣！ ## 后记 说实话感觉 JOISC 大部分题都只有联赛难度。 大部分题还是做得动的，整体质量蛮高的，如果不想做 cf 和 at 了可以来做做。 另外关于这些题解的整理，鸽了。 嘛...至少寒假里还是做了一点题的...尽管真的做的不多... 
正在渲染内容...
点赞
4
收藏
0
