Codeforces Round #697 (Div. 3)

1475A. Odd Divisor

问一个数是否有奇除数。

对 2 不断除，如果最后 n == 1即不可能存在，否在存在。

  1. int main() {
  2.     // freopen("in.txt", "r", stdin);
  3.     ios_base::sync_with_stdio(false), cin.tie(0);
  4.     for (cin >> _; _--;) {
  5.         ll n;
  6.         cin >> n;
  7.         while (n % 2 == 0) n /= 2;
  8.         cout << (n == 1 ? "NO\n" : "YES\n");
  9.     }
  10. }

1475B. New Year’s Number

  1. int main() {
  2.     // freopen("in.txt", "r", stdin);
  3.     ios_base::sync_with_stdio(false), cin.tie(0);
  4.     for (cin >> _; _--;) {
  5.         int n;
  6.         cin >> n;
  7.         cout << (n % 2020 <= n / 2020 ? "YES" : "NO") << "\n";
  8.     }
  9. }

1475C. Ball in Berland

题意：学校毕业舞会上要求每个班级必须出两队 couple 参加，然后每个班级有 a 个 男生，b 个女生参加、但只有 k 组男女匹配。

请问有多少种舞会参加可能性？

简单计数，然后注意重复计数（除2）

  1. int main() {
  2.     // freopen("in.txt", "r", stdin);
  3.     ios_base::sync_with_stdio(false), cin.tie(0);
  4.     for (cin >> _; _--;) {
  5.         int a, b, k;
  6.         cin >> a >> b >> k;
  7.         vector<int> A(k), B(k);
  8.         for (auto& x : A) cin >> x;
  9.         for (auto& x : B) cin >> x;
  11.         // 开始计数
  12.         map<int, int> ma, mb;
  13.         for (int i = 0; i < k; ++i) ma[A[i]]++, mb[B[i]]++;
  15.         ll ans = 0;
  16.         for (int i = 0; i < k; ++i)
  17.             ans += (k - 1) - (ma[A[i]] - 1) - (mb[B[i]] - 1);
  19.         assert(ans % 2 == 0); // 设置断言提示出错
  20.         cout << ans / 2 << endl;
  21.     }
  22. }

1475D - Cleaning the Phone

  1. int main() {
  2.     // freopen("in.txt", "r", stdin);
  3.     ios_base::sync_with_stdio(false), cin.tie(0);
  4.     for (cin >> _; _--;) {
  5.         ll n, m;
  6.         cin >> n >> m;
  7.         vector<ll> a(n);
  8.         for (ll& x : a) cin >> x;
  9.         vector<ll> B[2];
  10.         for (int i = 0, b; i < n; i += 1) {
  11.             cin >> b;
  12.             B[b - 1].push_back(a[i]);
  13.         }
  14.         for (int i = 0; i < 2; i += 1) {
  15.             sort(B[i].begin(), B[i].end(), greater<ll>());
  16.             partial_sum(B[i].begin(), B[i].end(), B[i].begin());
  17.         }
  18.         int ans = INT_MAX;
  19.         for (int i = 0; i <= B[0].size(); i += 1) {
  20.             ll rm = m - (i ? B[0][i - 1] : 0);
  21.             if (rm <= 0)
  22.                 ans = min(ans, i);
  23.             else {
  24.                 auto it = lower_bound(B[1].begin(), B[1].end(), rm);
  25.                 if (it == B[1].end()) continue;
  26.                 ans = min(ans, 2 * int(it - B[1].begin() + 1) + i);
  27.             }
  28.         }
  29.         cout << (ans == INT_MAX ? -1 : ans) << "\n";
  30.     }
  31. }

1475E - Advertising Agency

  1. /* Author: RioTian Time: 21/01/26
  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. #include <bits/stdc++.h>
  34. using namespace std;
  35. typedef long long LL;
  36. const int N = 2e5 + 5;
  37. constexpr int mod = 1'000'000'007;
  38. int _;
  39. int C(int m, int n) {
  40.     vector<vector<int>> v(m + 1, vector<int>(n + 1));
  41.     for (int i = 0; i <= m; i += 1)
  42.         for (int j = 0; j <= i and j <= n; j += 1)
  43.             v[i][j] = j ? (v[i - 1][j - 1] + v[i - 1][j]) % mod : 1;
  44.     return v.back().back();
  45. }
  46. int main() {
  47.     // freopen("in.txt","r",stdin);
  48.     ios_base::sync_with_stdio(false), cin.tie(0);
  49.     for (cin >> _; _--;) {
  50.         int n, k;
  51.         cin >> n >> k;
  52.         vector<int> v(n);
  53.         for (int& x : v) cin >> x;
  54.         sort(v.begin(), v.end(), greater<int>());
  55.         cout << C(count(v.begin(), v.end(), v[k - 1]),
  56.                   count(v.begin(), v.begin() + k, v[k - 1]))
  57.              << "\n";
  58.     }
  59. }

1475F - Unusual Matrix

  1. int main() {
  2.     // freopen("in.txt","r",stdin);
  3.     ios_base::sync_with_stdio(false), cin.tie(0);
  4.     for (cin >> _; _--;) {
  5.         int n;
  6.         cin >> n;
  7.         vector<string> a(n), b(n);
  8.         for (auto& s : a) cin >> s;
  9.         for (auto& s : b) cin >> s;
  10.         vector<vector<int>> c(n, vector<int>(n));
  11.         for (int i = 0; i < n; i += 1)
  12.             for (int j = 0; j < n; j += 1) c[i][j] = a[i][j] != b[i][j];
  13.         int ok = 1;
  14.         for (int i = 0; i < n; i += 1)
  15.             for (int j = 0; j < n; j += 1)
  16.                 ok &= (c[i][j] ^ c[0][j]) == (c[i][0] ^ c[0][0]);
  17.         cout << (ok ? "YES" : "NO") << "\n";
  18.     }
  19. }

1475G - Strange Beauty

枚举倍数

  1. int main() {
  2.     // freopen("in.txt","r",stdin);
  3.     ios_base::sync_with_stdio(false), cin.tie(0);
  4.     for (cin >> _; _--;) {
  5.         int n;
  6.         cin >> n;
  7.         vector<int> a(n);
  8.         for (int i = 0; i < n; i++) {
  9.             cin >> a[i];
  10.         }
  11.         int mx = *max_element(a.begin(), a.end());
  12.         vector<int> cnt(mx + 1);
  13.         for (int i = 0; i < n; i++) {
  14.             cnt[a[i]] += 1;
  15.         }
  16.         vector<int> dp(mx + 1);
  17.         for (int i = 1; i <= mx; i++) {
  18.             dp[i] += cnt[i];
  19.             for (int j = i + i; j <= mx; j += i) {
  20.                 dp[j] = max(dp[j], dp[i]);
  21.             }
  22.         }
  23.         cout << n - *max_element(dp.begin(), dp.end()) << '\n';
  24.     }
  25. }