P1005 超长数字串

Published on 2019 / 05 / 21

思路

想法一

最直接的做法，是维护一个字符串，枚举这个无限长的S字符串。然后直接在S中寻找第一次出现位置。空间是有限的，所以我们不可能无限制枚举。可以根据内存限制和测试点范围，估计一个大概的长度，然后填满这个有限长度的S。依照这个想法快速写出代码，可以：

能提交一个部分AC的程序，捞到保底分
方便构造复杂一点的测试用例

想法二

上面这样当然没法得到全部的正确答案。这个题目很明显，A的长度不超过200，这个长度为 200 的数，假设为 N，一定会出现在 S 中。知道某个 N，我们是可以根据规律直接计算出他出现的位置。所以这个问题就转化成求最小的 N，最小的 N 是可以通过枚举 N 的位数来直接尝试出的。

按照这个思路，可以得到求解方式为：

从 1 到 len(A) 枚举 N 的长度 L
对于每个长度 L，在 A 中从后往前构造长度为 L 的数 M，检测 M 构造的数是否满足 A
对于每个长度 L，不停的用 M 更新 N，求出最小的 N 值，记录 N 值在字符串 A 的偏移量
根据 N 和偏移量计算位置
S 从 1 开始编号，所以需要位置 +1 得到答案

不考虑数据大小，这个方式是正确的思路，稍微注意边界条件，可以得到正确的结果。边界条件包括：

字符串 A 全为 0，直接在前面补 1 得到 N，然后使用偏移量 -1 进行计算
每一个构造的 M 不能以 0 开头，如果是，直接跳过
在 A 中构造 L 长度的数值 M。如果 M 的位数不够，需要从前面的内容填充
如果前面 (L - 缺失位数)的内容全为 9，M 需要填充(L - 缺失位数)的 0
否则填充 (L - 缺失位数) 长度的 A中当前枚举位置前(L - 缺失位数)的值加 1

用一个例子来验证思路，假如输入数据是 0000。

直接补 1，得到最小的 N 为 10000。
10000是5位数，L=5。计算1-4位的值，再加上第5位的值，减去 N 在 A 的偏移量 -1，就是位置。
位置 +1 得到答案

每个长度为 L 的数在 S 中消耗的位数为 L * 9 * 10^(L-1)，可以得出

位数	计算方式	占的长度
1	1 * 9 * 10^(1-1)	9
2	2 * 9 * 10^(2-1)	180
3	3 * 9 * 10^(3-1)	2700
4	4 * 9 * 10^(4-1)	36000

第五位的偏移量为 5*(10000-10000)=0，位置为 9+180+2700+36000+0-(-1)=38890，+1 得到答案 38891。

想法三

按照思路二，写成了新的代码。但是还不能通过全部的点。A 长度最多为 200，这个范围肯定是超过最大的整型了，需要高精度。

如果是以前竞赛的时候，时间不够了，估计用 Int64 整完想法二的代码，差不多这个题就这么提交了。但是，现在，是为了学习 Go 来做题的，Go 有处理大数据的 math/big！

将想法二的代码，涉及到计算的地方都使用现成的big.Int相关的方法替换，出来的结果就是能支持 200 位 N 的结果计算的正确代码。

几个测试点

A	结果
21	15
00	191
99999	438886
9999999999	88888888881
0000000000	98888888891

代码

/*
ZHOU Cheng <c.zhou@live.com>
2019-5-18 22:48:21
*/
package main

import (
    "fmt"
    "math/big"
    "regexp"
    "strings"
)

var zero = big.NewInt(0)
var one = big.NewInt(1)
var ten = big.NewInt(10)

func getBigInt(s string) *big.Int {
    i, _ := new(big.Int).SetString(s, 10)
    return i
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// 获取填充 0 的长度为 n 的数值字符串
func getZeroString(value *big.Int, n int) string {
    s := value.String()
    for n = n - len(s); n > 0; n-- {
        s = "0" + s
    }
    return s
}

// 长度为 bit，在 a 中偏移量为 offset 的 num 是否符合条件。不符合返回 zero
func validateBitAndOffset(bit, offset int, a string) *big.Int {
    // 零开头的，不符合要求，直接返回 zero
    if strings.HasPrefix(a[offset:], "0") {
        return zero
    }

    // 当目前的长度少于期望的长度，使用前面的值来填充
    if offset+bit > len(a) {
        missBit := offset + bit - len(a)
        prevStr := a[offset-missBit : offset]
        p := new(big.Int)
        // 全 9 特殊处理，填充 0
        if match, _ := regexp.MatchString("^9*$", prevStr); match {
            p.SetInt64(0)
        } else {
            p.SetString(prevStr, 10)
            p.Add(p, one)
        }
        a += getZeroString(p, missBit)
    }

    num := getBigInt(a[offset : offset+bit])
    n := new(big.Int)
    var left, right int
    // 检测左边是否满足条件
    n.Sub(num, one)
    right = offset
    for right > 0 {
        if n.Cmp(one) < 0 {
            return zero
        }
        nStr := n.String()
        left = max(0, right-len(nStr))
        if a[left:right] != nStr[len(nStr)-(right-left):] {
            return zero
        }
        right -= len(nStr)
        n.Sub(n, one)
    }
    // 检测右边是否满足条件
    n.Add(num, one)
    left = offset + bit
    length := len(a)
    for left < length {
        nStr := n.String()
        right = min(length, left+len(nStr))
        if a[left:right] != nStr[0:right-left] {
            return zero
        }
        left += len(nStr)
        n.Add(n, one)
    }
    return num
}

// 计算数字出现的位置
func getNumberPosition(num *big.Int, offset int) *big.Int {
    result := big.NewInt(0 - int64(offset))
    if num.Cmp(ten) < 0 {
        result.Add(result, num)
        return result
    }

    length := len(num.String())
    start := big.NewInt(1)
    for i := 1; i < length; i++ {
        count := big.NewInt(9)
        count.Mul(count, start)
        count.Mul(count, big.NewInt(int64(i)))
        result.Add(result, count)
        start.Mul(start, ten)
    }

    start.Sub(num, start)
    curr := big.NewInt(int64(length))
    curr.Mul(curr, start)
    curr.Add(curr, big.NewInt(1))
    result.Add(result, curr)
    return result
}

func main() {
    var a string
    _, _ = fmt.Scanf("%s", &a)

    // 全 0 特殊处理
    if match, _ := regexp.MatchString("^0*$", a); match {
        num := getBigInt("1" + a)
        fmt.Println(getNumberPosition(num, -1))
        return
    }

    best := big.NewInt(0)
    for i, j := 1, len(a); i <= j; i++ {
        for offset := i - 1; offset >= 0; offset-- {
            num := validateBitAndOffset(i, offset, a)
            if num.Cmp(zero) > 0 {
                curr := getNumberPosition(num, offset)
                if best.Cmp(zero) == 0 || best.Cmp(curr) > 0 {
                    best = curr
                }
            }
        }
        // 当前位数寻找到最优结果，打印并结束循环
        if best.Cmp(zero) > 0 {
            fmt.Println(best.String())
            break
        }
    }
}