题解 | #智乃的天平#

写在前面

更好的阅读体验：https://www.cnblogs.com/luckyblock/p/18785878

比赛地址：https://ac.nowcoder.com/acm/contest/103957。

呃呃太唐了。

A

签到。

#include <bits/stdc++.h>
#define LL long long
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int a, b, w; std::cin >> a >> b >> w;

  if (a == w || b == w || (a + b == w) || (a + w == b) || (b + w == a)) {
    std::cout << "Yes" << "\n";
  } else {
    std::cout << "No" << "\n";
  }
  return 0;
}

B

签到，枚举。

#include <bits/stdc++.h>
#define LL long long
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int n; std::cin >> n;
  std::vector<int> a(n + 2);
  for (int i = 1; i <= n; ++ i) std::cin >> a[i];

  int ans = -1;
  for (int i = 2; i <= n - 1; ++ i) {
    if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
      ans = std::max(ans, a[i] - (a[i - 1] + a[i + 1]) / 2);
    }
  }
  std::cout << ans << "\n";
  return 0;
}

C

特判。

保证最终剩下的所有桶中都不触发消除，则最终剩下的球数量的上界显然为 $m(k - 1)$ 。

当 $q \le m(k - 1)$ 时若有解，则一种一定可行的操作方案是：不断往第一个桶里放球，直至恰好消除 $n-q$ 个球，然后将剩余的球平均放到所有桶里，此时一定不会触发消除。则有解当且仅当：

$\left[q\le m(k - 1)\right] \land \left[(n - q)\bmod k = 0\right]$

#include <bits/stdc++.h>
#define LL long long

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T; std::cin >> T;
  while (T --) {
    LL n, m, k, q;
    std::cin >> n >> m >> k >> q;
    
    int ans = (q <= m * (k - 1) && (n - q) % k == 0);
    
    std::cout << (ans ? "Yes" : "No") << "\n";
  }
  return 0;
}

D

树，枚举。

记节点 $i$ 的度数为 $a_i$ 。容易发现对于一棵以 $r$ 为根的有根树，根节点 $r$ 的孩子数为 $a_r$ ，其余所有点 $i(i\not= r)$ 的孩子数为 $a_i - 1$ 。

于是考虑预处理 $a_i$ 的前后缀最大值 $\operatorname{pre}_i$ 和 $\operatorname{suf}_i$ ，然后考虑枚举根节点 $i$ ，此时树的叉数 $k$ 即为：

$k = \max(\operatorname{pre}_{i - 1} -1, a_i, \operatorname{suf}_{i + 1} - 1)$

于是在所有的答案中按题意取最小值即可。

#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;

int n, into[kN], pre[kN], suf[kN];
std::vector<int> edge[kN];

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  std::cin >> n;
  for (int i = 1; i < n; ++ i) {
    int u, v; std::cin >> u >> v;
    edge[u].push_back(v), edge[v].push_back(u);
    ++ into[u], ++ into[v];
  }
  for (int i = 1; i <= n; ++ i) pre[i] = std::max(pre[i - 1], into[i]);
  for (int i = n; i; -- i) suf[i] = std::max(suf[i + 1], into[i]);

  int ans1 = n, ans2 = 0;
  for (int i = 1; i <= n; ++ i) {
    int v = std::max(pre[i - 1] - 1, std::max(into[i], suf[i + 1] - 1));
    if (v < ans1) ans1 = v, ans2 = i;
  }
  std::cout << ans1 << " " << ans2 << "\n";
  return 0;
}

E

枚举，DP。

众所周知有：

$\sum_{i=1}^r\sum_{j=1}^c a_i\times b_j = \left( \sum_{i=1}^r a_i\right)\times \left( \sum_{j = 1}^c b_j \right)$

发现数据范围很小，于是考虑每次询问时大力枚举被询问数 $x$ 的所有因数 $d$ ，则题目所求即为能否使用给定数列凑出两个数 $d$ 和 $\frac{x}{d}$ 。

