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

AtCoder Beginner Contest 284

时间：2023-01-07 21:55:26浏览次数：69  
标签：AtCoder cout Beginner int LL cin long using 284

A - Sequence of Strings (abc284 a)

题目大意

顺序给定\(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<string> qwq(n);
    for(auto &i : qwq)
        cin >> i;
    reverse(qwq.begin(), qwq.end());
    for(auto &i : qwq)
        cout << i << '\n';

    return 0;
}

B - Multi Test Cases (abc284 b)

题目大意

给定\(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 t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int ans = 0;
        while(n--){
            int x;
            cin >> x;
            ans += (x & 1);
        }
        cout << ans << '\n';
    }

    return 0;
}

C - Count Connected Components (abc284 c)

题目大意

给定一张图，问连通块个数。

解题思路

并查集维护连通性即可。

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

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

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

  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;
      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 u, v;
        cin >> u >> v;
        u--;
        v--;
        d.unite(u, v);
    }
    int ans = 0;
    for(int i = 0; i < n; ++ i)
        ans += (d.get(i) == i);
    cout << ans << '\n';



    return 0;
}

D - Happy New Year 2023 (abc284 d)

题目大意

给定一个数\(N = p^2q\)，其中 \(pq\)为质数，问 \(pq\)是多少。

解题思路

注意\(N \leq 9 \times 10^{18}\)，预处理质数到\(3e6\)，而不能是 \(1e6\)。

枚举\(p\)，因为题意保证了 \(N\)一定是 \(p^2q\)的形式，所以一旦 \(N \mod p^2 == 0\)就找到解了， \(q\)也一定是质数。

\(p\)枚举到 \(3e6\)后，再往上时 \(q\)的大小是小于 \(1e6\)的，所以\(p\)枚举到\(3e6\)后我们改为枚举 \(q\)，进行剩下的情况的判断即可。

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = unsigned 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)

