题解 | #[NOIP1999]回文数#
思路1:利用十进制做中转
1.将m 和 reverse(m) 转为10进制并求和
2.将sum转回 n 进制, 更新为 m
3.判断是否m是否为回文串
代码如下:
package main
import (
"fmt"
"strconv"
)
func reverse(s string) string {
str := ""
for _, k := range s {
str = string(k) + str
}
return str
}
func toDecimal(s string, n int) int {
res, length, cur := 0, len(s), 1
for i := length - 1; i >= 0; i-- {
if s[i] <= '9' {
res += int(s[i]-'0') * cur
} else if s[i] <= 'Z' {
res += (int(s[i]-'A') + 10) * cur
} else {
res += (int(s[i]-'a') + 10) * cur
}
cur *= n
}
return res
}
func main() {
var (
n int // 进制数
m string // 数
)
fmt.Scan(&n, &m)
for i := 1; i <= 30; i++ {
rm := reverse(m)
m10, rm10 := toDecimal(m, n), toDecimal(rm, n)
m = strconv.FormatInt(int64(m10+rm10), n)
if reverse(m) == m {
fmt.Printf("STEP=%d", i)
return
}
}
fmt.Println("Impossible!")
}
思路2:高精度