首页 > 其他分享 >JOISC 2017 题解

JOISC 2017 题解

时间:2024-02-12 11:11:55浏览次数:30  
标签:题解 可以 JOISC ge 端点 siz 区间 2017 我们

JOISC 2017

loj 上有几乎全部的题目,写了题意的就是 loj 上没有的。

D1T1

开场放大。

首先,对于一个点,它最后覆盖的一定是一个矩形,这就意味着如果我们知道了 \(u,d,l,r\) 操作各用了多少次,他们之间的顺序是不重要的,我们可以直接当做把一种操作做完再做剩下的操作,这样就可以做到 \(O(R^3C^3)\)。

考虑 \(R=1\) 的情况,对于 \(l,r\),需要满足可以覆盖左端点、右端点,两点之间的空隙,那么就有 \(l\ge a_1-1,r\ge C-a_n,l+r\ge a_{i+1}-a_i\),于是我们就可以求出 \(min(l+r)\)。

于是我们尝试只枚举 \(u,d\),然后计算最优的 \(l+r\)。枚举了 \(u,d\) 后,每个点当前覆盖了一条点。对于每一行,我们拿出已经被覆盖了的点,这就是 \(R=1\) 的情况,可以用上面的方法算每一行对 \(l,r\) 的限制,这样可以做到 \(O(R^3n)\)。注意到被覆盖的点集只会改变 \(O(n)\) 次,于是可以做到 \(O(R^2n^2)\)。

继续考虑优化。我们做了 \(u,d\) 操作后,把薯条和整个矩形都向下平移 \(u\) 的长度,这样对于所有 \(u+d\) 相等的情况,我们得到图案是一样的,只是原先的 \(R\times C\) 的矩形在上面滑动。同时不难发现,如果矩形的最下方覆盖了 \(a\) 的取值的某一取值的行,那么直接覆盖到该取值最下面的一行一定不劣。

我们发现,我们覆盖的行的 \(a\) 的取值显然是连续区间,可以用单调队列维护。具体地,我们把一种 \(a\) 的取值情况作为一个元素,从上往下考虑 \(a\) 取值相同的行的区间时,弹出过高的元素,统计下端点不覆盖到该区间的最靠下的矩形,然后把这个区间对应的元素加如单调队列。预处理出每种 \(a\) 取值对应的左右边界和两两之间的最大间隔,可以分别用单调队列维护。复杂度 \(O(Rn)\)。

进一步地,我们发现有用的 \(u+d\) 只有 \(O(n^2)\) 种,即 \({y_i-y_j,y_i-y_j+R}\),可以证明对于其他的长度,取集合内最小的大于它的数一定不劣。于是就可以做到 \(O(n^3)\)。

提交记录

D1T2

只会 KDT 优化建图的小丑。

好像建边可以优化。我们发现我们连边类似一个区间的形式。具体地,我们对于维护一个并查集和每个点所在段的右端点,遇到右端点就把左端点和左端点 +1 合并,然后把中间的一整段和当前点连边,再把整段拓展至当前最右侧。最后把跑一遍二分图染色求出连通块数就是答案。

提交记录

D1T3

显然可以先二分答案,关键是怎么判断是否合法。

有十分高妙的判定方法。首先,根据贪心,如果一个人会把另一个人点燃,那么这一个区间中的人都会被这个人点燃。因此,两个点 \((i,j)\) 可以在 T 秒内相遇当且仅当两点之间的距离大于 \(2tv(j-i)\),那么我们可以先把 \(a_i\) 减去 \(2tvi\),这样两点是否可达就可以直接判断。

判定分为两步。先从 \(k\) 开始往两边拓展,求出从 \(k\) 开始往左右各能拓展多远,然后从两端开始往中间拓展,最后如果一开始拓展的区间包含后面能拓展的区间就说明有解,否则就无解。本质就是从点燃区间 \([k,k]\) 开始拓展到其他区间,最后判断是否能够点燃区间 \([1,n]\)。

提交记录

D2T1

很厉害的题目。

把题意稍微转化一下,就是给你若干区间,你要可以选择一些区间反转,要求最小化被覆盖的次数最大的位置的覆盖次数。

第一步肯定是二分答案,关键是怎么判定合法。

首先有一个小观察,我们选择反转的区间的交集一定不为空,以为如果为空的话那么反转后不仅原来的区间被覆盖次数不变,其他位置的覆盖次数会增加,一定不优。

