Spark Exam 20240712

Conclusion

没有挂分，很好。

220/rnk3(out of 8)|期望220|理想310

其实很多时候过了不代表你就是最优的。

A. 于是我栽种玫瑰 (rose)

Statement

若对于无向图 \(G(V,E)\) ，其中 \(\forall x\in[1,n],ax+b\le n\) ，那么 \((x,ax+b)\in E\) 。求该图最大独立集大小。

\(1\le a,b,n\le 10^9\)

Solution

首先能够注意到该图是若干链构成的。一条链将贡献其长度除二上取整。

但是很难计算一条链的长度。注意到链长一共 \(\log n\) 个取值且单调不增。那么我们只需要：

二分找出一段一段的边界，这样就可以使用 \(\mathcal O(\log^3 n)\) 的复杂度解决了！（显然，这是很小的）

还能不能更给力一点？换一个视角，不从链的角度，考虑这个贡献等于从这个点开始的链长度为奇数的点的个数。这样我们就可以统计每种长度有几个点，那么怎么办呢，遇到不好直接求的情况，考虑先把它换成 弱一点的条件 ，比如求 有多少点长度大于等于 k ，递推算是好算的，就是一层一层展开，然后只要减一下就行了。

B. 只因为后面的一切已早早被确定下来 (destiny)

首先 枚举所有子集求和 ，这种事情可以参考一下 GF 的思路，是可以化成式子的即 \(\prod_{i=1}^{n-3}(\gcd(a_i,a_{i+1},a_{i+2},a_{i+3})+1)\)

求所有这种式子的和，可以考虑一个一个填数，用 dp 解决。

但是，我们关注的是 gcd 的情况，这个数是多少不重要，如何减少等价的状态数量？就要从因子上面下手，所以我们选择最小的能够转移的： \(a_i,\gcd(a_i,a_{i+1}),\gcd(a_i,a_{i+1},a_{i+2})\) ，这时，我们发现，几个状态变量之间互相限制，所以状态数只有 \(1500\)

C. Deliver me (deliverme)

这个题主要是告诉我们，调用查询或修改哪个调用数据结构次数多，那么选用的数据结构就应该倾向那个明显调用的多的操作。不要一味选用渐进最优的数据结构。

D. 分道扬镳 (farewell)

还没改 qwq