牛客小白月赛28 C. 单词记忆方法 题解

Description

牛牛考完了四六级，准备分享一下自己的英语学习方法。

牛牛：学习英语最重要的就是背单词，如果你能把所有的单词都记住，那么你的英语就能变成天下第一。

然而牛牛的记忆方法就是把单词的每个字母转换成数字，把A看成1，B看成2，C看成3{}A看成1，B看成2，C看成3，依次类推，然后计算出来这个单词每个字母的和。从此每次想到这个单词，就要先想到这个单词的和，然后想办法凑出这个和。

不久后，牛牛又对自己的记忆方法进行了更新，可以把重复的连续字母进行合并，

比如把ABCABC写成(ABC)2，HHHH写成(H2)2或者H4，这样计算和的时候只需要用里面的和乘个数就可以了，更加方便。（但是有时候牛牛由于老花眼没有发现几个相同的连续字母是重复的，所以导致他没进行合并）

现在到了牛牛考验你的时间了，牛牛告诉你一个单词，这个单词可能很长甚至你从来没见过，但牛牛要你按他的方法算出这个单词的和。

Solution

思路：递归。
对于每对括号，都可以看作是一个整体，那么我们可以用一个栈来存每一对括号的起始位置。由于存在多个括号嵌套，显然递归可以比较简洁地实现这个问题。
如果遇到(，当前位置为i，对应)的位置为j，那么我们可以对[i + 1, j - 1]区间重复上述的操作。直到出现当前位置为字母，检查后方是否有数字。如此处理这个字符串即可。

Code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 5;
int match[N];
string s; 
stack<int> st;
int get(char s) {
  return s - 'A' + 1;
}
ll solve(int l, int r) {
  ll res = 0, num = 0;
  for(int i = l; i <= r; ) {
    if(s[i] == '(') {
      ll ans = solve(i + 1, match[i] - 1);
      int cur = match[i] + 1;
      while(cur <= r && isdigit(s[cur])) {
        num = num * 10 + s[cur] - '0';
        cur++;
      }
      if(num) {
        res += num * ans;
      } else res += ans;
      i = cur;
      num = 0;
    } else {
      if(i + 1 <= r && isdigit(s[i + 1])) {
        int x = i + 1;
        while(x <= r && isdigit(s[x])) num = num * 10 + s[x] - '0', x++;
        res += get(s[i]) * num;
        i = x;
        num = 0;
      } else res += get(s[i]), i++;
    }
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> s;
  int n = s.size();
  for(int i = 0; i < s.size(); i++) {
    if(s[i] == '(') {
      st.push(i);
    } else if(s[i] == ')') {
      match[st.top()] = i;
      st.pop();
    }
  }
  cout << solve(0, n - 1) << "\n";
  return 0;
}