ABC368(A-G)

A - Cut

题目大意

给你 \(N\) 张牌组成一个牌堆，依次抽出顶部的 \(K\) 的 张牌放到底部。然后从牌堆底开始输出牌堆的内容。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    k = n - k;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = k; i < n; i++)
        cout << a[i] << ' ';
    for(int i = 0; i < k; i++)
        cout << a[i] << ' ';    
    return 0;
}

---

B - Decrease 2 max elements

题目大意

给你一个包含 \(N(1 \le N \le 100)\) 个正整数的序列 \(A = (A_1, A_2,\cdots, A_N)\) ，其中 \(1 \le A_i \le 100\)，执行以下操作直到序列中正整数的数量小于 \(2\) 个：

• 将 \(A\) 序列降序排序，然后将 \(A_1\) 和 \(A_2\) 的值减 \(1\)。

问：多少次之后会结束操作？

解题思路

数据范围很小。直接排序也可以，维护一个堆也可以。

参考代码

C++

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n;
    cin >> n;
    priority_queue<int> heap;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        heap.push(x);
    }
    int ans = 0;
    while (heap.size() >= 2)
    {
        ans++;
        int x = heap.top();
        heap.pop();
        int y = heap.top();
        heap.pop();
        if (x > 1)
            heap.push(x - 1);
        if (y > 1)
            heap.push(y - 1);
    }
    cout << ans << endl;
    return 0;
}

---

C - Triple Attack

题目大意

有 \(N(1 \le N \le 2 \times 10^5)\) 个敌人站成一条直线，从左到右数第 \(i\) 个敌人的血量是 \(H_i(1 \le H_i \le 10^9)\)，当一名敌人的血量变为 \(0\) 或更低时，这名敌人被击倒。

设 \(T\) 表示当前的时间，从第 \(1\) 秒开始，每隔 \(1\) 秒，你都会从左边开始选择第一个没有被击倒的敌人，如果当前时间 \(T\) 是 \(3\) 的倍数，对这名敌人造成 \(3\) 点伤害，否则对这名敌人造成 \(1\) 点伤害。

问：击倒所有敌人需要花费多少时间？

解题思路

每隔 \(3\) 秒就会对一名敌人造成攻击 \(5\) 点伤害，所以直接模掉就好。

参考代码

C++

#include <iostream>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    LL t = 0;
    for(int i = 0; i < n; i++)
    {
        LL h;
        cin >> h;
        LL k = h / 5;
        h %= 5;
        t += k * 3;
        while(h > 0)
        {
            t++;
            h -= t % 3 == 0 ? 3 : 1;
        }
    }
    cout << t << endl;
    return 0;
}

---

D - Minimum Steiner Tree

题目大意

给你一颗 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个节点的树，然后给你一个长度为 \(K(1 \le K \le N)\) 的点集 \(V = (V_1, V_2, \cdots, V_K)\)。你需要从树中移除一些点，使得剩下的那颗子树包含 \(V\) 中所有的点。问：包含 \(V\) 中所有的点的子树最少的顶点数量是多少？

解题思路

随便从 \(V_1\) 开始 dfs，遍历维护子树中有多少个点在 \(V\) 中，砍掉没有任何一个点在 \(V\) 中的子树即可。

参考代码

C++

#include <iostream>
#include <unordered_set>

using namespace std;

const int MAXN = 2E5 + 10;
const int MAXM = 2 * MAXN;

int head[MAXN], edge[MAXM], ne[MAXM], idx = 1;
void add(int u, int v)
{
    edge[idx] = v;
    ne[idx] = head[u];
    head[u] = idx++;
}

unordered_set<int> vs;
int dfs(int u, int fa)
{
    int cnt = 0;
    for (int i = head[u]; i; i = ne[i])
    {
        int v = edge[i];
        if (v == fa)
            continue;
        cnt += dfs(v, u);
    }
    if (cnt || vs.count(u))
        cnt++;
    return cnt;
}

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    for (int i = 0; i < k; i++)
    {
        int v;
        cin >> v;
        vs.insert(v);
    }
    cout << dfs(*vs.begin(), 0);
    return 0;
}

---

E - Train Delay

题目大意

