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

AtCoder Beginner Contest 375

时间：2024-10-13 20:00:11浏览次数：1  
标签：AtCoder Beginner int mint cin long vector using 375

A - Seats

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int long long

using vi = vector<int>;
using pii = pair<int,int>;


i32 main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N;
    cin >> N;

    string S;
    cin >> S;

    int res = 0;
    for(int i = 0; i + 2 < N; i ++) 
        if(S[i] == '#' and S[i + 2] == '#' and S[i + 1] == '.')
            res ++;
    cout << res;
    return 0;
}

B - Traveling Takahashi Problem

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int long long

using vi = vector<int>;
using pii = pair<int,int>;


i32 main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N;
    cin >> N;

    double res = 0;

    int lx = 0, ly = 0;
    for(int i = 1, x, y; i <= N; i ++) {
        cin >> x >> y;
        res += hypot(x - lx, y - ly);
        lx = x, ly = y;
    }
    res += hypot(lx, ly);
    cout << fixed << setprecision(20) << res;
    return 0;
}

C - Spiral Rotation

通过找规律发现，题目可以这样理解。

把矩形分成\(\frac N 2\)圈，从外向内，第一圈旋转\(\frac \pi 2\)，第二圈旋转\(2\frac{\pi}{2}\)，第三圈旋转\(3\frac \pi 2\)，第四圈旋转\(4\frac{\pi}{2}\)，并以此类推。

知道这个规律的话，我们就可以\(O(1)\)计算出每个点被移动到哪里。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int long long

using vi = vector<int>;
using pii = pair<int,int>;


i32 main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N;
    cin >> N;

    vector A(N + 1, vector<char>(N + 1));
    for(int i = 1; i <= N; i ++)
        for(int j = 1; j <= N; j ++)
            cin >> A[i][j];
    
    vector B(N + 1, vector<char>(N + 1));


    for(int i = 1; i <= N; i ++) {
        for(int j = 1; j <= N; j ++) {
            int t = min({i , j , N - i + 1, N - j + 1});
            int n = N - 2 * (t - 1), p = t % 4, q = 2 * t - 2;
            int x = i, y = j;
            while(p --) {
                int nx = y, ny = n - x + 1 + q;
                x = nx, y = ny;
            }
            B[x][y] = A[i][j];
        }
    }

    for(int i = 1; i <= N; i ++){
        for(int j = 1;j <= N; j ++){
            cout << B[i][j];
        }
        cout << "\n";
    }
    return 0;
}

D - ABA

可以分别统计前后缀每种字母出现的次数，然后可以直接枚举出回文串的样子。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int long long

using vi = vector<int>;
using pii = pair<int,int>;


i32 main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s;
    cin >> s;

    int n = s.size();

    vi pre(26), suf(26);
    for(int i = 2; i < n; i ++)
        suf[s[i] - 'A'] ++;
    pre[s[0] - 'A'] ++;


    int res = 0;
    for(int i = 1; i + 1 < n; i ++){
        for(int j = 0; j < 26; j ++)
            res += pre[j] * suf[j];
        pre[s[i] - 'A'] ++;
        suf[s[i + 1] - 'A'] --;
    }

    cout << res;
    return 0;
}

E - 3 Team Division

这里的换并不是交换，而是可以直接换，因此我们可以直接 dp。

这状态为\(f[i][x][y]\)表示前\(i\)个人，当前第\(1\)队权值和为\(x\)，第 2 队权值和为\(y\)的最小操作次数。

然后可以直接暴力枚举状态并转移即可。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int long long

using vi = vector<int>;
using pii = pair<int,int>;

const int inf = INT_MAX / 2;

