Codeforces Round #700 (Div. 2)

比赛链接: Click Here

1480A. Yet Another String Game

因为Alice是要追求小，Bob追求大值，所以只要变为 a 或 z.

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     for (cin >> _; _--;) {
  4.         string s;
  5.         cin >> s;
  6.         for (int i = 0; i < s.size(); ++i) 
  7.             if (i % 2 == 0) {
  8.                 if (s[i] == 'a') cout << 'b';
  9.                 else cout << 'a';
  10.             } else {
  11.                 if (s[i] != 'z') cout << 'z';
  12.                 else cout << 'y';
  13.             }
  14.         cout << "\n";
  15.     }
  16.     return 0;
  17. }

1480B. The Great Hero

排序，对英雄伤害少的排前面，统计总共打败的敌人数即可

  1. using ll = long long;
  2. int _;
  3. struct node {
  4.     ll a, b;
  5. };
  6. ll A, B;
  7. bool cmp(node a, node b) {
  8.     ll d1 = (a.b / A + a.b % A != 0) * a.a, d2 = (b.b / A + b.b % A != 0) * b.a;
  9.     return d1 < d2;
  10. }
  12. int main() {
  13.     ios_base::sync_with_stdio(false), cin.tie(0);
  14.     for (cin >> _; _--;) {
  15.         int n, cnt = 0;
  16.         cin >> A >> B >> n;
  17.         vector<node> e(n);
  18.         for (int i = 0; i < n; ++i) cin >> e[i].a;
  19.         for (int i = 0; i < n; ++i) cin >> e[i].b;
  20.         sort(e.begin(), e.end(), cmp);
  21.         for (int i = 0; i < n; ++i) {
  22.             while (B >= 1 && e[i].b >= 1) e[i].b -= A, B -= e[i].a;
  23.             if (e[i].b <= 0) cnt++;
  24.         }
  25.         cout << (cnt == n ? "YES\n" : "NO\n");
  26.     }
  27.     return 0;
  28. }

1480C. Searching Local Minimum

C题没做出来，待补。

1480D1. Painting the Array I

题意和思路来自网络

Codeforces Round #700 (Div. 2) A ~ D1个人题解 - 图1

  1. int _;
  2. int a[210000];
  4. int main() {
  5.     ios_base::sync_with_stdio(false), cin.tie(0);
  6.     int n;
  7.     cin >> n;
  8.     for (int i = 1; i <= n; ++i) cin >> a[i];
  9.     int lst = 0, sum = 0;
  10.     for (int i = 1; i <= n; ++i) {
  11.         if (a[i] == a[i + 1]) {
  12.             if (a[lst] != a[i])
  13.                 sum += 2;
  14.             else {
  15.                 bool f = false;
  16.                 for (int j = i - 1; true; --j) {
  17.                     if (a[j] != a[i] && a[j + 1] != a[i]) {
  18.                         f = true;
  19.                         break;
  20.                     }
  21.                     if (j == lst) break;
  22.                 }
  23.                 sum += f ? 2 : 1;
  24.             }
  25.             while (a[i] == a[i + 1]) ++i;
  26.             lst = i;
  27.         } else
  28.             sum++;
  29.         // cout << sum << "\n";
  30.     }
  31.     cout << sum << "\n";
  32.     return 0;
  33. }

1480D2. Painting the Array II

D2昨天没啥想法就被弃掉了（老菜鸡了）

顺便贴一下朋友的D2代码

  1. int _;
  2. int a[100005], b[100005], ans[100005], now[100005], pre[100005];
  3. int dfs(int x) {
  4.     if (ans[x] != -1) return ans[x];
  5.     if (x == 0) return 0;
  6.     ans[x] = dfs(x - 1);
  7.     if (pre[x]) ans[x] = max(ans[x], dfs(pre[x] + 1) + 1);
  8.     return ans[x];
  9. }
  10. int main() {
  11.     int T = 1;
  12.     // cin>>T;
  13.     while (T--) {
  14.         int n, x = 0;
  15.         cin >> n;
  16.         for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  17.         for (int i = 1; i <= n; i++)
  18.             if (a[i] != a[i - 1]) b[++x] = a[i];
  19.         for (int i = 1; i <= x; i++) pre[i] = now[b[i]], now[b[i]] = i;
  20.         memset(ans, -1, sizeof(ans));
  21.         dfs(x);
  22.         int mx = 0;
  23.         for (int i = 1; i <= x; i++) mx = max(mx, ans[i]);
  24.         cout << x - mx << endl;
  25.     }
  26.     return 0;
  27. }