A.好数（number）

很签，打完之后“不是这题我能做一个小时？？” 。

对于每个数，都把它与前面的所有数的加和求一遍存进桶里，再遇到一个新数 \(a_i\) 时，枚举前面的所有 \(a_j，j\in [1,i-1]\)，找桶里是否存在一个数 \(x\) 使得 \(x=a_i-a_j\) 即可.

因为这些数中有负数，所以我们可能会想到用 map 作为桶存加和，但这样（由于它相当购使的实现）相当于多挂了一个 \(\log\)，本地跑大样例准确时间要 3 秒多， 。

发现数据范围是 \(-10^5\le a_i\le 10^5\)，那么我们把所有数加上 \(10^5\)，这样就不会存在负数情况了，直接用数组存就好了。整体复杂度 \(O(n^2)\) 。

B. SOS字符串（sos）

dp 。

记 \(f_{i,0/1/2,j}\) 维护答案，第二维从 0、1、2 分别表示：第 i 位上是 SOS 中的第一个 S、与前一位可组成 SO、或者其他.

第三维表示有 j 个 SOS 了，若数量大于 3，j 也为 3.

• 当前位 \(i\) 位为第一个 S 时，可由前一位为 S，以及前一位状态为 2 转移而来：

• 当前位可与前一位组成 SO 时，那么上一位为 S：

• 当前位为其它状态时
  • 上一位可放 S，此时当前位不为 O 或者 S，否则就属于上面两种情况；
  • 上一位可为其他，此时当前位不为 S；
  • 上一位为 SO，当前位不为 S；

• j > 0 时，即可以有 SOS 了，那么当前位状态为 2 时，可由 SO + S 转移：

• j = 3 时，j 的大小不再变化，写成这样：

C. 集训营的气球（balloon）

退背包 。

发现其实就是 1 到 n 个人分别选不选一血背包，要么选要么不选，因为 c 够小，用总方案数减去选一血背包的人数小于 c 的方案数即可，这样求选一血的人数小于 c 的方案数就成了 01 背包问题了.

由于每次修改，一次背包是 \(O(nc)\) 的，如果每次修改都做一次背包的话，整体是 \(O(n^2c)\)，所以考虑退背包.

每次修改就相当于是把修改的那个人原有的贡献退出去，再进来新的贡献.

D.连通子树与树的重心（tree）

Qyun 的好吃博客 。

最后此篇关于「模拟赛」多校A层联训5的文章就讲到这里了,如果你想了解更多关于「模拟赛」多校A层联训5的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。