const LL p_max = 3E6 + 100;
LL pr[p_max], p_sz;
void get_prime() {
    static bool vis[p_max];
    FOR (i, 2, p_max) {
        if (!vis[i]){
            pr[p_sz++] = i;
        }
        FOR (j, 0, p_sz) {
            if (pr[j] * i >= p_max) break;
            vis[pr[j] * i] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    get_prime();
    int t;
    cin >> t;
    while(t--){
        LL n;
        cin >> n;
        FOR(i, 0, p_sz){
            LL p = pr[i];
            LL pp = p * p;
            if (n % p == 0){
                LL tmp = n / p;
                LL sq = sqrt(tmp);
                if (sq * sq == tmp){
                    cout << sq << ' ' << p << '\n';
                    break;
                }
            }
            if (n % pp == 0){
                LL tmp = n / pp;
                cout << p << ' ' << tmp << '\n';
                break;
            }
        }
    }

    return 0;
}

E - Count Simple Paths (abc284 e)

题目大意

给定一张图，问从\(1\)号点（编号从 \(1\)开始）的简单路径（不经过重复点）条数 \(k\)，输出 \(\min(k, 10^6)\)

解题思路

直接对原图进行\(DFS\)，由于每搜到一个状态就是一条未搜过的路径，因此搜到 \(10^6\)后直接退出搜索即可。

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

const int up = 1e6;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edge(n);
    for(int i = 0; i < m; ++ i){
        int u, v;
        cin >> u >> v;
        -- u;
        -- v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int ans = 0;
    vector<int> visit(n, 0);
    function<void(int)> dfs = [&](int u){
        visit[u] = 1;
        ++ ans;
        if (ans >= up)
            return;
        for(auto &v : edge[u]){
            if (visit[v])
                continue;
            dfs(v);
            if (ans >= up)
                return;
        }
        visit[u] = 0;
    };
    dfs(0);
    cout << ans << '\n';

    return 0;
}

F - ABCBAC (abc284 f)

题目大意

给定字符串\(s\)，\(n = len(s),i\) ，函数\(f_i(s)\)为以下三个字符串的拼接：

  • \(s[1:i]\)
  • \(s\)的翻转
  • \(s[i+1, n]\)

给定长度为\(2n\)的字符串\(t\)，找出一个长度为\(n\)的字符串\(s\)和 \(i\)满足 \(f_i(s) = t\)，或告知不存在。

解题思路

枚举\(i\)，\(f_i(s)\)就是由三部分\(p\)组成，剩下的就是判断第一部分\(p_1\)与第二部分 \(p_2\)的对应长度的后半部分是否互为回文串，以及 \(p_3\)和 \(p_2\)的对应长度的前半部份是否互为回文串。

令 \(s\prime\)为 串\(s\)的翻转，上述两个条件就是问 \(s\prime\)和 \(s\)对应子串是否相同，用字符串hash即可在 \(O(1)\)的时间判断。

总的复杂度就是\(O(n)\)。

这题还卡了\(1e9+7\)的模数，要换个模数或者双hash.

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

#define ENABLE_DOUBLE_HASH

const int x = 135;
const int N = 2e6 + 10;
const int p1 = 1e9 + 7, p2 = 1e9 + 9;
ULL xp1[N], xp2[N], xp[N];

void init_xp() {
    xp1[0] = xp2[0] = xp[0] = 1;
    for (int i = 1; i < N; ++i) {
        xp1[i] = xp1[i - 1] * x % p1;
        xp2[i] = xp2[i - 1] * x % p2;
        xp[i] = xp[i - 1] * x;
    }
}

struct String {
    char s[N];
    int length, subsize;
    bool sorted;
    ULL h[N], hl[N];

    ULL hash() {
        length = strlen(s);
        ULL res1 = 0, res2 = 0;
        h[length] = 0;  // ATTENTION!
        for (int j = length - 1; j >= 0; --j) {
        #ifdef ENABLE_DOUBLE_HASH
            res1 = (res1 * x + s[j]) % p1;
            res2 = (res2 * x + s[j]) % p2;
            h[j] = (res1 << 32) | res2;
        #else
            res1 = res1 * x + s[j];
            h[j] = res1;
        #endif
            // printf("%llu\n", h[j]);
        }
        return h[0];
    }

    // 获取子串哈希，左闭右开区间
    ULL get_substring_hash(int left, int right) const {
        int len = right - left;
    #ifdef ENABLE_DOUBLE_HASH
        // get hash of s[left...right-1]
        unsigned int mask32 = ~(0u);
        ULL left1 = h[left] >> 32, right1 = h[right] >> 32;
        ULL left2 = h[left] & mask32, right2 = h[right] & mask32;
        return (((left1 - right1 * xp1[len] % p1 + p1) % p1) << 32) |
               (((left2 - right2 * xp2[len] % p2 + p2) % p2));
    #else
        return h[left] - h[right] * xp[len];
    #endif
    }

    void init(const char *t) {
        length = strlen(t);
        strcpy(s, t);
    }
};

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    init_xp();
    int n;
    string s;
    cin >> n >> s;
    string t = s;
    reverse(t.begin(), t.end());
    String S, T;
    S.init(s.c_str());
    S.hash();
    T.init(t.c_str());
    T.hash();
    auto solve = [&](){
        for(int i = 0; i <= n; ++ i){
            int len1 = n - i;
            int len2 = i;
            if (S.get_substring_hash(i, i + len1) == T.get_substring_hash(0, len1) && 
                S.get_substring_hash(0, len2) == T.get_substring_hash(len1, len1 + len2))
                return i;
        }
        return -1;
    };
    int i = solve();
    if (i == -1)
        cout << i << '\n';
    else {
        cout << t.substr(n - i, n) << '\n' << i << '\n';
    }

    return 0;
}

G - Only Once (abc284 g)

题目大意

对于一个长度为\(n\)的数组 \(A\)，其中\(1 \leq a_i \leq n\)。 对于\(1\leq i \leq n\),定义一个长度为\(10^{100}\) 的数组 \(B_i\) ：

  • \(B_{i,1} = i\)
  • \(B_{i,j + 1} = A_{B_{i, j}} (1 \leq j < 10^{100})\)

令\(S_i\)表示 \(B_i\)数组中仅出现一次的数的个数。

在所有 \(n^n\)种情况的数组 \(A\)中，求所有\(S_i\)的和，即 \(\sum_{A}\sum_{i=1}^{n} S_i \mod M\)

解题思路

<++>

神奇的代码

Ex - Count Unlabeled Graphs (abc284 h)

题目大意

<++>

解题思路

<++>

神奇的代码

标签：AtCoder,cout,Beginner,int,LL,cin,long,using,284
From： https://www.cnblogs.com/Lanly/p/17033632.html

相关文章

  • E - Don't Isolate Elements -- ATCODER
    E-Don'tIsolateElementshttps://atcoder.jp/contests/abc283/tasks/abc283_e 思路 参考https://www.cnblogs.com/cilinmengye/p/17008799.html ......
  • AtCoder Beginner Contest 257 题解
    AtCoderBeginnerContest257Solution目录AtCoderBeginnerContest257Solution更好的阅读体验戳此进入题面链接题面Luogu链接abc跳了[ABC257D]JumpingTakahashi......
  • AtCoder Beginner Contest 258 题解
    AtCoderBeginnerContest258Solution目录AtCoderBeginnerContest258Solution更好的阅读体验戳此进入题面链接题面Luogu链接abcd跳了[ABC258E]PackingPotatoes......
  • AtCoder Beginner Contest 264 题解
    AtCoderBeginnerContest264Solution目录AtCoderBeginnerContest264Solution更好的阅读体验戳此进入题面链接题面Luogu链接abcd不说了[ABC264E]Blackout2题面......
  • AtCoder Beginner Contest 251 题解
    AtCoderBeginnerContest251Solution目录AtCoderBeginnerContest251Solution更好的阅读体验戳此进入题面链接题面Luogu链接老样子abc太水了就跳了[ABC251D]AtM......
  • AtCoder Beginner Contest 255 题解
    AtCoderBeginnerContest255Solution目录AtCoderBeginnerContest255Solution更好的阅读体验戳此进入题面链接题面Luogu链接abcd跳了[ABC255E]LuckyNumbers题......
  • AtCoder Beginner Contest 132
    AtCoderBeginnerContest132https://atcoder.jp/contests/abc132持续被暴打的一天，因为晚上要打cf，所以明天再来写总结。悲ct就是菜鸟newbie......
  • NC20284 [SCOI2011]糖果
    题目链接题目题目描述幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明......
  • AtCoder Beginner Contest 131
    AtCoderBeginnerContest131https://atcoder.jp/contests/abc1314/6：ABCDA-Security水题#include<bits/stdc++.h>usingnamespacestd;signedmain(){......
  • LOJ #2842. 「JOISC 2018 Day 4」野猪
    题面传送门考试的时候只想到处理\(O(1)\)的边没想到维护\(O(1)\)的路径。首先如果没有可以退一步的限制显然就是相邻两点的最短路之和。退一步的限制想到点边互换。与处......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99