Contest Info

date 2017.08.22 12:00-17:00

practice link

Solutions

A. Big binary tree

题目大意：你有一棵 \(n\leq 10^{8}\) 个点的完全二叉树，按堆的规则标号。初始点 \(i\) 的权值为 \(i\)，我们定义一条路径的权值为这条路径上所有的点权之和。接下来 \(m\leq 10^5\) 个操作，分为两种：

• 改变点 \(u\) 的权值为 \(x\)
• 询问经过 \(u\) 的所有路径中的最大价值

题解：如果是一棵满的二叉树，那么每个点往下的的一条链的最大的点权和，一定是在右链上取得。那么对于完全二叉树，只有点 \(n\) 往上的祖先链可能不满足上述性质，那么我们只需要从 \(n\) 开始，往上更新 dp 值即可。

对于之后的每次修改之后的点权，也不满足上述性质，我们用同样的方法，从被修改点往上更新 dp 值。对于每次询问，答案只有两种情况：1. 该点作为路径端点的 lca，此时答案为左右儿子的 dp 值之和加上该点权值。2. 否则，我们沿着该点往上爬，枚举祖先链中的每个点为路径 lca 即可。单次操作/询问的复杂度 \(\mathcal{O}(\log n)\)。

B. Ch’s gift

题目大意：给定一棵 \(n\) 个点的点上带权的树，和 \(m\) 次询问。每次询问给定 \(s,t,a,b\)，求从点 \(s\) 到点 \(t\) 的路径上，点权在区间 \([a,b]\) 中的点权之和。

题解：把询问的区间 \([a,b]\) 离线到点上（减去 \(a-1\) 的答案，加上 \(b\) 的答案），路径拆成 \(s,t\) 到根的路径减去两倍 \(\text{lca}(s,t)\) 到根的路径。然后我们按照权值对事件排序，权值相同时插入操作优先于更新答案的事件。插入时，我们只需要用树状数组维护 dfs 的差分，就可以做到区间修改，然后单点查询每个点到根的权值之和了。

也可以按照题解的做法，在 dfs 这棵树的时候，进入一个点将其插入 treap 中，出来的时候删除，也可以维护到根的权值之和。

C. CSGO

题目大意：给你平面上若干个点和若干条线段，所有线段严格不相交，所有点都不在任何一条线段上。现在给你若干个询问，每次给你一个点，问有多少个点和这个询问点的连线段与所有线段严格不相交。

题解：对每个询问单独考虑。以询问点为极点，平行于 \(x\) 轴建立极坐标系。由于所有线段严格不相交，那么在一条扫描线上，任意两条线段的极径的相对大小是不会发生变化的。所以我们可以用一条扫描线（以极点为端点的射线）从 \(0\) 扫到 \(2\pi\) ，扫描时用 set 维护极径从小到大的线段，并同时统计答案即可。

这道题似乎有些吃精度，我和题解的代码都必须要开到 1e-10 以下才能通过。当然如果用叉乘代替 atan2 来判断极角的相对大小可能会提升一些精度，但是实现起来就相对麻烦一些。还有一个问题是我一直搞不清楚 set 的实现机制，在比较函数的参数一直变化的情况下（例如本题的极角）用起来非常迷，可能还是要再去学习一个。

D. Dying Light

题目大意：\(n\) 个镜子组成了一个凸包，一个人在凸包的内部发射一束光，光照射到镜子上时会被反射并且产生一定的能量损失，如果光照射到两面镜子的交点处则会立刻被吸收。问光能接触几次镜子。

题解：按题意模拟（抄模板）即可。比赛的时候弊队模板炸了，而且一些判断的细节写得不够好，比如应该尽可能在判断之前少做计算。

E. FFF at Valentine

题目大意：给定一个简单有向图，随机选择两个不同的点 \(u,v\)，问你是否一定存在从 \(u\to v\) 的路径，或者存在从 \(v\to u\) 的路径。

题解：其实等价于判断整个图是否是一个链（两两点至少有单向路径可达的点集）。我们先对这个图强联通分量缩点，DAG 是否为一个链等价于是否存在路径数为 \(1\) 的路径覆盖，我们求最长路就行了。或者判断拓扑序是否唯一也是可以的。

比赛的时候，我是在正反图上各做了一次压位 dp，求出了每个点能到达的点集，和到达它的点集。

F. Senior Pan

题目大意：给定一个有向图，和 \(k\) 个关键点，求所有的关键点对中，距离最小的点对的距离。

题解：我们枚举关键点对的编号的二进制位，将关键点分为两类。然后分别以一类为起点和终点，各做一次 dijkstra，那么所有的点对都会被包含进去。（ps：用 set 写的 dijkstra 会被卡，用 priority_queue 就可以过，不知道为什么）

G. Missile Interception

题目大意：有 \(n\) 枚敌方的导弹，已知它们的初始位置、发射方向和速度。你可以选一个固定点，沿任意方向发射任意枚速度为 \(V\) 的拦截导弹，并且必须在敌方发射导弹之后才能发射，求最晚什么时候将敌人的全部导弹拦截。

题解：显然答案满足单调性。二分一个时间 \(t\) 以后，我们就知道那个时候敌方每枚导弹的位置，所以对于每枚导弹，满足要求的起点就是以那个位置为圆心，以 \(Vt\) 为半径的圆（包括圆内），然后只要判断 \(n\) 个圆有没有交即可。

H. Numbers

签到题

I. Senior PanⅡ

