AtCoder Beginner Contest 333 A~D(E,F更新中...)

A.Three Threes（循环）

题意：

给出一个正整数 $N$ ，要求输出 $N$ 个 $N$

分析：

按要求输出即可

代码：

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cout << n;
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

B.Pentagon（判断）

题意：

给出正五边形上四个顶点 $S_1,S_2, T_1,T_2(S_1 \ne S_2, T_1 \ne T2)$ ，问 $S_1$ 和 $S_2$ 连成的线端长度与 $T_1$ 和 $T_2$ 之间连成的线段长度是否相等。

分析：

正五边形任意两点之间的距离分以下两种：

两点相邻
两点不相邻

判断两条线段是否属于同一类型即可。

代码：

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s, t;
    cin >> s >> t;
    int s1 = s[0] - 'A';
    int s2 = s[1] - 'A';
    int t1 = t[0] - 'A';
    int t2 = t[1] - 'A';
    int len1 = 0, len2 = 0;
    if (abs(s2 - s1) != 1 && abs(s2 - s1) != 4) len1 = 1;
    if (abs(t2 - t1) != 1 && abs(t2 - t1) != 4) len2 = 1;
    if (len1 == len2) {
        cout << "Yes" << endl; 
    } else {
        cout << "No" << endl;
    }
}

int main() {
    solve();
    return 0;
}

C.Repunit Trio（预处理）

题意：

有一个序列，里面每个数字均由若干个 $1$ 组成，如 $1, 11, 111, ...$ ，问任取该序列中的三个数字（每个数字可重复取）加在一起组成的所有数字中第 $N$ 小的数字是多少？

分析：

先预处理由 $1$ 组成的数字。

然后使用三场循环枚举能组成的数字。

枚举结束后排序去重，并输出第 $N$ 小的数字即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

vector<LL> ans, num;

void solve() {
    LL val = 0;
    for (int i = 1; i <= 15; i++) {
        val = val * 10 + 1;
        num.push_back(val);
    }
    for (int i = 0; i <= 14; i++) {
        for (int j = 0; j <= 14; j++) {
            for (int k = 0; k <= 14; k++) {
                ans.push_back(num[i] + num[j] + num[k]);
            }
        }
    }
    ans.push_back(0);//加个0，把存储答案的下标修改为从1开始
    sort(ans.begin(), ans.end());
    int len = unique(ans.begin(), ans.end()) - ans.begin();
    int n;
    cin >> n;
    cout << ans[n] << endl;
}

int main() {
    solve();
    return 0;
}

D.Erase Leaves（贪心）

题意：

给出一棵树，允许进行若干次如下操作：

选择一个叶节点，并将该叶节点删除

问：至少需要操作多少次，才能将节点 $1$ 删除。

分析：

想要让 $1$ 成为叶节点，那么必然需要将1连着的边删除到只剩一条。而想要删除每一条边实际上需要将该边连接的整棵子树全部删除才行，那么最后留下的那条边连接的子树一定为 $1$ 的最大子树。

以 $1$ 为根节点进行遍历，记录每个节点的子树大小，最后的答案就是连接 $1$ 的 $k$ 棵子树中除最大的子树外的所有子树节点之和，再加上最后删除节点 $1$ 的操作次数。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 3e5 + 5e2;

vector<int> G[N];
int sz[N];

void dfs(int root, int pre) {
    sz[root] = 1;
    int len = G[root].size();
    for (int i = 0; i < len; i++) {
        int v = G[root][i];
        if (v != pre) {
            dfs(v, root);
            sz[root] += sz[v];
        }
    }
}

vector<int> child;

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, -1);
    int len = G[1].size();
    for (int i = 0; i < len; i++) {
        child.push_back(sz[G[1][i]]);
    }
    sort(child.begin(), child.end());
    int ans = 0;
    for (int i = 0; i < len - 1; i++) {
        ans += child[i];
    }
    cout << ans + 1 << endl;
}

int main() {
    solve();
    return 0;
}