做题感悟:比赛的时候用的广搜,然后高高兴兴的写完果断TLE ,做题的时候无论什么题都要用笔画一下,模拟几组数据,这样也许就AC了(做题经验,有心者谨记!)。
解题思路:贪心/规律
这题如果暴力找倍数的话必定超时(如果不超时就是数据问题了),但是我们可以把它的倍数分类,把位数相同的倍数放在一类里,这样一共才18类,分类后只需要找这一类中最小的元素代表这一类就可以了。问题就转化到怎样找某一定位数某个数的字典序最小的倍数,我们知道最小字典序的那个数最前面如果最小的话只能放1后面尽可能放 0 ,这样可以使达到的倍数尽量小。
这里假设 k 的 6 位的倍数是 100xyz(这个数是超过 100000 的第一个倍数),那么这个数是否是最小的呢?我们让 100xyz 再加上 k (这里假设加上 k 之后位数不超 6 位),假设得到 100wpq,那么这个数的字典序一定比 100xyz的字典序大,由这个我们也可以知道 100xyz 一直加 k 得到的位数为 6 位的数的倍数一定都比 100xyz字典序大,这样我们可以得到答案的解,就是枚举超过 10,100 ,1000 ,10000 ……10^18 的第一个 k 的倍数取字典序最小的一个。
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<cctype> #include<iomanip> #include<algorithm> using namespace std ; #define INT long long int #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const INT mod = 10000007 ; const int MY = 1400 + 5 ; const int MX = 18 + 5 ; char ans[MX] ,str[MX] ; INT n ,k ; int judge(int x) { int ans = 0 ; while(x) { x /= 10 ; ans++ ; } return ans ; } int main() { while(scanf("%I64d%I64d" ,&n ,&k) ,n+k) { sprintf(ans ,"%lld" ,k) ; int m = judge(k) ; for(int i = m ;i <= 18 ; ++i) // 枚举每一种 { INT temp = pow(10 ,i) ; if(temp > n) break ; if(temp % k == 0) { sprintf(str ,"%lld" ,temp) ; if(strcmp(ans ,str) > 0) strcpy(ans ,str) ; } INT tx = (temp/k+1)*k ; if(tx > n) continue ; sprintf(str ,"%lld" ,tx) ; if(strcmp(ans ,str) > 0) strcpy(ans ,str) ; } cout<<ans<<endl ; } return 0 ; }