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

AtCoder Beginner Contest 280

时间:2022-12-04 21:36:42浏览次数:63  
标签:AtCoder cout Beginner int cin long using 280 dp

A - Pawn on a Grid (abc280 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);
    int n, m;
    cin >> n >> m;
    int ans = 0;
    for(int i = 0; i < n; ++ i){
        string s;
        cin >> s;
        for(auto c : s)
            ans += (c == '#');
    }
    cout << ans << '\n';

    return 0;
}



B - Inverse Prefix Sum (abc280 b)

题目大意

给定一个数组\(s\),求另一个数组 \(a\),对任意\(k\),满足 \(\sum_{i=0}^{k}a_i = s_k\)

解题思路

对\(s\)数组作出差分数组即可。

神奇的代码
#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 la = 0;
    for(int i = 1; i <= n; ++ i){
        int a;
        cin >> a;
        cout << a - la << ' ';
        la = a;
    }

    return 0;
}



C - Extra Character (abc280 c)

题目大意

给定字符串\(s,t\),其中字符串 \(t\)是串 \(s\)某位插入一个字母得到的。问该位置。

解题思路

逐位比较找到第一个不同字母的位置即为答案。

神奇的代码
#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 s, t;
    cin >> s >> t;
    int pos = t.size();
    for(size_t i = 0; i < s.size(); ++ i)
        if (s[i] != t[i]){
            pos = i + 1;
            break;
        }
    cout << pos << '\n';
    return 0;
}



D - Factorial and Multiple (abc280 d)

题目大意

给定\(k\),求最小的 \(n\),使得 \(n!\)是 \(k\)的倍数。

解题思路

对\(k\)质因数分解,依次对每个质数的幂,求出是其倍数的最小的 \(n\)。答案就是这些 \(n\)的最大值。

而对某一质数\(p\),有贡献的,显然只有\(p!,2p!,3p!,...,xp!\),依次暴力统计这些阶乘有多少个 \(p\) 即可找到最小的\(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);
    LL k;
    cin >> k;
    LL ans = 0;
    int up = sqrt(k);
    for(int i = 2; i <= up; ++ i){
        int cnt = 0;
        while(k % i == 0){
            k /= i;
            ++ cnt;
        }
        LL tmp = 0;
        while(cnt > 0){ // `while(cnt)` will get TLE!
            tmp += i;
            LL cur = tmp;
            while(cur % i == 0){
                cur /= i;
                -- cnt;
            }
        }
        ans = max(ans, tmp);
    }
    ans = max(ans, k);
    cout << ans << '\n';

    return 0;
}



E - Critical Hit (abc280 e)

题目大意

怪物有\(n\)滴血,你对怪物进行攻击,有 \(p\)的概率造成 \(2\)的伤害, \(1-p\)的概率造成 \(1\)的伤害。问打死怪物(血量\(\leq 0\))的期望次数。

解题思路

设\(dp[i]\)表示已经对怪物造成了 \(i\)的伤害,打死怪物需要的期望操作次数。

考虑对怪物的一次操作,有 \(p\)的概率还需要 \(dp[i+2]\)次操作打死怪兽,有 \(1-p\)的概率还需要 \(dp[i+1]\)次操作打死怪兽 ,根据期望的定义,就有

\[dp[i] = 1 + p \times dp[i + 2] + (1 - p) \times dp[i + 1] \]

初始值\(dp[n] = 0, dp[n + 1] = 0\),答案就是 \(dp[0]\)

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

const LL mo = 998244353;

