AtCoder Beginner Contest 369

A - 369 (abc369 A)

题目大意

给定两个数\(a,b\),问有多少个整数\(x\),使得 \(a,b,x\)经过某种排列后成为等差数列,

解题思路

就三种情况:\(xab\)\(axb\)\(abx\),三种情况都求出来,然后放到 set去重即为答案。中间的情况要判断是否是实数。

神奇的代码
#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 a, b;
    cin >> a >> b;
    if (a > b)
        swap(a, b);
    set<int> ans{a - (b - a), b + (b - a)};
    if ((b - a) % 2 == 0)
        ans.insert(a + (b - a) / 2);
    cout << ans.size() << '\n';

    return 0;
}



B - Piano 3 (abc369 B)

题目大意

谈钢琴,给出左右手依次要弹奏的键,问左右手移动的距离数。

解题思路

模拟即可,用一个map记录左右手当前位置,然后移动到下一个位置时计算距离,累计求和集合。

神奇的代码
#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;
    int ans = 0;
    map<char, int> pos;
    while (n--) {
        int p;
        string s;
        cin >> p >> s;
        if (pos.find(s[0]) != pos.end()) {
            ans += abs(pos[s[0]] - p);
        }
        pos[s[0]] = p;
    }
    cout << ans << '\n';

    return 0;
}



C - Count Arithmetic Subarrays (abc369 C)

题目大意

给定一个数组\(a\),问有多少个 \(l,r\),使得 \(a[l..r]\)是一个等差数列。

解题思路

等差数列即公差相等。从\(a\)的差分数组\(b\)来看, \(a[l..r]\)是等差数列,意味着差分数组的对应区间的数是相等的,那就是说,对于\(a[l..r]\)是等差数列的 \(l,r\)对数,等价于 \(b[i..j]\)是相同数的对数。(特判下\(a[l..r]\)长度是 \(1\)的情况)

那先求 \(a\)的差分数组\(b\),然后对该差分数组的相同数的区间,比如 \(b[i..j] = c\),那么对于\(a\)数组符合条件的 \(l,r\) 就有 \(\frac{(j - i + 1)(j - 1)}{2}\)种取法。

对每个这样的区间累计求和即为答案。

神奇的代码
#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;
    vector<int> l(n);
    int la = -1;
    int cnt = 0;
    LL ans = n;
    for (int i = 1; i < n; ++i) {
        if (a[i] - a[i - 1] != la) {
            ans += 1ll * cnt * (cnt - 1) / 2;
            cnt = 2;
            la = a[i] - a[i - 1];
        } else {
            ++cnt;
        }
    }
    ans += 1ll * cnt * (cnt - 1) / 2;
    cout << ans << '\n';

    return 0;
}



D - Bonus EXP (abc369 D)

题目大意

\(n\)个怪兽,你要依次打他们。

对于第 \(i\)只怪兽,要么与它战斗,要么放走他。

如果与它战斗,你会获胜,且会获得 \(x_i\)经验。如果它是你第偶数只打败的怪兽,则还可以额外获得 \(x_i\)经验,即共获得双倍经验。

问获得的经验数的最大值。

解题思路

比较朴素的\(dp\),很显然对于每只怪兽考虑打或不打,如果选择打,其结果会受到 是否是第偶数只打败这一状态的影响,因此我们的\(dp\)状态,除了包含基本状态 考虑前$i$只怪兽外,还要加上状态打败了奇数/偶数只怪兽这一\(0/1\)状态。

有了这一状态后,就可以写出关于经验的转移式子了。即 \(dp[i][0/1]\)表示考虑前 \(i\)只怪兽,已经打败了偶数只/奇数只怪兽时,获得的最大经验值。

然后考虑第\(i\)只打或不打 ,得到对应的经验值,转移到后续状态即可。

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

LL inf = 1e18;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    array<LL, 2> dp = {0, -inf};
    for (int i = 0; i < n; i++) {
        array<LL, 2> dp2 = {0, 0};
        dp2[0] = max(dp[0], dp[1] + a[i] + a[i]);
        dp2[1] = max(dp[1], dp[0] + a[i]);
        dp2.swap(dp);
    }
    cout << max(dp[0], dp[1]) << '\n';

    return 0;
}



E - Sightseeing Tour (abc369 E)

题目大意

给定一张无向图,边有边权。

回答\(q\)个询问。

每个询问给定 \(k \leq 5\)条边,表示从\(1 \to n\),必须经过至少一次这些边,的最短路径。

解题思路

这里给的边数很少。

