P9034 「KDOI-04」Again Counting Set

Alex_Wei · 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)，同样无解。

注意集合内可以有任意正整数个 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;
}