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 转移式:
- 不把 \(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])\);
- 把 \(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