题解 | #F. 小红的零#

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

F. 小红的零

整数末尾0的个数,取决于2和5的因子个数的最小值.

难点就在于:最小值

先来看2道基础题

对于一个数组arr, 给予一个x, 求

这题的思路,就是对arr进行排序,然后绝对值去掉,这样就划分为2个部分,一部分小于x,另一部分大于等于x

利用前缀和预处理,可以二分到分界点, 解决问题

求一个数组的所有子区间(2的因子个数)累加和

这是弱化版本,那其思路遍历右端点,然后累计

S(i) = S(i-1) + (i+1)*f(i)

最终S(i)的累加和

而这题的核心思路,其实上延续了类似思想

令f(x)为前x项的2因子的前缀和, g(x)为前x项的5因子的前缀和

对于某个区间[l, r]

则区间[l, r] 其贡献为

    • 贡献为 g(r) - g(l - 1)
    • 贡献为f(r) - f(l - 1)

本质上这题的巧妙之处在于

  • 维护2因子多的区间(累加和,个数)
  • 维护5因子多的区间 (累加和,个数)

而这个因子多少,是一个变动的过程,根据右端点来决定范围

  • 大于z(x),为2因子多的区间

  • 小于等于z(x), 则为5因子多的区间

所以这边采用4个树状数组

fw2, fwc2代表2因子的前缀和f(x),对应2因子的区间个数,

fw5, fwc5代表5因子的前缀和g(x),对应5因子的区间个数

而把 z(x) 作为 树状数组的 index-key

因为2因子和5因子个数,最多30n,考虑到负值,最多60n

引入offset作为偏移,不需要离散化

感觉这题思路还是挺绕的,可能直接看代码,更容易理解

感觉这题掺杂了 前缀和的前缀和

import java.io.*;
import java.util.*;

public class Main {

    static class BIT {
        int n;
        long[] arr;
        public BIT(int n) {
            this.n = n;
            this.arr = new long[n + 1];
        }
        void update(int p, long v) {
            while (p <= n) {
                this.arr[p] += v;
                p += p&-p;
            }
        }
        long query(int p) {
            long res = 0;
            while (p > 0) {
                res += this.arr[p];
                p -= p&-p;
            }
            return res;
        }
    }

    static int split(int v, int b) {
        int cnt = 0;
        while (v % b == 0) {
            v /= b;
            cnt++;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();

        int mx = 60 * n; // 2^30 > 1e9, 因为绝对值的问题,所以30*2*n
        int offset = 30 * n; // 引入offset,是因为这边没有离散化,而是做了一个偏移,平衡负值

        BIT fw2 = new BIT(mx);  // 2的因子累加和
        BIT fwc2 = new BIT(mx); // 2的因子计数

        BIT fw5 = new BIT(mx);  // 5的因子累加和
        BIT fwc5 = new BIT(mx); // 5的因子计数

        long res = 0;
        int acc2 = 0, acc5 = 0;
        int diff = 0;
        for (int i = 0; i < n; i++) {
            // 前缀和为key
            fw2.update(diff + offset, acc2);
            fwc2.update(diff + offset, 1);
            fw5.update(diff + offset, acc5);
            fwc5.update(diff + offset, 1);

            int v = sc.nextInt();
            int n2 = split(v, 2);
            int n5 = split(v, 5);
            diff += (n2 - n5);
            acc2 += n2;
            acc5 += n5;

            // 进行统计计算
            long sum2 = fw2.query(mx) - fw2.query(diff + offset);
            long cnt2 = fwc2.query(mx) - fwc2.query(diff + offset);
            long sum5 = fw5.query(diff + offset);
            long cnt5 = fwc5.query(diff + offset);
            res += (acc2 * cnt2 - sum2) + (acc5 * cnt5 - sum5);
        }

        System.out.println(res);

    }

}
全部评论
请问,S(i) = 2 * S(i-1) + (i+1)*f(i)是怎么推出来的啊
1
送花
回复 分享
发布于 2023-11-21 10:03 北京
fw 可还行, hhhhh
1
送花
回复 分享
发布于 2023-11-22 15:25 安徽
国泰君安
校招火热招聘中
官网直投

相关推荐

💼公司岗位&nbsp;tx客户端岗本人背景中九硕,cpp选手。当时在牛子上看cpp选手找不到后端岗实习,遂投了腾子的客户端想练练手。🕐面试过程投递之后很快约面了,一面面试官比较和蔼问的也是正常八股加项目的模式。然后约了二面,二面面试官应该是入职后的leader,这轮面试就离谱了,一开始问了一些八股(感觉那面试官也不怎么懂技术像是照着书上写好的问题问一样),后面离谱的来了,直接疯狂压力测试(你为什么觉得你能xxx,你能不能接受xxx)。当时因为对tx还有滤镜,把自己当作一个牛马的姿态来回答这些问题。面完之后面试官可能觉得我是一个合格的牛马,他加了我微信,问我什么时候能去实习,我说六月初,他说有点晚了,然后考虑了一天还是给我过了面试,然后3面和hr面就也是正常流程了。🐶事件起因5月末的时候导师临时给安排了一个项目,于是我就去微信问那个leader,能不能推迟到6月24入职,如果不能我可以主动放弃offer,他当时犹豫再三还是同意了(现在回想起来可能是当时还没有备胎)。就在昨天他又问我什么时候入职,然后我说24号,他说有点晚叫我看看系统上还有没有其它入职时间,因为我还没在系统上填入职信息(在牛子上看到说只有快入职了,才会有人审核,遂想端午节后再填),查看不了可申请入职的时间。和他说了原因后,这下给他抓到把柄了,直接来一句&amp;quot;你对这次实习并不重视,确实没什么必要了&amp;quot;&nbsp;&nbsp;😅。感觉应该是找到备胎硬气了,就想把我踹走。不过爷也不想去了,客户端前景本来就不太好,这个leader也是个pua怪加压力怪,反正也是双向选择。最后再给大家一个建议,在面试过程中就感觉不舒服的组,一定不要去了,去了也只会更难受。 #不给转正的实习,你还去吗#&nbsp;&nbsp;#找实习多的是你不知道的事#
景洪:“在面试过程中就感觉不舒服的组,一定不要去了,去了也只会更难受。” 谢谢楼主的总结,这个太赞同了,我有次就是实习前面试感觉体验特别差,入职之后就是各种pua和压力。 大佬,你值得更好的
点赞 评论 收藏
分享
5 1 评论
分享
牛客网
牛客企业服务