AtCoder Beginner Contest 368

A - Cut (abc368 A)

题目大意

给定一个数组,将右边\(k\)个数保持原顺序挪到左边,输出。

解题思路

即从左边第\(n-k\)个数开始输出即可。或者用rotate函数转换一下。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    k = n - k;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    rotate(a.begin(), a.begin() + k, a.end());
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';

    return 0;
}



B - Decrease 2 max elements (abc368 B)

题目大意

给定一个数组,每次将最大的两个数减一,直到只有一个或无正数。输出操作的次数。

解题思路

最多\(100\)个数,每个数最大 \(100\),因此最大的操作次数只有\(O(100^2)\),加上每次操作的复杂度是 \(O(n\log n)\),因此直接模拟的复杂度即为 \(O(n^3\log n)\),能过。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    int cnt = 0;
    while (count_if(a.begin(), a.end(), [](int x) { return x > 0; }) > 1) {
        sort(a.begin(), a.end(), greater<int>());
        a[0]--;
        a[1]--;
        cnt++;
    }
    cout << cnt << '\n';

    return 0;
}



C - Triple Attack (abc368 C)

题目大意

\(n\)个怪兽血量 \(h_i\),依次打它们。当前怪物死了则打下一个。

初始时刻\(t=0\),每时刻都会对当前怪物造成 \(1\)的伤害,如果 \(t \% 3 == 0\),则可以额外造成 \(2\)的伤害(即一共 \(3\)的伤害)。

问打死所有怪物时的时刻。

解题思路

直接模拟时刻流逝,其最大时刻高达\(O(10^{14})\),但注意到打怪物的时刻越多,伤害越高,因此对于每个怪兽,我们不必模拟时刻流逝,而是二分打死怪物的时刻 \(T\),看看时间\((t, T]\)的伤害是否足够打死当前怪兽。

对每个怪兽都二分求出一下打死的时刻,最后的二分结果即为答案。

计算 \((t, T]\)时间的伤害,即为 \(T - t + \lfloor \frac{T}{3} \rfloor - \lfloor \frac{t}{3} \rfloor\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    LL t = 0;
    LL up = 1e18;
    auto check = [](LL l, LL r) -> LL { return r - l + 2ll * (r / 3 - l / 3); };
    auto solve = [&](LL t, int x) -> LL {
        LL l = t, r = up;
        while (l + 1 < r) {
            LL mid = (l + r) / 2;
            if (check(t, mid) < x)
                l = mid;
            else
                r = mid;
        }
        return r;
    };
    while (n--) {
        int x;
        cin >> x;
        t = solve(t, x);
    }
    cout << t << '\n';

    return 0;
}



D - Minimum Steiner Tree (abc368 D)

题目大意

给定一棵树,问保留\(k\)个点且连通的最小点数是多少。

解题思路

以第一个保留的点为根,进行\(DFS\)

\(DFS\)过程中的当前点 \(u\),判断其是否需要保留,则需要知道其子树是否有需要保留的点,有则当前点 \(u\)需要保留。

因此 \(DFS\)返回的东西即为该子树是否有需要保留的点\(fixed\)。最后答案就是 fixed点的数量。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<vector<int>> edge(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    vector<int> fix(n, 0);
    int root = 0;
    for (int i = 0; i < k; ++i) {
        cin >> root;
        --root;
        fix[root] = 1;
    }
    int ans = 0;
    auto dfs = [&](auto dfs, int u, int fa) -> bool {
        bool fixed = fix[u];
        for (auto v : edge[u]) {
            if (v == fa)
                continue;
            fixed |= dfs(dfs, v, u);
        }
        ans += fixed;
        return fixed;
    };
    dfs(dfs, root, root);
    cout << ans << '\n';

    return 0;
}



E - Train Delay (abc368 E)

题目大意

给定\(n\)个城市和 \(m\)个火车的信息,从\(s_i \to t_i\),时间是 \(S_i \to T_i\)

先给定 \(x_1\),即第一个城市火车延误出发时间,要求 \(x_2,x_3,...,x_n\),使得:

  • 对于任意两个火车信息满足 \(t_i = s_j, T_i \leq S_j\)的,也满足\(T_i + x_i \leq S_j + x_j\),即原来可换乘的俩列车, 在延误后仍可换乘。
  • \(\sum_{i=2}^n x_i\)最小

解题思路

<++>

神奇的代码



F - Dividing Game (abc368 F)

题目大意

给定\(n\)个数, \(Anna\)杏菜\(Bruno\)玩游戏, \(Anna\)先。

每轮,选一个数,将其变为真因子。

无法操作即输。问最优情况下谁赢。

解题思路

知道博弈论的\(SG\)知识就可以解了。

每个数之间是互不干扰的,因此每个数可以视为一个独立局面,因此整个局面的\(sg\)值就是每个独立局面的 \(sg\)值的异或。

考虑一个独立局面的 \(sg\)值怎么求,即 \(sg[x]\)。根据 \(sg\)值定义,其为所有后继情况的 \(sg\)值的 \(mex\),即 \(sg[x] = \mex_{x \% i == 0} (sg[i])\)

