【二分】Kevin喜欢零

向右看齐 2024-03-16 09:28 7阅读 0赞

[D-Kevin喜欢零(简单版本)\_牛客小白月赛73 (nowcoder.com)][D-Kevin_73 _nowcoder.com]

题意：

![b1a7055eb55a4ae7ba473834b7890957.png][]

思路：

一个数末尾0的个数取决于min(cnt2,cnt5)的数量

考虑枚举l，然后二分r

注意，要二分的是合法区间的左边界和合法区间的右边界

这种二分方式很常见，务必掌握

然后答案区间就取max(l1,r1),max(r1,r2)即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    const int mxe=3e5+10;
    
    int N,K;
    int a[mxn];
    int ca[mxn],cb[mxn];
    int pre_a[mxn],pre_b[mxn];
    
    void solve(){
    	cin>>N>>K;
    	for(int i=0;i<=N+10;i++) pre_a[i]=pre_b[i]=ca[i]=cb[i]=0ll;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N;i++){
    		int u=a[i];
    		while(u%2==0) u/=2,ca[i]++;
    		while(u%5==0) u/=5,cb[i]++;
    	}
    	for(int i=1;i<=N;i++){
    		pre_a[i]=pre_a[i-1]+ca[i];
    		pre_b[i]=pre_b[i-1]+cb[i];
    	}
    	int ans=0;
    	for(int l=1;l<=N;l++){
    		int v1=K+pre_a[l-1];
    		int v2=K+pre_b[l-1];
    		int l1=lower_bound(pre_a+1,pre_a+1+N,v1)-pre_a;
    		int r1=upper_bound(pre_a+1,pre_a+1+N,v1)-pre_a-1;
    		int l2=lower_bound(pre_b+1,pre_b+1+N,v2)-pre_b;
    		int r2=upper_bound(pre_b+1,pre_b+1+N,v2)-pre_b-1;
    		int L=max(l1,l2);
    		int R=max(r1,r2);
    		if(L==N+1) continue;
    		L=max(L,l);
    		ans+=(R-L+1);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[D-Kevin_73 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/57683/D
[b1a7055eb55a4ae7ba473834b7890957.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/1d0e62affabe49758bb5e1e43e70d9fb.png

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关【Kevin聊敏捷】02 项目管理的四种生命周期

文章目录四种生命周期的定义 \ 迭代vs 增量参考四种生命周期的定义预测性生命周期：这是一种传统的生命周期，前提是进行了大量的计划

清疚/ 2024年03月29日 15:42/ 0 赞/ 3 阅读

相关【Kevin聊敏捷】28. 看板Kanban-概述

> 接触过敏捷管理的人，对“看板Kanban”这个词一定不会陌生，这个虽然是源于“精益Lean”，但是经过改进之后，在敏捷管理中也有很好的应用。大家对这张图一定不陌生，你可

水深无声/ 2024年03月27日 14:23/ 0 赞/ 11 阅读

相关【二分】Kevin喜欢零

[D-Kevin喜欢零(简单版本)\_牛客小白月赛73 (nowcoder.com)][D-Kevin_73 _nowcoder.com] 题意： ![b1a7055eb5

向右看齐/ 2024年03月16日 09:28/ 0 赞/ 8 阅读

相关我不是不喜欢工作，只是不喜欢开会

项目经理最躲不过去的，就是开会。从项目立项开始到项目验收交付结束，一大串必要的、非必要的大会小会都在等着你。有网友吐槽：世界上最遥远的距离，不是生和死，而是我站在你的面

女爷i/ 2022年12月10日 08:44/ 0 赞/ 139 阅读

相关喜欢的诗词记录

喜欢的诗词记录金风玉露一相逢，便胜却人间无数。–宋·秦观《鹊桥仙·纤云弄巧》衰兰送客咸阳道，天若有情天易老。–唐·李贺《金铜仙人辞汉歌》松下问童子，言师采药去。

我不是女神ヾ/ 2022年10月09日 04:49/ 0 赞/ 126 阅读

相关喜欢的插件

打字效果-typed.js: [https://github.com/mattboldt/typed.js/][https_github.com_mattboldt_typed

àì夳堔傛蜴生んèń/ 2022年09月28日 13:06/ 0 赞/ 78 阅读

相关为什么我喜欢Firefox

昨天看到文章说Firefox 快不行了，的确心里替Firefox不平。用了许多浏览器，但最喜欢的就是Firefox. 列一些实际的原因： 1. IE对操作系统有限

怼烎@/ 2022年08月26日 11:13/ 0 赞/ 219 阅读

相关 Kevin Montrose谈StackExchange API的历史与错误

本文来源于我在InfoQ中文站翻译的文章，原文地址是：http://www.infoq.com/cn/news/2011/08/StackExchange-API 为现有站点

淡淡的烟草味﹌/ 2022年06月18日 01:24/ 0 赞/ 13 阅读

相关一些喜欢的句子~

不一定哪里搬来的QwQ知道出处的一定会写的QwQ 明日はきっと明日はきっと仆が世界の中心なので明天一定明天一定我就会是这世界的中心！ ——《妄想税》初音未来

╰+哭是因爲堅強的太久メ/ 2021年09月20日 08:46/ 0 赞/ 267 阅读

相关也许喜欢，但是，再见！

![640?wx\_fmt=png][640_wx_fmt_png] 你让世界变得柔软，也让风有了色彩｜第99篇 ![0?wx\_fmt=jpeg][0_wx_fmt_j

骑猪看日落/ 2021年05月12日 11:37/ 0 赞/ 299 阅读