补题链接：Here

A - Payment

水题，请问在使用 AtCoder Beginner Contest 173 (AB 思维，C搜索，DF思维) - 图1 元钞票的倍数的钱付款以后能找零多少

  1. void solve() {
  2.     int n; cin >> n, n %= 1000;
  3.     cout << (n == 0 ? 0 : 1000 - n);
  4. }

B - Judge Status Summary

利用 map 的键值特性存值

  1. void solve() {
  2.     int n; cin >> n;
  3.     string s;
  4.     map<string, int>mp;
  5.     while (n--) {
  6.         cin >> s;
  7.         mp[s]++;
  8.     }
  9.     cout << "AC x " << mp["AC"] << "\n";
  10.     cout << "WA x " << mp["WA"] << "\n";
  11.     cout << "TLE x " << mp["TLE"] << "\n";
  12.     cout << "RE x " << mp["RE"] << "\n";
  13. }

C - H and V

题意：给一个n x m的矩阵，由’#‘和’.’构成，分别代表黑色和白色，现在你可以任选若干行和若干列将其涂成红色，问有多少种涂法使最终只有k个黑色。

因为n和m都是小于等于6的，所以对于一个 AtCoder Beginner Contest 173 (AB 思维，C搜索，DF思维) - 图2 的矩阵所有情况也就 AtCoder Beginner Contest 173 (AB 思维，C搜索，DF思维) - 图3 种，那就直接爆搜。

爆搜

  1. string g[10];
  2. int ans, cnt;
  3. int h, w, k;
  4. bool vis[10];
  5. void dfs(int r, int c, int sum) {
  6.     if (r == h and c == w) {
  7.         if (cnt - sum == k)ans++;
  8.         return ;
  9.     }
  10.     int num = 0;
  11.     if (r == h) {
  12.         for (int i = 0; i < h; ++i)
  13.             if (g[i][c] == '#' and (!vis[i]))
  14.                 num++;
  15.         dfs(r, c + 1, sum + num);
  16.         dfs(r, c + 1, sum);
  17.     } else {
  18.         for (int i = 0; i < w; ++i)
  19.             if (g[r][i] == '#')num++;
  20.         vis[r] = 1;
  21.         dfs(r + 1, c, sum + num);
  22.         vis[r] = 0;
  23.         dfs(r + 1, c, sum);
  24.     }
  25. }
  27. void solve() {
  28.     cin >> h >> w >> k;
  29.     for (int i = 0; i < h; ++i)cin >> g[i];
  30.     for (int i = 0; i < h; ++i)
  31.         for (int j = 0; j < w; ++j)if (g[i][j] == '#')cnt++;
  32.     dfs(0, 0, 0);
  33.     cout << ans << "\n";
  34. }

二进制枚举

  1. string s[10];
  2. void solve() {
  3.     int h, w, k;
  4.     cin >> h >> w >> k;
  5.     for (int i = 0; i < h; ++i)cin >> s[i];
  6.     int ans = 0;
  7.     for (int i =  0; i < (1 << h); ++i)
  8.         for (int j = 0; j < (1 << w); ++j) {
  9.             int cnt = 0;
  10.             for (int ii = 0; ii < h; ++ii)
  11.                 for (int jj = 0; jj < w; ++jj)
  12.                     if ((i >> ii & 1) && !(j >> jj & 1))
  13.                         cnt += s[ii][jj] == '#';
  14.             ans += cnt == k;
  15.         }
  16.     cout << ans << "\n";
  17. }

3道类似的题目

AtCoder Beginner Contest 167 C Skill Up 满足C(n,1),C(n,2),C(n,3),……,C(n,n)的深搜dfs

AtCoder Beginner Contest 165 C Many Requirements 深搜dfs+生成非递减数组

AtCoder Beginner Contest 159 E Dividing Chocolate 二维前缀和+子矩阵和+深搜行+枚举列+注意行边界处理+注意列边界处理

D - Chat in a Circle

现在有一排数字，现在要将这排数字按顺序放入一个圈，每个数字在插入圈时，他的权值就是相邻两个数字中小的那个，第一个插入的人权值为0，问总权值是多少。

既然要让权值最大，那必然要让大的值先插入，否则会被相邻的小的值影响，导致不能贡献权值。以为是一个圈，左右两边都能贡献权值，所以除了最大的数只能贡献一次，剩余的数都可以贡献两次。

  1. using ll = long long;
  2. bool cmp(ll a, ll b) {return a > b;}
  3. void solve() {
  4.     int n; cin >> n;
  5.     ll sum = 0;
  6.     int a[n + 1];
  7.     for (int i = 1; i <= n; ++i)cin >> a[i];
  8.     sort(a + 1, a + 1 + n, cmp);
  9.     sum += a[1];
  10.     int idx = 2;
  11.     for (int i = 2; i < n; ++i) {
  12.         if (i % 2 == 0)sum += a[idx]; // 贡献两次
  13.         else sum += a[idx++];
  14.     }
  15.     cout << sum;
  16. }

F - Intervals on Tree

题意：给你一棵树，节点为1到n，取若干连续编号的节点，求出其连通分量，问所有连续段的连通分量之和。

因为是树，所以一条边必然连接两个连通分量，所以我们可以假设把每个点看成一个连通分量，然后每加入一个边，就把含他的 AtCoder Beginner Contest 173 (AB 思维，C搜索，DF思维) - 图4 的数量去掉。

  1. void solve() {
  2.     int n; cin >> n;
  3.     ll sum = 0;
  4.     int l, r;
  5.     for (int i = 1; i <= n; ++i)
  6.         sum += 1ll * i * (n - i + 1);
  7.     for (int i = 1; i < n; ++i) {
  8.         cin >> l >> r;
  9.         if (l > r)swap(l, r);
  10.         sum -= 1ll * l * (n - r + 1);
  11.     }
  12.     cout << sum;
  13. }