首页 > 其他分享 >题解 ARC163C【Harmonic Mean】

题解 ARC163C【Harmonic Mean】

时间:2023-07-03 09:01:17浏览次数:50  
标签:ARC163C le frac 题解 ll Harmonic bases ans 分母

没想出来什么优美的解法,来个乱搞。

特判平凡情况 \(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\) 时,我们重复执行:

  1. 从 \(bases\) 中取出最大的分母 \(u\)(感受一下就会发现最大的比最小的更优),并从 \(bases\) 中删除。
  2. 如果 \(2\mid u\),且分母 \(\frac{3}{2}u\) 和 \(3u\) 不在 \(ans\) 中且不超过 \(10^9\),就可以把 \(u\) 拆成 \(\frac{3}{2}u\) 和 \(3u\),加入 \(bases\) 和 \(ans\) 中。

发现这么做完之后,\(|ans|\) 只能达到 \(200\),也就是说只能解决 \(n\le 200\) 的问题。

这样就没办法了吗?当然不是。既然开始乱搞了,就要把乱搞贯彻到底。

  1. 否则如果 \(3\mid u\),且分母 \(\frac{4}{3}u\) 和 \(4u\) 不在 \(ans\) 中且不超过 \(10^9\),就可以把 \(u\) 拆成 \(\frac{4}{3}u\) 和 \(4u\),加入 \(bases\) 和 \(ans\) 中。

发现这么做完之后,\(|ans|\) 只能达到 \(276\),也就是说只能解决 \(n\le 276\) 的问题。

  1. 否则如果 \(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

相关文章

  • AtCoder ABC307D 题解
    AtCoderABC307DMismatchedParentheses题解思路分析First——配对括号序列首先,每个右括号肯定是要与其左边最近的左括号配对。因此,我们便可以使用一个栈来进行存放左括号的下标。当有右括号时,便可以弹出栈顶元素,但是栈为空时,便无法配对。拿样例1举个例子:8a(b(d))c......
  • 洛谷 P1081 题解
    P1081[NOIP2012提高组]开车旅行题解Link洛谷题目链接Solution首先考虑这道题的暴力做法,对于第一问,枚举每个起始点,暴力计算每个点之后最近和第二近的位置,计算答案,最后取最大值。对于第二问,对每个询问独立模拟即可。复杂度较高,无法通过此题。第一个优化:考虑到对于固定的当......
  • docker启动RabbitMQ以及常见问题解决
    docker启动MQ容器下载docker镜像dockersearchrabbitmqdockerpullrabbitmqdockerrun-d--hostnamemy-rabbit--namerabbit-p15672:15672-p5672:5672rabbitmq:latest启动容器后浏览器无法访问dockerexec-it3b124f0c9712/bin/bashrabbitmq-pluginsenab......
  • CF842E Nikita and game 题解
    题意一棵树初始只有一个编号为1的根结点。\(n\)次操作,每次新增一个点作为\(p_i\)的子结点,询问更新后有多少点可以作为树直径的端点。\(n\le3\times10^5\)。题解以下\(dist(x,y)\)表示点\(x\)与点\(y\)在树上的距离。不难发现若干条直径必然叠合于至少一点,任选这......
  • Codeforces Round 881 Div2 A-F1题解
    codeforcesround881div2题解马上要秋招了,自己本事全丢了,感觉如果这样的话今年就估计要饿死了。先打div3,7月份得开始收心了A.SashaandArrayColoring题意,可以分任意组,每组的贡献是max-min,问最大贡献显然是贪心,从大到小配对一下就行,不想放代码了’B.LongLong给出一......
  • JSON中,java.lang.NoClassDefFoundError: net/sf/ezmorph/Morpher问题解决
    使用JSON,在SERVLET或者STRUTS的ACTION中取得数据时,如果会出现异常:java.lang.NoClassDefFoundError:net/sf/ezmorph/Morpher是因为需要的类没有找到,一般,是因为少导入了JAR包,使用JSON时,除了要导入JSON网站上面下载的json-lib-2.2-jdk15.jar包之外,还必须有其它几个依赖包:commons-bean......
  • dpkg-reconfigure命令找不到问题解决
    作者: adminhttps://cloudbool.com/archive/dpkg-reconfigure-command-not-found.html今天在SSH远程连接到服务器时,遇到了dpkg-reconfigure命令找不到的问题,觉得很是奇怪,花了点时间研究下,这里做个记录,以备后用。前情提要我远程的服务器系统是自行使用DebiannetinstISO镜......
  • [ABC306] C/D 题解
    C.Centers 参考算法统计,排序\(\rmSyx\)给你\(3\timesN\)个数,其中\(\rmSyx\)可以保证:\(1\simN\)之间的所有数都出现了\(3\)次,请你将\(1\simN\)之间的数每个出现在第\(2\)个位置的下标进行排序,并从小到大输出原数。用\(\rmmap\)记录数出现的次数,......
  • 【题解】#119. 最大整数 题解(2023-07-01更新)
    #119.最大整数题解题目传送门更新日志2023-05-2617:20文章完成2023-05-3015:22文章审核通过2023-07-0116:04修改了代码题目知识点字符串+贪心题意说明设有n个正整数($n<20$),将它们连接成一排,组成一个最大的多位整数。(题目简介明了,一看就是出题人懒得写题目背景)......
  • 【题解】P8679 [蓝桥杯 2019 省 B] 填空问题 题解
    P8679[蓝桥杯2019省B]填空问题题解题目传送门欢迎大家指出错误并联系这个蒟蒻更新日志2023-05-2521:02文章完成2023-05-2711:34文章通过审核2023-06-2021:03优化了文章代码格式试题A:组队【解析】本题是一道经典的DFS搜索题,每次对各号位的选手进行DFS,......