A Sequence with Digits
这道题考场的时候大概看完题就发现如果出现(0)那么接下来的数一直都不会变，但是我却不能证明这个玩意。
大概想了5min决定打一个暴力交上去试一下然后就过了（？？？）。
考到后面我因为怕fst于是又回来想了一下A这样暴力的复杂度为什么是正确的。
然后我突然发现每次最多只会加(9 imes 9 = 81 < 100)，所以必然会出现一个(xx10xx)，而每次最少加(1 imes 1 = 1)，所以最多加(1000)次就会出现这样的数，这道题就解决了。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int t;
ll a, k;
ll FMI(ll x) {
ll ret = 20;
while (x) {
ret = min(ret, x % 10);
x /= 10;
}
return ret;
}
ll FMX(ll x) {
ll ret = -20;
while (x) {
ret = max(ret, x % 10);
x /= 10;
}
return ret;
}
int main() {
cin >> t;
while (t--) {
cin >> a >> k;
if (k == 1) {
cout << a << "
";
continue;
}
for (ll i = 2; i <= k; i++) {
ll x = FMI(a);
ll y = FMX(a);
if (x > 0) {
a += x * y;
} else {
break;
}
}
cout << a << "
";
}
return 0;
}
B Young Explorers
考虑贪心。
首先每个人肯定都尽量和自己(e)值相同的人在一组。
因为不管他和(e)值比他小的还是(e)值比他大的每一组的人数都会增加，组数肯定会减少。
于是我们记录(cnt[i])代表(e)为(i)的人的数量。
对于每个(i)，(ans += cnt[i]/i)。
我们发现有可能有剩余，那么我们就把他们分到比自己(e)值大(1)的那个组去，把他们当成(e)为(i+1)的人。
每次(cnt)要清空。
#include <iostream>
#include <cstdio>
using namespace std;
int t;
int n;
int e[200010];
int cnt[200010];
int ans;
int main() {
cin >> t;
while (t--) {
ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cnt[i] = 0;
}
for (int i = 1; i <= n; i++) {
cin >> e[i];
cnt[e[i]]++;
}
for (int i = 1; i <= n; i++) {
ans += cnt[i] / i;
cnt[i + 1] += cnt[i] % i;
}
cout << ans << "
";
}
return 0;
}