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

AtCoder Beginner Contest 293

时间：2023-03-17 20:12:47浏览次数：44  
标签：AtCoder cnt return Beginner int LL cin using 293

上周因为GDKOI咕咕咕了

A - Swap Odd and Even (abc293 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 s;
    cin >> s;
    for(int i = 0; i < s.size(); i += 2)
        swap(s[i], s[i + 1]);
    cout << s << '\n';

    return 0;
}

B - Call the ID Number (abc293 b)

题目大意

每人有一个标号和一个叫号，第\(i\)个人标号为 \(i\)，叫号为 \(a_i\)。

依次对每个人，如果此人的标号没被叫到，则此人会叫其叫号，否则直接到下一个人。

问最终有多少人不会叫。

解题思路

按照题意模拟即可。

其实题意都没看懂，看了样例才明白。

神奇的代码 
#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> call(n, 0);
    for(int i = 0; i < n; ++ i){
        int x;
        cin >> x;
        -- x;
        if (call[i] == 0)
            call[x] = 1;
    }
    int ans = count(call.begin(), call.end(), 0);
    cout << ans << '\n';
    for(int i = 0; i < n; ++ i){
        if (call[i] == 0)
            cout << i + 1 << ' ';
    }
    cout << '\n';

    return 0;
}

C - Make Takahashi Happy (abc293 c)

题目大意

二维网格，左上走到右下，一次往右或往下走一格。格子上有数字。

问有多少种路径，其走过的数据互不相同。

解题思路

网格只有\(10 \times 10\)，暴力复杂度是 \(O(2^{20})\)，直接搜即可。

神奇的代码 
#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<vector<int>> g(h, vector<int>(w, 0));
    for(auto &i : g)
        for(auto &j : i)
            cin >> j;
    int ans = 0;
    set<int> qwq;
    function<void(int, int)> dfs = [&](int x, int y){
        if (x == h - 1 && y == w - 1){
            ++ ans;
            return;
        }
        if (x != h - 1 && qwq.count(g[x + 1][y]) == 0){
            qwq.insert(g[x + 1][y]);
            dfs(x + 1, y);
            qwq.erase(g[x + 1][y]);
        }
        if (y != w - 1 && qwq.count(g[x][y + 1]) == 0){
            qwq.insert(g[x][y + 1]);
            dfs(x, y + 1);
            qwq.erase(g[x][y + 1]);
        }
    };
    qwq.insert(g[0][0]);
    dfs(0, 0);
    cout << ans << '\n';

    return 0;
}

D - Tying Rope (abc293 d)

题目大意

\(n\)条绳子， \(m\)个捆绑操作。

每个操作将两个绳子的一端绑起来。一端最多只能被捆绑一次。

问最终得到了多少个环形绳子和非环形绳子。

解题思路

将每个绳子看成一个点，绑起来相当于连一条边。

绳子只有两端意味着每个点至多只有两条边与其相连。

因此每条边，要么是环上的边，要么是链上的边，不会是环里横跨环的边。

即最终的图只有两种：\(x\)个点 \(x\)条边的环，以及 \(x\)个点 \(x-1\)条边的链。

因此我们就统计一下最终图的连通块的数量，做做容斥就出来了。（考虑一条边减少一个连通块）

而统计连通块的数量则用并查集。

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

class dsu {
    public:
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p.resize(n);
        sz.resize(n);
        iota(p.begin(), p.end(), 0);
        fill(sz.begin(), sz.end(), 1);
    }

    inline int get(int x) {
        return (x == p[x] ? x : (p[x] = get(p[x])));
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            p[x] = y;
            sz[y] += sz[x];
            return true;
        }
        return false;
    }
};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    dsu d(n);
    for(int i = 0; i < m; ++ i){
        int x, y;
        string s;
        cin >> x >> s >> y >> s;
        -- x;
        -- y;
        d.unite(x, y);
    }
    int cnt = 0;
    for(int i = 0; i < n; ++ i)
        cnt += (d.get(i) == i);
    int ans1 = m - (n - cnt), ans2 = cnt - ans1;
    cout << ans1 << ' ' << ans2 << '\n';

    return 0;
}

E - Geometric Progression (abc293 e)

题目大意

给定\(a,x,m\)，求 \(\sum_{i=0}^{x-1}a^i \mod m\)

解题思路

因为递推式和求和式都是线性的，因此可以用矩阵来求。

\[\left[ \begin{matrix} a^i \\ s_{i-1} \end{matrix} \right] = \left[ \begin{matrix} a & 0 \\ 1 & 1 \end{matrix} \right] \left[ \begin{matrix} a^{i-1} \\ s_{i-2} \end{matrix} \right] \]

