Sicily 1498 Elementary Additions 我的解法

summary

:

题意

重新定义了数的表示，

• 0 => {}
• 1 => {{}}
• 2 => {{},{{}}}
• 3 => {{},{{}},{{},{{}}}}

给出右边的集合形式的表示，计算两个数相加的结果，结果也以集合的形式表示。

分析

找规律，0是空集，1是集合里面包含了整个0的集合的表示，接着2，左边是1的集合里面 的东西，右边是1整个集合的表示，中间用逗号分开，对于3，左边是2的集合里面的东西， 右边是2整个集合的表示，中间用逗号分开。

利用上面的规律，给定任意的整数，就可以通过递归来输出集合的形式了。

怎么根据集合的形式得到整数呢？

看逗号！0和1是没有逗号的，它们可以通过比较字符串区分，2是1个逗号，3是 2 * 1 + 1 = 3个逗号，4是3 * 2 + 1 = 7个逗号，于是n是 2 * (n - 1的逗号数) + 1个逗号。这样就可以得到任意集合的形式对应的整数了。

我的代码

这里我用到了std::string的一些函数，<algorithm>的一些函数，还有std::map， 虽然比较无耻，但是毕竟是代码重用。

::: {.code-include lexer="cpp"} ../../../sicily/1498/1498.cpp :::