有 \(N(2 \le N \le 2 \times 10 ^ 5)\) 个城市，\(M(2 \le M \le 2\times 10^5)\) 条铁路，第 \(i\) 条铁路的从 \(A_i\) 城市出发，到达 \(B_i\) 城市，预计出发时间为 \(S_i\)，预计到达时间为 \(T_i\)。对于两条铁路 \(i\) 和 \(j\)，如果 \(B_i = A_j\) 且 \(T_i \le S_j\)，则乘客可以先坐铁路 \(i\) 换乘铁路 \(j\)，我们称 \((i, j)\) 是可换乘铁路。

现在，第 \(1\) 条铁路的发车时间需要延迟 \(X_1\)，即实际出发的时间变成 \(S_1 + X_1\)，实际到达时间变成 \(T_1 + X_1\)。为了让某些乘客仍然可以经过铁路 \(1\) 换成到其他铁路，其他铁路可能需要延迟一定时间。例如，假设原本可以通过铁路 \(1\) 换乘铁路 \(j\)，在铁路 \(1\) 延迟 \(X_1\) 之后，有可能出现 \(S_1 + X_1 > T_j\)，这会导致乘客无法通过铁路 \(1\) 换乘铁路 \(j\)，所以需要对铁路 \(j\) 延迟一定时间 \(X_j\) 保证乘客可换乘，即 \(S_1 + X_1 \le T_j + X_j\)。而铁路 \(j\) 的延迟可能会导致其他铁路的延迟。记 \(X_2, X_3, \cdots, X_M\) 表示每条铁路延迟的时间，你需要在保证所有原本可换乘的铁路在延迟之后仍然可以换乘，同时最小化 \(\sum\limits_{j = 2} ^ MX_j\) 的值。

解题思路

非常有现实意义的一道题。（虽然我是看了题解才会的）

思考一下如何决定对一条铁路延迟多久的时间发车。首先，对于一条铁路 \(i\)，我们需要知道在发车时刻 \(S_i\) 前有多少条铁路的终点是 \(B_i\)，然后，在这些铁路中，找到一条最晚到达 \(B_i\) 的铁路，假设这条铁路是 \(j\)，则可以根据铁路 \(j\) 的实际到达时间 \(X_j + T_j\) 来决定铁路 \(i\) 应该延迟多久。如果 \(X_j + T_j > S_i\)，则需要对铁路 \(i\) 延迟 \(X_i = X_j + T_j - S_i\)，才能让这些铁路可以换乘。如果 \(X_j + T_j \le S_i\)，则无需延迟（\(X_i = 0\)）。

这种分析需要我们按照时间顺序考虑每条铁路，因此，我们将铁路按照时间顺序排序。考虑到铁路有发车时间和到达时间两个时间属性，进一步将一条铁路拆分成发车时间点和到达时间点两个事件，按照时间排序，依次处理所有事件：

• 对于到达事件，我们维护一个 \(\text{station}_i\) 表示当前到达城市 \(i\) 的最晚时间，则有 \(X_i = \max(X_i, \text{station}_i - S_i)\)
• 对于出发时间，在出发时 \(X_i\) 的时间已经确定，因此可以确定这条铁路实际的到达时间为 \(T_i + X_i\)，进而有 \(\text{station}_i = \max(\text{station}_i, T_i + X_i)\)

参考代码

C++

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

struct Event
{
    bool is_arrive;
    int id;
    int city;
    LL time;
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<LL> x(m), station(n);
    cin >> x[0];
    vector<Event> event(2 * m);
    for (int i = 0; i < m; i++)
    {
        int a, b, s, t;
        cin >> a >> b >> s >> t;
        a--, b--;
        event[i] = {false, i, a, s};
        event[i + m] = {true, i, b, t};
    }
    sort(event.begin(), event.end(), [](const Event &x, const Event &y) -> bool
         { return x.time < y.time || (x.time == y.time && x.is_arrive && !y.is_arrive); });
    for (auto e : event)
        if (e.is_arrive)
        {
            int id = e.id;
            int b = e.city;
            station[b] = max(station[b], x[id] + e.time);
        }
        else
        {
            int id = e.id;
            int a = e.city;
            x[id] = max(x[id], station[a] - e.time);
        }
    for (int i = 1; i < m; i++)
        cout << x[i] << ' ';
    return 0;
}

