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

AtCoder Beginner Contest 305

时间：2023-06-10 22:47:00浏览次数：51  
标签：AtCoder Beginner int LL 305 long cin ++ trans

A - Water Station (abc305 a)

题目大意

给定一个数字\(x\)，输出一个数字，它是最接近\(x\)的 \(5\)的倍数。

解题思路

令\(y = x \% 5\)，如果 \(y \leq 2\)，那答案就是 \(x - y\)，否则就是 \(x + 5 - y\)。

神奇的代码 
#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 x;
    cin >> x;
    int mod = x % 5;
    if (mod <= 2)
        x -= mod;
    else 
        x += 5 - mod;
    cout << x << '\n';

    return 0;
}

B - ABCDEFG (abc305 b)

题目大意

给定\(ABCDEFG\)的相邻距离，给定两个字母，问它们的距离。

解题思路

累加距离即可。

神奇的代码 
#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);
    array<int, 7> dis{3,1,4,1,5,9};
    string a, b;
    cin >> a >> b;
    if (a > b)
        swap(a, b);
    int ans = accumulate(dis.begin() + a[0] - 'A', dis.begin() + b[0] - 'A', 0);
    cout << ans << '\n';

    return 0;
}

C - Snuke the Cookie Picker (abc305 c)

题目大意

二维平面，有一个矩形少了一块，问这一块的位置。

解题思路

找到矩形的左上和右下，然后遍历矩形的每一块看看是不是少了。

神奇的代码 
#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 h, w;
    cin >> h >> w;
    vector<string> s(h);
    for(auto &i : s)
        cin >> i;
    int sx = h, sy = w, ex = 0, ey = 0;
    for(int i = 0; i < h; ++ i)
        for(int j = 0; j < w; ++ j){
            if (s[i][j] == '#'){
                sx = min(sx, i);
                sy = min(sy, j);
                ex = max(ex, i);
                ey = max(ey, j);
            }
        }
    int ansx = 0, ansy = 0;
    for(int i = sx; i <= ex; ++ i)
        for(int j = sy; j <= ey; ++ j){
            if (s[i][j] == '.'){
                ansx = i;
                ansy = j;
            }
        }
    cout << ansx + 1 << ' ' << ansy + 1 << '\n';

    return 0;
}

D - Sleep Log (abc305 d)

题目大意

给定一个睡觉日志\(a\)，从\(0\)开始（题目从\(1\)开始），奇数项表示醒来的分钟数，偶数项表示开睡的分钟数。

回答\(q\)组询问，每组询问 \(l, r\)，问从第 \(l\)分钟到第 \(r\)分钟，共睡了多久。

解题思路

因为分钟数高达\(10^9\)，因此不能每分钟的累加。

先对睡觉日志求一遍睡眠时间的前缀和。

对于询问 \(l, r\)，先找到第一个大于等于其的日志分钟数位置 \(posl, posr\)。

答案首先加上 \(a[posl] \to a[posr]\)的睡眠分钟数（前缀和得出），缺少了时间段 \(l \to a[posl]\)和额外的时间段 \(r \to a[posr]\)，判断其是否是睡眠的时间段，从而加回答案或减去即可。

神奇的代码 
#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<LL> a(n);
    for(auto &i : a)
        cin >> i;
    vector<LL> presum(n);
    for(int i = 2; i < n; i += 2){
        presum[i] = presum[i - 1] + a[i] - a[i - 1];
        if (i < n)
            presum[i + 1] = presum[i];
    }
    int q;
    cin >> q;
    while(q --){
        int l, r;
        cin >> l >> r;
        int posl = lower_bound(a.begin(), a.end(), l) - a.begin();
        int posr = lower_bound(a.begin(), a.end(), r) - a.begin();
        LL ans = presum[posr] - presum[posl];
        if (~posl & 1)
            ans += a[posl] - l;
        if (~posr & 1)
            ans -= a[posr] - r;
        cout << ans << '\n';
    }

    return 0;
}

E - Art Gallery on Graph (abc305 e)

题目大意

给定一张\(n\)个点 \(m\)条边的无向图，边权为\(1\)。有\(k\)个关键点，每个关键点\(k_i\)可以监视距离不超过 \(h_i\)的点。

一个点若被至少一个关键点监视，则称该点被监视。

升序给出被监视点的标号。

解题思路