i32 main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    
    int sum = 0;
    vector<pii> p(n);
    for(auto &[a, b] : p)
        cin >> a >> b, a --, sum += b;

    if(sum % 3 != 0) {
        cout << "-1\n";
        return 0;
    } 
    sum /= 3;
    vector f(sum + 1, vi(sum + 1, inf));

    f[0][0] = 0;

    for(int pre = 0;auto &[a , b] : p){
        pre += b;
        vector g(sum + 1, vi(sum + 1, inf));
        for(int x = 0, y; x < 3; x ++ ) {
            y = (x != a);
            for(int i = 0; i <= sum; i ++){
                for(int j = 0; j <= sum; j ++){
                    if(x == 0) {
                        if(i - b >= 0) g[i][j] = min(g[i][j], f[i - b][j] + y);
                    }else if(x == 1){
                        if(j - b >= 0) g[i][j] = min(g[i][j], f[i][j - b] + y);
                    } else {
                        if(pre - i - j - b >= 0) g[i][j] = min(g[i][j], f[i][j] + y);
                    }
                }
            }
        }
        f = move(g);
    }
    
    int res = f[sum][sum];
    if(res == inf) res = -1;
    cout << res;
    return 0;
}

F - Road Blocked

我们可以离线，然后倒序做，此时删边操作就变成了加边。

每加入一条边，我们就可以把边所影响的点对进行松弛操作，因为加边的次数不超过\(300\)，因此总的复杂度就是 floyd

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int long long

using vi = vector<int>;
using pii = pair<int,int>;

const int inf = LLONG_MAX / 3;

i32 main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;

    vector<array<int,3>> edge(m);

    for(auto &[u, v, w] : edge)
        cin >> u >> v >> w;

    vector<bool> closed(m);

    vector<vi> query(q);
    for(int op, x, y; auto &it : query) {
        cin >> op;
        if(op == 1) {
            cin >> x, x --;
            closed[x] = true;
            it.push_back(x);
        } else {
            cin >> x >> y;
            it.push_back(x);
            it.push_back(y);
        }
    }

    vector dis(n + 1, vi(n + 1, inf));
    for(int i = 1; i <= n; i ++) dis[i][i] = 0;
    for(int i = 0; i < m; i ++) {
        if(closed[i]) continue;
        const auto &[u, v, w] = edge[i];
        dis[u][v] = dis[v][u] = min(dis[u][v], w);
    }

    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++) {
            if(i == k) continue;
            for(int j = 1; j < i; j ++) {
                if(j == k) continue;
                dis[i][j] = dis[j][i] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }

    ranges::reverse(query);
    
    vi res;
    for(auto it : query) {
        if(it.size() == 1) {
            const auto &[u, v, w] = edge[it[0]];
            dis[u][v] = dis[v][u] = min(dis[u][v], w);
            for(int i = 1; i <= n; i ++ )
                for(int j = 1; j < i; j ++ )
                    dis[i][j] = dis[j][i] = min({dis[i][j], dis[i][u] + w + dis[v][j], dis[i][v] + w + dis[u][j]});
        } else {
            int x = it[0], y = it[1];
            if(dis[x][y] == inf) res.push_back(-1);
            else res.push_back(dis[x][y]);
        }
    }
    ranges::reverse(res);
    for(auto i : res) cout << i << "\n";
    return 0;
}

G - Road Blocked 2

题目要求的是，哪些边被所有的最短路经过。

首先我们考虑如何求出一条边是否被最短路经过。我们从\(1\)求一遍最短路记为\(d1\)，从\(n\)求一遍最短路记为\(dn\)。

对于一条边\((u,v,w)\)如果满足\(d1[u] + w + dn[v] = d1[n]\)则证明这条边在至少在一条最短路上。

我们在求最短路的过程中，还可以dp 求出从起点到当前点最短路的方案数，以\(1\)为起点记为\(c1\)，以\(n\)为起点记为\(cn\)。

那么如果\(c1[u]\times cn[v] = c1[n]\)则说明当前边被所有的最短路经过。

这里的方案数可能分到，我们比较模意义下即可。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int long long

using vi = vector<int>;
using pii = pair<int,int>;

const int inf = LLONG_MAX / 2;
const int mod = 998244353;

struct mint {
    int x;

    mint(int x = 0) : x(x) {}

    void norm(){
        x = (x % mod + mod) % mod;
        return;
    }

    mint &operator=(int o) { return x = o, *this; }

    mint &operator+=(mint o) { return (x += o.x) >= mod && (x -= mod), *this; }

    mint &operator-=(mint o) { return (x -= o.x) < 0 && (x += mod), *this; }

    mint &operator*=(mint o) { return x = (i64) x * o.x % mod, *this; }