long long qpower(long long a, long long b){
    long long qwq = 1;
    while(b){
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x){
    return qpower(x, mo - 2);
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, p;
    cin >> n >> p;
    vector<int> dp(n + 3, 0);
    LL inv100 = inv(100);
    for(int i = n - 1; i >= 0; -- i){
        dp[i] = 1 + 1ll * p * inv100 % mo * dp[i + 2]  % mo + 1ll * (100 - p) * inv100 % mo * dp[i + 1] % mo;
        dp[i] %= mo;
    }
    cout << dp[0] << '\n';

    return 0;
}


F - Pay or Receive (abc280 f)

题目大意

给定一张\(n\)个点 \(m\)条边的图,边 \((a,b)\)正向权值为 \(c\),逆向权值为 \(-c\)。

\(q\)个询问,每个询问问从 点\(x\)走到点 \(y\),途径的边的权值和的最大值。不可达则为\(nan\),无穷大则为 \(inf\)。

解题思路

真是个妙妙性质题。

不可达用并查集判断即可。

无穷大则说明该连通块存在正权环。

否则所有环的权值为\(0\)。(负的话换个方向走就正了)

那此时两点的边权和必然是个定值。(若两点存在两条路径,其边权和不一样,那它们组成的环的权值就不是\(0\))

此时我们用\(BFS\)预处理从一个点\(u\)出发到所有点的距离数组\(dis[i]\)。那么从 \(x->y\)的距离可以由\(x->u, u->y\)两部分组成,即 \(dis[y] - dis[x]\)。

在预处理过程中如果发现从\(u\)到某点 \(x\)的距离不唯一,那么就一定存在正环了,该连通块的答案就是 \(inf\)。

神奇的代码
#include <bits/stdc++.h>
#include <vector>
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, q;
    cin >> n >> m >> q;
    vector<vector<pair<int, int>>> edge(n);
    vector<int> fa(n);
    iota(fa.begin(), fa.end(), 0);
    function<int(int)> findfa = [&](int x){
        return fa[x] == x ? x : fa[x] = findfa(fa[x]);
    };
    for(int i = 1; i <= m; ++ i){
        int u, v, w;
        cin >> u >> v >> w;
        -- u, -- v;
        edge[u].push_back({v, w});
        edge[v].push_back({u, -w});
        int fu = findfa(u);
        int fv = findfa(v);
        fa[fv] = fu;
    }

    vector<int> neg(n, 0);
    vector<LL> dis(n, INF);

    auto bfs = [&](int s){
        queue<int> team;
        team.push(s);
        dis[s] = 0;
        while(!team.empty()){
            int u = team.front();
            team.pop();
            for(auto [v, w] : edge[u]){
                if (dis[v] == INF){
                    dis[v] = dis[u] + w;
                    team.push(v);
                }else if (dis[v] != dis[u] + w){
                    neg[s] = 1;
                }
            }
        }
    };
    for(int i = 0; i < n; ++ i){
        if (fa[i] == i)
            bfs(i);
    }
    while(q--){
        int u, v;
        cin >> u >> v;
        -- u, -- v;
        int fu = findfa(u);
        int fv = findfa(v);
        if (fu != fv){
            cout << "nan" << '\n';
        }else if (neg[fu] != 0){
            cout << "inf" << '\n';
        }else {
            cout << dis[v] - dis[u] << '\n';
        }
    }

    return 0;
}


G - Do Use Hexagon Grid 2 (abc280 g)

题目大意

<++>

解题思路

<++>

神奇的代码



Ex - Substring Sort (abc280 h)

题目大意

<++>

解题思路

<++>

神奇的代码



标签:AtCoder,cout,Beginner,int,cin,long,using,280,dp
From: https://www.cnblogs.com/Lanly/p/16950858.html

相关文章

  • AtCoder Beginner Contest 280 A-F
    AtCoderBeginnerContest280A-Fhttps://atcoder.jp/contests/abc280个人认为D>>E,F被D搞心态了,导致EF都没看()A-PawnonaGrid统计#的个数#include<bits/stdc......
  • AtCoder Beginner Contest 280
    D-FactorialandMultiple对\(k\)进行质因数分解。如果\(k\)最大的质因子\(p\)满足\(p*p>k\),那么答案就是\(p\)。因为一定要包含一次,也只需要包含一次。......
  • AtCoder Beginner Contest 280
    D-FactorialandMultiple数论  首先上这道题需要的数论知识:n!的素因子分解中,n!=p1^a1*p2^a2*p3^a3*.....*pk^ak中对于素因数pi,其对于的ai=n/pi+n/p......
  • abc--280--F
    F-PayorReceive题目大意给你一个图,查询两个点的最长路边权是正着走是正数,反着走为负数无法到达为nan,无穷大为inf注意:会有重边和自环思路用并查集划分连通块,用df......
  • abc--280--E
    题目大意一个人有n条命,你有p%的概率一次打它两条命,有(100-p)%的概率一次打他一条命求你打死它需要的次数的期望值思路其实也就和走台阶的那个题目是一样的,用dp写就行了......
  • abc--280--D
    D-FactorialandMultiple题目大意找到一个最小的n,使得n的阶乘能整除k思路将它化为一堆的质数,然后满足这些质数至少需要多大的数最后这个找最大的数的时候,直接暴力......
  • AtCoder Beginner Contest 280 题解
    A-PawnonaGrid看样例猜题意(要求的是#的数量,直接判断。//If,oneday,Ifinallymanagetomakemydreamsareality...//Iwonder,willyoustillbethere......
  • AtCoder Beginner Contest 280 D-E
    D-FactorialandMultiple前置知识\(n!\)中包含素因子\(p\)的个数为\[cnt=\sum\limits_{k\geq1}^{p^k\leqn}\lfloor\frac{n}{p^k}\rfloor\]例如:\(n!\)......
  • ORA-28040: 没有匹配的验证协议
    问题:ORA-28040:没有匹配的验证协议原因:Oracle数据库安装的是12.2版本,OracleClient安装的版本是11(ODTwithODAC1120320_32bit)。解决:打开 sqlnet.ora 文件,增加以下两行......
  • mysql学习系列:总结数据库连接不上的数种情况,问题编号:ERROR 1045 (28000)
    (文章目录)场景今天重启CDH的时候,发现重启报错,查看日志才发现是mysql数据库连接不上。在尝试解决的过程中,踩到一些坑。所以总结一下,并分享给大家看看,减少大家伙继续踩坑的......