首页 > 其他分享 >Codeforces Round 911 (Div. 2) vp D题

Codeforces Round 911 (Div. 2) vp D题

时间:2024-03-01 20:56:39浏览次数:30  
标签:gcd sum vp 因数 就是 Div 911 统计 数字

前面三题,就B题一道900的题目让我wa了两发,而且有点难看出来
主要是想不到。。不知道该怎么像。
应该算是题目理解不清晰吧,很麻烦。。这个原因可以说是没有一个完整的思考路径,我能够直接想到答案接近的处理方法,但是细节上没有注意。在考虑问题的时候可能。。需要慢一些,太快了,容易漏下点东西,然后就会一直wa。

A和C都是水题(其实E也差不多,只要会tarjan的人都能写)

这个D题,很值得讨论一下,是一个复盘的很好的对象。

我先把我考试的时候的思路写下来

首先,我们可以知道,对于a数组里面的两个数字\(a[i],a[j]\ (i\leq j)\),对答案的贡献是\(gcd(a[i],a[j])*(n-j)\),这是可以计算得到的。
但是,不管怎么样,只要我们试图去计算两个数字之间的\(gcd\),这个代码就必然超时。因为,很明显,\(gcd(a[i],a[j])\)和\(gcd(a[j],a[k])\)是没有任何明显的数值上的关系的,也就是,在这个层面上,我们尝试去计算两个数字之间的gcd并且统计,是绝对打不破\(O(n^2)\)复杂度的瓶颈的。而\(n=1e5\),这是不能接受的。
所以要转换思路,假如\(gcd(a[i],a[j])\)换成其他计算,这题可能就假了,gcd是有它本身的特殊性的,我们其实是能从上面的分析得到的(不然就是假题)。
所以我们要做的就是利用gcd的特殊性来进行统计答案。gcd是最大公约数,这是他的定义。我们可以发现,最大公约数的大小和参与计算的数值是有直接关系的,而\(a[i]\leq 1e5\),这就能说明很多了。
然后我考试的时候就开始脑抽了。。我算了算\(1e5\)范围的质数(?我在干什么),发现只有少于1e4个,然后觉得可做,然后想了想发现gcd和质数没什么关系,然后就觉得这题做不了了。。。
其实这题目和质数就是没有任何关系的。有关系的是每一个数字的因数。我们可以先对a数组排序,然后从小到大枚举\(a[i]\),然后再枚举\(a[i]\)的因数,对于它的每一个因数,统计前面有多少个数字出现了这个因数,给答案先加上。
这很明显的是有重复的,但是我们在\(O(n\sqrt{a[i]})\)的复杂度内统计到了一个类似答案的东西!
然后后面的事情其实就是减去重复的部分了,重复的部分就是类似一个数字有因子2,4,8,而另一个数字也有,那这三个因数就都会被统计一次。我们要做的,就是枚举每一个因数,然后枚举它的每一个倍数,让小的因数的数量减去属于它的大的因数的数量,因为它不是gcd,它只是一个公约数,并不是最大的。

这个容斥的过程是很难想的。
其实也还好。
就是,sum[i]先表示有几个数字以i作为公约数,然后对于sum[2],很明显,sum[4]肯定是在sum[2]里面被统计过的,sum[6]也是,sum[8]也是,sum........,那我们用sum[2]-=sum[4]+sum[6]+sum[8],一直减到最后,剩下的sum[2]的内容,不就是以2作为最大公约数的数字数量了吗?因为如果两个数字没有2这个公约数,它开始就不在,如果他们有其他的更大的公约数,那它就是2的倍数,刚刚的过程就已经把它剪掉了。
剩下的,不就是答案了?

这个过程是\(O(a[i]\sqrt{a[i]})\)的,所以这个算法的总体的时间复杂度就是\(O((n+a[i])\sqrt{a[i]})\)

可以通过。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
    char c=getchar();ll a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll n,a[200101];
ll sum[200101],cnt[200101];//sum[i]表示有几个数字以i作为公约数,后面处理之后就变成了作为最大公约数了
vector<ll> fact[100201];
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    for(int i=1;i<=100000;i++)
    {
        for(int j=i;j<=100000;j+=i)
        {
            fact[j].push_back(i);//以j的因子有那些
        }
    }
    int T=read();
    while(T--)
    {
        n=read();
        memset(sum,0,sizeof(sum));
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
        }
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++)
        {
            int len=fact[a[i]].size();
            for(int j=0;j<len;j++)
            {
                sum[fact[a[i]][j]]+=cnt[fact[a[i]][j]]*(n-i);
                cnt[fact[a[i]][j]]++;//前面有几个数字
            }
        }
        ll ans=0;
        for(int i=a[n];i>=1;i--)
        {
            for(int j=i+i;j<=100000;j+=i)
            {
                sum[i]-=sum[j];
            }
            ans+=sum[i]*i;
        }
        cout<<ans<<endl;
    }
    return 0;
}