于是我们就可以选择任意一个在被反转区间的交集中的位置 \(p\),记每个位置的被覆盖次数是 \(a_i\),被反转区间覆盖次数是 \(t_i\),反转被覆盖的次数是 \(c_i\),那么对于 \(i\in [1,p)\), \(c_i=(a_i-t_i)+(t_p-t_i)\),通过 \(c_i\ge mid\) 可以推出 \(t_i\ge\left\lfloor\dfrac{a_i+t_p-mid}{2}\right\rfloor\),于是我们可以贪心地选择右端点最大的区间进行反转来满足 \(t_i\) 的限制,然后再判断是否合法。复杂度 \(O(n^2V\log n\log V)\)。

然后考虑能不能去掉枚举 \(t_p\)。

现在有结论: \(c_p\in\{\max(c_i),\max(c_i)-1\}\)。

证明:设反转区间的交是 \([l,r]\),我们取消一个左端点是 \(l\) 的反转区间和一个右端点是 \(r\) 的反转区间,那么 \(c_p\) 会增加 2,而不在翻转区间交中的 \(c_i\) 至少会减少 1,不断进行下去可以在答案不变的情况下做到 \(max(c_p-c_i)\le 1\)。

因为 \(c_p=a_p-t_p\in[mid-1,mid]\),我们需要枚举的 \(t_p\) 就只有 \(O(1)\) 个,于是可以做到 \(O(n^2\log n\log V)\)。

我们再考虑能不能去掉枚举 \(p\)。

同样有结论:\(a_p=\max(a_i)\)。

证明:对于不在反转区间交中的位置 \(i\),因为 \(t_i<t_p\),那么 \(c_i=a_i+t_p-2t_i>a_i-t_p\),通过上一个性质可以得到 \(c_i\le c_p+1\),于是有 \(a_p-t_p+1>a_i-t_p\),于是 \(a_p\ge a_i\)。

于是我们任取一个 \(a_p=\max(a_i)\) 的 \(p\) 来判断是否合法即可。复杂度 \(O(n\log n\log V)\)。

提交记录

D2T2

传送门

题意:Alice 有一个数 X,她可以向 Bob 传一个长度不超过 150 的 01 串,但是其中有 \(k\) 位会被破坏,变成 0,Bob 需要求出 X。

思路:随机化好题。

考虑把原序列每两个为一段,然后用三进制数来表示,这样最多可以传 \(3^{\frac{150-40}{2}}=5\times 10^{16}\) 的数。

考虑随机化。我们把两个人手上的序列随机打乱,这样就可以有更多的位置来用。但是还是过不去。

考虑怎么优化。假设一个段只有一个位置可以用,而且刚好可以表示出我们要表示的数,这样就可以利用上非法位置。加上优化后就可以通过了。

其实还可以再优化,就是把三进制下每一位再随机一次。

提交记录

D2T3

想到了大致方向。

首先可以暴力让每个点向两侧第一个不小于它的点连边,然后可以暴力跑 bfs。

考虑优化。对于每个点,我们肯定是尽可能地往远走,而每一次只有两种选择,那么可以倍增,于是可以求出每个点往远能走多远。对于询问,先从左端点往右跳,再从右端点往左跳即可。

提交记录

D3T1

推出了最终会选择一些区间的性质,感觉可以 \(O(n^2)\) DP,但是不太能优化。

考虑 \(D=T\) 的条件,就是说我们不会让 \([i,n]\cup [1,j]\) 的一段人下车,不用考虑环的情况。

设 \(f[i]\) 表示考虑到 \(i\) 的最优解。写出 DP 转移式:

  1. 不把 \(i\) 赶下车,那么留下来需要喝 \(\left\lfloor\dfrac{X}{T}\right\rfloor+[X\pmod T\ge D_i]\) 次水,转移是 \(f[i]\leftarrow f[i-1]+W(\left\lfloor\dfrac{X}{T}\right\rfloor+[X\bmod T\ge D_i])\);
  2. 把 \(i\) 赶下车,那么我们枚举赶下车的一段人 \((j,i]\),那么我们需要知道这些人最早可以在第几轮被赶下车,记为 \(mint_i\),那么有 \(mint_i=\min\limits_{D_i<(S_j\bmod T)<D_{i+1}}\left\lfloor\dfrac{S_j}{T}\right\rfloor\),转移就是 \(f[i]\leftarrow f[j]+preC[i]-preC[j]+W(i-j)mint_i\)。

考虑怎么优化后一种转移。我们发现这就是斜率优化的形式,不过 \(mint_i\) 不满足斜率单调,于是需要用二分栈来优化,可以做到 \(O(n\log n)\)。

移动次数是 \(4m+\left\lceil\log_3n\right\rceil2m=14m\) 次。

提交记录

D3T2

想到了求每个点能走到的范围和如何判断能不能走某条边,但是没想到直接记搜就是对的。

我们先求出每个点可以走的范围。我们从一个点开始,先往两边拓展,能走就继续搜下去,然后把自己能到的范围和自己能到的点的范围取并,可以证明复杂度是对的。

