自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:44:48，当前版本为作者最后更新于2023-02-08 10:13:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

条件四要求 $k \geq 2$，结合条件三要求 $\min x \leq 1$（反证法易证）。

当 $\min x = 1$ 时，条件三要求集合内所有数均为 $1$，结合条件四，合法集合仅有 $S = \{1, 1\}$。

当 $\min x = 0$ 时，条件三满足，条件四形如 $\sum x = \max x + \operatorname{mex}(S)$。

设 $S$ 所有非最大值且非零数集合为 $T$。

感性理解 $\operatorname{mex}(S)$ 不会太大（$\operatorname{mex}(S)$ 增长时，$\sum_{x\in T} x$ 的最小值以平方级别增长）。手玩可知：

• $\operatorname{mex}(S) = 1$ 不可能。
• $\operatorname{mex}(S) = 2$ 时，$T = \{1, 1\}$（最大值可为 $1$ 或 $3\sim n$ 任意值）。
• $\operatorname{mex}(S) = 3$ 时，$T = \{1, 2\}$（最大值可为 $2$ 或 $4\sim n$ 任意值）或 $\{1, 1, 1\}$（最大值为 $2$）。
• $\operatorname{mex}(S) = 4$ 时，$T = \{1, 1, 2\}$（最大值为 $3$）。
• $\operatorname{mex}(S) = 5$ 时，就算最大值为 $4$，那么 $T$ 中所有数之和也至少为 $1 + 2 + 3 > 5$。
• 类似可证对于更大的 $\operatorname{mex}(S)$，同样无解。

注意集合内可以有任意正整数个 $0$。根据上述分析计算答案即可。

时间复杂度 $\mathcal{O}(1)$。

#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long solve() {
  cin >> n >> k;
  if(k == 1) return 0;
  long long ans = 0;
  if(k >= 4) {
    ans += 1 + max(0ll, n - 2);
    if(n >= 2) ans += 1 + max(0ll, n - 3);
  }
  if(k >= 5) {
    if(n >= 2) ans++;
    if(n >= 3) ans++;
  }
  if(k == 2) ans++;
  return ans;
}
int main() {
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while(T--) cout << solve() << "\n";
  return 0;
}