题解：P12132 [蓝桥杯 2025 省 B] 可分解的正整数

AlmightyA · 2025-04-13 20:45:51 · 题解

题目传送门

不要被题面吓到！！！

蒟蒻的第一篇题解，求管理员大大审核通过!

我们可以发现，数对{ -1，0，1 }及其他的和为0。
这是因为众所周知，-x + x = 0， 几个0加起来都是0。
那么我们只需将A_i判断是否是1即可，因为任何非1的正整数都可以通过0加上a_i来得出（1只能{0, 1}，长度不够)，绝对有序，不需要什么无脑的暴力枚举。
那么，有了这样的伪代码：

arraymaxsize = 1e5 + 5->const int
a[arraymaxsize]->int array
fun main()->int:
  ans, n->int
  ans = 0
  in:n
  ans = n
  for i = 1 i <= n i++:
    in:a[i]
    if a[i] == 1:
      ans++
  out:ans
  return 0

代码实在简单，不写了，看提交记录，目前已加入代码公开计划。