---

F - Dividing Game

题目大意

Anna 和 Bruno 在玩一个游戏：有一个长度为 \(N(1 \le N \le 10^5)\) 的序列 \(A = (A_1, A_2, \cdots, A_N)\)，其中 \(2 \le A_i \le 10^5\)。由 Anna 开始双方轮流行动，每次行动时：任意选择一个数字 \(i\), 然后将 \(A_i\) 替换成 \(x\)，其中 \(x\) 表示 \(A_i\) 的因子且 \(x \neq A_i\)。如果轮到某一方时，无法做出任何行动，那么这个人就输了。问：如果双方都采取最佳策略，谁必胜？

解题思路

很裸的一个 SG 函数模板，因为每次行动都是将某个 \(A_i\) 替换成更小的数字，所以直接用记忆化搜索 + SG 函数值异或即可。这样每个数字最多被计算一次，计算的代价就是因数分解的代价，时间复杂度是 \(O(n\sqrt{A_{max}})\)，又因为 \(2 \le A_i \le 10^5\)，是可以通过的

进一步的，不妨将 \(A_i\) 分解成 \(A_i = p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}\)，每一次将 \(A_i\) 替换成 \(x\) 相当于让 \(A_i\) 除掉一些质因子，而一共有 \(\sum\limits_{j = 1}^kc_j\) 个质因子，也就是一个数字最多可以除掉 \(\sum\limits_{j = 1}^kc_j\) 个质因子，也可以最少除掉 \(1\) 个。除掉一个质因子类似于 nim 游戏中拿掉一个石子，所以这等价于一个 nim 游戏，每个数字的 SG 值其实就等于 \(\sum\limits_{j = 1}^kc_j\)。问题等价于对所有 \(A_i\) 做一次质因子分解，求出 \(\text{SG}(A_i)= \sum\limits_{j = 1}^kc_j\)，可以使用欧拉筛筛出所有的质数，加快质因子分解的速度，但这还不够快。

注意到 \(\text{SG}(A_i) = \sum\limits_{j = 1}^kc_j\) 其实是一个加性函数，即满足 \(f(1) = 0\) 且 \(f(xy) = f(x) + f(y)\)，所以在欧拉筛的时候，利用加性函数性质计算出所有数字的 SG 值。例如，假设现在有数字 \(i\)，和一个质数 \(p\)（根据质数的性质，我们有 \(\text{SG}(p) = 1\)），则在 \(i \times p\) 被筛掉时，可以同时计算出 \(\text{SG}(i\times p) = \text{SG}(i) + \text{SG}(p) = \text{SG}(i) + 1\)。这样的话，就可以在 \(O(A_{max})\) 的时间内求解。

参考代码

纯 SG 函数Nim + 筛法 + 加性函数性质

#include <iostream>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> sg;
    sg[1] = 0;
    int now = 0;

    auto SG = [&sg](auto &self, int x) -> int
    {
        auto it = sg.find(x);
        if(it != sg.end())
            return it->second;
        unordered_set<int> vis;

        for(int i = 2; i * i <= x; i++)
            if(x % i == 0)
            {
                vis.insert(self(self, i));
                vis.insert(self(self, x / i));
            }
        int ans = 1;
        while(vis.count(ans))
            ans++;
        sg[x] = ans;
        return ans;
    };

    for(int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        now ^= SG(SG, a);
    }
    cout << (now ? "Anna" : "Bruno") << endl;
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int len = *max_element(a.begin(), a.end());
    vector<int> prime;
    vector<bool> is_prime(len + 1, true);
    vector<int> sg(len + 1);
    for (int i = 2; i <= len; i++)
    {
        if (is_prime[i])
        {
            prime.push_back(i);
            sg[i] = 1;
        }
        for (auto p : prime)
        {
            if (p * i > len)
                break;
            is_prime[p * i] = false;
            sg[p * i] = 1 + sg[i];
            if (i % p == 0)
                break;
        }
    }
    int ans = 0;
    for (auto x : a)
        ans ^= sg[x];
    cout << (ans ? "Anna" : "Bruno") << endl;
    return 0;
}

