P8811 [蓝桥杯 2022 国 C] 六六大顺 题解

· · 题解

P8811 [蓝桥杯 2022 国 C] 六六大顺 题解

老规矩，题目传送门

思路

S &= \sum _ {i = 1} ^ {n} {\underbrace{666 \cdots 66}_{\text{i 个 6}}} ^ 2 \\ &= \sum _ {i = 1} ^ {n} {(\frac{2}{3} \cdot \underbrace{999 \cdots 99}_{\text{i 个 9}})} ^ 2 \\ &= \sum _ {i = 1} ^ {n} \frac{4}{9} \cdot (10 ^ i - 1) ^ 2 \\ &= \frac{4}{9} \cdot \sum _ {i = 1} ^ {n} (10 ^ {2i} - 2 \cdot 10 ^ i + 1) \\ &= \frac{4}{9} \cdot (\underbrace{101010 \cdots 1010}_{\text{n 个 10}}0 + \underbrace{222 \cdots 22}_{\text{n 个 2}}0 + n) \end{aligned}

见 n ≤ 10 ^ 7 识高精。

但是，如果你直接用封装好的板子，MLE。

大佬们又说了：把 int 换成 char！

换了，TLE。

那怎么办？

我们发现，现在常见的高精度模板都使用了 vector 这个常数极大的东西，反而没有用 int 数组模拟的。

因此，让我们回归原始，再运用几个卡常小妙招，就能 AC 了。

AC 代码

#include <stdio.h>
using namespace std;
const int MAX = 2e7 + 1;
int n, arr[MAX];//arr模拟高精数组
int main()
{
    scanf("%d", &n);
    arr[0] = 4 * n % 10, arr[1] = 4 * n / 10;//将4n存入数组
    for (int i = 1; i <= n; ++i)//++i卡常小妙招（bushi
    {
        arr[i << 1] = 4, arr[i] -= 8;//将1010…100，22…20的4倍加给数组
        arr[i + 1] += arr[i] / 10, arr[i] %= 10;
        if (arr[i] < 0)
        {
            arr[i] += 10, --arr[i + 1];
        }//进退位
    }
    for (int i = n + 1; arr[i] < 0; ++i)
    {
        arr[i + 1] += arr[i] / 10, arr[i] %= 10;
        arr[i] += 10, --arr[i + 1];
    }//单纯进位 
    for (int i = 2 * n - 1; ~i; --i)
    {
        arr[i] += 10 * arr[i + 1];
        putchar(arr[i] / 9 + '0');
        arr[i] %= 9;
    }//一边输出一边除以9 
    return 0; 
}

AC 记录