ABC389(A-F)

A - 9x9

题目大意

给你一个长度为 \(3\) 的字符串，第 \(1\) 位和第 \(3\) 位是数字，第 \(2\) 位是乘法符号 \(\times\)，输出这个算式的结果。

参考代码

C++

#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    cout << (s[0] - '0') * (s[2] - '0') << endl;
    return 0;
}

---

B - tcaF

题目大意

给你一个正整数 \(X(2 \le X \le 3 \times 10 ^ {18})\)，找到一个正整数 \(N\) 使得 \(N! = X\)，保证答案一定存在。

参考代码

C++

#include <iostream>

using namespace std;
using ULL = unsigned long long;

int main()
{
    ULL x, num = 1;
    cin >> x;
    for(; x != num; num++)
        x /= num;
    cout << num << endl;
    return 0;
}

---

C - Snake Queue

题目大意

有一个蛇的队列，你需要处理 \(Q\) 个询问：

• 1 l，队列中加入一条长度为 \(l\) 的蛇。每一条蛇有头坐标和尾坐标。尾坐标等于头坐标加上自身的长度。如果当前队列为空，则新加入的蛇的头坐标为 \(0\)。如果队列不为空，则新加入的蛇的头坐标等于队列中最后一条蛇的尾坐标。
• 2：队列中第一条蛇出队。
• 3 k：输出第 \(k\) 条蛇的头坐标。

解题思路

维护队列的前缀和就好。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    int q;
    cin >> q;
    vector<LL> a = {0}, s = {0};
    int head = 1;
    while(q--)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int l;
            cin >> l;
            a.push_back(l);
            s.push_back(l + s.back());
        }
        else if(op == 2)
            head++;
        else
        {
            int k;
            cin >> k;
            cout << s[head + k - 2] - s[head - 1] << endl;
        }
    }
    return 0;
}

---

D - Squares in Circle

题目大意

有一个二维的平面，划分成多个 \(1 \times 1\) 的网格。如果在原点画一个半径为 \(R(1 \le R \le 10 ^ 6)\) 的圆，有多少个网格会被这个圆完整的包含？

解题思路

\(R \le 10 ^ 6\)，直接枚举就好。

参考代码

C++

#include <cmath>
#include <iostream>

using namespace std;
using LL = long long;

int main()
{
    auto sq = [](double x) -> double
    { return x * x; };

    double r;
    cin >> r;
    double rr = r * r;
    LL ans = 0;
    for(double y = 0.5, yy = sq(y); 0.25 + yy <= rr; y += 1, yy = sq(y))
    {
        double x = sqrt(rr - yy);
        int j = floor(x - 0.5);
        int cnt = 2 * j + 1;
        ans += cnt;
        if(y > 1)
            ans += cnt;
    }
    cout << ans << endl;
    return 0;
}

---

E - Square Price

题目大意

有 \(N(2 \le N \le 10 ^ 5)\) 种商品，每种商品都有无限个。购买 \(k\) 个第 \(i\) 种商品的价格为 \(k^2P_i\) 元，其中 \(1 \le P_i \le 2 \times 10^ 9\) 。你有 \(M(1 \le M \le 10 ^ {18})\) 元，最多能买多少个商品？

解题思路

可以发现，第 \(i\) 种商品的第 \(k\) 个的价格实际是 \((k^2 - (k-1)^2)P_i = (2k-1)P_i\)

这里如果用优先队列一个一个买的话会超时，但实际上可以二分 \(X\) 元以内的商品能不能全部买完，时间复杂度为 \(O(N\log m)\)。

注意这题 \(k^2P_i\) 会爆 long long，需要开 __int128。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;
using i128 = __int128;