题意就是问每个点距离一堆特殊点的距离是否满足要求。初看没什么思路，因为\(k\)和\(n\)是同一个数量级，因此不能 \(k\)次 \(BFS\)。但忽然想到了GXOI/GZOI2019 旅行者，里面为了求一些点到一些点的最短距离，额外增加了个起点和终点，这样求一次最短路就可以了。

同样的道理，我们可以也增加一个起点\(st\)，该起点与 \(k\)个关键点都连边。至于边权，因为每个关键点的监视距离不一样，因此为了统一最后的判断（距离起点 \(st\)的距离），我们设关键点中最大的监视距离为 \(maxx\)，则 \(st \to k_i\)的边权为 \(maxx - h_i\)，这样最后从起点跑一遍最短路后，与起点距离不超过 \(maxx\)的点都被监视了。

注意这个起点\(st\)是我们额外加的，实际不存在，要防止关键点通过起点监视了其他点，因此要设 \(k_i \to st\)的距离为无穷大。

因为增加了额外点和额外边，边权不再是\(1\)了。因此不能跑 \(BFS\)，可以跑 \(Dijkstra\)。

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

const int inf = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<array<int, 2>>> edge(n + 1);
    auto add = [&](int u, int v, int w = 1, int w2 = 1){
        edge[u].push_back({v, w});
        edge[v].push_back({u, w2});
    };
    for(int i = 0; i < m; ++ i){
        int a, b;
        cin >> a >> b;
        -- a, -- b;
        add(a, b);
    }
    int st = n;
    int mstamina = 0;
    vector<array<int, 2>> p(k);
    for(auto &i : p){
        cin >> i[0] >> i[1];
        i[0] --;
        mstamina = max(mstamina, i[1]);
    }
    for(auto &i : p){
        add(st, i[0], mstamina - i[1], inf);
    }
    priority_queue<array<int, 2>> team;
    vector<int> dis(n + 1, inf);
    team.push({0, st});
    dis[st] = 0;
    while(!team.empty()){
        auto [expect, u] = team.top();
        team.pop();
        if (dis[u] != -expect)
            continue;
        for(auto &[v, w] : edge[u]){
            if (dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                team.push({-dis[v], v});
            }
        }
    }
    vector<int> ans;
    for(int i = 0; i < n; ++ i)
        if (dis[i] <= mstamina && dis[i] != inf){
            ans.push_back(i + 1);
        }
    cout << ans.size() << '\n';
    for(auto &i : ans)
        cout << i << ' ';
    cout << '\n';

    return 0;
}

F - Dungeon Explore (abc305 f)

题目大意

交互题。

一张无向图，但你不知道具体情况。从 \(1\)出发到 \(n\)。

一开始处于\(1\)号点。

当你处于 \(i\)号点，裁判会告诉你与 \(i\)号点相邻的点。

你需要决定下一个去的点的编号。

在移动不超过\(2n\)次走到点 \(n\)。

解题思路

其实就是一个\(DFS\)过程，\(DFS\)过程维护点的访问状态，每个点最多进栈一次出栈一次，因此在不超过 \(2n\)次就可以遍历所有的点，因此也能到达点 \(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, m;
    cin >> n >> m;
    vector<int> visit(n + 1, 0);
    function<void(int)> dfs = [&](int u){
        if (u == n){
            exit(0);
        }
        int k, _;
        cin >> k;
        vector<int> nxt(k);
        for(auto &i : nxt)
            cin >> i;
        for(auto &i : nxt){
            if (!visit[i]){
                cout << i << endl;
                visit[i] = 1;
                dfs(i);
                cout << u << endl;
                for(int i = 0; i <= k; ++ i)
                    cin >> _;
            }
        }
    };
    visit[1] = 1;
    dfs(1);

    return 0;
}

G - Banned Substrings (abc305 g)

题目大意

给定\(m\)个 \(ab\)字符串。

问有多少种长度为 \(n\)的字符串，其子串不包括这 \(m\)个字符串。

\(n \leq 10^{18}\)

解题思路

一眼原，找到了两年前写的代码，直接复制粘贴（

对这\(m\)个字符串建立 \(AC\)自动机，然后问题就转换成有多少条长度为 \(n\)的路径，其不经过一些特殊点。

经典路径计数问题，\(dp[i][j]\)表示从起点出发，不经过特殊点，走了\(i\)个点，最终到达点 \(j\) 的方案数。转移就是从\(i-1\)中枚举 \(j\)的相邻点转移。

