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

AtCoder Beginner Contest 371

时间：2024-09-14 22:51:50浏览次数：8  
标签：AtCoder Beginner int LL cin vector 371 id mod

A - Jiro (abc371 A)

题目大意

三个人，给定他们相互之间的大小关系。

问谁在中间。

解题思路

排个序，大小结果就是题目给的，因为问的是中间是谁，所以写的时候并没在意是升序排还是降序排。

神奇的代码 
#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);
    string a, b, c;
    cin >> a >> b >> c;
    array<int, 3> id{};
    iota(id.begin(), id.end(), 0);
    map<pair<int, int>, int> mp;
    mp[{0, 1}] = a[0] == '>';
    mp[{1, 0}] = a[0] == '<';
    mp[{0, 2}] = b[0] == '>';
    mp[{2, 0}] = b[0] == '<';
    mp[{1, 2}] = c[0] == '>';
    mp[{2, 1}] = c[0] == '<';
    sort(id.begin(), id.end(), [&](int x, int y) { return mp[{x, y}]; });
    string ans = "ABC";
    cout << ans[id[1]] << '\n';

    return 0;
}

B - Taro (abc371 B)

题目大意

\(n\)个家庭，依次出生 \(m\)个孩子，每个家庭的第一个出生的男婴儿会授予名字 taro。

依次回答每个孩子的名字是不是taro。

解题思路

维护每个家庭是否有男婴儿出生，然后依次判断每个孩子是不是男的，且是第一个男的即可。

神奇的代码 
#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, m;
    cin >> n >> m;
    vector<int> tora(n, 0);
    while (m--) {
        int f;
        string s;
        cin >> f >> s;
        --f;
        if (s[0] == 'F' || tora[f]) {
            cout << "No" << '\n';
        } else {
            tora[f] = 1;
            cout << "Yes" << '\n';
        }
    }

    return 0;
}

C - Make Isomorphic (abc371 C)

题目大意

给定两张无向图\(G,H\)。

给定一个操作代价，在图\(H\)中给\((i,j)\)连一条边或删一条边的花费 \(a_{ij}\)。

问最小的代价，使得两张图同构。

解题思路

同构即存在一种点标号的映射关系，使得映射后两张图一模一样（包括点标号和对应的边）。

由于点数只有\(8\)，我们先花 \(O(8!)\)枚举这个映射（即一个排列），然后看这个映射关系下，使得两张图相等所需要的代价。

计算代价即花\(O(n^2)\)的时间，枚举所有的边\((i,j), i < j\)，如果 \(G\)存在该边但\(H\)不存在或\(G\)不存在但 \(H\)存在，进行一次操作。 所有的操作代价累加即为该映射关系的操作代价。

所有的映射关系的代价的最小值即为答案。

时间复杂度为\(O(n!n^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;
    array<int, 2> m{};
    array<vector<vector<int>>, 2> edge{vector<vector<int>>(n, vector<int>(n)),
                                       vector<vector<int>>(n, vector<int>(n))};
    for (int k = 0; k < 2; ++k) {
        cin >> m[k];
        for (int i = 0; i < m[k]; ++i) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            edge[k][u][v] = edge[k][v][u] = 1;
        }
    }
    vector<vector<int>> a(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            cin >> a[i][j];
            a[j][i] = a[i][j];
        }
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    int ans = 1e9 + 7;
    auto solve = [&](vector<int> id) {
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (edge[0][id[i]][id[j]] != edge[1][i][j]) {
                    res += a[i][j];
                }
            }
        }
        return res;
    };
    do {
        ans = min(ans, solve(id));
    } while (next_permutation(id.begin(), id.end()));

    cout << ans << '\n';

    return 0;
}

D - 1D Country (abc371 D)

题目大意

一维数轴，给定\(n\)个村落的位置和人口。

\(q\)个询问，每个询问给定 \(l,r\)，问位于\(l,r\)之间的村落人口数量。

解题思路

题意给的村落位置本身有序。

直接维护关于村落的人口前缀和。

对于每个询问，二分找到位于\(l,r\)区间的村落的左右端点，然后通过前缀和求得这期间的人口数量。

