• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

AtCoder Beginner Contest 177 (个人题解,C后缀和,D并查集,E质因数分解)

开发技术 开发技术 2周前 (04-07) 4次浏览

补题链接:Here

A – Don’t be late

题意:高桥(Takahashi )现在要去距离家 (D) 米的地方面基,请问如果以最高速度 (S) 能否再 (T) 时刻准时到达?

(cout << (d / s <= t ? “Yes” : “No”);)

注意点使用 float

B – Substring

注意到 S T 长度很小,所有可以枚举

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    int ans = m;
    for (int start = 0; start <= n - m; ++start) {
        int cnt = 0;
        for (int i = 0; i < m; ++i)
            if (t[i] != s[start + i]) cnt++;
        ans = min(ans, cnt);
    }
    cout << ans << "n";
    return 0;
}

C – Sum of product of pairs

维护后缀和,记得取模即可

using ll = long long;
const ll mod = 1e9 + 7;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    ll a[n + 1], lst[n + 2] = {};
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = n; i >= 1; --i) {
        lst[i] = (lst[i + 1] % mod + (i == n ? 0 : a[i + 1]) % mod) % mod;
    }
    ll ans = 0;
    for (int i = 1; i < n; ++i) {
        ans = (ans + a[i] * lst[i] + mod) % mod;
    }
    cout << ans % mod << "n";
    return 0;
}

D – Friends

题意:给定 n 个人的 m 对朋友关系,现在进行最小化分组要是每个组里都没有互相认识的人,

思路:并查集,求出最大连通分量即可

  • (mathcal{O}(NlogN))
const int N = 2e5 + 7;
int f[N], Siz[N];
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x != y)
        f[x] = y, Siz[y] += Siz[x];
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n, m;
    for (int i = 1; i <= N - 1; ++i) f[i] = i, Siz[i] = 1;
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        merge(x, y);
    }
    sort(Siz, Siz + n + 1);
    cout << Siz[n];
    return 0;
}

E – Coprime

质因数分解,统计含有每个质因子的数的个数,然后求出最大的个数。如果这个值为 (1),说明两两互质;如果这个值小于(N),说明总体互质。

int cnt[1 << 20];
int all = 0;
bool isp[1 << 20];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        cnt[x]++;
        all = gcd(all, x);
    }
    bool f = true;
    for (int i = 2; i < (1 << 20); ++i) {
        int sum = 0;
        for (int j = i; j < (1 << 20); j += i) sum += cnt[j];
        if (sum > 1) f = false;
    }
    cout << (f ? "pairwise coprime" : all == 1 ? "setwise coprime"
                                               : "not coprime");
    return 0;
}

AtCoder Beginner Contest 177


喜欢 (0)