提交记录

D3T3

从部分分开始想到了大概。

从链的部分分入手。我们尝试去确定 dfn 序,那么我们就需要比较两个点的 dfn 序大小关系,即一个点能否在不经过另一个点的情况下到达 0,这个可以用一次询问求出,于是就可以直接排序。

然后是深度不超过 9 的树的部分分。

我们先确定每个点的深度。我们维护当前深度不超过 \(d\) 的点的集合,初始 \(d=0\),然后每次判断能否从 0 只经过集合内的点到达当前点,如果能到达就说明这个点的深度是 \(d+1\)。

接着考虑怎么确定每个点的父亲。我们把同一层的点重标号,然后对于下一层的点,可以二分找到这个点的父亲在重标号后是谁,那么就可以 \(O(\log n)\) 求出一个点的父亲。

接着是树的部分分。

我们还是尝试维护一个包含 0 的连通块。那么我们随便找一个点,然后二分找出这个点到根的路径上编号最小的点,然后从这个点再开始找点,直到这个点和一个连通块中的点直接相连,然后就可以求出这个点的父亲边。

最后是正解。

其实和树的部分很像,同样是维护联通块,然后可以求出一棵 dfs 树,那么就可以在树上二分找出这个点的所有返祖边,这样就可以确定所有的边。

提交记录

D4T1

又是暴搜复杂度正确的题。

我们记 \(f(x,y,d)\) 表示从 \((x,y)\) 沿着 \(d\) 方向出发最远可以走多远,我们可以用 ST 表维护在什么位置转弯。可以证明,总状态数是 \(O((H+W)\sqrt{Q})\) 的,可以通过。

提交记录

D4T2

传送门

题意:通信题。

Alice 有一棵树,最大深度不超过 18,Alice 可以给每个点赋一个 \([0,2^{28})\) 内的权值,Bob 每次会得到两点的权值,它需要判断两点是否是祖先后代关系。

思路:神题,完全不是人能想出来的。

首先肯定是想到传 dfn 和 siz,但是我们只有 28 位,要想办法来压缩。因为 dfn 相对不好压缩,我们考虑怎么压缩 siz。

我们尝试用一个序列去拟合 siz,即我们构造一个序列 \(f_0\sim f_{511}\),对于每个点 \(x\),找到第一个 \(f_i\ge siz_x\) 的 \(i\),加入 \(f_i-siz_x\) 个虚拟儿子,这样我们就可以把 siz 信息压缩到 9 位。

然后考虑怎么构造这个序列。我们需要满足 \(f_{511}\ge 2^19,\sum(f_i-siz_x)\le 2^19-n\)。

考虑构造等比数列,即 \(f_i=\left\lfloor(1+q)^i\right\rfloor\),其中 \(q\) 是很小的实数,这样每个的虚拟儿子个数不会超过 \(q\times siz_x\),而题目保证了 \(maxdep\le 19\),于是 \(\sum siz\le 19n\),因此 \(\sum(f_i-siz_x)\le 19qn\)。

不过等比数列前面部分增长速度慢,可以令 \(f_i=\max(1,qf_{i-1})+f_{i-1}\)。最后 \(q\) 取 \([0.022,0.045]\) 都可以。

提交记录

D4T3

计算几何+数据结构

因为所有颜色的点数和是 \(O(n)\) 的,这就有自然根号。

具体地,假设我们可以 \(O(C)\) 求出以一个点为起点,另一个颜色的点作为终点的射线经过线段的次数,或者一个点为中点,另一个颜色的点为起点的射线经过线段的次数,那么对于每次询问,我们可以在 \(O(min(|A|,|B|C))\) 的时间内计算答案。

如果 \(\min(|A|,|B|)<\sqrt{n}\),这样总共最多 \(O(Q\sqrt{n}C)\),如果 \(\min(|A|,|B|)>\sqrt{n}\),那么每种这样的颜色最多有 \(\sqrt{n}\) 次操作,总共最多 \(O(n\sqrt{n}C)\),于是总复杂度 \(O((n+Q)\sqrt{n}C)\)。

然后考虑怎么求答案。先考虑第一种情况,能做贡献的点就在这个点和线段的端点连的射线之间的部分。

考虑如何计算。

我们把这个点和线段端点连起来,设这个三角形的底角分别是 \(\theta1,\theta2\)。我们把能作贡献的区域沿线段划分成两个部分,其中一个部分的点和线段连成的三角形的夹角 \(\lambda1,\lambda2\) 满足 \(\theta1\ge\lambda1,\theta2\ge\lambda2\),令一个部分满足 \(\lambda1\le\pi-\theta1,\lambda2\le\pi-\theta2\),如果把 \(\theta1,\theta2\) 看成 \(x,y\) ,那么可以转成二维数点问题,可以用主席树解决。