时间复杂度是\(O(q\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> x(n);
    for (auto& i : x)
        cin >> i;
    vector<LL> p(n);
    for (auto& i : p)
        cin >> i;
    vector<LL> presum(n);
    partial_sum(p.begin(), p.end(), presum.begin());
    auto get_sum = [&](int l, int r) {
        if (l > r)
            return 0ll;
        return presum[r] - (l ? presum[l - 1] : 0);
    };
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        auto L = lower_bound(x.begin(), x.end(), l) - x.begin();
        auto R = upper_bound(x.begin(), x.end(), r) - x.begin();
        cout << get_sum(L, R - 1) << '\n';
    }

    return 0;
}

E - I Hate Sigma Problems (abc371 E)

题目大意

给定\(n\)个数 \(a\)，定义 \(f(l,r)\)表示区间 \([l,r]\)的数的种类。

求 \(\sum_{i=1}^{n}\sum_{j=i}^{n} f(i,j)\)

解题思路

考虑枚举\(j\)的话会发现不太可行，考虑直接的一个排列 \(1,2,3,4,5...\)，对于每个 \(j\)，每个\(i\)都对应了一个不同的\(f(i,j)\) ，感觉无法合并。

考虑答案的来源，即贡献的来源，是每一个数。比如\(2,3,2,5\)， \(f(2,3) = 2 = 1 + 1\)， \(3,2\)分别对答案有 \(1\)的贡献。而 \(f(1,3) = 2 = 1 + 1\)，这里同样是 \(3,2\)对答案有 \(1\)的贡献，但这里有两个 \(2\)，只有其中的一个才有 \(1\)的贡献，我们可以规定最右边的 \(2\)有 \(1\)的贡献。

我们的视角从 求\(f(l,r)\)的值 变成了求 每一个数 \(a_i\) 在多少个区间 \((l,r)\)有 \(1\)的贡献。

很显然，这个\(l\)的取值是 \([1,l]\)， 而\(r\)的取值要满足 \([i,r]\)没有另一个 \(a_i\)，即计 \(nxt_i\)表示下一个 \(a_i\)的位置，那么 \(r\)的取值就是 \([i,nxt_i)\)。因此对于一个\(a_i\)，它有贡献的区间数量即为 \(i \times (nxt_i - i)\) 。所有的\(a_i\)累加即为答案。

而 \(nxt_i\)的求法就倒序扫一遍，维护 \(last_i\)表示上一个数 \(i\)出现的位置即可。

即答案就是 \(\sum_{i=1}^{n} i(nxt_i - i)\)，时间复杂度是\(O(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;
        --i;
    }
    vector<int> r(n);
    vector<int> pos(n, n);
    for (int i = n - 1; i >= 0; --i) {
        r[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    fill(pos.begin(), pos.end(), 0);
    LL ans = 0;
    for (int i = 0; i < n; ++i) {
        int lcnt = i + 1;
        int rcnt = r[i] - i;
        ans += 1ll * lcnt * rcnt;
    }
    cout << ans << '\n';

    return 0;
}

F - Takahashi in Narrow Road (abc371 F)

题目大意

一维数轴，\(n\)个人，依次完成以下 \(q\)个目标。

对于第 \(i\)个目标，让第 \(t_i\)个人移动到 \(q_i\)位置。

每次操作，可以让一个人向左右移动一格，如果目标位置有人则不能移动，得让对方先移动。

求完成所有目标所需要的最小操作次数。

解题思路

研究G题了这题还没看

神奇的代码

G - Lexicographically Smallest Permutation (abc371 G)

题目大意

给定两个排列\(p,a\)。

可进行一种操作任意次，即令 \(a_i = a_{p_i}\)。

问得到的 \(a\)的字典序的最小值。

解题思路

替换操作可以看成是有若干个环的图，有连边\(i \to p_i\)。

问题就是求一个 \(x\)，使得每个点往前走 \(x\)步，得到的新的数组的字典序最小。

由字典序的比较顺序，首先是让第一个数最小。

那就找第一个数所在的环，遍历一遍，找到数最小的位置，得到一个偏移量 \(b\)。记该环的大小为\(a\)。

这样，只要我们最后的偏移量 \(x\)满足 \(x \equiv b (\mod a)\)，这样第一个位置就是最小的情况。

然后考虑下一个数所在的环（如果和\(1\)在同一个环，就忽略，继续找下一个不在之前考虑的环），在该环中，我们同样要找最小的值，但和之前直接遍历环的每个元素不同，由于之前有个限制\(x \equiv b (\mod a)\)，因此在该环里，我们只能看第\(x\)个点，第 \(x + a\)个点，第 \(x + 2a\)个点，...，这哪个点权最小（要保持不破坏之前考虑的环的偏移量）。

假设在有限个点，我们找到数最小的位置 \(B\)，即该环的大小为 \(A\)，那就是说，我们最终的偏移量 \(x\)要满足两个同余等式： \(x \equiv b (\mod a)\)和\(x \equiv B (\mod A)\)，通过扩展中国剩余定理可以将其合并成一个等价的同余式\(x \equiv b_0 (\mod a_0)\)。

然后就继续遍历剩下的环，不断合并同余式，最后偏移量就是\(b_0 \% a_0\)。

据官方题解，\(a,b\)的值会超\(2^{2367}\)，因此下面的\(c++\)代码尽管开了 __in128仍会爆。

c++代码 
#include <bits/stdc++.h>
using namespace std;
using LL = __int128;

LL x, y, d;

void exgcd(LL& x, LL& y, LL a, LL b) {
    if (!b)
        d = a, x = 1, y = 0;
    else
        exgcd(y, x, b, a % b), y -= a / b * x;
}

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }

LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }

