AtCoder Beginner Contest 284 题解

发表于 更新于 分类于 本文字数： 869 阅读时长 ≈ 3 分钟

A. Sequence Order

题意：输入 \(n\) 个字符串 \(s_1, s_2, \cdots, s_n\)，将他们倒序输出。

输入字符串，将他们压入栈中，然后依次输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
stack<string> st;
int main() {
    cin >> n;
    while (n--) {
        cin >> s;
        st.push(s);
    }
    while (!st.empty()) {
        cout << st.top() << endl;
        st.pop();
    }
    return 0;
}

B. Multi Test Cases

题意：有 \(t\) 组数据，每次给定一个长 \(n\) 的数组，每组求其中奇数的个数。

根据题意，每次判断累加即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int t, n;
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        int ans = 0;
        for (int i = 1, x; i <= n; i++)
            cin >> x, ans += (x % 2 == 1);
        cout << ans << endl;
    }
    return 0;
}

C. Count Connected Components

题意：求一个无向图中连通块的个数。

设 \(mark_i\) 表示点已经访问过。遍历 \(i=1\cdots n\)，若 \(mark_i\) 的值为 false，则从 \(i\) 开始进行深度优先搜索，将所有与 \(i\) 相连的点标记为已访问，最后答案加 \(1\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int N = 101;
int n, m, mrk[N];
vector<int> es[N];
void dfs (int x) {
    mrk[x] = 1;
    for (auto v: es[x])
        if (!mrk[v]) dfs(v);
}
int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        es[u].push_back(v), es[v].push_back(u);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!mrk[i]) ++ans, dfs(i);
    cout << ans << endl;
    return 0;
}

D. Happy New Year 2023

题意：有 \(t\) 组数据，每组给定一个整数 \(n\)（\(1 \leq n \leq 9 \times 10^{18}\)），已知 \(n\) 可以表示为唯一的 \(n=p^2q\)，且 \(p, q\) 是质数，求 \(p\) 和 \(q\) 的值。

设知 \(n=p^2q \sim 10^{18}\)，设 \(q \sim 10^m\)，则 \(p \sim 10^{\frac{18-m}{2}}\)。

则 \(p, q\) 的阶的最大值就是 \(\max(m, \frac{18-m}{2})\)。

若 \(m = \max(m, \frac{18-m}{2})\)，则 \(2m \geq 18-m\)，得 \(m\geq 6\)，则 \(18-m \leq 12\)，得 \(\frac{18-m}{2} \leq 6\)，故而可以先找到 \(q\)，所以只需要找到 \(10^6\) 的素数。

反之，则 \(2m \leq 18-m\)，得 \(m \leq 6\)，所以也只需要找到 \(10^6\) 的素数。但是，\(n\) 的最大值是 \(9\times 10^{18}\)，所以可以筛到 \(10^7\)。

综上所述，只需要找到 \(10^6\) 的素数，然后枚举 \(p\) 或 \(q\) 是否符合条件即可。

筛到一个满足 \(p \equiv 0 \pmod n\) 的素数 \(p\) 时，若 \(p \equiv 0 \pmod{\frac{n}{p}}\)，则这个素数 \(p\) 一定是 \(n=p^2q\) 中的素数 \(p\)，否则这个素数一定是 \(q\)。

知，\(1 \sim x\) 的素数大概是 \(\dfrac{x}{\ln x}\) 个，设筛到的素数为 \(s\)（此处 \(s=10^7\)），则时间复杂度为 \(O(s+\frac{ts}{\ln s})\)，其中 \(t\) 为数据组数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n;
vector<ll> primes;
void sieve (ll x) {
    vector<bool> vst(x+1);
    for (ll i = 2; i <= x; i++) {
        if (!vst[i]) primes.push_back(i);
        for (auto pj: primes) {
            if (i*pj > x) break;
            vst[i*pj] = true;
            if (i % pj == 0) break;
        }
    }
}
int main() {
    cin >> t;
    sieve(10000000);
    while (t--) {
        cin >> n;
        for (auto p: primes) {
            if (n%p == 0) {
                if ((n/p)%p==0) { // then it's the p
                    cout << p << " " << n/p/p << endl;
                    break;
                } else {
                    cout << (ll) sqrtl(n/p) << " " << p << endl;
                  	break;
                }
            }
        }
    }
    return 0;
}

E. Count Simple Paths

题意：求无向图从点 \(1\) 开始的简单路径个数，并对 \(10^6\) 取 \(\min\)。

直接从 \(1\) 开始 DFS，若个数超过 \(10^6\)，则输出 1000000 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int N = 200001;
int n, m;
vector<int> es[N];
int cnt = 0;
set<int> st;
void dfs (int x) {
    if (cnt >= 1000000) {
        cout << 1000000 << endl;
        exit(0);
    }
    ++cnt;
    st.insert(x);
    for (auto v: es[x]) {
        if (!st.count(v)) {
            dfs(v);
            st.erase(v);
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        es[u].push_back(v), es[v].push_back(u);
    }
    dfs(1);
    cout << cnt << endl;
    return 0;
}