枚举因子数是\(O(\sqrt{x}) = 10^{2.5}\),而\(n=10^5\) ,因此花\(O(n\sqrt{x})\)预处理出所有数的\(sg\)值,然后异或一下,为 \(0\)则 先手输,否则 先手赢。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N = 1e5 + 8;
    vector<int> sg(N);
    sg[1] = 0;
    auto getSG = [&](int x) {
        set<int> hold{sg[1]};
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                hold.insert(sg[x / i]);
                hold.insert(sg[i]);
            }
        }
        for (int i = 0; i < N; ++i) {
            if (hold.find(i) == hold.end()) {
                return i;
            }
        }
        assert(0);
    };
    for (int i = 2; i < N; ++i) {
        sg[i] = getSG(i);
    }
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        ans ^= sg[x];
    }
    if (ans) {
        cout << "Anna" << '\n';
    } else {
        cout << "Bruno" << '\n';
    }

    return 0;
}



G - Add and Multiply Queries (abc368 G)

题目大意

给定两个数组\(a,b\),维护下列三种操作:

  • 1 i x,令\(a_i = x\)
  • 2 i x,令\(b_i = x\)
  • 3 l r,求最大值\(v\),其初始 \(v=0\),依次 \(i \in [l,r]\) ,令\(v = v + a_i\)\(v = v * b_i\)

题目保证操作三的答案不超过\(10^{18}\)

解题思路

对于一次操作\(3\),很显然对于 \(i \in [l,r]\) ,我令\(v = \max(v + a_i, v * b_i)\)。一次的复杂度是 \(O(n)\)

注意到操作三的答案不超过\(10^{18}\),这意味着什么呢。

首先,如果 \(b_i = 1\),我们很显然是选择操作 \(1\),而对于要判断最大值的,必定有 \(b_i \geq 2\)\(v = \max(v + a_i, v*b_i) \geq 2v\),也就是说,每做一次判断, \(v\)都会翻倍,最多翻 \(64\)次,就达到 \(10^{18}\)了。

所以,每次区间 \([l,r]\)中,实际上只有最多\(O(64)\)\(b_i \geq 2\),其余都是 \(1\),这意味着都会选择 \(v=v+a_i\)

因此每次操作区间 \([l,r]\),我们直接模拟,

  • 找到第一个 \(b_{pos} \geq 2\)
  • 处理 \([l, pos-1]\)的操作,即 \(v = v + suma[l..pos-1]\)
  • 处理 \([pos, pos]\)的操作,即 \(v = \max(v + a_{pos}, v * b_{pos})\)
  • \(l = pos + 1\),重复第一个操作

最多跑 \(O(60)\)次就跑完了,因为带修改,第一步操作就用线段树上二分,通过区间最大值>1找到其位置,第二步操作就是一个区间和。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 2e5 + 8;

class info {
  public:
    LL sum;
    int maxx;

    info(LL sum = 0, int maxx = 0) : sum(sum), maxx(maxx) {}
    info operator+(const info& rhs) const {
        return info(sum + rhs.sum, max(maxx, rhs.maxx));
    }
};

class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
  public:
    info val[N << 2];

    void build(int root, int l, int r, vector<int>& a, vector<int>& b) {
        if (l == r) {
            val[root] = info(a[l], b[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, a, b);
        build(rson, mid + 1, r, a, b);
        val[root] = val[lson] + val[rson];
    }

    void update(int root, int l, int r, int pos, info& v) {
        if (l == r) {
            val[root] = v;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(lson, l, mid, pos, v);
        else
            update(rson, mid + 1, r, pos, v);
        val[root] = val[lson] + val[rson];
    }

    info query(int root, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return val[root];
        }
        int mid = (l + r) >> 1;
        info resl{}, resr{};
        if (L <= mid)
            resl = query(lson, l, mid, L, R);
        if (R > mid)
            resr = query(rson, mid + 1, r, L, R);
        return resl + resr;
    }

    int findfirst(int root, int l, int r, int L, int R) {
        if (l > R || r < L) {
            return 0;
        }
        if (L <= l && r <= R && val[root].maxx < 2) {
            return 0;
        }
        if (l == r) {
            return l;
        }
        int mid = (l + r) >> 1;
        int ret = findfirst(lson, l, mid, L, R);
        if (ret == 0) {
            ret = findfirst(rson, mid + 1, r, L, R);
        }
        return ret;
    }
} seg;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    vector<int> b(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
    seg.build(1, 1, n, a, b);
    int q;
    cin >> q;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int pos, x;
            cin >> pos >> x;
            a[pos] = x;
            info v(a[pos], b[pos]);
            seg.update(1, 1, n, pos, v);
        } else if (op == 2) {
            int pos, x;
            cin >> pos >> x;
            b[pos] = x;
            info v(a[pos], b[pos]);
            seg.update(1, 1, n, pos, v);
        } else {
            int l, r;
            cin >> l >> r;
            LL ans = a[l];
            l++;
            while (l <= r) {
                int pos = seg.findfirst(1, 1, n, l, r);
                if (pos == 0) {
                    ans += seg.query(1, 1, n, l, r).sum;
                    break;
                } else {
                    info v = seg.query(1, 1, n, l, pos - 1);
                    ans += v.sum;
                    ans = max(ans + a[pos], ans * b[pos]);
                    l = pos + 1;
                }
            }
            cout << ans << '\n';
        }
    }

    return 0;
}