ZOJ Monthly, January 2019 E:Little Sub and Mr.Potato's Math Problem 构造

本文主要是介绍ZOJ Monthly, January 2019 E:Little Sub and Mr.Potato's Math Problem 构造，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

让我们来考虑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。

 

输入输出样例

输入样例#1： 复制

2 4

输出样例#1： 复制

11

输入样例#2： 复制

100000001 1000000000

输出样例#2： 复制

100000000888888879

说明

【数据约定】

40%的数据，1<=K,M<=10^5；

100%的数据，1<=K,M<=10^9。

 

比赛的时候，思路请教的学长讨论出来了，但是就一直WA，，然后听说这题是是洛谷的原题，题意：https://www.luogu.org/problemnew/show/P2022

然后就比较迷，两边的数据好像不一样，洛谷能过的，EOJ不一定能过，EOJ能过得，poj就不能过。

具体思路：

参考博客：https://www.cnblogs.com/Dup4/p/10292338.html    （这个代码好，都能过）

洛谷：https://www.luogu.org/problemnew/solution/P2022 这个也讲不错

//均AC代码

#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef unsigned long long ull;const double eps = 1e-8;
const ll MOD = 1e9 + 7;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;ll k, m;
int arr[maxn];
ll pow_10[10];void Init()
{pow_10[0] = 1;for (int i = 1; i <= 18; ++i){pow_10[i] = pow_10[i - 1] * 10;}
}void solve()
{ll num = 1;for (int i = 1;; ++i){if (num > k) break;else if (num == k){if (i == m){printf("%lld\n", k);return;}else{puts("0");return;}}num *= 10;}int len = 0;num = k;while (num){arr[++len] = num % 10;num /= 10;}reverse(arr + 1, arr + 1 + len);ll ans = 0;num = 0;for (int i = 1; i <= len; ++i){num = num * 10 + arr[i];ans += num - pow_10[i - 1];if (i != len) ++ans;}if (ans >= m){puts("0");return;}else if (ans == m - 1){printf("%lld\n", k);return;}while (1){len++;num *= 10;if (ans + num - pow_10[len - 1] >= m - 1){ans = pow_10[len - 1] + m - ans - 2;printf("%lld\n", ans);return;}ans += num - pow_10[len - 1];}
}void RUN()
{Init();int t;scanf("%d", &t);while (t--){scanf("%lld %lld", &k, &m);solve();}
}int main()
{
#ifdef LOCAL_JUDGEfreopen("Text.txt", "r", stdin);
#endif // LOCAL_JUDGERUN();#ifdef LOCAL_JUDGEfclose(stdin);
#endif // LOCAL_JUDGEreturn 0;
}

自己WA错误

#include <iostream>
#include <stdio.h>
using namespace std;
#define ll long long
ll k,m;
ll a,g,tt,ans,b,temp;
ll mi[20];
int main()
{mi[0]=1;for(int i=1;i<19;i++) mi[i]=mi[i-1]*10;int t;scanf("%d",&t);while(t--){scanf("%lld%lld",&k,&m); //k是那个数，m位for(int i=0;i<10;i++){if(k==mi[i]&&m!=i+1){printf("0\n"); return 0;}}a=1;g=k; tt=k;while(g){a*=10;g=g/10;}ans=0;b=a/10;while(k){ans+=(k-(b-1));b=b/10;k=k/10;}temp=m-ans;if(temp<0){cout<<"0"<<endl;return 0;}if(temp==0){cout<<k<<endl;return 0;}// cout<<ans<<endl;ans=0;ll y;while(1){tt*=10;y=(tt-a);//cout<<temp<<"   " <<y<<" "<<tt<<" "<<a<<endl;if(y>=temp){ans=a+temp;break;}else{temp-=y;}a=a*10;}printf("%lld\n",ans-1);}return 0;
}

 

这篇关于ZOJ Monthly, January 2019 E:Little Sub and Mr.Potato's Math Problem 构造的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---