LL a, b, A, B;

void merge() {
    exgcd(x, y, a, A);
    LL c = B - b;
    assert(c % d == 0);
    x = x * c / d % (A / d);
    if (x < 0)
        x += A / d;
    LL mod = lcm(a, A);
    b = (a * x + b) % mod;
    if (b < 0)
        b += mod;
    a = mod;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> p(n), v(n);
    for (auto& i : p) {
        cin >> i;
        --i;
    }
    for (auto& i : v)
        cin >> i;
    vector<vector<int>> cir;
    vector<int> vis(n);
    for (int i = 0; i < n; ++i) {
        if (vis[i])
            continue;
        vector<int> h{i};
        for (int j = p[i]; j != i; j = p[j]) {
            vis[j] = 1;
            h.push_back(j);
        }
        cir.push_back(h);
    }
    a = 1;
    b = 0;
    for (int i = 0; i < cir.size(); ++i) {
        auto& h = cir[i];
        int id = b % h.size();
        vector<int> used(h.size(), 0);
        for (int i = id;; i = (i + a) % h.size()) {
            if (used[i])
                break;
            used[i] = 1;
            if (v[h[i]] < v[h[id]])
                id = i;
        }
        A = h.size();
        B = id;
        if (i > 0)
            merge();
        else
            a = A, b = B;
    }
    LL step = b % a;
    vector<int> ans(n);
    for (auto& h : cir) {
        for (int i = 0, j = step % h.size(); i < h.size();
             i++, j = (j + 1) % h.size()) {
            ans[h[i]] = v[h[j]];
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << " \n"[i == n - 1];
    }

    return 0;
}

怎么办呢，用chatgpt改成pythonb吧jls的代码貌似没用高精，研究研究

python代码 
# 扩展欧几里得算法
def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return d, x, y

# 求最大公约数
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

# 求最小公倍数
def lcm(a, b):
    return a // gcd(a, b) * b

# 初始化全局变量
x, y, d = 0, 0, 0
a, b, A, B = 0, 0, 0, 0

# 合并两个同余方程
def merge():
    global a, b, A, B, x, y, d
    d, x, y = exgcd(a, A)
    c = B - b
    assert c % d == 0
    x = (x * (c // d)) % (A // d)
    if x < 0:
        x += A // d
    mod = lcm(a, A)
    b = (a * x + b) % mod
    if b < 0:
        b += mod
    a = mod

def main():
    n = int(input())
    p = [int(i) - 1 for i in input().split()]
    v = list(map(int, input().split()))

    # 寻找环
    cir = []
    vis = [0] * n
    for i in range(n):
        if vis[i]:
            continue
        h = [i]
        vis[i] = 1
        j = p[i]
        while j != i:
            vis[j] = 1
            h.append(j)
            j = p[j]
        cir.append(h)

    global a, b, A, B
    a, b = 1, 0
    for i, h in enumerate(cir):
        id = b % len(h)
        used = [0] * len(h)
        j = id
        while not used[j]:
            used[j] = 1
            if v[h[j]] < v[h[id]]:
                id = j
            j = (j + a) % len(h)
        A = len(h)
        B = id
        if i > 0:
            merge()
        else:
            a, b = A, B

    step = b % a
    ans = [0] * n
    for h in cir:
        for i in range(len(h)):
            j = (step + i) % len(h)
            ans[h[i]] = v[h[j]]

    print(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

标签：AtCoder,Beginner,int,LL,cin,vector,371,id,mod
From： https://www.cnblogs.com/Lanly/p/18414807

相关文章

  • AtCoder Beginner Contest 371
    ABC371总结AtCoderBeginnerContest371一些废话想着以后换一种方式写总结，不再以那种题解形式，写起来又累又难写，只对其中部分有意思的题目写出完整的题解。就是以随笔的形式，在打完比赛后写出自己的一些感悟，每道题做的过程中的一些思路、用时和需要改进的地方，就是类似随笔之类的......
  • AtCoder Beginner Contest 371
    https://atcoder.jp/contests/abc371C:暴力。思路是把1-8的点映射到全排列上面，然后把有的点去掉没的点加上取ans最小值。这题复杂度是\(8！\times7\times4\),暴力求全排列即可（第一次写暴力全排列思索了一会复杂度#include<bits/stdc++.h>usingnamespacestd;#definepiipai......
  • 题解 [ABC371G] Lexicographically Smallest Permutation（中文/English）
    本题解提供英文版，位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.官方题解竟然用Python来算高精度lcm，我来提供一个可以避免一切大整数运算的方法。考察\(u\getsP_u\)这张图的每个置换环。为了使答案字典序最小，显然需要从前往后......
  • Taro（ABC 371）
    #include<bits/stdc++.h>#defineendl'\n'#defineintllusingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();signedmain(){#ifdefGordenfreopen("in.txt","rt",stdi......
  • AtCoder Beginner Contest 370 补题记录
    A-RaiseBothHands题意：给出Snuke举的左右手情况，如果只举左手，输出Yes，如果只举右手，输出No，否则输出Invalid思路：举左手：（l==1&&r==0)举右手：(l==1&&r==0)其他情况都是Invalidvoidsolve(){intl=read(),r=read();if(l==1&&r==0){......
  • AtCoder Beginner Contest 274 A~E 题解
    吐槽：这比赛名字为啥没有英文版。。。A-BattingAverage题目大意给定整数\(A,B\)，输出\(\fracBA\)，保留三位小数。\(1\leA\le10\)\(0\leB\leA\)分析签到题，使用printf或cout格式化输出即可。代码#include<cstdio>usingnamespacestd;intmain(){ inta,b; sc......
  • TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 29
    好久没写题解了，这就来水一篇。A-JobInterview题目大意给定一个长为\(N\)的字符串\(S\)，由o、-、x组成。判断\(S\)是否符合下列条件：\(S\)中至少有一个o。\(S\)中没有x。\(1\leN\le100\)分析签到题。直接按题意模拟即可。代码#include<cstdio>usingn......
  • AtCoder Beginner Contest 318 G - Typical Path Problem 题解
    G-TypicalPathProblem题目大意给定一张\(N\)个点、\(M\)条边的简单无向图\(G\)和三个整数\(A,B,C\)。是否存在一条从顶点\(A\)到\(C\)，且经过\(B\)的简单路径？数据范围：\(3\leN\le2\times10^5\)\(N-1\leM\le\min(\frac{N(N-1)}2,2\times10^5)\)\(1\leA......
  • UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
    A-ChristmasPresent题目大意给定两个正整数\(B,G\)（\(1\leB,G\le1000\)且\(B\neG\)），判断哪个更大。分析模拟即可。代码#include<cstdio>usingnamespacestd;intmain(){ intb,g; scanf("%d%d",&b,&g); puts(b>g?"Bat":&qu......
  • AtCoder Beginner Contest 254 A~E 题解
    A-LastTwoDigits题目大意给定正整数\(N\)，求\(N\)的后两位。\(100\leN\le999\)输入格式\(N\)输出格式输出\(N\)的后两位，注意输出可能有前导0。样例\(N\)输出\(254\)54\(101\)01分析题目已经规定\(N\)是三位数，因此无需使用整数输入，直接将输入看成......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99