P4157 [SCOI2006]整数划分

P4157 [SCOI2006]整数划分

感性地感受一下，如果一个数分得很细，就是指数级别的，会特别大。手玩一下，可以发现尽可能分到 $3$ 。

查看代码

#include <cstdio>
#include <vector>
using namespace std;
int n;
vector<int> ans;
void mul()
{
    for (int &i : ans)
        i *= 3;
    for (int i = 0; i < ans.size() - 1; i++)
    {
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
    if (ans.back() > 9)
    {
        ans.push_back(ans.back() / 10);
        ans[ans.size() - 2] %= 10;
    }
}
int main()
{
    scanf("%d", &n);
    if (n % 3 == 0)
    {
        n -= 3;
        ans.push_back(3);
    }
    else if (n % 3 == 1)
    {
        n -= 4;
        ans.push_back(4);
    }
    else if (n % 3 == 2)
    {
        n -= 2;
        ans.push_back(2);
    }
    for (int i = 1; i <= n / 3; i++)
        mul();
    printf("%d\n", ans.size());
    for (int i = ans.size() - 1, cnt = 1; i + 1 && cnt <= 100; i--, cnt++)
        printf("%d", ans[i]);
    return 0;
}