A-想要更多的0_2022河南萌新联赛第(六)场:郑州大学 (nowcoder.com)
2022/8/20 23:54:50
本文主要是介绍A-想要更多的0_2022河南萌新联赛第(六)场:郑州大学 (nowcoder.com),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A-想要更多的0_2022河南萌新联赛第(六)场:郑州大学 (nowcoder.com)
这个题思路倒是很好想到主要是处理[0,n]区间内0出现的次数
考虑这个问题 比如对3891205举例。
-
我们取到数第四位数,其形式也就可以是xxx0xxx这种情况你前面可以取[1,389]后面可以取[0,999]所以答案就是389*1000。这种情况是小于本位
-
如果我们取倒数第二位,xxxxx0x前面可以取[1,38911]后面可以取[0,9],但是我前面也可以取38912但是后面就只能取[0,5]了。所以这种情况就是38911*10+6;,这种情况是等于本位
这已经足够解决这个问题了,我们将问题延伸到1-9这样的数字,就多了一种情况就是大于本位,还是拿上面那个数举例子。xxx6xxx
这样子就是高位只能取[0,388]了,因为取389无论如何都是大于原数的。
思路来源:(11条消息) 经典的数1问题天岚1993量产机的博客-CSDN博客
#include<bits/stdc++.h> using namespace std; #define fel(i,x,y) for(int i=x;i<=y;i++) #define feh(i,x,y) for(int i=x;i>=y;i--) #define int long long #define pb push_back #define IOS cin.tie(0)->sync_with_stdio(false); #define inf 0x7fffffff #define endl "\n" /* 二分肯定是二分 但是如何求一个区间内的的0的个数 求[m,n]区间内0的个数只要求[0,m-1]和[0,n]即可 求0-n这个区间内右多少个0我就直接枚举每个位置上是0数字有多少 */ int n,k; int sum(int x){ int ans=1,d=1,t=x;//但是如果x等于0的话就不会进入循环 while(x){ if(x%10==0)//当前位置为0的情况这种情况高位不能全为0即可并且但高位相等的情况时低位最大只能等于原数 ans+=(x/10-1)*d + (t%d+1); else ans+=(x/10)*d;//这种情况就是高位可以取[1-389]低位可以取[0,999]; d*=10; x/=10; } return ans; } bool check(int x){//求[x,n]区间内0出现的个数是否大于k int t=sum(n)-sum(x-1); return t>=k; } signed main(){ cin>>n>>k; int l=0,r=n,ans=0; if(sum(n)<k){ cout<<-1<<endl; return 0; } while(l<=r){ int mid=l+r>>1; if(check(mid)) ans=mid,l=mid+1; else r=mid-1; } cout<<ans<<endl; return 0; }
这篇关于A-想要更多的0_2022河南萌新联赛第(六)场:郑州大学 (nowcoder.com)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!