C/C++教程

A - Sequence with Digits

本文主要是介绍A - Sequence with Digits,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题意:由递推式 a n + 1 = a n + m i n D i g i t ( a n ) ⋅ m a x D i g i t ( a n ) a_{n+1}=a_n+minDigit(a_n)⋅maxDigit(a_n) an+1​=an​+minDigit(an​)⋅maxDigit(an​),其中 m i n D i g i t ( a n ) minDigit(a_n) minDigit(an​), m a x D i g i t ( a n ) maxDigit(a_n) maxDigit(an​)分别为 a n a_n an​中最小的一位数和最大的一位数,求 a k a_k ak​的值。
做法:题目的数据范围非常大,显然直接暴力是不可取的。对于这种递推式的题,有时结果会有一定的规律性,可以打表肉眼观察,也可以通过严格的数学推理证明。在本题中,我使用了打表的方法,不难看出当k达到一定值时结果不会发生改变,因为最小的一位是0,0乘任何数都得0,所以结论就很显然了。由于本人数论水平较低,就不通过数学推理证明了,据说 codeforces上有严格的证明,有兴趣的同学自行查看。
代码:

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int, int> PII;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
int t;
ll n, k;
int main() {
	cin >> t;
	while(t--) {
		cin >> n >> k;
		for(int i = 1; i <= min(k - 1, 1000ll); i++) {
			ll tmp = n, maxn = 0, minn = 9;
			while(tmp) {
				maxn = max(maxn, tmp % 10);
				minn = min(minn, tmp % 10);
				tmp /= 10;
			}
			n += maxn * minn;
		}
		printf("%lld\n", n);
	}
	return 0;
}
这篇关于A - Sequence with Digits的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!