JZTXT

【每日一题】AtCoder Beginner Contest 045 | C - たくさんの数式 题解

发布时间 2023-09-13 18:45:48作者: SILL

 描述

　　

　　问题大意：给予一个由数字1至9组成得字符串S，你需要在任意两个相邻的数字之间加入符号“+”，求取所得的数学表达式的值。计算所有有可能的数学表达式的结果的总和。

思路

　　初初以为简单，但细做之下发现很复杂。冥思苦想之下茅塞顿开，算作柳暗花明又一村了。

　　对于任何一个数字字符串，都可以将其拆分为有限个数字字符串。

　　题例的“125”实在是过于简短，无法体现出算法的底层逻辑，是故本文以“1245”为例。

　　

　　对于“1245”，其拆分结果如下：

  1. 1245 
  2. (1, 2, 4, 5) 
  3. (1, 245)
  4. (1, 2, 45)
  5. (124, 5)
  6. (12, 45) 
  7. (12, 4, 5)
  8. (1, 24, 5)

　　不难看出，所谓拆解就是求取按序连接后可以得出原字符串的子字符串的集合。

　　所以一种比较好的解法就是递归得取某位之前的值，加上该位之后所有可能性结果相加的和的总和。

 

　　有一点需要注意就是递归得过程中虽然结果加上了某位后一位开始的子字符串结果总和，却并没有在那些结果中加上该位自身。所以递归求得的结果需要再加上自身一定次数，将这个次数设为k，后一位开始、到末尾结束的子字符串长度设为l，则不难证出，当l > 1时，有 

k=2l-1-1

　　每一位求取的结果都要加上k，才能得到正确的结果。

 

　　描述得有些抽象，看代码应该就能理解了。

　　闲言少叙，上代码。

 

代码

package main

import (
    "fmt"
    "math"
    "strconv"
)

func main() {
   var s string
   fmt.Scanf("%s", &s)
   fmt.Printf("%d", subSum(s, 0))
}

func subSum(s string, res int) int {
    for i := 0; i < len(s); i += 1 {
      var tmp_2 int
      tmp_1, _ := strconv.ParseInt(s[: i + 1], 10, 64) // 获取下标i之前的子字符串并转为数值
      // 获取下一位字符开始的子字符串所有有可能的拆解的数量
      if len(s[i + 1: ]) <= 1 {
         tmp_2 = 0
      } else {
         tmp_2 = int(tmp_1) * int(math.Floor((math.Pow(2, float64(len(s[i + 1: ]) - 1)) - 1)))
      }
      // 当前的结果即下标i之前的数值乘以下一位字符开始的所有子字符串拆解结果的数量，加上下一位字符开始的所有子字符串拆解结果的总和
      res += (subSum(s[i + 1: ], int(tmp_1)) + tmp_2)
   }
   return res
}