因为 \(n\)很大，且转移式子是线性的，\(dp\)转移可以写成矩阵的形式，快速幂一下就得到结果了。

神奇的代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 300
    #define M 2

    int trans[N][M];
    int fail[N];
    int sign[N];
    int tot;

    public:
    void insert(const char *s){
        int cur = 0;
        sign[cur] = 0;
        for(int i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - '0']){
                trans[cur][s[i] - '0'] = ++ tot;
                sign[tot] = 0;
            }
            cur = trans[cur][s[i] - '0'];
        }
        sign[cur] = 1;
    }

    void build(){
        queue<int> team;
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int j = 0; j < M; ++ j){
                if (trans[u][j]){
                    fail[trans[u][j]] = trans[fail[u]][j];
                    team.push(trans[u][j]);
                }else{
                    trans[u][j] = trans[fail[u]][j];
                }
                sign[trans[u][j]] |= sign[fail[trans[u][j]]];
            }
        }
    }

    friend LL work(LL);
}AC;

const LL mo = 998244353;

class Matrix{
    public:
    LL a[300][300];
    int n;

    Matrix(int ss,int val = 0){
        n=ss;
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j){
                a[i][j] = val;
            }
    }

    Matrix(const Matrix & b){
        n = b.n;
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < n; ++ j){
                a[i][j] = b.a[i][j];
            }
        }
    }

    Matrix operator * (const Matrix & b){
        Matrix tmp(this->n);
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j)
                for(int k = 0; k < n; ++ k)
                    tmp.a[i][j] = (a[i][k] * b.a[k][j] % mo + tmp.a[i][j]) % mo;
        return tmp;
    }

    void print(){
        for(int i = 0; i < n ; ++ i){
            for(int j = 0; j < n; ++ j){
                printf("%lld%c",a[i][j],j==n-1?'\n':' ');
            }
        }
    }
};

Matrix qpower(Matrix a, LL b){
    Matrix tmp(a.n);
    for(int i = 0; i < a.n; ++ i)
        tmp.a[i][i] = 1;
    while(b){
        if (b&1) tmp = tmp * a;
        a = a * a;
        b >>= 1;
    }
    return tmp;
}

LL work(LL n){
    int cnt = AC.tot;
    Matrix ma(cnt+1);
    for(int i = 0; i <= cnt; ++ i){
        for(int j = 0; j < M; ++ j){
            ++ ma.a[i][AC.trans[i][j]];
        }
    }
    int qaq = 0;
    for(int i = 0; i <= cnt; ++ i){
        if (! AC.sign[i]) ++ qaq;
    }
    Matrix tmp(qaq);
    int x = -1, y = 0;
    for(int i = 0; i <= cnt; ++ i){
        if (AC.sign[i]) continue;
        y = 0;
        ++ x;
        for (int j = 0; j <= cnt; ++ j){
            if (AC.sign[j]) continue;
            tmp.a[x][y] = ma.a[i][j];
            ++ y;
        }
    }
    // tmp.print();
    Matrix qwq = qpower(tmp,n);
    LL ans = 0;
    for(int i = 0; i < qaq; ++ i)
        ans = (ans + qwq.a[0][i]) % mo;
    return ans;
}

char s[15];

int main(){
    int m;
    LL n;
    read(n);
    read(m);
    while(m--){
        scanf("%s",s);
        for(size_t i = 0; s[i]; ++ i){
            switch(s[i]){
                case 'a' : s[i] = '0'; break;
                case 'b' : s[i] = '1'; break;
            }
        }
        AC.insert(s);
    }
    AC.build();
    LL ans;
    ans = work(n);
    write(ans,'\n');
    return 0;
}

不过本题的字符串只包含\(01\)，可以直接矩阵优化 \(dp\)转移。

Ex - Shojin (abc305 h)

题目大意

给定\(n\)个二元组 \((a,b)\)。

将二元组拆分成\(k\)段，让每段的代价的和不超过 \(x\)。

问最小的 \(k\)，以及对应的最小代价和。

每段的代价和定义如下：

首先可以对该段的二元组任意排序，然后初始代价 \(x\)，对每个二元组\((a,b)\)依次计算 \(x = ax + b\)。最后的 \(x\)就是该段的代价。

解题思路

<++>

神奇的代码

标签：AtCoder,Beginner,int,LL,305,long,cin,++,trans
From： https://www.cnblogs.com/Lanly/p/17472104.html