考虑最简单的情况,即\(k=1\),给的边是\(u,v\),那么很显然答案就是 \(1 \to u \to v \to n\)或者 \(1 \to v \to u \to n\), 即考虑从\(1\)节点出发,以最短路先到 \(u\)还是先到 \(v\)

这里 \(k=5\),但情况数仍然不多,我们仍然枚举中途经过的点,共有\(O(k! 2^k)\)种情况(枚举遍历边的顺序,对于每条边再枚举访问端点的顺序), \(k=5\)的话就是 \(3e3\),情况数不大,有了经过的点之后,剩下的就是以最短路径依次遍历每个点。由于 \(n\leq 400\),可以事先用 \(floyd\)求出任意两点的距离,然后对于每个询问,花费 \(O(k! 2^k)\)枚举遍历点的顺序,然后用 \(O(2k)\)计算该顺序对应的最短路长度,所有情况取最小即为答案。

总的时间复杂度为\(O(n^3 + q(k! 2^k + k))\)

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

const LL inf = 1e18;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edge(m);
    vector<vector<LL>> dis(n, vector<LL>(n, inf));
    for (int i = 0; i < n; i++)
        dis[i][i] = 0;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        dis[u][v] = min(dis[u][v], (LL)w);
        dis[v][u] = min(dis[v][u], (LL)w);
        edge[i] = {u, v, w};
    }
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    int q;
    cin >> q;
    auto calc = [&](vector<int>& p) -> LL {
        LL sum = 0;
        int st = 0;
        for (int i = 0; i < p.size(); i += 2) {
            int u = p[i], v = p[i + 1];
            sum += dis[st][u];
            st = v;
        }
        sum += dis[st][n - 1];
        return sum;
    };

    while (q--) {
        int k;
        cin >> k;
        vector<int> b(k);
        for (auto& x : b) {
            cin >> x;
            --x;
        }
        int up = (1 << k);
        LL ans = inf;
        do {
            for (int i = 0; i < up; ++i) {
                vector<int> p;
                LL sumb = 0;
                for (int j = 0; j < k; ++j) {
                    auto [u, v, w] = edge[b[j]];
                    sumb += w;
                    if ((i >> j) & 1) {
                        swap(u, v);
                    }
                    p.push_back(u);
                    p.push_back(v);
                }
                LL sum = calc(p) + sumb;
                ans = min(ans, sum);
            }
        } while (next_permutation(b.begin(), b.end()));
        cout << ans << '\n';
    }

    return 0;
}



F - Gather Coins (abc369 F)

题目大意

\(h\times w\)网格,有些格子有金币。

从左上走到右下,只能向右走和向下走。

问取得金币的最大值。

解题思路

朴素\(dp\)就是 \(dp[i][j] = \max(dp[i - 1][j], dp[i][j - 1]) + (coin[i][j] == 1)\),但\(h \times w\)可达 \(1e10\),整不动。但金币数最多只有 \(10^5\),我们知道 \(dp\)的值只有在有金币的格子才会变动,实际有效的格子只有 \(10^5\)个。我们仅考虑这些格子的 \(dp\)值怎么计算。

考虑 \(dp[i][j]\)表示当前处于有金币的格子 \((i,j)\)时的最大金币数,考虑能够转移到此的状态,即 $dp[i][j] = \max_{x \leq i, y \leq j, coin[i][j]}(dp[x][y]) + 1。

这个转移条件其实就是个二维偏序,因此对金币的位置\((x,y)\)从小到大排序,然后依次枚举这些金币,当考虑到第 \(i\)个金币时, \(j \leq i\)的金币 一定满足\(x_j \leq x_i\),因此我们只需找到 \(y_j \leq y_i\)的最大的 \(dp[x_j][y_j]\)值即可,这是一个区间最值查询,用线段树维护即可。

即对金币的位置\((x,y)\)从小到大排序,然后依次枚举这些金币,用线段树维护枚举过的金币关于y_j下标的dp最大值。考虑上述的转移条件,在线段树查询时,由于枚举顺序的缘故,天然满足\(x \leq i\)的条件,而线段树的区间查询找到满足 \(y < j\)\(\max(dp[x][y])\),因此上述的二维偏序的最值问题就可以用线段树解决了。

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

