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代码

注1：我在育才信奥老师指点之下AC的（ 注2：这道题思路比较两极分化，我写的是DFS代码，如果想看打表去翻翻别的 这是本蒟蒻第一次写难题题解哦，写的不好请见谅~ 正式题解看下面 1.题意分析 题目很简单，就不分析了（ 2.本题大坑 有人看到"利用 nnn 根火柴棒”这句话就马上开始了程序编写，将 nnn 拆分，但是如果这样想，就掉坑里了，盲目拆分一定一定会TLE，这样解不可行。 3.正解思路 我们将 nnn 拆分成两个数之和，每个数的循环终点定大一些（例如1000或者900），用dfs计算摆出这个数需要几根火柴棒之后相加即可。 附上代码： 看到这里了，点个赞吧~