补题链接：Here

A - Don’t be late

题意：高桥（Takahashi ）现在要去距离家 AtCoder Beginner Contest 177 （个人题解，C后缀和，D并查集，E质因数分解） - 图1 米的地方面基，请问如果以最高速度 AtCoder Beginner Contest 177 （个人题解，C后缀和，D并查集，E质因数分解） - 图2 能否再 AtCoder Beginner Contest 177 （个人题解，C后缀和，D并查集，E质因数分解） - 图3 时刻准时到达？

AtCoder Beginner Contest 177 （个人题解，C后缀和，D并查集，E质因数分解） - 图4%3B#card=math&code=cout%20%3C%3C%20%28d%20%2F%20s%20%3C%3D%20t%20%3F%20%22Yes%22%20%3A%20%22No%22%29%3B)

注意点使用 float

B - Substring

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

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     string s, t;
  4.     cin >> s >> t;
  5.     int n = s.size(), m = t.size();
  6.     int ans = m;
  7.     for (int start = 0; start <= n - m; ++start) {
  8.         int cnt = 0;
  9.         for (int i = 0; i < m; ++i)
  10.             if (t[i] != s[start + i]) cnt++;
  11.         ans = min(ans, cnt);
  12.     }
  13.     cout << ans << "\n";
  14.     return 0;
  15. }

C - Sum of product of pairs

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

  1. using ll = long long;
  2. const ll mod = 1e9 + 7;
  3. int main() {
  4.     ios_base::sync_with_stdio(false), cin.tie(0);
  5.     int n;
  6.     cin >> n;
  7.     ll a[n + 1], lst[n + 2] = {};
  8.     for (int i = 1; i <= n; ++i) cin >> a[i];
  9.     for (int i = n; i >= 1; --i) {
  10.         lst[i] = (lst[i + 1] % mod + (i == n ? 0 : a[i + 1]) % mod) % mod;
  11.     }
  12.     ll ans = 0;
  13.     for (int i = 1; i < n; ++i) {
  14.         ans = (ans + a[i] * lst[i] + mod) % mod;
  15.     }
  16.     cout << ans % mod << "\n";
  17.     return 0;
  18. }

D - Friends

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

思路：并查集，求出最大连通分量即可

  • AtCoder Beginner Contest 177 （个人题解，C后缀和，D并查集，E质因数分解） - 图5#card=math&code=%5Cmathcal%7BO%7D%28NlogN%29)
  1. const int N = 2e5 + 7;
  2. int f[N], Siz[N];
  3. int find(int x) {
  4.     return f[x] == x ? x : f[x] = find(f[x]);
  5. }
  6. void merge(int x, int y) {
  7.     x = find(x), y = find(y);
  8.     if (x != y)
  9.         f[x] = y, Siz[y] += Siz[x];
  10. }
  11. int main() {
  12.     ios_base::sync_with_stdio(false), cin.tie(0);
  13.     int n, m;
  14.     for (int i = 1; i <= N - 1; ++i) f[i] = i, Siz[i] = 1;
  15.     cin >> n >> m;
  16.     while (m--) {
  17.         int x, y;
  18.         cin >> x >> y;
  19.         merge(x, y);
  20.     }
  21.     sort(Siz, Siz + n + 1);
  22.     cout << Siz[n];
  23.     return 0;
  24. }

E - Coprime

质因数分解，统计含有每个质因子的数的个数，然后求出最大的个数。如果这个值为 AtCoder Beginner Contest 177 （个人题解，C后缀和，D并查集，E质因数分解） - 图6，说明两两互质；如果这个值小于AtCoder Beginner Contest 177 （个人题解，C后缀和，D并查集，E质因数分解） - 图7，说明总体互质。

  1. int cnt[1 << 20];
  2. int all = 0;
  3. bool isp[1 << 20];
  4. int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
  5. int main() {
  6.     ios_base::sync_with_stdio(false), cin.tie(0);
  7.     int n;
  8.     cin >> n;
  9.     for (int i = 0, x; i < n; ++i) {
  10.         cin >> x;
  11.         cnt[x]++;
  12.         all = gcd(all, x);
  13.     }
  14.     bool f = true;
  15.     for (int i = 2; i < (1 << 20); ++i) {
  16.         int sum = 0;
  17.         for (int j = i; j < (1 << 20); j += i) sum += cnt[j];
  18.         if (sum > 1) f = false;
  19.     }
  20.     cout << (f ? "pairwise coprime" : all == 1 ? "setwise coprime"
  21.                                                : "not coprime");
  22.     return 0;
  23. }

AtCoder Beginner Contest 177