因此就中间那个矩阵的\(x\)次幂 \(\times\)初始矩阵状态就能得到其和 \(s_n\)了。

初始矩阵就是

\[\left[ \begin{matrix} 1 \\ 0 \\ \end{matrix} \right] \]

而\(x\)次幂则用快速幂的形式求即可。

如果用等比数列的话需要求\(a-1\)在 \(m\)下的逆元，而这必须得保证 \(a-1\)与 \(m\)互质，题意没保证，故无法求。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

LL MOD;

struct Mat {
    static const LL M = 2;
    LL v[M][M];
    Mat() { memset(v, 0, sizeof v); }
    void eye() { FOR (i, 0, M) v[i][i] = 1; }
    LL* operator [] (LL x) { return v[x]; }
    const LL* operator [] (LL x) const { return v[x]; }
    Mat operator * (const Mat& B) {
        const Mat& A = *this;
        Mat ret;
        FOR (k, 0, M)
            FOR (i, 0, M) if (A[i][k])
                FOR (j, 0, M)     
                    ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
        return ret;
    }
    Mat pow(LL n) const {
        Mat A = *this, ret; ret.eye();
        for (; n; n >>= 1, A = A * A)
            if (n & 1) ret = ret * A;
        return ret;
    }
    Mat operator + (const Mat& B) {
        const Mat& A = *this;
        Mat ret;
        FOR (i, 0, M)
            FOR (j, 0, M)
                 ret[i][j] = (A[i][j] + B[i][j]) % MOD;
        return ret;
    }
    void prt() const {
        FOR (i, 0, M)
            FOR (j, 0, M)
                 printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
    }
};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    LL a, x, m;
    cin >> a >> x >> m;
    MOD = m;
    Mat qwq;
    qwq[0][0] = a;
    qwq[1][0] = qwq[1][1] = 1;
    Mat ans = qwq.pow(x);
    LL res = ans[1][0];
    cout << res << '\n';

    return 0;
}

F - Zero or One (abc293 f)

题目大意

给定一个数字\(x\)，问多少个 \(b\)，使得 \(x\)在 \(b\)进制下，每个数位要么是 \(0\)要么是 \(1\)。

多组询问。

解题思路

随着\(b\)增大， \(x\)在 \(b\)进制下的数位的数量是越来越小的。

我们可以暴力判断小的进制是否符合要求，对于大的进制，因为位数很少，可以花 \(2^n\)枚举每个数位的状态（是\(0\)还是\(1\)），再二分一下进制\(b\)，看看是否存在一个进制满足上述要求。

神奇的代码 
#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 t;
    cin >> t;
    while(t--){
        LL x;
        cin >> x;
        int up = min(5000ll, x);
        int ans = 1;
        auto check1 = [&](int base){
            LL tmp = x;
            while(tmp){
                if ((tmp % base) > 1)
                    return false;
                tmp /= base;
            }
            return true;
        };
        for(int i = 3; i <= up; ++ i){
            ans += check1(i);
        }
        int up2 = log(x) / log(up) + 1;
        auto check2 = [&](int s){
            __int128 l = up + 1, r = x + 1;
            auto solve = [&](__int128 val){
                __int128 tmp = 1, sum = 0;
                int tmps = s;
                for(int i = 0; i < up2; ++ i){
                    sum += tmp * (tmps & 1);
                    tmp *= val;
                    tmps >>= 1;
                }
                return sum;
            };
            while(l + 1 < r){
                __int128 mid = (l + r) >> 1;
                __int128 sum = solve(mid);
                if (sum >= 0 && sum <= x) // sum < 0 => overflow => sum > x 
                    l = mid;
                else 
                    r = mid;
            }
            return solve(l) == x;
        };
        for(int i = 0; i < (1 << up2); ++ i){
            ans += check2(i);
        }
        cout << ans << '\n';
    }

    return 0;
}

G - Triple Index (abc293 g)

题目大意

给定一个\(n\)个数字的数组\(a\)，和 \(q\)组询问，每组询问给定 \(l,r\)，问有多少个 \(l \leq i < j < k \leq r\)，满足 \(a_i = a_j = a_k\)

解题思路

考虑一个询问，其答案就是\(\sum \binom{cnt[i]}{3}\)，其中 \(cnt[i]\)表示这个该询问区间中数字 \(i\)的数量。

注意到当询问区间发生变化时， \(cnt\)数组非常容易维护，且每次移位只有一个 \(cnt\)值发生变化。因此离线莫队即可。