题目大意：求 \([L,R]\) 中除了 \(1\) 以外的最小因子为 \(k\) 的数之和。

题解：首先注意到 \(k\) 不是质数时答案为 \(0\) 。设 \(S(n,k)\) 表示 \([1,n]\) 中用筛法处理完 \(k\) 之后剩余的数之和。则 \([1,R]\) 的答案为 \(S(\lfloor\frac{R}{k}\rfloor, k-1)\) 减去 \([1,\min(\lfloor\frac{R}{k}\rfloor, k-1)]\) 中所有质数的和。注意到 \(k^{2}>R\) 时答案要么是 \(k\) 要么是 \(0\) ，可以特殊处理，所以我们只要处理 \(k^{2}\le R\) 的情况即可，第二维最多为 \(\sqrt{10^{11}}\) 。我们使用（记忆化）搜索来解决这个问题，状态转移方程为：

\[ S(i,j)= \left\{ \begin{aligned} &\frac{i(i+1)}{2},&j=1\\ &S(i,j-1),&j \text{ is not a prime}\\ &S(i,j-1),&i<j^{2}\\ &S(i,j-1)-j\cdot\left(S(\lfloor\frac{i}{j}\rfloor,j-1)-S(j-1,j-1)\right),&\text{others}\\ \end{aligned} \right. \]

这道题不加记忆化也能通过，不过加了记忆化以后会快一倍多。

J. Two strings

题目大意：给出两个串 \(S_1,S_2\)，串 \(S_1\) 只由大小写字母组成。串 \(S_2\) 只由大小写字母、 . 以及 * 组成。问你两个串是否完全匹配。其中 . 可以单个任何字符，* 表示其前一个字母出现若干次（可以 \(0\) 次）。

题解：我们令 \(dp[i][j]\) 表示 \(S_1[1...i]\) 和 \(S_2[1...j]\) 是否能完全匹配。转移方程为：

• 若 \(S_2[j] = `.`\)，那么 \(dp[i][j] = dp[i][j] \lor dp[i-1][j-1]\)
• 若 \(S_2[j]\) 为大小写字母，那么 \(dp[i][j]=dp[i][j] \lor \Big(dp[i-1][j-1]\land \big[S_1[i]=S_2[j]\big]\Big)\)
• 若 \(S_2[j]=`*`\)，我们还要分
  • 若 \(S_2[j-1]=`.`\)，那么 \(\displaystyle dp[i][j]=dp[i][j]\lor \bigvee_{0\leq k}\Big(dp[i-k][j-2]\land \big[\forall p(p\in [i-k+1,i) \to [S_1[p]=S_1[i]])\big]\Big)\)
  • 若 \(S_2[j-1]\) 为大小写字母，那么 \(\displaystyle dp[i][j]=dp[i][j]\lor \bigvee_{0\leq k}\Big(dp[i-k][j-2]\land \big[\forall p(p\in [i-k+1,i] \to [S_1[p]=S_2[j-1]])\big]\Big)\)

朴素的转移是 \(\mathcal{O}(n^3)\) ，我们注意到 \(\displaystyle \bigvee_{0\leq k}\Big(dp[i-k][j-2]\land \big[\forall p(p\in [i-k+1,i) \to [S_1[p]=S_1[i]])\big]\Big)\) 这个条件可以用滑窗优化，所以最后复杂度为 \(\mathcal{O}(n^2)\)。

Replay and Summary

Replay

先吐槽一下这场的题面真是各种错误啊，数据真的各种弱啊。

Z 先发现 H 是道水题，上来切了。然后 W 觉得 E 也很水啊，写完 wa 了一发之后冷静了一下，Z 造了组数据然后 W 改了改算法也 a 了。D 跟 W 讨论了一下 B，觉得随便怎么树上套个数据结构就可以做，但是 D 想用树剖，W 觉得没必要，而且有点害怕 64MB 的空间，所以直接用树状数组维护了一下每个点到根的信息。D 写完 1a。

Z 发现 I 是一个 old 题，以前做过，然后就开始写。写完之后果然 wa 了。D 也大概想到了 F 的做法，跟 W 讨论了一下都感觉没什么问题，然后写了。也 wa 掉了。

D 发现自己的做法不能处理一些情况，就开始改。而 Z 有点心态爆炸，不停改改改，贡献了很多 -1。D 在反图上又跑了一次之后过掉了 F。

W 终于开始决定看很多队伍都通过的 J 题，感觉肯定有很多队伍用正则通过了本题。但是 W 不会用正则库啊，现查感觉不符合武德啊。于是 W 决定自己想。就想出了一个 O(n^3) 的 dp。然后发现似乎可以滑窗优化转移，就 O(n^2) 了！ 在艰难地通过了 D 造的几组超强数据后，J 题 1a了。

然后 W 实在看不下去 Z 的胡乱提交，来帮 Z 读代码，对每句话发出灵魂拷问“这句话是这样吗？真的是这样吗？”。在 W 的灵魂拷问之下，Z 发现了一个错误，改掉之后过了。

剩下三道计算几何和一道奇怪题。Z 开始搞 D，然后 W 和 D 讨论 A。讨论了一会儿，D 就开始写 A 了。写完 wa 掉了一次，两人又讨论发现了一个特例，判了之后也过掉了。剩下的时间 Z 给 D 贡献了 -10。最后 10min，发现 G 是个 sb 题，然而没时间写了。

计算几何还是弊队弱项，得加强练习。主要的问题在于：1.模板的精度处理不当 2.实现算法的细节损失太多精度。