12.[NOIP2008 提高组] 火柴棒等式 难度：普及+/提高 来源：-- AC代码（C++）： 没有注释，自行学习。 by：ACGO 你的点赞和关注就是我更新题解的最大动力！ ------------------------------点个赞吧 ↓ ！----------------------------

**你的点赞和关注就是我更新题解的最大动力！ ------------------------------点个赞吧 ↓ ！----------------------------

题解： 因为nnn<=242424，我们马上看出来，这个等式能模拟出的最大的数字绝对不会大于100010001000，所以我们考虑表示出111-100010001000的所有数字，基于这个开始枚举，最后得出答案。 是的，有些事情就是这么巧妙，什么打表啊，枚举啊，模拟啊，都是智慧的结晶，请大家不要嗤之以鼻。 所以我们开始模拟。 先处理出的a[]a[]a[]数组保存的是当数组下标为iii的时候，需要几根火柴模拟出来。为什么aaa数组要开200020002000呢？因为后来判断的时候要a[i+j]a[i+j]a[i+j]，而iii和jjj都是100010001000规模的，不开200020002000会RE。 然后我们打表处理出mmm数组，表示拼出数字，注意是数字iii的时候需要几根火柴，然后就可以按位表示了。应该很简单。 最后判断，不用多说了。 注意要加444。 所以就AC了: 欢迎加入团队

看数据范围，很小，手算或者程序打表就可以过。 代码：

话不多说，请看题解~

打表即可

题意分析 用 nnn 根火柴棒拼等式 A+B=CA+B=CA+B=C，求有多少种拼法。 解题思路 首先看到数据范围，第一个想到的就是打表枚举，那枚举什么呢？肯定是 ABCABCABC 了。能确定的是需要 444 根火柴棒拼符号，因此我们有至多 202020 根火柴棒来拼 ABCABCABC。一看好像很多，最少花费的数字是1，最高能到 101010 位数！事实并非如此，以下是上界推导，也是本题难点： 设 A=1A=1A=1（最小火柴 222 根），s(N)s(N)s(N) 为拼 NNN 所需要的火柴数 推出 a+b+c≤20a+b+c ≤ 20a+b+c≤20，B=C−1B=C-1B=C−1，所以 s(C)+s(C−1)≤18s(C)+s(C-1) ≤ 18s(C)+s(C−1)≤18 假设一个枚举上界 C≤2000C≤2000C≤2000，对 C≥2000C≥2000C≥2000 上述等式不成立，所以可以证明上界 C≤2000C≤2000C≤2000 可用 当 AAA 不是 111 时，所需火柴更多，不等式更严 所以在 n≤24n≤24n≤24 时，CCC 最大不超过 200020002000 当然，也可以根据数据范围猜测数较小 接下来是就是实现，既然已经知道了数据范围，就可以根据范围来枚举。若枚举 ABCABCABC 并在枚举时计算火柴棒花费则可能会超时，可以先把所有 ABCABCABC 的可能值，也就是 200020002000 以下的所有数字需要的火柴棒数量计算出来，可以节省大量时间。枚举 aaa 和 bbb 各自最多约 150015001500 种可能，大概 2e62e62e6 的计算量，不会超时 AC代码