数据很水吧?
查看原帖
数据很水吧?
1229013
Mr_LiuXinan楼主2024/7/31 08:59

这8个测试点的所有数的乘积貌似都没有超过那个mod? 不然我这种代码怎么会AC了

代码如下:

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <unordered_map>

typedef long long ll;
const ll mod = 317847191;
int n, m;
ll multi = 1;
unordered_map<ll, int> ump;
vector<ll> v1, v2;

ll getmax()
{
    while (!ump[v2[0]])
    {
        pop_heap(v2.begin(), v2.end());
        v2.pop_back();
    }
    return v2[0];
}

ll getmin()
{
    while (!ump[v1[0]])
    {
        pop_heap(v1.begin(), v1.end(), greater<int>());
        v1.pop_back();
    }
    return v1[0];
}

ll fastpow(ll a, ll b, ll mod)
{
    ll res = 1;
    a %= mod;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    ll t;
    for (int i = 1; i <= n; ++i)
    {
        cin >> t;
        multi = multi * t % mod;
        if (!ump[t])
        {
            v1.push_back(t);
            v2.push_back(t);
            push_heap(v1.begin(), v1.end(), greater<int>());
            push_heap(v2.begin(), v2.end());
        }
        ump[t]++;
    }

    char op;
    ll x;
    while (m--)
    {
        cin >> op;
        if (op == 'D')
        {
            cin >> x;
            if (ump[x] > 0)
            {
                ump[x]--;
                multi = multi / x;  //问题在这里,这里这么写,直接除掉被删掉的数,本不应该AC的
            }
        }
        else if (op == 'B')
        {
            cout << getmax() << "\n";
        }
        else if (op == 'S')
        {
            cout << getmin() << "\n";
        }
        else if (op == 'M')
        {
            cout << fastpow(getmax(), getmin(), mod) << "\n";
        }
        else if (op == 'T')
        {
            cout << multi << "\n";
        }
    }
    return 0;
}

2024/7/31 08:59
加载中...