---

G - Add and Multiply Queries

题目大意

给你两个长度为 \(N(1 \le N \le 1 \times 10^5)\) 的序列 \(A = (A_1, A_2, \cdots, A_N)\) 和 \(B = (B_1, B_2, \cdots, B_N)\)，其中 \(1 \le A_i, B_i \le 10 ^9\)，同时给你 \(Q(1 \le Q \le 1 \times 10^5)\) 个操作，有三种类型：

• 1 i x，表示将 \(A_i\) 替换成 \(x\)
• 2 i x，表示将 \(B_i\) 替换成 \(x\)
• 3 l r，初始时设置变量 \(v\) 的值为 \(0\)，接下来，对于所有的 \(i = l, l + 1, \cdots, r\) 按顺序将 \(v\) 替换成 \(\max(v + A_i, v \times B_i)\)。然后，输出 \(v\) 的值。

输入数据保证第三种操作的答案的值一定小于 \(10^{18}\)

解题思路

如果 \(B_i = 1\)，那么替换 \(v + A_i\) 一定更好，如果 \(B_i > 1\)，本次替换后 \(v\) 的值至少会变成原来的 \(2\) 倍。注意到 输入数据保证第三种操作的答案的值一定小于 \(10^{18}\)，可以发现这种倍增的次数一定不会太多（因为 \(2^{60} > 10^{18}\)，所以倍增至多出现 \(60\) 次）。 我们可以记录下所有 \(B_i > 1\) 的位置，处理第三种操作的时候，设下一个倍增的位置是 \(p\)，则在 \(p\) 之前的位置一定将 \(v\) 替换成 \(v_i + A_i\) 的。

于是，我们首先维护所有满足的 \(B_i > 1\) 的 \(i\)，存放到一个 set里面，就可以快速求出下一个倍增的位置。对于 \(A\) 维护一个树状数组，批量的求一段区间和。时间复杂度大概是 O\((60\times Q\log N)\) 。

参考代码

C++

#include <iostream>
#include <set>
#include <vector>

using namespace std;
using LL = long long;

struct FenwickTree
{
    int n;
    vector<LL> t;

    FenwickTree(const vector<LL> &a) : n(a.size() - 1), t(n + 1)
    {
        for(int i = 1; i <= n; i++)
        {
            t[i] += a[i];
            int j = i + lowbit(i);
            if (j <= n)
                t[j] += t[i];
        }
    }

    LL query(int l, int r) const { return prefix(r) - prefix(l - 1); }

    LL prefix(int x) const
    {
        LL res = 0;
        for (; x; x -= lowbit(x))
            res += t[x];
        return res;
    }

    void add(int x, LL k)
    {
        for (; x <= n; x += lowbit(x))
            t[x] += k;
    }

    int lowbit(int x) const { return x & -x; }
};

int main()
{
    int n;
    cin >> n;
    vector<LL> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    FenwickTree t(a);
    set<int> b_pos;
    for(int i = 1; i <= n; i++)
    {
        cin >> b[i];
        if(b[i] > 1)
            b_pos.insert(i);
    }
    b_pos.insert(n + 1);
    int q;
    cin >> q;
    while(q--)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int i, x;
            cin >> i >> x;
            t.add(i, x - a[i]);
            a[i] = x;
        }
        else if(op == 2)
        {
            int i, x;
            cin >> i >> x;
            if(b[i] > 1 && x == 1)
                b_pos.erase(i);
            else if(b[i] == 1 && x > 1)
                b_pos.insert(i);
            b[i] = x;
        }
        else
        {
            LL v = 0;
            int l, r;
            cin >> l >> r;
            auto it = b_pos.upper_bound(l);
            while(l <= r)
            {
                int r_pos = min(r, *it - 1);
                v += t.query(l, r_pos);
                if(r_pos == r)
                    break;
                v = max(v + a[*it], v * b[*it]);
                l = *it + 1;
                it++;
            }
            cout << v << endl;
        }
    }
    return 0;
}

---

---

最后更新: 2024-11-13
创建日期: 2024-11-13