第二种情况和第一种类似,也可以转成二维数点。

复杂度 \(O((n+Q)\sqrt{n}\log n)\)。

最后提一嘴,暴力是可过的。

提交记录

标签:题解,可以,JOISC,ge,端点,siz,区间,2017,我们
From: https://www.cnblogs.com/Xttttr/p/18013737

相关文章

  • JOISC 2016 题解
    JOISC2016loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1一开始把题目看错了,还写了棵线段树。把询问离线,倒着扫一遍,就变成了求最长不上升子序列,用树状数组维护即可。提交记录D1T2来自Kubic的神仙做法。考虑Filp一个位置和剩下所有位置,记录每个数作为答案......
  • JOISC 2015 题解
    JOISC2015loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1简单题。因为\(k\)很小,考虑依次确定最后第\(i\)位是什么。我们倒序考虑所有操作,维护最后第\(i\)位当前在第几位,就可以一直推下去。提交记录D1T2直接暴力复杂度就是\(O(k4^k)\)的,可以通过。提交......
  • JOISC 2014 题解
    JOISC2014loj上有几乎全部的题目,写了题意的就是loj上没有的。D1T1想到了最短路的做法,不过可能还需要整体二分,复杂度至少有2log。有复杂度更优秀的贪心做法。把边按时间倒序加边,然后从终点开始dfs来更新每个点可以的最晚出发时间,每条边走之后肯定就不会再让答案变优了,......
  • CF1628E Groceries in Meteor Town 题解
    题目链接点击打开链接题目解法感觉就是很多个套路组合出来,但我有些套路都不会/ll套路1看到从一点出发,到其他点的路径上的最大权,可以想到\(kruskal\)生成树(这提示我不仅是图可以用\(kruskal\)生成树,树也可以捏)我们建大根的\(kruskal\)生成树,那么将问题转化成了找一个......
  • 图上的游戏 题解
    「2020集训队论文」图上的游戏。算法\(1\):给定点集\(S\),\(|S|=n\),其中有\(m\)个好点。每次可以询问指定点集中是否存在好点,求所有好点。询问次数\(O(\min\{m\logn,n\})\)。对\(S\)分治,若当前不存在好点则退出。每个好点被询问\(\lceil\logn\rceil\)次,分治次......
  • CF1715E Long Way Home题解
    题解注意到\(k\)是一个很小的数,我们考虑分层图是否可做,这时航线有\(n^2\)条,我们可能会建出\((k+1)m+kn^2\)条边,空间会炸掉,然而单单从分层图的角度来优化,是困难的。对于\(m=0\)的情况。考虑\(\text{dp}\),定义\(dp_{i,j}\)表示乘坐不超过\(i\)次航班到达\(j\)的最......
  • CF1928E 题解
    \(\textbf{ProblemStatement}\)给定\(n,x,y,s\),构造长度为\(n\)的序列\(a\),满足:\(a_1=x\)。\(\foralli\in[2,n],a_i=a_{i-1}+y\)或者\(a_i=a_{i-1}\bmody\)。\(\sum\limits_{i=1}^na_i=s\)。给出构造或报告无解。\(\sumn,\sums\le......
  • 题解 AT_mujin_pc_2016_c【オレンジグラフ】
    本文中点的编号从\(0\)开始。显然,题目中要求橙色的边构成极大的二分图。枚举二分图左右部分别有哪些点。特别地,钦定\(0\)号点是左部点。将所有跨左右部的边染为橙色,如果所有点通过橙色的边连通,就得到了一组合法的解;如果不连通,显然可以将更多的边染成橙色,使得所有点连通。//......
  • 题解 ABC336G【16 Integers】
    萌萌BEST定理练习题。赛时几乎做出来了,但写挂了,现在在火车上没事干就给补了。考虑建图,图中共有\(8\)个节点,节点的编号是\((\mathbb{Z}/2\mathbb{Z})^3\)的每个元素。对于每个四元组\((i,j,k,l)\in(\mathbb{Z}/2\mathbb{Z})^4\),在图中连\(X_{i,j,k,l}\)条\((i,j,k)\to(j......
  • 洛谷 P1795 无穷的序列 题解
    题目传送门题目大意:给定整数\(a\),判断\(a\)是否属于数列\(1,2,4,7,11\cdots\)。多测。1.暴力枚举(90pts)不难发现,该数列除第一项外第\(n\)项比第\(n-1\)项多\(n-1\)。故暴力枚举\(n\),计算数列的每一项,判断是否与\(a\)相等,大于\(a\)就break。多测加记忆化,用mx......