int main()
{
    int n;
    LL m;
    cin >> n >> m;
    vector<LL> p(n);
    for (auto &x : p)
        cin >> x;

    auto check = [&p, m](LL x) -> bool
    {
        i128 sum = m;
        for (auto pi : p)
        {
            i128 k = (x + pi) / (2 * pi);
            sum -= k * k * pi;
            if (sum < 0)
                return false;
        }
        return true;
    };

    LL l = 0, r = m;
    while (l < r)
    {
        LL mid = (l + r + 1) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    LL ans = 0;
    for (auto pi : p)
    {
        LL k = (l + pi) / (2 * pi);
        ans += k;
        m -= k * k * pi;
    }
    ans += m / (l + 1);
    cout << ans << endl;
    return 0;
}

---

F - Rated Range

题目大意

你打算参加 \(N(1 \le N \le 2 \times 10^5)\) 场比赛，如果在第 \(i\) 场比赛开始前你的分数在闭区间 \([L_i, R_i]\) 中（\(1 \le L_i \le R_i \le 5 \times 10^5\)），比赛结束后分数会增加 \(1\)。

有 \(Q(1 \le Q \le 3 \times 10^5)\) 个询问，每个询问给你一个整数 \(X(1 \le X \le 5 \times 10^5)\)，你需要回答如果初始的分数是 \(X\)，在参加完这 \(N\) 场比赛之后分数是多少。

解题思路

设 \(F(x)\) 表示初始分数为 \(x\) 经过 \(N\) 场比赛之后的分数。不难发现 \(F(x)\) 是单调递增的。这是因为分数是一分一分的加的，所以对于 \(x \le y\)，至多有 \(F(x) = F(y)\)。

于是考虑将 \(Q\) 个询问按照初始分数排序，然后用线段树维护，显然，无论经过多少场比赛，线段树的值也是单调的，某一场比赛就相当于是给 \([L_i, R_i]\) 中的值 \(+1\)。在线段树节点中维护区间的最大最小值，就可以出对应的区间进行修改。时间复杂度为 \(O(N\log Q)\)。

参考代码

C++

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

class SegTree
{
public:
    SegTree(const vector<int> &a) : n(a.size() - 1), t(4 * n)
    {
        auto build = [&](auto &self, int p, int beg, int end) -> void
        {
            if (beg == end)
            {
                t[p].min_val = t[p].max_val = a[beg];
                return;
            }
            int lch = 2 * p, rch = 2 * p + 1;
            int mid = (beg + end) / 2;
            self(self, lch, beg, mid);
            self(self, rch, mid + 1, end);
            push_up(p);
        };

        build(build, 1, 1, n);
    }

    void update(int l, int r) { add(1, 1, n, l, r); }

    int ask(int pos) { return at(1, 1, n, pos); }

private:
    struct Node
    {
        int min_val, max_val, add;
    };

    int n;
    vector<Node> t;

    void push_up(int p)
    {
        int lch = p * 2, rch = p * 2 + 1;
        t[p].min_val = t[lch].min_val;
        t[p].max_val = t[rch].max_val;
    }

    void push_down(int p)
    {
        auto add_lazy = [&](int p, int add) -> void
        {
            t[p].max_val += add;
            t[p].min_val += add;
            t[p].add += add;
        };

        int lch = p * 2, rch = p * 2 + 1;
        add_lazy(lch, t[p].add);
        add_lazy(rch, t[p].add);
        t[p].add = 0;
    }

    void add(int p, int beg, int end, int l, int r)
    {
        if (t[p].max_val < l || t[p].min_val > r)
            return;
        if (t[p].min_val >= l && t[p].max_val <= r)
        {
            t[p].min_val++;
            t[p].max_val++;
            t[p].add++;
            return;
        }
        push_down(p);
        int lch = 2 * p, rch = 2 * p + 1;
        int mid = (beg + end) / 2;
        add(lch, beg, mid, l, r);
        add(rch, mid + 1, end, l, r);
        push_up(p);
    }

    int at(int p, int beg, int end, int pos)
    {
        if (beg == end)
            return t[p].max_val;
        push_down(p);
        int lch = 2 * p, rch = 2 * p + 1;
        int mid = (beg + end) / 2;
        return pos <= mid ? at(lch, beg, mid, pos) : at(rch, mid + 1, end, pos);
    }
};

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> contests(n);
    for (auto &[l, r] : contests)
        cin >> l >> r;
    int q;
    cin >> q;
    vector<int> a(q + 1);
    for (int i = 1; i <= q; i++)
        cin >> a[i];
    vector<int> b = a;
    sort(b.begin(), b.end());
    unordered_map<int, int> pos;
    for (int i = 1; i <= q; i++)
        pos[b[i]] = i;
    SegTree t(b);
    for (auto [l, r] : contests)
        t.update(l, r);
    for (int i = 1; i <= q; i++)
    {
        int x = a[i];
        cout << t.ask(pos[x]) << endl;
    }
    return 0;
}

---

最后更新: 2025-06-06
创建日期: 2025-06-06