    mint &operator^=(int b) {
        mint w = *this;
        mint ret(1);
        for (; b; b >>= 1, w *= w) if (b & 1) ret *= w;
        return x = ret.x, *this;
    }

    mint &operator/=(mint o) { return *this *= (o ^= (mod - 2)); }

    friend mint operator+(mint a, mint b) { return a += b; }

    friend mint operator-(mint a, mint b) { return a -= b; }

    friend mint operator*(mint a, mint b) { return a *= b; }

    friend mint operator/(mint a, mint b) { return a /= b; }

    friend mint operator^(mint a, int b) { return a ^= b; }

    friend bool operator==(mint a, mint b) {
        a.norm(), b.norm();
        return a.x == b.x;
    }
};


i32 main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m;

    vector<array<int,3>> edge(m);
    vector<vector<pii>> e(n + 1);

    for(auto &[u, v, w] : edge) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }

    auto dij  = [=](int s) {
        vi dis(n + 1, inf), vis(n + 1);
        vector<mint> cnt(n + 1);
        dis[s] = 0, cnt[s] = 1;;
        priority_queue<pii,vector<pii>, greater<>> heap;
        heap.emplace(0, s);

        while(not heap.empty()) {
            auto [d, x] = heap.top();
            heap.pop();
            if(vis[x]) continue;
            vis[x] = 1;
            for(auto [y, w] : e[x]) {
                if(dis[y] < d + w) continue;
                if(dis[y] == d + w) {
                    cnt[y] += cnt[x];
                    continue;
                } 
                dis[y] = d + w, cnt[y] = cnt[x];
                heap.emplace(dis[y], y);
            }
        }
        return pair(dis, cnt);
    };

    auto [d1, c1] = dij(1);
    auto [dn, cn] = dij(n);

    for(auto &[u, v, w] : edge){
        if(d1[u] + w + dn[v] == d1[n] and c1[u] * cn[v] == c1[n])
            cout << "Yes\n";
        else if(d1[v] + w + dn[u] == d1[n] and c1[v] * cn[u] == c1[n])
            cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

另一个思路是，我们把所有至少被一条最短路经过的边取出来，建新图。对新图求一下桥即可。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int long long

using vi = vector<int>;
using pii = pair<int,int>;

const int inf = LLONG_MAX / 2;

i32 main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m;

    vector<array<int,3>> edge(m);
    vector<vector<pii>> e(n + 1);

    for(auto &[u, v, w] : edge) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }

    auto dij  = [=](int s) {
        vi dis(n + 1, inf), vis(n + 1);
        dis[s] = 0;
        priority_queue<pii,vector<pii>, greater<>> heap;
        heap.emplace(0, s);

        while(not heap.empty()) {
            auto [d, x] = heap.top();
            heap.pop();
            if(vis[x]) continue;
            vis[x] = 1;
            for(auto [y, w] : e[x]) {
                if(vis[y]) continue;
                if(dis[y] <= d + w) continue;
                dis[y] = d + w;
                heap.emplace(dis[y], y);
            }
        }
        return dis;
    };

    auto d1 = dij(1), dn = dij(n);

    vector<vector<pii>> g(n + 1);
    for(int i = 0; i < m; i ++) {
        const auto &[u, v, w] = edge[i];
        if(d1[u] + w + dn[v] == d1[n])
            g[u].emplace_back(v, i), g[v].emplace_back(u, i);
        else if(d1[v] + w + dn[u] == d1[n])
            g[u].emplace_back(v, i), g[v].emplace_back(u, i);
    }

    vi bridges(m), dfn(n + 1), low(n + 1), fa(n + 1);
    int cnt = 0;

    auto tarjan = [&](auto &&tarjan, int x) -> void {
        low[x] = dfn[x] = ++ cnt;
        for(auto [y, id]: g[x]) {
            if(!dfn[y]) {
                fa[y] = x, tarjan(tarjan, y);
                low[x] = min(low[x], low[y]);
                if(low[y] > dfn[x]) bridges[id] = 1;
            } else if(fa[x] != y) {
                low[x] = min(low[x], dfn[y]);
            }
        }
        return;
    };

    for(int i = 1; i <= n; i ++)
        if(!dfn[i]) tarjan(tarjan, i);

    for(auto i : bridges){
        if(i) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

标签：AtCoder,Beginner,int,mint,cin,long,vector,using,375
From： https://www.cnblogs.com/PHarr/p/18462861

相关文章

  • パナソニックグループ プログラミングコンテスト2024（ABC 375）
    罚时不好吃，一口都没吃形象理解这一场的CA.Seats\(\text{diff}20\)对给定序列\(S\)找出\(i\)的个数,使得\(S_{i}=0,S_{i+1}=1,S_{i+2}=0\)#defineintlonglongstringx;signedmain(){ intn;cin>>n; cin>>x; intans=0; for(inti=0;i<=(int)x.length(......
  • Panasonic Programming Contest 2024（AtCoder Beginner Contest 375）
    PanasonicProgrammingContest2024（AtCoderBeginnerContest375）\(A\)Seats\(AC\)基础字符串。点击查看代码intmain(){intn,ans=0,i;strings;cin>>n>>s;for(i=0;i<n;i++){ans+=(s[i]=='#'&&s[i......
  • AtCoder Beginner Contest 375
    省流版A.枚举所有子串判断即可B.模拟计算记录累加即可C.根据旋转的周期性对每个点旋转次数取模后暴力旋转即可D.枚举\(k\)，考虑\(i,j\)的对数，写成数学表达式后维护个数和位置和即可E.背包问题，以前两个数组和为状态，考虑每个数移动到何处转移即可F.逆向，删边变加边，维护......
  • KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374）E题
    六年级蒟蒻来题解了！！！题目大意：给定你一个n，表示有n个生产线，每一个生产线都有两种机器，第i个生产线第一件产品每天可以造Ai件零件但是得付出Pi元的代价，第二件产品每天可以生产Bi件物品但是得付出Qi元的代价，然后给你x元的预算问你所有流水线中的最小值的最大值是多少？思路：首先我们......
  • AtCoder Beginner Contest 373 (A-F)
    AtCoderBeginnerContest373(A-F)比赛链接A-September#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voidShowball(){intans=0;for(inti=1;i<=12;i++){strings;cin>>s;ans+=((int)s.si......
  • 洛谷P3375
    kmp算法：扫描字符串A，并且更新可以匹配到B的什么位置。时间复杂度O(n)。P[i]表示当前模式串在该位置匹配冲突时，应该将模式串的哪一位与此对齐。总之就是扫描字符串A，并更新2可以匹配到什么位置点击查看代码#include<bits/stdc++.h>#defineiosios::sync_with_stdio(false);c......
  • 【做题笔记】Atcoder 之 dp 专题训练
    ABCDEFGHI概率dp。设\(dp_{i,j}\)表示前\(i\)个硬币中有\(j\)个正面的概率。转移显然：\(dp_{i,j}=dp_{i-1,j-1}\timesp_i+dp_{i-1,j}\times(1-p_i)\)当\(j=0\)时，前\(i\)个硬币中没有正面。所以只能由反面的概率转移过来，转移为：\(dp_{i,j}=dp_{i-1,j}\time......
  • 洛谷题单指南-字符串-P3375 【模板】KMP
    原题链接：https://www.luogu.com.cn/problem/P3375题意解读：给定两个字符串：原串s，模式串p，求p在s中出现的所有位置，并输出p的长度为1~p.size()的子串的最长相同真前、后缀的长度。解题思路：KMP模版题，分两问，第一问通过KMP核心算法实现，第二问输出模式串的Next数组内容，接下来一一解读。......
  • AtCoder Beginner Contest 374(D-E)
    A-C：惯例是宝宝题，会打暴力就能过哈D：其实也是暴力dfs，有一个double打错成int（我是猪鼻），卡了我很久#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e3+10,eps=1e-7;intn,s,t;boolvis[10];doublesum=1e8;structNode{ doublex,y,x1,y1;}a[maxn];doub......
  • キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）
    A.Takahashisan2判断一个字符串是否以san结尾usingnamespacereader;intmain(){strings;cin>>s;if(s[s.length()-1]=='n'ands[s.length()-2]=='a'ands[s.length()-3]=='s'){cout<<"Yes";......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99