CarryNotKarry

  • 首页
  • 语言学习
    • C++程序设计
    • 汇编语言
    • Python
  • 比赛总结
  • ACM-ICPC
    • 动态规划
    • 字符串
    • 搜索
    • 数学
    • 数据结构
    • 图论
    • 计算几何
    • 杂项
  • 分享
  • 上课内容
  • 其他
Carry
CUGBACMer/皇马球迷/C罗人迷
  1. 首页
  2. ACM-ICPC
  3. 数学
  4. 正文

牛客小白月赛F(根号trick)

2022年10月29日 391点热度 0人点赞 0条评论

今天写牛客小白月赛的时候,做完前三题看到第四题是一个模拟,就没有写了,直接去看做的人数较多的F,做法直接让我大开眼界...
题目链接:牛客小白月赛F-困难卷积

题意:

给出两个序列a_i,b_i,求出:

\sum_{i=1}^{n} \sum_{j=1}^{n}\left \lfloor \sqrt{\left|a_{i}-b_{j}\right|} \right \rfloor

范围是:
1\le n\le 10^6, 0\le a_i,b_i \le 3\times 10^6, \Sigma a_i,\ \Sigma b_i\le 10^7

思路

这里一开始注意到特殊的地方,也就是为什么给出a,b序列的总和小于等于10^7,重点就是在这里:

根号trick:序列a_i中不同数字的个数小于等于\sqrt{\Sigma a_i}

其实这么一想,已知总和sum,问最多有多少个不同的a_i来构成。我们可以用贪心的方法,例如上面的总和是10^7,所以我们从最小的开始选,选1,2,3,\cdots,假如最大选到m,那么可以得出目前的总和是

sum^\prime = 1+2+3+\cdots +m-1+m=\frac{(1+m)\times m}{2}\le sum=10^7

所以能够得出来m最多是\sqrt{2\times 10^7}=4472,姑且算它5000吧,所以这样平方级别的复杂度完全可以通过。

那么这个m=5000能够说明什么呢?之前的n=10^6,这样差别很大,说明一定一定一定有很多重复的数字,所以我们完全不用重复枚举,一个数字重复出现我们只算一次,具体请看代码就懂啦~

代码

map<int,int> mpa, mpb;
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>x, mpa[x]++;
    for (int i=1;i<=n;i++) cin>>x, mpb[x]++;
    for (auto &[x, na]:mpa)
        for (auto &[y, nb]:mpb)
            ans += (int)sqrt(Abs(x-y))*na*nb;
    cout<<ans;
}

补充

与此类似的,还有给你一个很大的数字,实际上能够拆分的不同的质因数也只有少数刚过10个,一般差不多是12个。

标签: 根号 牛客小白月赛
最后更新:2022年10月29日

Carry

来自于湖南长沙

点赞
< 上一篇
下一篇 >

文章评论

取消回复
标签
根号 牛客小白月赛
文章目录
  • 题意:
  • 思路
  • 代码
  • 补充
其他文章

Carry爱三进制题解

【区间DP】POJ2955.Brackets

Codeforces Educational Round 122(Rated for Div.2)比赛总结 (rating+77)

汇编语言 实验四 子程序结构

汇编语言 实验三 循环结构和分支结构程序设计

C++程序设计

【基环树+思维】AcWing 1738.蹄球——每日一题2.6

AtCoder Beginner Contest 238比赛总结

【算法学习】线性基

【线性基】[BJWC2011]元素题解

From Carry
  • 在下不才,本博客也是为了记录自己的成长,并非成为非常专业的博客。
  • 如果有能够帮助你的地方是我最大的荣幸,一起加油吧!

ECNU-My love

THEME KRATOS MADE BY VTROIS