AtCoder ABC298 D - Writing a Numeral

2huk · 2023-04-18 16:06:20 · 题解

题目描述

我们有一个数字串 S，最开始 S = 1。

执行 Q 次操作：

• 1 x 将 x 插入 S 最后；
• 2 删除 S 的第一个数字；
• 3 输出当前的 S。

数据范围

分析

对于这道题目，我们当然不可以按照题目要求模拟，定义一个字符串 S 存储当前数字，对于第一个操作直接 S.push_back(x)，第二个操作直接 S.erase(s.begin())，第三个操作直接计算。

这样显然不可取，对于第二个和第三个操作都是 \Theta(n) 的时间复杂度。

观察第一个和第二个操作，在末尾插入，在开头删除，正好是队列 FIFO 的性质。

接下来考虑队列 queue，以下为三种操作对应的实现过程：

1. 在末尾插入 x，可以 q.push(x)；
2. 删除第一个元素，也就是弹出队头元素，可以 q.pop()；
3. 输出当前的数字，可以在上面两个操作中顺带地求出 res，输出即可。

代码

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

#define int long long

const int N = 1e6 + 10, P = 998244353;

int Q, op, x, res = 1;

queue<int> q;       // 队列 

int add(int a, int b)       // (a + b) % P 的值 
{
    return ((a % P) + (b % P) % P + P) % P;
}

int mul(int a, int b)       // (a ×b) % P 的值 
{
    return ((a % P) * (b % P)) % P; 
}

int fpm(int a, int b)       // (a ^ b) % P 的值 
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = mul(res, a);
        b >>= 1;
        a = mul(a, a);
    }
    return res;
}

signed main()
{
    q.push(1);      // 开始队列中为 1 
    cin >> Q;

    while (Q -- )       // Q 次询问 
    {
        cin >> op;
        if (op == 1)        // 第一种操作：将 x 入队 
        {
            cin >> x;
            q.push(x);
            res = add(res * 10, x);
        }
        if (op == 2)        // 第二种操作：弹出队头元素 
        {
            res = add(res, -(q.front() * fpm(10, q.size() - 1)));
            q.pop();
        }
        if (op == 3)        // 第三种操作：输出答案 
        {   
            cout << res << '\n';
        }
    }

    return 0;
}