为什么我会想不到这个过程?
(不得不承认我都不知道为什么我会tm想到质数。。)
这可以算是gcd的偏难的题目了,把dp和gcd结合了。
这个先统计,然后再减去重复的想法,本身就是比较难想的。它是很缺少启发性的,因为在你统计的时候,你要怎么才能知道你统计的东西是能够这种去重得到的呢?
呃,对于这一题其实还好,因为你知道了所有的因数之后,gcd其实是一个类似他们的导数的东西,它只是相邻两个之间的增量吧。
还是有点可能能够直接看出来的。
但是对于其他这种题呢?
那估计就是难题了。这个时候我感觉刷题量的优势就体现出来了。刷的题多了,其实就知道了这样去处理gcd是可以的。或者说,其实就知道了gcd的处理方式比较唯一或者说是不多。那就很快了。因为除了这个办法没有其他办法。

对于这题的复盘,主要就是记录一下这个先统计再去重的思路可以用再这种题目上,这样以后遇到这种题目就能写出来了。还有因数的处理吧。

还是要多写,多看,多想啊。

标签:gcd,sum,vp,因数,就是,Div,911,统计,数字
From: https://www.cnblogs.com/HLZZPawa/p/18047910

相关文章

  • div3笔记
     Problem-E-Codeforces这道题用了记录一个数末尾零的板子(敲重点)!!!再说一遍,简单博弈论就是贪心!1voidsolve(){2cin>>n>>m;3vector<int>a(n),b(n);4for(inti=0;i<n;i++)cin>>a[i];5intlen=0;//这组数字总共有几位,总长度6......
  • 2024 蓝桥杯模拟赛3(div1+div2)
    2024蓝桥杯模拟赛3(div1+div2)P8834[传智杯#3决赛]序列简单的模拟,数据范围很小,暴力即可点击查看代码#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+5;voidsolve(){ lln,k,a[N],cnt=0; cin>>n>>k; for(inti=1;i<=n;i++)c......
  • vue项目引入高德地图报错:Map container div not exist (火狐浏览器不加载地图)
    问题描述:谷歌浏览器正常显示地图,火狐浏览器不加载,并且报错:  Mapcontainerdivnotexist错误代码如下:  修改后代码如下:  参考大佬:https://blog.csdn.net/white_777/article/details/128286558  ......
  • Codeforces Round 930 (Div. 2) - sol
    20240301由于笔者实力较弱,所以这只是Div2的题解。四年一次的比赛啊,还是要打。Dashboard-CodeforcesRound930(Div.2)-CodeforcesA.ShufflePartyYouaregivenanarray\(a_1,a_2,\ldots,a_n\).Initially,\(a_i=i\)foreach\(1\lei\len\).Theopera......
  • 14 CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)C. Tenzing and Balls(dp+前缀
    思路:dp还是挺明显的,思路可以参考最长上升子序列有点dp的感觉\(f[i]\)表示考虑前\(i\)个数,的最大值当前数有两种删或不删不删:\(f[i]=f[i-1]\);删:\(f[i]=max{f[j-1]+i-j+1}\)这个转移是\(O(n^2)\)的显然时间上来不及考虑优化,第一层循环一定是省不了的考虑优化掉第二层循环......
  • 云原生:使用HPA和VPA实现集群扩缩容
    1背景我们之前介绍过,随着业务流量上涨之后,我们的系统需要适时的进行扩容。数据存储层我们也介绍过MySQL的扩容ScaleUP(纵向扩展)和ScaleOut(横向扩展)垂直拆分(ScaleUp纵向扩展):包括垂直分库、垂直分表水平拆分(ScaleOut横向扩展):包括库内分表、分库分表详细可以参考笔者......
  • Codeforce Round 929(Div.3)
    CodeforcesRound929(Div.3)刷题记录A.TurtlePuzzle:RearrangeandNegate//Problem:A.TurtlePuzzle:RearrangeandNegate//Contest:Codeforces-CodeforcesRound929(Div.3)//URL:https://codeforces.com/contest/1933/problem/0//MemoryLimit:256MB......
  • Codeforces Round 929 (Div. 3)
    CodeforcesRound929(Div.3)A-TurtlePuzzle:RearrangeandNegate代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128_t;usingpiii=pa......
  • 13 Codeforces Round 886 (Div. 4)G. The Morning Star(简单容斥)
    G.TheMorningStar思路:用map记录x,y,以及y-x、y+x从前往后统计一遍答案即可公式\(ans+=cnt[x]+cnt[y]-2*cnt[x,y]+cnt[y+x]+cnt[y-x]\)\(cnt[x]+cny[y]-2*cnt[x,y]\)是统计坐标轴方向的,-2倍是需要把本身这个点给减去容斥是减一倍,这里还需要把自己给挖掉\(cnt[y+x]+cnt[y......
  • CVPR、ECCV、ICCV三大顶会显著性目标检测近三年发表论文统计
    2021(11篇)CVPR1.CalibratedRGB-DSalientObjectDetectionWeiJi,JingjingLi,ShuangYu,MiaoZhang,YongriPiao,ShunyuYao,QiBi,KaiMa,YefengZheng,HuchuanLu,LiCheng;ProceedingsoftheIEEE/CVFConferenceonComputerVisionandPatternRecogn......