題目大意

給定正整數(shù) $n$（$2\le n\le 10^9$）。
考慮無序整數(shù)對 $(x, y)$（$1\le x,y\le n, x\ne y$）。
求滿足 「$x+y$ 結(jié)尾連續(xù)的 9 最多」的數(shù)對 $(x,y)$ 的個數(shù)。

例子：
$n=50$，$(49,50)$ 是一個滿足條件的數(shù)對。

比賽時我的思路

首先注意到，「兩個正整數(shù)的和」的結(jié)尾的連續(xù)的 9 一定不包含進(jìn)位的貢獻(xiàn)，也不產(chǎn)生進(jìn)位。

首先考慮（數(shù)對的和的）結(jié)尾最多有幾個連續(xù)的 9 。不難得出：
設(shè) $n$ 的位數(shù)為 $k$ ，令 $x=5\times 10^{k-1}$ 。
若 $n\ge x$，則和的結(jié)尾最多有 $k$ 個連續(xù)的 9 。
若 $n=10^{k} - 1$，滿足條件的數(shù)對有 $n - x$ 個，否則有 $n-x+1$ 個。

若 $n < x$ ，數(shù)對之和的第 $k$ 位一定小于 $9$，故結(jié)尾至多有 $k-1$ 個連續(xù)的 9 。

若 $k-1=0$，則為平凡情形。
考慮 $k\ge 2$ 的情形。
設(shè) $n$ 的 第 $k$ 位上的數(shù)字為 $h(n)$，顯然有 $h(n) > 0 $ 。

考慮數(shù)對 $(x,y)$（$x>y$），設(shè) $x$ 的第 $k$ 位上的數(shù)字為 $h(x)$ 。
將所有滿足條件的數(shù)對 $(x,y)$ 分成下列若干類：

$h(n)>h(x)=h(y)=0$

$h(n)>h(x) = h(y) > 0$

$h(n)>h(x) > h(y)>0$

$h(n)>h(x) > h(y)=0$

$h(n)=h(x) > h(y) > 0$

$h(n) = h(x) > h(y) = 0$

$h(n) = h(x)= h(y) $

在比賽中，我沒考慮到上述第 7 種情況。

總結(jié)

本題的思維方式：分類。

實(shí)現(xiàn)技巧：
求一個正整數(shù) $n$ 的位數(shù)可用 to_string(n).size() 。

轉(zhuǎn)載于:https://www.cnblogs.com/Patt/p/8053576.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 899D Shovel Sale的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。