竞赛讨论区 > 【每日一题】12月28日题目精讲
头像
王清楚
编辑于 2020-12-28 17:32
+ 关注

【每日一题】12月28日题目精讲

题号 NC113786
名称 Topforces Strikes Back
来源 CF1183F
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

作者:YangYL°

前言

这道题目是一道非常巧妙的贪心。

难度:4星

简略题意:

给定一个长度为 的序列,在序列中取至多三个数,使得这取的数互不为倍数关系。

具体做法:

因为是最多取 3 个数,不妨按取的数的个数进行分类讨论。

  • : 取一个数

这样的话当然是取最大的那个数最优,Pass。

  • :取两个数

通过手玩几组样例后,我们发现最大的那个数总是出现在 取两个数得到的最大值中。于是大胆猜想,最后的答案一定会包含最大的数。

首先约定最大的数为

接下来我们严谨证明这一点:

证明:不能为最大值,有可能取不到)

这时候,进行分类讨论:

倘若 都是 的因子,不同,所以 = ,不等式成立。这时候显然应该取 能得到最优解,那么无法构造一个序列使得等式不成立。

倘若 其中一个是 的因子,可以使得等式右边的那个 等于 中 不是 的因子的数,不等式成立。这时候应该取 能得到最优解。

倘若 都不是 的因子, 我们可以使得等式右边的那个 等于 中 较大的不是 的因子的数,不等式成立。这时候显然应该取 能得到最优解。

所以两个数的情况的最大值无论如何都会包含

因此两个数的做法就是:取序列中的最大值,然后取不是 的因子的数中的最大值,两个数相加得到两个数的情况的最优解。

  • : 取三个数。

这是一个重头戏。

根据我们在 中证明的结论来看,我们第三个情况也应该朝那个方向思考。

假设取三个数 :

(互不为倍数关系并且小于等于最大值 , 有可能取不到)

  • 倘若 都是 的因子。 那么 = ,不难发现这个情况下,构造一个序列,其中的所有数都是 的因子,取 是优于取 的(d + e不存在)。因此在这种情况下不等式有可能不成立,于是我们特判一下是否同时存在

  • 倘若 其中一个不是 的因子,那么不妨令等式的右边的 中任意一个等于这个非 的因子的数,那么就转化到了 中两个数都是 的因子的情况,不再赘述。这时候取 取得最优解。

  • 倘若 其中两个不是 的因子,那么不妨令等式的右边的 等于这两个非 的因子的数,剩下的一个数必然小于等于

  • 倘若 三个都不是 的因子,同上面两个不是 的因子的情况,不再赘述。

所以说:取三个数的做法就是:首先特判一下是否存在 都为 的因子,这种情况下对于答案取一个 ,使得情况如果存在就被考虑。 接下来取 , 然后删去所有 的因子(要取 的话, 的因子一定不出现在最后答案里面)

接下来就变成了取两个数的情况。

在剩下的数里面仍然取 , 按照两个数的做法做即可。

Code

#include <bits/stdc++.h>
using namespace std; 
const int MAXN = 2e5 + 50;
int arr[MAXN],n;
int ST[MAXN],T[MAXN];

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int main()
{
    int Q;
    cin >> Q;
    for(int v = 1 ; v <= Q ; v ++)
    {
        n = read();
        for(int i = 1 ; i <= n ; i ++)
            arr[i] = read(),ST[arr[i]] = arr[i];
        sort(arr + 1 , arr + 1 + n);
        int Ans = arr[n],Max = arr[n];
        //上面是取两个数的最大情况。
        int f2 = 0,f3 = 0,f5 = 0;
        if(Max % 5 == 0 && ST[Max / 5] != 0) f5 = 1; //ST是一个桶
        if(Max % 3 == 0 && ST[Max / 3] != 0) f3 = 1; 
        if(Max % 2 == 0 && ST[Max / 2] != 0) f2 = 1;
        if(f2 && f3 && f5)
        Ans = max(Ans,Max / 5 + Max / 3 + Max / 2);//特判
        for(int i = 1 ; i <= n ; i ++)
        {
            T[i] = arr[i];
            if(arr[n] % T[i])
            Ans = max(Ans,arr[n] + T[i]);
        }//这里是取两个数的情况,答案取个max
        for(int i = 1 ; i <= n ; i ++)//首先取Max,删掉Max的因子
            if(Max % T[i] == 0) T[i] = 2e9;
        int M = 0;
        for(int i = 1 ; i <= n ; i ++)
            if(T[i] != 2e9)M = max(M,T[i]);//找出剩下的数的里面的最大值
        for(int i = 1 ; i <= n ; i ++)//按照两个数的做法做
            if(M % T[i] != 0 && T[i] != 2e9) Ans = max(Ans,Max + M + T[i]);
        cout << Ans << endl;
        for(int i = 1 ; i <= n ; i ++)
            ST[arr[i]] = 0;//多组数据,清空桶
    }
    return 0;
}

但是事实上,上面的做法浪费了时间在sort上,我们其实并不需要sort。时间复杂度是可以做到 O(n) 的

于是贴上 O(n) 的代码:

#include <bits/stdc++.h>
using namespace std; 
const int MAXN = 2e5 + 50;
int arr[MAXN],n;
int ST[MAXN],T[MAXN];

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

int main()
{
    int Q;
    cin >> Q;
    for(int v = 1 ; v <= Q ; v ++)
    {
        n = read();
        for(int i = 1 ; i <= n ; i ++)
            arr[i] = read(),ST[arr[i]] = arr[i];
        int Ans = -1,Max = -1;
        for(int i = 1 ; i <= n ; i ++)
            Max = max(arr[i],Max);
        Ans = Max;
        //上面是取两个数的最大情况。
        int f2 = 0,f3 = 0,f5 = 0;
        if(Max % 5 == 0 && ST[Max / 5] != 0) f5 = 1; //ST是一个桶
        if(Max % 3 == 0 && ST[Max / 3] != 0) f3 = 1; 
        if(Max % 2 == 0 && ST[Max / 2] != 0) f2 = 1;
        if(f2 && f3 && f5)
        Ans = max(Ans,Max / 5 + Max / 3 + Max / 2);//特判
        for(int i = 1 ; i <= n ; i ++)
        {
            T[i] = arr[i];
            if(Max % T[i])
            Ans = max(Ans,Max + T[i]);
        }//这里是取两个数的情况,答案取个max
        for(int i = 1 ; i <= n ; i ++)//首先取Max,删掉Max的因子
            if(Max % T[i] == 0) T[i] = 2e9;
        int M = 0;
        for(int i = 1 ; i <= n ; i ++)
            if(T[i] != 2e9)M = max(M,T[i]);//找出剩下的数的里面的最大值
        for(int i = 1 ; i <= n ; i ++)//按照两个数的做法做
            if(M % T[i] != 0 && T[i] != 2e9) Ans = max(Ans,Max + M + T[i]);
        cout << Ans << endl;
        for(int i = 1 ; i <= n ; i ++)
            ST[arr[i]] = 0;//多组数据,清空桶
    }
    return 0;
}

两份代码貌似没有什么变化,主要就是一个用了sort,一个没有

欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目1月4日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(4) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