首页 > 其他分享 >AtCoder Beginner Contest 369

AtCoder Beginner Contest 369

时间：2024-09-07 19:02:31浏览次数：3  
标签：AtCoder Beginner int LL cin vector 369 dp dis

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;
}

标签：AtCoder,Beginner,int,LL,cin,vector,369,dp,dis
From： https://www.cnblogs.com/Lanly/p/18402027

相关文章

  • [luoguAT_abc369_f]Gather Coins
    题意给定\(N\timesM\)的网格，给定\(K\)个二元组\((x_1,y_1),(x_2,y_2),\cdots,(x_K,y_K)\)，求从\((1,1)\)到\((N,M)\)只向右或向下走最多可以经过多少个给定的方格，并给出一种方案。赛时不会赛后由于只能向右或向下走，因此当前所处位置\((nowx,nowy)\)中，\(......
  • [luoguAT_abc369_e] Sight[luoguAT_abc369_e]Sightseeing Tour
    题意给定一个包含\(N\)个点和\(M\)条无向边的带权图，保证图中没有自环，但可能包含重边。给出\(Q\)次查询，每次查询给出\(K\)条边\(B_1,B_2,\cdots,B_K\)，要求求出从节点\(1\)到节点\(N\)且这\(K\)条边都至少经过一次的最短路（经过边的方向和顺序任意）。赛时Dijkstra......
  • 题解：AT_abc369_e [ABC369E] Sightseeing Tour 详细版
    题目大意给定一个NNN个点，MMM条边的无向图。其中边有边权。有......
  • 题解：SP3693 KGSS - Maximum Sum
    原题传送门思路分析线段树。这道题让我们进行两种操作，分别是单点修改和区间查询，结合数据范围，很明显是一道线段树。区间里最大的\(A_i+A_j\)，其实就是求区间里的最大值和次大值，我们用线段树维护最大值和次大值。建树voidbuild(intnow,inttl,inttr){ if(tl==tr){ tmax......
  • ABC369
     C对于一个等差数列，它里面包含的等差数列（取这个数列的第i位~第j位），必定也是等差数列。寻找等差数列的时候，如果一个等差数列，向最左/最右加1个数后，仍是等差数列，则把它们加上。从而寻找所有场上的等差数列，必定是不重叠的，等差数列彼此独立。从而可以从1遍历到n，O(n)复杂度。对于每......
  • AtCoder Beginner Contest 369 题ABCD详细题解--包含解题思路和两种语言(C++,Python)
    前言:    本文为AtCoderBeginnerContest369题ABCD详细题解，包括题目大意，详细的解题思路和两种语言描述，觉的有帮助或者写的不错可以点个赞几天前的比赛拖的有点久了比赛题目连接：Tasks-AtCoderBeginnerContest369目录题A:题目大意和解题思路:代码(C++):......
  • AtCoder ABC 369题解
    前言本题解部分思路来源于网络，仅供参考！A-369题目大意给定\(A\)，\(B\)两个整数，求有多少个整数\(x\)使得可以通过某种排列使得\(A\)，\(B\)，\(x\)为等差数列。解题思路稍加分析即可得到：如果\(A=B\)则结果为\(1\)。如果\(A=B\)但\((A+B)\bmod......
  • [ABC369G] As far as possible
    考虑删除树上一条边\((u,v,l)\)，此时剩余部分构成两个连通块，如果不包含节点\(1\)的连通块中有Aoki选择的点，那个这条边的贡献至少为\(2l\)。简单构造发现，当Takahashi构造的路径恰好为Aoki选择的点和\(1\)构成的虚树时，能够取到路径长度的最小值。此时我们将题目转......
  • 8.31 晚上 ABC369 总结 & 题解
    打了一天的比赛。ABCD太水了，直接放代码链接得了，点字母就能看对应代码。E-SightseeingTour看范围$N$只有$400$，所以我们可以先用floyd搞出任意两点间的距离。对于每次询问，发现$K_i$只有$5$，所以可以直接深搜应该走哪座桥，和应该走到哪一端。时间复杂度$O(N3+QK_i......
  • ABC369F F - Gather Coins 题解
    题目链接：https://atcoder.jp/contests/abc369/tasks/abc369_f题目大意：在一个\(H\timesW\)的二维迷宫中有\(N\)枚硬币，其中第\(i\)枚硬币在\((R_i,C_i)\)（本题中，我们用\((r,c)\)表示二维迷宫中从上到下第\(r\)行从左到右第\(c\)列的那个格子）。你一开始在迷宫的左......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99