社区讨论

为什么 0 分?

P15269「UTOI 1D」Flowerfell参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mlhy7xq5
此快照首次捕获于
2026/02/11 19:30
上周
此快照最后确认于
2026/02/13 18:35
6 天前
查看原帖
思路:
考虑一个数总能被拆成至多 4 个平方数的和,考虑 3,1,3,2,3,1,3,2,3,1,3,2,3,1,33\dots,1,3\dots,2,3\dots,1,3\dots,2 ,3\dots,1,3\dots,2,3\dots,1,3\dots
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int kN = 1e5 + 7;
void solve(){
  int k; cin >> k;
  if(k == 1) cout << 4 << '\n' << "1 2 1 2\n";
  else if(k == 2) cout << 5 << '\n' << "1 2 1 2 3\n";
  else if(k == 3) cout << 6 << '\n' << "1 2 1 2 1 2\n";
  else if(k == 4) cout << 6 << '\n' << "1 2 3 2 3 1\n";
  else{
    int a = 0, b = 0, c = 0, d = 0;
    for (int A = 0; A * A <= k; ++A){
      int rem1 = k - A * A;
      if(rem1 == 0){
        a = A; break;
      }
      for (int B = A; B * B <= rem1; ++B){
        int rem2 = rem1 - B * B;
        if(rem2 == 0){
          a = A, b = B; break;
        }
        for (int C = B; C * C <= rem2; ++C){
          int rem3 = rem2 - C * C;
          if(rem3 == 0){
            a = A, b = B, c = C;
            break;
          }
          int D = sqrt(rem3);
          if (D * D == rem3){
            a = A, b = B, c = C, d = D;
            break;
          }
        }
        if(a) break;
      }
      if(a) break;
    }
    if(a * a == k){
      cout << 2 * a + 2 << '\n';
      for(int i = 1; i <= a - 1; i++) cout << 3 << ' ';
      cout << 1 << ' ' << 2 << ' ' << 1 << ' ' << 2 << ' ';
      for(int i = 1; i <= a - 1; i++) cout << 3 << ' ';
      cout << '\n';
      return ;
    }
    if(a * a + b * b == k){
      cout << 2 * a + 2 * b + 1 << '\n';
      for(int i = 1; i <= a - 1; i++) cout << 3 << ' ';
      cout << 1 << ' ';
      for(int i = 1; i <= b - 1; i++) cout << 3 << ' ';
      cout << 2 << ' ' << 1 << ' ' << 2 << ' ';
      for(int i = 1; i <= a - 1; i++) cout << 3 << ' ';
      cout << 1 << ' ';
      for(int i = 1; i <= b - 1; i++) cout << 3 << ' ';
      cout << '\n';
      return ;
    }
    if(a * a + b * b + c * c == k){
      cout << 2 * a + 2 * b + 2 * c << '\n';
      for(int i = 1; i <= a - 1; i++) cout << 3 << ' ';
      cout << 1 << ' ';
      for(int i = 1; i <= b - 1; i++) cout << 3 << ' ';
      cout << 2 << ' ';
      for(int i = 1; i <= c - 1; i++) cout << 3 << ' ';
      cout << 1 << ' ' << 2 << ' ';
      for(int i = 1; i <= a - 1; i++) cout << 3 << ' ';
      cout << 1 << ' ';
      for(int i = 1; i <= b - 1; i++) cout << 3 << ' ';
      cout << 2 << ' ';
      for(int i = 1; i <= c - 1; i++) cout << 3 << ' ';
      cout << '\n';
      return ;
    }
    cout << 2 * a + 2 * b + 2 * c + 2 * d - 1 << '\n';
    for(int i = 1; i <= a - 1; i++) cout << 3 << ' ';
    cout << 1 << ' ';
    for(int i = 1; i <= b - 1; i++) cout << 3 << ' ';
    cout << 2 << ' ';
    for(int i = 1; i <= c - 1; i++) cout << 3 << ' ';
    cout << 1 << ' ';
    for(int i = 1; i <= d - 1; i++) cout << 3 << ' ';
    cout << 2 << ' ';
    for(int i = 1; i <= a - 1; i++) cout << 3 << ' ';
    cout << 1 << ' ';
    for(int i = 1; i <= b - 1; i++) cout << 3 << ' ';
    cout << 2 << ' ';
    for(int i = 1; i <= c - 1; i++) cout << 3 << ' ';
    cout << 1 << ' ';
    for(int i = 1; i <= d - 1; i++) cout << 3 << ' ';
    cout << '\n';
  }
}
signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int D, T;
  cin >> D >> T;
  while(T--) solve();
  return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...