洛谷 P2022 有趣的数 解题报告
2024-10-19 07:39:39
P2022 有趣的数
题目描述
让我们来考虑1到N的正整数集合。让我们把集合中的元素按照字典序排列,例如当N=11时,其顺序应该为:1,10,11,2,3,4,5,6,7,8,9。
定义K在N个数中的位置为Q(N,K),例如Q(11,2)=4。现在给出整数K和M,要求找到最小的N,使得Q(N,K)=M。
输入输出格式
输入格式:
输入文件只有一行,是两个整数K和M。
输出格式:
输出文件只有一行,是最小的N,如果不存在这样的N就输出0。
说明
【数据约定】
40%的数据,1<=K,M<=10^5;
100%的数据,1<=K,M<=10^9。
我大概是看了题解胡乱搞过得。。
首先手玩玩出如何在给定的集合找到指定位置的数,然后玄学看出单调性开始二分答案,最后要判一堆一堆的东西。。
乱搞的代码:
#include <cstdio>
#define ll long long
ll m,k,c=1;
ll get(ll n,ll x,ll d)
{
ll cnt=0;
while(233)
{
if(n>=d&&n<d*10) break;
cnt+=x-d;
x*=10;
d*=10;
}
cnt+=(x>n?n:x)+1-d;
return cnt;
}
ll get0(ll x)
{
ll t=x/10,d=1,cnt=0;
while(t)
d*=10,t/=10;
while(x)
{
cnt+=x+1-d;
d/=10;
x/=10;
}
return cnt;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("wr.out","w",stdout);
scanf("%lld%lld",&k,&m);
for(ll i=1,f=1;i<=10;i++,f*=10)
{
if(k==f&&m!=i)
{
printf("0\n");
return 0;
}
}
int t=get0(k);
if(t>m)
{
printf("0\n");
return 0;
}
else if(t==m)
{
printf("%d\n",k);
return 0;
}
m-=t-1;
ll l=k*10,r=1e18;
while(c<k) c*=10;
k*=10;
if(k-c>m)
{
printf("%lld\n",m+c-2);
return 0;
}
while(l<r)
{
ll mid=l+r>>1;
if(get(mid,k,c)>=m)
r=mid;
else
l=mid+1;
}
printf("%lld\n",l-1);
return 0;
}
2018.7.9
最新文章
- sh7.创建yum源脚本练习
- CI框架搭建
- 梯度下降(Gradient Descent)小结
- 让计算机崩溃的python代码,求共同分析
- Linux-CentOS 6.5 mini 中没有curses.h的问题
- JavaScript中的ParseInt(";08";)和“09”返回0的原因分析及解决办法
- 关于linux python vim的一些基础知识(很零散)
- C# JackLib系列之Form窗体的ShowWithoutActivation属性及其作用
- iOS开发:AVPlayer实现流音频边播边存
- Java从入门到精通(一)
- [置顶] STM32移植contiki进阶之三(中):timer 中文版
- VS2012生成绿色版程序的方法
- 正确、安全地停止SpringBoot应用服务
- tcpdump使用方法小结
- python自学1——接口测试
- XIB中拖UIScrollView的困难
- @ConfigurationProperties + @EnableConfigurationProperties
- urllib.parse.quote
- python——append与extend
- (转)Xcode导航快捷键(大全)