神奇的代码 
#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, q;
    cin >> n >> q;
    vector<int> a(n);
    for(auto &i : a)
        cin >> i;
    vector<LL> cnt(200001, 0);
    vector<array<int, 2>> query(q);
    for(auto &i : query){
        cin >> i[0] >> i[1];
        i[0] --;
    }
    vector<int> id(q, 0);
    int blk_num = sqrt(q), blk_size = q / blk_num;
    vector<int> belong(n);
    for(int i = 0; i < blk_num; ++ i){
        for(int j = i * blk_size; j < (i + 1) * blk_size && j < n; ++ j)
            belong[j] = i;
    }
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int a, int b){
        if (belong[query[a][0]] != belong[query[b][0]]){
            return belong[query[a][0]] < belong[query[b][0]];
        }else {
            return bool((query[a][1] < query[b][1]) ^ (belong[query[a][0]] & 1));
        }
        });
    int l = 0, r = 0;
    vector<LL> ans(q);
    LL cur = 0;
    auto mv = [&](int pos, int val){
        int num = a[pos];
        if (cnt[num] >= 3)
            cur -= cnt[num] * (cnt[num] - 1) * (cnt[num] - 2) / 6;
        cnt[num] += val;
        if (cnt[num] >= 3)
            cur += cnt[num] * (cnt[num] - 1) * (cnt[num] - 2) / 6;
    };
    for(auto &i : id){
        int L = query[i][0], R = query[i][1];
        debug(L, R);
        while(l > L)
            mv(-- l, 1);
        while(r < R)
            mv(r ++, 1);
        while(l < L)
            mv(l ++, -1);
        while(r > R)
            mv(-- r, -1);
        ans[i] = cur;
    }
    for(auto &i : ans)
        cout << i << '\n';

    return 0;
}

Ex - Optimal Path Decomposition (abc293 h)

题目大意

给定一棵树，要求对每个节点涂色，最小化数字\(k\)，使得：

  • 每个颜色的节点构成一个连通块
  • 任意一条简单路径上，节点的颜色种类不超过\(k\)

求该 \(k\)。

解题思路

<++>

神奇的代码

标签：AtCoder,cnt,return,Beginner,int,LL,cin,using,293
From： https://www.cnblogs.com/Lanly/p/17228010.html

相关文章

  • AtCoder Beginner Contest 293(C,D ,E,F)
    AtCoderBeginnerContest293(C,D,E,F)CC这道题其实还蛮好写的，就是一个\(dfs\),然后我看错了题意，就记录一下这道题的大意是我们需要从\((1,1)\)走到\((n,m)\),我们只......
  • [AtCoder Beginner Contest 281][G. Farthest City]
    和CF1657E的做法十分相似题目链接：G-FarthestCity题目大意：问有多少个\(n(3\len\le500)\)个点的无向连通图满足，若设\(1\)到\(i\)的最短路距离为\(dis_i\)，则......
  • AtCoder Regular Contest 158
    Preface这场比赛刚好周日晚上没事就打了，堪堪混过三道题，也算是小上了一波分吧但是由于A题脑抽了一波卡了30min，导致排名不高，也没时间看DE了，属实有点可惜A-+3+5+7显......
  • AtCoder Beginner Contest 293
    题解报告基本的一些理解和问题都在注释中A：SwapOddandEven//水题#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>usingnamespace......
  • AtCoder Beginner Contest 240 F
    ABC240F思路维护前缀和B，以及B的前缀和C，然后在每次添加连续y个x的时候，从中找出最大的\(C_i\)(用pre记录)，更新答案。有四种情况\(B\geq0,x>0\)那么新出现的\(C_i\)中......
  • atcoder ABC
    Ex-OptimalPathDecomposition题目只能给链染色，问你最短的（两点距离最大值），距离为不同颜色个数f[u],g[u]，f表示u可以和father同一个颜色，g表示不可以。转移记录三个值。......
  • ABC 293 ABCD(并查集)
    A-SwapOddandEven#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PII;constLLMAXN=1e18,MINN=-1e18;constLLN=1e6......
  • ATABC293D Tying Rope
    ATABC293DTyingRope题意有\(N\)根一端涂成红色，另一端涂成蓝色的绳子，现进行\(M\)次操作，第\(i\)次操作给出两个整数\(A_i\)，\(C_i\)与两个字符\(B_i\)，\(D_i\)，表......
  • 题解 ABC293D【Tying Rope】
    颜色是不好处理的，我们不妨不区分绳子的两个端点，将每条绳子作为一个节点，每条边直接将两个节点连接起来。每个绳子的端点本质上是保证了每个点的度数不超过\(2\)，也就是说图......
  • 题解 ABC293E【Geometric Progression】
    由于模数不一定是大质数，我们不能直接套等比数列求和公式。换一种思路，数列\(\langle1,A,A^2,\cdots,A^{X-1}\rangle\)可以看做线性递推，因此设计矩阵：\[\boldsymbolT=\b......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99