「解题报告」AtCoder Regular Contest 122

A

考虑 (dp[i]) 表示长度为 (i) 的加减号序列的方案数,其实是 (fib) 序列

那么每个标号统计有多少种方案是正号,负号,减掉计算贡献即可

感觉不太符合传统 (A) 的定位,然后就写了 (40min)

B

这个应该属于传统 (B) 的定位

考虑枚举 (2x),离散化权值之后做前缀和,那么把题目中的式子拆开分别统计即可

过这题比过上面一个快了不知道多少

C

直接 (1,4,3,4,3) 是一个 (fib) 序列,设到了 (fib[n]) 时停止了加数,那么 (fib[i]) 时整一个 (1/2) 就是添加一个 (fib[n-i])

实现非常复杂,看起来毫无头绪(最终代码却短得可怜,这合理吗?)

考虑设最终加入的序列是 (fib[1dots n]),那么如果加入的是 (n-i) 是奇数,那么就要把 (fib[i]) 加给 (y),即 (2) 操作,是偶数就是 (i) 操作

对于 (3/4) 操作也是类似的,也是 ( m{odd}) 对应 (4) 操作,貌似正确性都是显然的

D

不难发现可以按位考虑,如果有偶数个 (1),那么后手可以让 (0,0) 配对,(1,1) 配对

那么把 (0) 的放到一个集合里面,(1) 的放到另外一个集合里面,分治处理

而对于不满足 (0,1) 个数都是偶数的部分可以直接冲一个 (trie) 维护后手的异或最小值操作

(0) 扔到树上,(1) 在里面查询,对于查出来的结果最后取 (min) 即可

值得注意的是,实现的时候 vector<int> v0,v1; 直接在函数里面开,否则清空的时候就无了

E

考虑 ( m{GCD})( m{LCM}) 的本质是对所有的质因子的次方数取 (min/max)

那么如果一个 (a_i) 可以作为序列结尾需要满足 ( m{GCD(LCM_{j e i}(a_j),a_i)< a_i})

但是每个 (a_i) 都很大,(LCM) 会超过限制,所以转化一波:( m{LCM(GCD(a_j,a_i))}),这式子不难证明不超过 (a_i)

那么考虑枚举每一位填什么,如果满足就填,如果某个位置没有数字,就无解


看起来前几个很好做呀,赛时卡了波 ( m{C}) 没有仔细思考这个 ( m{D/E}) 有点亏

F

貌似上来结论就不太会证明,那么鸽掉了

原文地址:https://www.cnblogs.com/yspm/p/14879682.html