2022.1.24 WC2022 skip2004 讲课题目

UOJ #665 【IOI2021】registers

奇奇怪怪 pia pia sila sila 题目,不知道补得有啥意义所以干脆不补(或者说等以后有时间再慢慢啃这种题目吧

UOJ #664 【IOI2021】dungeons

考虑一个关键性质:打死一个怪以后,英雄的体力值会增长怪物的血量,也就是说,如果英雄打死了一个和自己势均力敌的怪物,那么其血量会成倍增长。

发现了这个性质之后,我们考虑对权值分层,即设第 \(i\) 层表示血量区间 \([2^i,2^{i+1})\),假设现在英雄血量位于第 \(i\) 层表示的区间,那显然血量 \(<2^i\) 的怪都可以被英雄秒掉,而对于血量 \(\ge 2^i\) 的怪,我们不知道其是否能被英雄打败,因此我们考虑这样的策略:先假设它们都不能被英雄打败,这样每次英雄经过血量 \(<2^i\) 的房间就会获得 \(s_j\) 的血量并到达房间 \(w_i\),经过血量 \(\ge 2^i\) 的房间就会获得 \(p_j\) 的血量并到达房间 \(l_i\)。我们考虑对此做倍增,即设:

  • \(to_{i,j,k}\)​ 表示在第 \(i\)​ 层,从 \(j\)​ 开始,每经过一个血量 \(<2^i\)​ 的怪都到达 \(w_i\)​,经过一个 \(\ge 2^i\)​ 的怪都到达 \(l_i\)​,这样走 \(2^k\)​ 步后会到达哪个房间。
  • \(sum_{i,j,k}\)​ 表示在第 \(i\)​ 层,从 \(j\)​ 开始,每经过一个血量 \(<2^i\)​ 的怪都积累 \(s_i\)​ 的血量,经过一个 \(\ge 2^i\)​ 的怪都积累 \(p_i\)​ 的血量,这样走 \(2^k\)​ 步后血量会增加多少。
  • \(mx_{i,j,k}\) 表示在第 \(i\) 层,从 \(j\) 开始,初始血量至多为多少,才能保证在接下来 \(2^k\) 步中打不败任何一个 \(\ge 2^i\) 的怪。

上面三个数组都可以在预处理时候求出。这样每次查询时,每进入一层,就倍增找到后面第一个可以打败的血量 \(\ge 2^i\) 的怪,根据上面的推论,打掉这个怪之后肯定会进入下一层,因此总复杂度 \((n+q)\log^2n\),由于 \(n\) 较大,直接这样做会 MLE,不过注意到 \(q\) 很小,因此考虑 \(B\) 进制倍增,这样复杂度变为 \(n\log_Bn\log_2n+qB\log_Bn\log n\),取 \(B=8\) 可以通过。

UOJ #671 【UNR #5】诡异操作

首先考虑一个比较朴素的暴力:操作 1 显然可以 seg-beats,也就是按照区间 sqrt 区间求和的套路,每次递归到一个区间时如果区间中所有元素都为 \(0\) 则 return。而对于 \(2\) 操作,我们在线段树上每个节点维护一个长度为 \(128\) 的数组 \(b_0,b_1,\cdots,b_{127}\),其中 \(b_i\) 表示这个区间中有多少个数在这一位上为 \(1\),然后修改就直接将对应位上是 \(0\) 的位置改为 \(0\)​ 即可。算下复杂度,每个点最多被 and 的次数为 \(\log v\),而每次 and 最多对应 \(\log v\) 次除法,而 \(2\) 操作复杂度显然是 \(\log n\log v\),因此总复杂度 \(n\log^2v+q\log n\log v\),一脸过不去的样子。

考虑优化,我们注意到如果一个节点比较靠近叶子,那么这个长度为 \(128\) 的数组中,肯定几乎所有数最高的那些位都是 \(0\),因此我们考虑将数组置换一下,即对于线段树上长度为 \(L\) 的区间,改维护一个长度 \(L\) 的数组,其中第 \(i\) 位表示等于 \(\sum\limits_{j=0}^{127}b_j\text{ 的第 }i\text{ 位}·2^j\),合并就类别带进位的加法。这样我们 \(2\) 操作复杂度变为 \(\log^2n\),而 \(1\) 操作向下搜索的复杂度可以用 \(\log v·\sum\limits\log len\) 来计算,后面的 \(\sum\) 的时间复杂度递推式为 \(T(n)=T(n/2)+\log n\),根据主定理可知 \(T(n)=\mathcal O(n)\),于是总复杂度就变为 \(n\log v+q\log^2n\),可以通过。

需要卡常。

UOJ #604 【UER #9】赶路

好久之前做的了,讲到这道题时我甚至连题意都忘了

大体思路就是分治,每次分治一个集合 \(S\) 以及两个点 \(x,y\),递归地解决从 \(x\) 出发经过 \(S\) 中点到达 \(y\) 的位置,分治中途就取出最终间的点 \(z\),然后对 \(S\) 中其他点 \(p\),以直线 \(xz\) 为分界线,如果 \(xp\) 和 \(xy\) 在同一侧就放到右侧,否则放到左侧,容易证明其正确性。

CF1208H Red Blue Tree

又毒瘤又 nb 的 DS,今天大概是没时间了,以后有时间一定优先补这道题并单独写题解(

CF1083C Max Mex

又是一道很久之前过的题目,大概就线段树上 \([l,r]\)​ 的区间维护包含 \(l\sim r\)​ 中所有的点的最短路径,然后线段树上二分,找到最后一个满足存在一条路径覆盖了 \(0\sim i\) 中所有点的 \(i\),合并可以通过 ST 表求 LCA 做到 \(\mathcal O(1)\),时间复杂度 \(n\log n\)​。

CF566C Logistical Questions

https://www.cnblogs.com/ET2006/p/Codeforces-566C.html

数据结构 1

不知道原题,鸽了(

数据结构 2

不知道原题 \(\times 2\)​,鸽了(

Codeforces Gym 102979K Knowledge Is...

首先这种题好像没法直接建出来图来跑什么东西解决,因此只能从特殊连边方式入手采取贪心的方式解决问题。我们将所有区间按左端点从小到大排序,那么不难发现当我们尝试匹配一个区间 \([l_i,r_i]\) 时,如果存在一个候选集合中的区间能与之匹配,我们肯定会贪心地选择能匹配的区间中右端点 \(<l_i\) 且最小的,这个显然可以 set 维护。

直接按照上面的方式写大概可以获得 WA on test 6 的好成绩,考虑如下 hack:

4
1 2
3 5
4 7
6 8

原因在于你选择将 \([1,2]\) 与 \([3,5]\) 匹配后就将这个区间固定下来了,实际上 \([4,7]\) 也能匹配 \([1,2]\),但其不能与 \([6,8]\) 匹配,而 \([3,5]\) 匹配,也就是说实际上 \([4,7]\) 与 \([1,2]\)​ 匹配更加能够尽可能用完右端点大的区间,因此我们考虑加个反悔的元素:我们将所有已经匹配的区间对中较右的再扔进一个 set,如果一个区间 \([l_i,r_i]\) 不能匹配候选集合中的区间,我们就考虑反悔集合中右端点最小的区间 \([L,R]\),如果 \(R<r_i\) 我们就用 \([l_i,r_i]\) 匹配 \([L,R]\) 匹配的区间然后将 \([L,R]\) 加入候选集合。

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

Codeforces Gym 102586L Yosupo's Algorithm

首先考虑最暴力的做法:枚举可以匹配的点对,假设第 \(i\) 个点对的两个点的横坐标分别为 \(a_i,b_i\),那么我们将 \((a_i,b_i)\) 看作二维平面上的一个点,问题就转化为二维数点,离线 + 树状数组解决。

考虑优化,注意到我们将所有 \(\mathcal O(n^2)\)​ 个点对都存下来有点浪费,因此考虑删除一些无用点对。我们考虑将所有点按 \(y\) 坐标排序后分治,分治到区间 \([l,r]\) 时,设 \(mid=\dfrac{l+r}{2}\),那么有这样一个性质:对于 \([l,mid]\) 中的红点 \(i\) 和 \([mid+1,r]\) 中的蓝点 \(j\),点对 \((i,j)\) 是有用的当且仅当 \(i\) 是 \([l,mid]\) 中红点权值最大的,或者 \(j\) 是 \([mid+1,r]\) 中蓝点权值最大的。

证明异常容易的,考虑反证法,假设对于 \([l,mid]\) 中的红点 \(i\) 和 \([mid+1,r]\) 中的蓝点 \(j\),点对 \((i,j)\) 是 \([L,R]\) 询问的最优答案,但 \(i\) 不是 \([l,mid]\) 中红点权值最大的,且 \(j\) 不是 \([mid+1,r]\) 中蓝点权值最大的,那么我们考虑 \(i,j\) 在不在 \([L,R]\) 中的状态,显然它们要么同时在 \([L,R]\) 中要么同时不在,考虑 \([l,mid]\) 中权值最大的红点 \(X\) 以及 \([mid+1,r]\) 中权值最大的蓝点 \(Y\),如果 \(X,Y\) 在不在 \([L,R]\) 中的状态至少一者与 \(i(j)\) 相同,那么我们把其中一个点换成这个点答案肯定最大,否则 \(X,Y\) 关于 \([L,R]\) 肯定相同,它们肯定会对答案产生更大的贡献。

这样点对数就降到了 \(n\log n\),时间复杂度 \(n\log^2n+q\log n\)。

P6580 [Ynoi2019] 美好的每一天~ 不连续的存在

没听懂,先鸽着(

上一篇:在排序数组中查找元素的第一个和最后一个位置(24)


下一篇:浅谈MVVM架构