牛客 215E 黄魔法师 题解

Description

给出 \(n, k\)，求一个长度为 \(n\) 的数组 \(a\), 满足有恰好 \(k\) 对数对 \((i, j) (1 \leq i < j \leq n)\) 满足 \(a_i + a_j\) 为完全平方数。如果不存在，输出 \(-1\)。

link

Solution

显然如果 \(k>\binom{n}{2}\) 就一定无解。

构造时会发现肯定要尽量弄成相同的然后进行微调，那么设 \(m\) 为最大的数满足 \(\binom{m}{2}\leq k\)，\(r=k-\binom{m}{2}\)。

这个时候直接选 \(m\) 个 \(2\) 会发现多出来的 \(r\) 很难微调，因为这个时候要是调整加数的话最小就是增加 \(m\) 了。

这时可以把 \(m\) 个数拆成 \(r\) 个 \(A\) 和 \(m-r\) 个 \(B\)，然后找 \(1\) 个 \(C\) 使得 \(A+B,2A,2B,A+C\) 均为完全平方数并且其他的都不是完全平方数，剩下多的 \(n-m-1\) 个 \(D\) 只要随便找一个数使得加出来不是完全平方数即可。

经枚举 \(A=2,B=98,C=7,D=1\) 可以满足条件。

时间复杂度：\(O(n)\)。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e5 + 5;

int n, k, m, r;

bool check(int x) {
  int y = sqrtl(x);
  for (; y * y > x; --y) {}
  for (; (y + 1) * (y + 1) <= x; ++y) {}
  return x == y * y;
}

void dickdreamer() {
  std::cin >> n >> k;
  if (k > n * (n - 1) / 2) return void(std::cout << "-1\n");
  for (m = 1; m * (m + 1) / 2 <= k; ++m) {}
  if (n == m) {
    for (int i = 1; i <= n; ++i) std::cout << "2 ";
    return;
  }
  r = k - m * (m - 1) / 2;
  for (int i = 1; i <= r; ++i) std::cout << "2 ";
  for (int i = 1; i <= m - r; ++i) std::cout << "98 ";
  std::cout << "7 ";
  for (int i = 1; i <= n - m - 1; ++i) std::cout << "1 ";
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}