先考虑一个暴力 DP，记 $f_{i, j, k}$ 使用数列前 $i$ 个数，能否凑出行的和为 $j$ ，列的和为 $k$ 。初始化 $f_{0, 0, 0} = \operatorname{true}$ ，转移时大力枚举每个数 $a_i$ 放到行/列，或者舍弃：

$f_{i, j, k} \leftarrow \begin{cases}f_{i - 1, j, k}\\f_{i - 1, j - a_i, k}(a_i\le j\le x)\\f_{i - 1, j, k - a_i}(a_i\le k\le x)\end{cases}$

上述状态可以在 $O(nx^2)$ 时间复杂度内预处理出来。则对于每次询问都大力枚举被询问书的因数 $d$ ，有解当且仅当存在 $d$ ，使得 $f_{n, d, \frac{x}{d}} = \operatorname{true}$ 。

这个时候写完代码准备交了，一看下面我草居然还要输出方案！？怎么搞？！

于是考虑改造一下 DP 状态，使之能够记录当前这步转移进行了什么操作即可。记 $\operatorname{from}_{i, j, k}=-1/1/2$ 表示若 $f_{i, j, k} = \operatorname{true}$ ，当前这步转移对 $a_i$ 进行的操作为：舍弃/加到了行上/加到了列上。若 $f_{i,j,k}=\operatorname{false}$ 则 $\operatorname{from}_{i, j, k} = 0$ 。在进行上述枚举转移 $f$ 时顺便维护 $\operatorname{from}$ 即可。

每次询问时，若枚举到了一个合法的 $d$ 满足 $f_{n, d, \frac{x}{d}} = \operatorname{true}$ ，则考虑倒序枚举 $i(1\le i\le n)$ ，并根据记录的 $\operatorname{from}$ 还原每一步的操作即可，总时间复杂度 $O(nx^2 + m(\sqrt{x} + n))$ 。

实现时可以合并两个数组 $f$ 和 $\operatorname{from}$ ，具体实现详见代码。

注意：以下代码为根据上述暴力 DP 直接实现的，并不能通过 hard version 的 F 题。

#include <bits/stdc++.h>
#define LL long long

const int kN = 110;
const int kM = 110;

int n, m, a[kN];
int from[kN][kM][kM];

int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++ i) std::cin >> a[i];

  from[0][0][0] = -1;
  for (int i = 1; i <= n; ++ i) {
    for (int j = 0; j <= 100; ++ j) {
      for (int k = 0; k <= 100; ++ k) {
        if (from[i - 1][j][k]) from[i][j][k] = -1;
      }
    }

    for (int j = a[i]; j <= 100; ++ j) {
      for (int k = 0; k <= 100; ++ k) {
        if (!from[i][j][k] && from[i - 1][j - a[i]][k]) from[i][j][k] = 1;
      }
    }

    for (int j = 0; j <= 100; ++ j) {
      for (int k = a[i]; k <= 100; ++ k) {
        if (!from[i][j][k] && from[i - 1][j][k - a[i]]) from[i][j][k] = 2;
      }
    }
  }

  while (m --) {
    int x, ans = 0; std::cin >> x;

    for (int d = 1; d * d <= x; ++ d) {
      if (x % d) continue;
      if (from[n][d][x / d]) {
        ans = d;
        break;
      } else if (from[n][x / d][d]) {
        ans = x / d;
        break;
      }
    }

    std::cout << (ans ? "Yes" : "No") << "\n";
    if (!ans) continue;
    
    int suma = ans, sumb = x / ans;
    std::vector<int> ans1, ans2;
    for (int i = n; i; -- i) {
      if (from[i][suma][sumb] == -1) continue;
      if (from[i][suma][sumb] == 1) ans1.push_back(a[i]), suma -= a[i];
      if (from[i][suma][sumb] == 2) ans2.push_back(a[i]), sumb -= a[i];
    }
    std::cout << ans1.size() << " " << ans2.size() << "\n";
    for (auto v: ans1) std::cout << v << " ";
    std::cout << "\n";
    for (auto v: ans2) std::cout << v << " ";
    std::cout << "\n";
  }

  return 0;
}

F

DP，减去无用状态、无用转移的 DP 优化。

