(场上没出,此代码参考并得到了瑞神指导 )
规律+暴力
首先判不能组成的末位9的情况;
然后判后面连续的9的个数k,然后枚举末位含有k个连续的9的数,每个数组成个数加入到答案中
#includetypedef long long ll; using namespace std; ll a[22] = {0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999LL, 9999999999LL}; ll b[22] = {0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000LL, 10000000000LL}; int main() { ll n, sum; cin >> n; sum = n + n - 1; int p = 0; while(sum >= a[p]) ++p; --p; if(p == 0) { cout << (n - 1) * n / 2 << endl; return 0; } ll ans = 0, cur = a[p]; for(int i = 0; i < 10; ++i) { sum = n + n - 1; if(sum < cur) break; if(n >= cur) { ans += (cur - 1) / 2; } else { ll m = n + n - cur + 1; if(m > 1) { ans += m / 2; } } cur += b[p]; } cout << ans << endl; return 0; }