没想出来什么优美的解法,来个乱搞。
特判平凡情况 \(n\le 2\),其中 \(n=1\) 显然有 \(1=\frac{1}{1}\),\(n=2\) 无解。
众所周知 \(1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^k}+\frac{1}{2^k}\)。注意到公式中除了 \(\frac{1}{2^k}\) 有重复外,其余项均无重复。容易想到将其中一个 \(\frac{1}{2^k}\) 拆成 \(1:2\) 的两部分,即 \(\frac{1}{2^k}=\frac{1}{2^{k-1}\times 3}+\frac{1}{2^k\times 3}\)。此时的项数 \(n=k+2\),要使得分母不超过 \(10^9\),可以解决 \(n\le 30\) 的问题。
例如:
- \(1=\frac{1}{2}+\frac{1}{2}=\frac{1}{2}+\frac{1}{3}+\frac{1}{6}\)。
- \(1=\frac{1}{2}+\frac{1}{4}+\frac{1}{4}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{12}\)。
尝试将上面的做法推广,使得其不仅能做 \(n\le 30\),还能做 \(n\le 500\)。首先,我们写出 \(1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^{28}}+\frac{1}{2^{27}\times 3}+\frac{1}{2^{28}\times 3}\)。我们维护两个集合 \(bases\) 和 \(ans\),其中 \(bases\) 是可以继续拆的分母的集合(见下文),\(ans\) 是答案的分母的集合。
那么,当 \(|ans| < n\) 时,我们重复执行:
- 从 \(bases\) 中取出最大的分母 \(u\)(感受一下就会发现最大的比最小的更优),并从 \(bases\) 中删除。
- 如果 \(2\mid u\),且分母 \(\frac{3}{2}u\) 和 \(3u\) 不在 \(ans\) 中且不超过 \(10^9\),就可以把 \(u\) 拆成 \(\frac{3}{2}u\) 和 \(3u\),加入 \(bases\) 和 \(ans\) 中。
发现这么做完之后,\(|ans|\) 只能达到 \(200\),也就是说只能解决 \(n\le 200\) 的问题。
这样就没办法了吗?当然不是。既然开始乱搞了,就要把乱搞贯彻到底。
- 否则如果 \(3\mid u\),且分母 \(\frac{4}{3}u\) 和 \(4u\) 不在 \(ans\) 中且不超过 \(10^9\),就可以把 \(u\) 拆成 \(\frac{4}{3}u\) 和 \(4u\),加入 \(bases\) 和 \(ans\) 中。
发现这么做完之后,\(|ans|\) 只能达到 \(276\),也就是说只能解决 \(n\le 276\) 的问题。
- 否则如果 \(4\mid u\),且分母 \(\frac{5}{4}u\) 和 \(5u\) 不在 \(ans\) 中且不超过 \(10^9\),就可以把 \(u\) 拆成 \(\frac{5}{4}u\) 和 \(5u\),加入 \(bases\) 和 \(ans\) 中。
发现这么做完之后,\(|ans|\) 已经足够 \(500\) 了!其准确值为 \(|ans|=1317\)。
于是做完了。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
ll T, n;
int main() {
for(scanf("%lld", &T); T; T--) {
scanf("%lld", &n);
if(n == 1) {
puts("Yes\n1");
continue;
}
if(n == 2) {
puts("No");
continue;
}
if(n <= 30) {
puts("Yes");
rep(i, 1, n-2) printf("%lld ", 1LL << i);
printf("%lld %lld\n", (1LL << (n - 2)) * 3, (1LL << (n - 3)) * 3);
continue;
}
set<ll> bases;
rep(i, 1, 28) bases.insert(1LL << i);
bases.insert((1LL << 28) * 3);
bases.insert((1LL << 27) * 3);
set<ll> ans = bases;
while(!bases.empty() && (ll)ans.size() < n) {
ll u = *bases.rbegin();
bases.erase(u);
if(u % 2 == 0 && u * 3 <= 1000000000 && !ans.count(u * 3) && !ans.count(u / 2 * 3)) {
bases.insert(u * 3);
bases.insert(u / 2 * 3);
ans.erase(u);
ans.insert(u * 3);
ans.insert(u / 2 * 3);
}
else if(u % 3 == 0 && u * 4 <= 1000000000 && !ans.count(u * 4) && !ans.count(u / 3 * 4)) {
bases.insert(u * 4);
bases.insert(u / 3 * 4);
ans.erase(u);
ans.insert(u * 4);
ans.insert(u / 3 * 4);
}
else if(u % 4 == 0 && u * 5 <= 1000000000 && !ans.count(u * 5) && !ans.count(u / 4 * 5)) {
bases.insert(u * 5);
bases.insert(u / 4 * 5);
ans.erase(u);
ans.insert(u * 5);
ans.insert(u / 4 * 5);
}
}
puts("Yes");
for(ll i : ans) printf("%lld ", i);
puts("");
}
return 0;
}
标签:ARC163C,le,frac,题解,ll,Harmonic,bases,ans,分母
From: https://www.cnblogs.com/ruierqwq/p/arc163c.html