请首先阅读上一题 easy version 的题解。

发现此时直接套用上述状态直接做空间时间都会爆掉。但是发现数据范围并没有增大很多，于是考虑能否优化。

发现上述状态中，行和列实际上是没有区别的，状态 $f_{n, j, k}$ 和状态 $f_{n, k, j}$ 本质上是相同的，则实际上存在大量的无用状态和无用转移。

由于询问满足 $x\le 10^4$ ，根据小学数学知识可以发现，若 $x$ 有解，即存在 $f_{n, j, k} = \operatorname{true}$ ，则一定有： $\min(j, k) \le \sqrt{x}$ 。于是考虑钦定在上述状态 $f_{i, j, k}$ 和 $\operatorname{from}_{i, j, k}$ 中， $j$ 不大于 $\sqrt{x}$ ，则对应的 $k$ 一定不大于 $\frac{x}{j}$ （即钦定构造方案时保证行的和 $j$ 不大于列的和 $k$ ）。

此时状态 $f_{i, j, k}$ 空间复杂度变为 $O(n\times \sqrt{x}\times x) = O(nx^{\frac{3}{2}})$ 级别，空间复杂度上没问题了。转移时钦定枚举 $j$ 时不大于 $\sqrt{x}$ ， $k$ 不大于 $\frac{x}{j}$ ，则由调和级数可知，对于每个 $i$ 转移次数为：

$\sum_{j=1}^{\sqrt{x}} \frac{x}{j} = \frac{x}{1} + \frac{x}{2} + \cdots + \frac{x}{\sqrt{x}} \le x\ln x$

然后就能在 $O(nx\ln x)$ 的时间复杂度内处理出所有状态了。询问时保证枚举的因数 $d\le \sqrt{x}$ ，然后套用 E 的做法即可。总时间复杂度 $O(nx\ln x + m(\sqrt{x} + n))$

#include <bits/stdc++.h>
#define LL long long
 
const int kN = 510;
const int kM = 110;
 
int n, m, a[kN];
int from[kN][kM][kM * kM];
 
int main() {
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++ i) std::cin >> a[i];
 
  from[0][0][0] = -1;
  for (int i = 1; i <= n; ++ i) {
    for (int j = 0; j <= 100; ++ j) {
      for (int k = 0; k <= 100 * 100 / std::max(1, j); ++ k) {
        if (from[i - 1][j][k]) from[i][j][k] = -1;
      }
    }
 
    for (int j = a[i]; j <= 100; ++ j) {
      for (int k = 0; k <= 100 * 100 / std::max(1, j); ++ k) {
        if (!from[i][j][k] && from[i - 1][j - a[i]][k]) from[i][j][k] = 1;
      }
    }
 
    for (int j = 0; j <= 100; ++ j) {
      for (int k = a[i]; k <= 100 * 100 / std::max(1, j); ++ k) {
        if (!from[i][j][k] && from[i - 1][j][k - a[i]]) from[i][j][k] = 2;
      }
    }
  }
 
  while (m --) {
    int x, ans = 0; std::cin >> x;
    for (int d = 1; d * d <= x; ++ d) {
      if (x % d) continue;
      if (from[n][d][x / d]) {
        ans = d;
        break;
      }
    }
 
    std::cout << (ans ? "Yes" : "No") << "\n";
    if (!ans) continue;
    
    int suma = ans, sumb = x / ans;
    std::vector<int> ans1, ans2;
    for (int i = n; i; -- i) {
      if (from[i][suma][sumb] == -1) continue;
      if (from[i][suma][sumb] == 1) ans1.push_back(a[i]), suma -= a[i];
      if (from[i][suma][sumb] == 2) ans2.push_back(a[i]), sumb -= a[i];
    }
    std::cout << ans1.size() << " " << ans2.size() << "\n";
    for (auto v: ans1) std::cout << v << " ";
    std::cout << "\n";
    for (auto v: ans2) std::cout << v << " ";
    std::cout << "\n";
  }
 
  return 0;
}

写在最后

学到了什么：

F：减去无用状态、无用转移的 DP 优化。