雅礼 2023.12.27 习题课记录

前言

这一场罚时多，都是一些低级错误。

好吧全都是水题。

水题（只放代码）

莫诺卡普参加了一场编程比赛，其中包括 \(26\) 个问题，从 A 到 Z 命名。问题按难度排序。此外，已知莫诺卡普可以在 \(1\) 分钟内解决问题 A，在 \(2\) 分钟内解决问题 B，\(\dots\)，在 \(26\) 分钟内解决问题 Z。比赛结束后，你发现了他的比赛记录 - 一个由大写拉丁字母组成的字符串，其中第 \(i\) 个字母表示莫诺卡普在比赛的第 \(i\) 分钟时正在解决的问题。如果莫诺卡普总共花费了足够的时间来解决一个问题，他就解决了它。请计算莫诺卡普在比赛期间解决的问题数量。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

int n;
string s;
int a[kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    for (int i = 1; i <= 26; ++ i) {
      a[i] = 0;
    }
    cin >> n >> s;
    for (int i = 0; i < s.size(); ++ i) {
      ++ a[s[i] - 'A' + 1];
    }
    int ans = 0;
    for (int i = 1; i <= 26; ++ i) {
      if (a[i] >= i) {
        ++ ans;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

C - Preparing for the Contest（CF1914B）

输出一个长度为 \(n\) 的序列，使序列中后一个数比前一个数大的次数为 \(k\)。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

int n, k;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> n >> k;
    for (int i = 1; i <= (!k? 0 : k); ++ i) {
      cout << i << ' ';
    }
    int ans = 1;
    for (int i = n; ans <= (!k? n : n - k); -- i) {
      cout << i << ' ';
      ++ ans;
    } 
    cout << '\n';
  }
  return 0;
}

E - Rating Increase（CF1913A）

给定 \(\overline{ab}\)，求任意一种可能的 \(a,b\)，其中 \(0<a<b\) 且 \(a,b\) 无前导零。如果无解，请输出 \(-1\)。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

string s;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> s;
    bool f = 0;
    for (int i = 0; i < s.size() - 1; ++ i) {
      if (stoi(s.substr(0, i + 1)) < stoi(s.substr(i + 1)) && s[i + 1] != '0') {
        cout << s.substr(0, i + 1) << ' ' << s.substr(i + 1) << '\n';
        f = 1;
        break;
      } 
    }
    if (!f) {
      cout << -1 << '\n'; 
    }
  }
  return 0;
}

高级水题

F - Swap and Delete（CF1913B）

有一个只含 \(\texttt{0}\) 和 \(\texttt{1}\) 的字符串 \(s\)，你可以对它进行如下两种操作：耗费一个金币，从 \(s\) 中删除 \(1\) 个字符，将 \(s\) 中任意两字符互换位置（免费）。定义一个字符串 \(t\) 是美的代表对于所有满足 \(1 \le i \le \left|t\right|\) 的 \(i\)，\(s_i \ne t_i\) 。你可以进行任意多次操作，假设 \(s\) 修改后变为了 \(s'\)，问最少花费多少金币能使最终得到的 \(s'\) 是美的。

记录每个 \(s\) 的 \(0\) 和 \(1\) 的数量，然后遍历 \(s\)，\(s\) 串为 \(1\) 则填 \(0\)，为 \(0\) 则填 \(1\)。当无法继续填时输出 \(s\) 的长度减去填的字符总数。因为此时后面的不管怎么填一定会有相同，只能全删。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

string s;

auto C() {
  int zr = 0, one = 0;
  for (int i = 0; i < s.size(); ++ i) {
    s[i] == '0'? ++ zr : ++ one;
  }
  return make_pair(one, zr);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> s;
    int a = C().first, b = C().second;
    string s2 = "";
    for (int i = 0; i < s.size(); ++ i) {
      if (s[i] == '0') {
        if (a > 0) {
          s2 += "1";
          -- a;
        } else {
          break;
        }
      } else {
        if (b > 0) {
          -- b;
          s2 += "0";
        } else {
          break;
        }
      }
    }
    cout << s.size() - s2.size() << '\n';
  }
  return 0;
}

D - Quests（CF1914C）

有 \(n\) 个任务，在完成 \(i\) 任务时，\(i\) 之前的所有任务都必须完成。同时，可以多次完成某个任务。总共可以做 \(k\) 次任务，第一次完成 \(i\) 任务的贡献为 \(a_i\) ，后面完成 \(i\) 任务的贡献为 \(b_i\) ，求最大贡献。

当 \(k\) 个次数全部用于前 \(i\) 个任务时，当且仅当每个任务都至少做过一遍，且剩余的次数全部用于前 \(i\) 个任务中 \(b\) 花费最大的任务，取到当前情况的最大花费。

最优的策略是选 \(1 \sim i\) 中最大的 \(b_i\)，选 \(k - i\ (1 \le i \le \min(n, k))\) 次，然后把答案加起来。

前缀和预处理。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

int n, k;

struct node {
  ll a, b;
} a[kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> n >> k;
    for (int i = 0; i < n; ++ i) {
      cin >> a[i].a;
    }
    for (int i = 0; i < n; ++ i) {
      cin >> a[i].b;
    }
    ll p = 0, cnt = 0, maxa = 0, ans = 0;
    for (int i = 0; i < n && i != k; ++ i) {
      maxa = max(maxa, a[i].b), cnt += a[i].a;
      p = (k - i - 1) * maxa + cnt, ans = max(ans, p);
    }
    cout << ans << '\n';
  }
  return 0;
}

A - Three Activities（CF1914D）

给定三个数组 \(a,b,c\)，找三个互不相同的整数 \(i,j,k\)，使得 \(a_i+b_j+c_k\) 的值最大。

额，出这种题很无聊，洛谷都评了个黄（CSPJ T3 难度左右）。除了码量多了一点还有什么难度？看了洛谷题解，还有用 dp 的……

直接搜索即可。先按照从大到小排好序，然后搜索时搜索前 \(3\) 大的每种排列，取最大值。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

int n, ans = 0;
bool vis[kMaxN];

struct node {
  int w, id;
} a[kMaxN], b[kMaxN], c[kMaxN];

bool cmp(node a, node b) {
  return a.w > b.w;
}

void S(int k, int sum) {
  if (k > 3) {
    ans = max(ans, sum);
    return;
  }
  for (int i = 1; i <= 3; ++ i) {
    if (k == 1) {
      if (!vis[a[i].id]) {
        vis[a[i].id] = 1;
        S(k + 1, sum + a[i].w);
        vis[a[i].id] = 0;
      }
    }
    if (k == 2) {
      if (!vis[b[i].id]) {
        vis[b[i].id] = 1;
        S(k + 1, sum + b[i].w);
        vis[b[i].id] = 0;
      }
    }
    if (k == 3) {
      if (!vis[c[i].id]) {
        vis[c[i].id] = 1;
        S(k + 1, sum + c[i].w);
        vis[c[i].id] = 0;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  mtest {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i].w;
    }
    for (int i = 1; i <= n; ++ i) {
      cin >> b[i].w;
    }
    for (int i = 1; i <= n; ++ i) {
      cin >> c[i].w;
    }
    for (int i = 1; i <= n; ++ i) {
      a[i].id = b[i].id = c[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp);
    sort(c + 1, c + n + 1, cmp);
    memset(vis, 0, sizeof vis);
    ans = 0;
    S(1, 0);
    cout << ans << '\n';
  }
  return 0;
}

正常题

G - Game with Multiset（CF1913C）

你有一个空的多重集，你需要处理若干下列询问：ADD \(x\)：加入一个数值为 \(2^x\) 的元素到该多重集，GET \(w\)：判断是否存在一个该多重集的子集，使得这个子集的所有元素之和等于 \(w\)。

这是唯一一道正常题。

首先我们预处理 \(2^0 \sim 2^{29}\)，存在一个 map 里，\(mp_i = 2^i\)。然后再开另一个 map，名为 mp2。

1. ADD

将 \(2^i\) 的元素 \(+1\) 即可。（++ mp2[mp[v]）

2. GET

我们从 \(29\) 开始遍历 \(mp\)。每一次 \(w\) 不为 \(0\) 且 \(v \ge mp_i\) 时，如果 \(2^i\) 的个数不为 \(0\)，将 \(w\) 减去 \(\min(v \div \text{mp}_i, \text{mp2}_{\text{mp}_i})\text{mp}_i\)。

如果 \(w\) 最后为 \(0\)，输出 YES，否则输出 NO。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>

using namespace std;

using ll = long long;

#define mtest for (cin >> t; t; -- t)

const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

ll m;
map<ll, ll> mp, mp2;

void init() {
  for (ll i = 0; i < 30; ++ i) {
    mp[i] = (1ll << i);
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  init();
  cin >> m;
  for (; m; -- m) {
    int op, v;
    cin >> op >> v;
    if (op == 1) {
      ++ mp2[mp[v]];
    } else {
      for (ll i = 29; i >= 0; -- i) {
        if (v != 0 && v >= mp[i]) {
          if (mp2.count(mp[i])) {
            v -= min(v / mp[i], mp2[mp[i]]) * mp[i];
          }
        }
      }
      cout << (!v? "YES" : "NO") << '\n';
    }
  }
  return 0;
}

本栏目推荐文章
• 2023年度总结
• 算法练习题
• CSP-J/S 2023 游记
• Libevent [补档-2023-08-29]
• 本地套接字 [补档-2023-07-24]
• UDP通信 [补档-2023-07-22]
• 多路io复用Select [补档-2023-07-16]
• 多路io复用pool [补档-2023-07-19]
• 多路io复用epoll [补档-2023-07-20]
• socket编程 [补档-2023-07-10]

习题 2023 12 27习题2023 12 27 2023 27 12 习题2023 12 20 12.27 12 27 12.27 12月27日打卡 习题 教材 第二章27 12月27日总结 12.27 12.29 12 27 需求 笔记12.27软件