3月27日训练赛(广工新生赛)(未完待续)

未拿到现场赛时代码,在这里按AC时刻做思路复盘,要获取正解请参看官方题解:

网络同步赛题面 官方题解

总结在最末。

G 分割(一血)

数学题

读完题,马上想到把 {x}{y} 分别排成升序,然后列式子:
Answer=\sum_{1\leq i<j\leq m}(y_j-y_i)*\sum_{1\leq k<l\leq n}(x_l-x_k)
如何计算 \sum_{1\leq k<l\leq m}(x_l-x_k)

固定 x_i ,考虑 x_i 构成的项:

  • 共有 i-1 项形如 (x_i-x_j)1\leq j<i
  • 共有 n-i 项形如 (x_j-x_i)i<j\leq n

因此 x_i 的系数为 (i-1)-(n-i)=2i-1-n

\therefore \sum_{1\leq k<l\leq m}(x_l-x_k)=\sum_{i=1}^n{(2i-1-n)*x_i} ,此式可以 O(n) 计算。

y 的部分同理。总复杂度 O(n\ log \ n)

I 母牛哥与子序列

数学题

先考虑包含空列的所有子序列,设总和为 S

\forall a_i ,可以把所有子序列分成包含 a_i 和不包含的两类,所以 S 一定有因式 (1+a_i)

所以,由对称性, S=C*\prod_{i=1}^n(1+a_i)C 为待定常数,最终答案应为 S-1

检验样例发现 C=1 。复杂度 O(n)

D 动态序列(一血)

数学题

  • 要支持首尾插入、随机访问,使用deque 存原数组。
  • 维护加法和乘法,和线段树模板2这道题一样,不修改原数组,而是维护两个标记 uv ,表示当前已经进行的运算为 原来的值原来的值原来的值原来的值\times u+v ,可以 O(1) 完成询问1、2、5。
  • 插入新数 x 时,只需向deque中插入 x_0 ,使其满足 x_0u+v=x ,即 x_0=(x-v)u^{-1} ,由数据范围知 u 的逆元的确始终存在。插入需要计算逆元,询问4、5的复杂度为 O(log|B|)B 为操作数值域。

接下来除了H题都是乱搞AC的。。。

C 涂墙

猜结论题

讲讲我猜出来的过程。

读完题并没发现啥性质,又想到这场是新生赛,当时过的人还挺多,所以应该不难出,果断速了发搜索,测了n=1e6的极限情况可以秒出YES,然而交上去T了。难道要打表?改了打表代码开始跑,过了好久没跑出来,我就更纳闷了,100W都可以秒出,这咋会T?

这时我开始猜测,搜索运行时间和数值大小没啥关系,应该是和解的结构相关:当某个数无解,要跑完整个搜索树才能被判定无解,这也是搜索算法的时间瓶颈;而有解时,应该对解的构造限制很松,在搜索树上随便跑跑就可以出解,比如100W的秒出YES;于是我又猜测,对于一个一般的数,构造解应该是一个容易的问题,即有解的数是普遍存在的,无解的数是稀疏的。那就考虑观察一下无解的数的规律。果断把还在跑的打表程序关了,然后观察已经打出来的表。

然后发现无解的情况确实越来越稀疏,而且从三十几开始,到表的结束(大概一百多)都是有解的,所以大胆猜测:之后的数都是有解。特判了前面的数,一交,居然A了!!!

B 找山坡

数据结构

  • $RMQ$ 预处理静态区间最小值。
  • 对答案贡献的应该是一些区间 [L,R] ,考虑从小到大枚举左端点 L ,初始 L=1
  • 对于每个下标 L ,可以二分出最大的下标 R_R ,满足下标区间 [L,R_R] 的最小值为 a[L]
  • 然后在 [L,R_R] 中计算最大的下标 R ,满足 a[L]=a[R]
    • 如果 a[L]=a[R_R] ,则 R=R_R
    • 否则,可以二分出最大的 R<R_R ,满足下标区间 [R+1,R_R] 的最小值比 a[L] 大;
  • 更新答案。
  • L=R+1 ,开始下一轮循环。

复杂度 O(n\ log\ n)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注