相关文章

  • ATCoder [ABC167D] Teleporter
    #题目解析这段代码的目标是处理一个含有$n$个元素的整数序列，根据一定的规则，重复操作$k$次后，确定操作结束时位于序列哪个位置。##解题思路1.**读取输入**：首先，我们读取输入的整数$n$和$k$，以及整数序列`a`。我们需要对序列的每个元素减一，以适应从0开始的索引。cin......
  • AtCoder Beginner Contest 290 Ex Bow Meow Optimization
    洛谷传送门AtCoder传送门考虑观察答案形态。当\(n,m\)均为偶数时，前一半位置有\(\frac{n}{2}\)个是狗，\(\frac{m}{2}\)个是猫。并且前半段从前往后和后半段从后往前都是按权值从小到大放。调整法证明即可。当\(n\)或\(m\)为奇数时，把\(a_i\)或\(b_i\)最大的放中间......
  • Atcoder ARC100D Equal Cut
    发现是\(3\)个断点且数据范围的\(n\le2\times10^5\)，根据2022CSP-SA留下的心理阴影不难想到可以枚举中间的那个点的同时移动左右两个端点。考虑如何移动，已知现在在枚举中间的断点\(i\)，则现在被分为了两部分\(1\simi\)和\(i\simn\)，因为要使极差最小，那就先可以让每一......
  • Atcoder ABC221G Jumping sequence
    发现这个\((x,y)\)对应的是曼哈顿距离不太好求，那直接逆时针旋转\(45\)度（其实应该还要伸长\(\sqrt{2}\)倍，但是可以当做\(d_i\)也伸长\(\sqrt{2}\)倍不用去管）转化成切比雪夫距离\((x-y,x+y)\)。同时对应的\(4\)个方向在旋转后对应的方向也得到了改变：\(U(-d,d),......
  • SONiC 202305 Release内容
    SONiC社区采用Github平台进行项目管理，Github平台不仅仅提供代码的托管服务，还能提供IsuueTracking，Releasemanagement等RequirementEngineering的功能。在GithubSONiC页面上选择Projects/SONiC202305Release以后，可以看到表格的形式显示的该Release计划的77个Issue的内容。到......
  • AtCoder Beginner Contest 240 D
    D-StrangeBallstag：栈模拟发现自己隔了快半年再做此题看错相同数字的球消失的条件，不是\(k\geq2\)而是\(k=a_i\)电子竞技不需要视力题意：当球\(a_i(1\leqi\leqN)\)有\(a_i\)个一起出现时，这\(a_i\)个球就会消失，问每次放一个球进去，放进去后还剩多少个球？用个......
  • AtCoder Beginner Contest 150 E Change a Little Bit
    洛谷传送门AtCoder传送门令\(S_i\getsS_i\oplusT_i\)，那么代价中\(D\)变成\(S_i=1\)的\(i\)数量。转化为对所有\(f(S)\)求和，最后答案乘上\(2^n\)。考虑贪心地求\(f(S)\)。肯定是先选择小的\(C_i\)，把\(S_i\)变成\(0\)。正确性显然。下面把\(C_i\)从大到......
  • AtCoder Beginner Contest 281 Ex Alchemy
    洛谷传送门AtCoder传送门考虑设\(f_i\)为\(i\)的答案，那么：\[f_i=[x_i](1+x)^A\prod\limits_{j=2}^{i-1}(1+f_jx)\]这个东西其实是可以分治FFT的。具体地，设分治区间为\([l,r]\)，要求一个\(r-l+1\)次多项式\(\prod\limits_{i=l}^r(1+f_ix)\)。......
  • AtCoder Beginner Contest 287 G Balance Update Query
    洛谷传送门AtCoder传送门线段树上二分入门题。考虑一个贪心：每次询问按\(a_i\)从大到小选。正确性显然。考虑动态开点线段树，每个结点\(a_i\in[l,r]\)存\(\sum\limits_{a_i\in[l,r]}b_i\)和\(\sum\limits_{a_i\in[l,r]}a_ib_i\)。线段树上二分找到第一个\(......
  • AtCoder Beginner Contest 258 G Grid Card Game
    洛谷传送门AtCoder传送门记\(b_i=\sum\limits_{j=1}^ma_{i,j},c_j=\sum\limits_{i=1}^na_{i,j}\)。首先考虑这样一个事情，就是对于\(b_i\le0\)的行有没有可能被选。如果选了它：如果没有选任何列，选这一行肯定不优；如果选了若干列，根据题目的要求，这若干列与这......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99