Day24h

分类

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章（共5篇）

Send Boxes to Alice

E. Send Boxes to Alice 首先求出每一个位置的前缀和。对答案进行复杂度为\(\sqrt{a[n]}\)的遍历，因为最后的答案不可能大于\(\sqrt{a[n]}\) for(ll j=2;j*j<=a[n];++j) if(a[n]%j==0) ...

前缀和思维

2019-11-23

0 398

前缀和

前缀和一维：构建前缀数组： for(int i=1;i<=n;++i) a[i]+=a[i-1]; 应用场景： ①求 \(a[1]～a[i]\)的累加和 ans=a[i]; ②求\(a[i]～a[j](j>=i)\)的累加和 ans=a[j...

前缀和

2020-01-12

0 344

Monitor

Monitor 该题的目标对象是一个二维数组 ①该题没有给出二维数组的具体范围，而只是给出了\(n*m<=1e7\) 不能够直接定义数组，那么就可以进行动态开辟数组 vector<vector<int> > a(n+5,vector<int&g...

前缀和差分

2020-01-12

0 357

Vasya and Robot

C. Vasya and Robot 关键算法：二分、前缀和刚看到题的时候一点想法都没有... 先观察一下数据范围$(1≤n≤2⋅10^5)(−10^9≤x,y≤10^9) $ 可以用两个数组\(x[i],y[i]\)来表示在\(i\)操作完之后的机器人的位置 fo...

前缀和二分

2020-01-12

0 351

Molly's Chemicals

C. Molly's Chemicals 这道题的思路跟C. Summarize to the Power of Two十分的相似。都是要求关于某个数的倍数。优化方式都是用一个 map 来储存存在的数字，然后用某个数的幂次方减去当前遍历数字，看 map 是否存在有这个值。因为转化为幂次...

前缀和

2020-01-12

0 409