const int N = 2e5 + 8;
const int inf = 1e9 + 7;

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

    void pushup(int root) {
        if (val[lson] > val[rson]) {
            val[root] = val[lson];
            id[root] = id[lson];
        } else {
            val[root] = val[rson];
            id[root] = id[rson];
        }
    }

    void build(int root, int l, int r) {
        if (l == r) {
            val[root] = -inf;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        pushup(root);
    }

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

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

} seg;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w, n;
    cin >> h >> w >> n;
    vector<array<int, 2>> pos(n + 2);
    for (int i = 1; i <= n; ++i)
        cin >> pos[i][0] >> pos[i][1];
    pos[0] = {1, 1};
    pos[n + 1] = {h, w};
    sort(pos.begin(), pos.end());
    seg.build(1, 1, w);
    seg.update(1, 1, w, 1, 0, 0);
    vector<int> tr(n);
    for (int i = 1; i <= n + 1; ++i) {
        auto& [x, y] = pos[i];
        auto res = seg.query(1, 1, w, 1, y);
        int dp = res.first + 1;
        tr[i] = res.second;
        seg.update(1, 1, w, y, dp, i);
    }
    auto [ans, p] = seg.query(1, 1, w, w, w);
    cout << ans - 1 << '\n';
    string op;
    while (p != 0) {
        auto [x1, y1] = pos[p];
        p = tr[p];
        auto [x2, y2] = pos[p];
        auto dx = abs(x1 - x2);
        auto dy = abs(y1 - y2);
        if (dx) {
            op += string(dx, "UD"[x1 > x2]);
        }
        if (dy) {
            op += string(dy, "LR"[y1 > y2]);
        }
    }
    reverse(op.begin(), op.end());
    cout << op << '\n';

    return 0;
}



G - As far as possible (abc369 G)

题目大意

给定一棵树,边有边权。

对于\(k=1,2,...,n\),要求选 \(k\)个点,使得从 \(1\)号点出发,遍历每个点,最终回到 \(1\)号点的距离的最小值最大。

解题思路

如果我给定了\(k\)个点,怎么求这个的最小值呢。

容易发现答案其实就是这 \(k\)个点到根的路径的的长度的两倍。

\(k=1\)时,很显然我们选择距离根最远的点。

然后当 \(k=2\)时,由于先前的选择,会导致一些点对答案的贡献发生了变化——其到根的路径有一部分与之前选择的点到根的路径有交集,那交集的部分不会有额外的贡献。因此当我们选择一个点后,除了一路沿父亲节点更新贡献外,还要更新父亲兄弟节点及其子树的贡献改变。这个贡献改变自然是一棵子树,通过树的\(dfs\) 序来维护这个贡献改变,其实就是一个区间操作,可以用线段树维护,其复杂度只有\(O(\log)\),而贡献改变会发生多少次呢?一个点最多只会带来一次贡献改变,因此最多区间操作 \(O(n)\)次,因此总的复杂度只有 \(O(n \log n)\)次。

\(val[i]\)表示\(dfs\)序里的第 \(i\)个节点,如果我选择它,它对答案贡献(增加)了多少。每次我们肯定选择最大的 \(val\),选择这个 \(val\)后,会使得一些子树内的节点对答案的贡献减少(减去交集路径长度),每个子树内的节点在 \(dfs\)序里面对应了一个区间,因此我们用线段树维护这个 \(val\)数组,每次查询就是个区间最值,每次更新贡献就是个区间操作。

但如果从另一个角度来看,考虑对这棵树进行长链剖分,容易发现答案就是最长的 \(k\)个长链的长度的两倍。

神奇的代码
#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<vector<array<int, 2>>> edge(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    vector<int> mxson(n, -1);
    vector<LL> deep(n, 0), maxdeep(n, 0);
    function<void(int, int)> dfs1 = [&](int u, int fa) {
        maxdeep[u] = deep[u];
        for (auto [v, w] : edge[u]) {
            if (v == fa)
                continue;
            deep[v] = deep[u] + w;
            dfs1(v, u);
            maxdeep[u] = max(maxdeep[u], maxdeep[v]);
            if (mxson[u] == -1 || maxdeep[mxson[u]] < maxdeep[v]) {
                mxson[u] = v;
            }
        }
    };
    dfs1(0, -1);
    vector<LL> lian;
    function<void(int, int, LL)> dfs2 = [&](int u, int fa, LL dis) {
        for (auto [v, w] : edge[u]) {
            if (v == fa)
                continue;
            if (v == mxson[u])
                dfs2(v, u, dis + w);
            else
                dfs2(v, u, w);
        }
        if (mxson[u] == -1) {
            lian.push_back(dis);
        }
    };
    dfs2(0, -1, 0);
    sort(lian.begin(), lian.end(), greater<LL>());
    int up = 0;
    LL ans = 0;
    for (int i = 0; i < lian.size(); ++i) {
        ans += lian[i];
        cout << ans * 2 << '\n';
    }
    for (int i = lian.size(); i < n; ++i) {
        cout << ans * 2 << '\n';
    }

    return 0;
}