P2022 有趣的数
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。
输入输出样例
Sample 1: 2 4
Sample 2: 100000001 1000000000
这里Sample 1 和 2是分开的两个数据点。
Sample 1: 11
Sample 2: 100000000888888879
说明
【数据约定】
40%的数据,1<=K,M<=10^5;
100%的数据,1<=K,M<=10^9。
感受:
我当时在想难道用暴力?倍增?二分?……结果是道数论题,我C 鬼能做出来?自己看题解吧。
先上50分暴力代码:(利用string的字典序排序 挨个排序 记录符合要求个数,判断,输出)
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll n,m;
string s;
void prepare(){
ll p=n,l(),a[]={};
while(p) a[++l]=p%,p=p/;
for(ll i=l;i;i--) s+=char(a[i]+'');
}
int judge(){
ll i,j;
ll l=,p=,sum=;
ll k=n;
for(;k;k/=,l++);
k=n;
for(i=;i<=l-;i++) p=p*;
if(k==p&&m>l) return ;
while(k){
sum+=k-p;
k=k/;
p=p/;
}
sum+=(l-);
return sum>=m;
}
int main(){
ll i,j,k;
scanf("%d%d",&n,&m);
if(n==&&m==){
printf("");return ;
}
if(judge()){
printf("0\n");return ;
}
prepare();
i=;
ll sum=;
for(;;i++){
string ss;
ll p=i,a[]={},l=;
while(p)a[++l]=p%,p=p/;
for(j=l;j;j--) ss+=char(a[j]+'');
if(ss<=s) sum++;
if(sum==m){
printf("%d",i);
return ;
}
}
return ;
}
题解:
由于答案可能非常大,所以这道题显然不能用枚举,即便用二分,时间复杂度{O[N(logN)^2]}也特别大。我们可以设所有字典序比K小的数中的第M-1个为X,N就等于K与X的最大值,怎么求X呢?[delete]当然是枚举。[/delete]我们把所有字典序比K小的数分成无穷大个集合。集合Ai里的任意两个数j,k,都满足i=floor(log10(j))=floor(log10(k))(floor(a)表示取a的整数部分,log10(a)表示以10为底,以a为真的对数值),其中最大值为ai。我们可以发现,设K的左数第i位是pi,qi=∑pj*(i-j+1)(1<=j<=i),当j<=log10(K),|Aj|=qj-1,aj=qj-1;当j>log10(K),|Aj|=|A(j-1)|*10(请读者自己证明)。由此我们可求出X所在集合Ai,且X=ai+[M-∑|Aj|(1<=j<=i)]-1。求X所在集合的时间复杂度和求出X所在集合后求X的值的时间复杂度均为O[log10(N)],总的时间复杂度为O[log10(N)]。
AC代码:
#include<iostream>
using namespace std;
long long k,m,i,number,n;
int main(){
cin>>k>>m;
for(i=;i<=k;i*=) number+=k/i-i+;number--;
if(number>=m||k-(i/)==&&number<m-){cout<<;return ;}
for(i=k-(i/),n=k;number<m-;i*=,number+=i,n*=);
cout<<max(n-number+m-,k);
return ;
}
最新文章
- [转载]Grunt插件之LiveReload 实现页面自动刷新,所见即所得编辑
- Github注册过程
- jquery音乐播放器(歌词滚动版)
- Linux下LDAPSearch的例子
- linux install sublime_text3
- OGNL valueStack StackContext(ActionContext)深入分析(转+个人理解)
- Mysql的Error 1364
- flexigrid 修改json格式
- Android中绘制圆角矩形图片及任意形状图片
- Hardcoded string XXX,&;…
- win10 DVWA下载安装配置(新手学渗透)
- H5与C3权威指南笔记--box-shadow
- Wannafly挑战赛23 T2游戏 SG函数
- C++ 获取字符串中的所有汉字
- python之装饰器函数
- 如何在生产环境使用Btrace进行调试
- 平面图转对偶图&;19_03_21校内训练 [Everfeel]
- (二)使用预定义模型 QStringListModel例子
- Java学习笔记心得——初识Java
- 如何导入数据到Mysql
热门文章
- 有关获取session属性时报nullPointException(空指针异常)的解决方案
- [转帖]ExtJs与服务器的交互(一)
- oracle中substr函数的用法
- Receive Windows Messages In Your Custom Delphi Class - NonWindowed Control - AllocateHWnd
- 理解MVVM模式
- netcdf入门(转)
- SQL Server 2008数据库重命名方法
- Java 完美判断中文字符的方法
- linux 内核调试方法
- 求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)