社区讨论
为什么 0 分?
P15269「UTOI 1D」Flowerfell参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mlhy7xq5
- 此快照首次捕获于
- 2026/02/11 19:30 上周
- 此快照最后确认于
- 2026/02/13 18:35 6 天前
思路:
考虑一个数总能被拆成至多 4 个平方数的和,考虑
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 条回复,欢迎继续交流。
正在加载回复...