这题是不是想到裂项就会了但是我赛时没想到
下面复读 Ender32k 做法。
根据 \(\frac{1}{i(i + 1)} = \frac{1}{i} - \frac{1}{i + 1}\),可以构造 \(\frac{1}{2}, \frac{1}{6}, ..., \frac{1}{(n - 1)n}, \frac{1}{n}\)。但是如果存在正整数 \(t\) 使得 \(t(t + 1) = n\) 那就寄了,因为会重。
于是我们把 \(\frac{1}{n}\) 和 \(\frac{1}{t(t + 1)}\) 合并变成 \(\frac{1}{\frac{t(t + 1)}{2}}\),把 \(\frac{1}{(n - 1)n}\) 变成 \(\frac{1}{\frac{3(n - 1)n}{2}}, \frac{1}{3(n - 1)n}\) 即可。
但是 \(n = 12, 420\) 时 \(\frac{1}{\frac{t(t + 1)}{2}}\) 还可以跟前面的继续合并,因此要特判。
code
// Problem: C - Harmonic Mean
// Contest: AtCoder - AtCoder Regular Contest 163
// URL: https://atcoder.jp/contests/arc163/tasks/arc163_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
void solve() {
int n;
scanf("%d", &n);
if (n == 1) {
puts("Yes\n1");
return;
}
if (n == 2) {
puts("No");
return;
}
int t = -1;
for (int i = 1; i <= n; ++i) {
if (i * (i + 1) == n) {
t = i;
break;
}
}
puts("Yes");
if (t == -1) {
for (int i = 1; i < n; ++i) {
printf("%d ", i * (i + 1));
}
printf("%d\n", n);
return;
}
if (n == 12) {
printf("2 3 ");
for (int i = 4; i <= n - 2; ++i) {
printf("%d ", i * (i + 1));
}
puts("264 396 792");
return;
}
if (n == 420) {
for (int i = 1; i <= n - 2; ++i) {
if (i * (i + 1) == 210) {
continue;
}
if (i == t) {
printf("105 ");
} else {
printf("%d ", i * (i + 1));
}
}
int t = 175980;
printf("%d %d %d\n", t * 2, t * 3, t * 6);
return;
}
for (int i = 1; i <= n - 2; ++i) {
if (i * (i + 1) == n) {
printf("%d ", i * (i + 1) / 2);
continue;
}
printf("%d ", i * (i + 1));
}
int k = (n - 1) * n;
printf("%d %d\n", k * 3 / 2, k * 3);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Harmonic AtCoder Regular Contest Meanharmonic atcoder regular contest harmonic atcoder 163c mean atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder