牛客IOI周赛24-普及组 B 数字串

Descripiton

SOlution

不难发现 的长度最多为 。
对于一段不包含 的串，

• 需要满足条件 至少长度为
• 需要满足条件 至多长度为

即长度为 的串都可能为答案的贡献，对此我们可以暴力找出到底这一段有多长，因为这一段的长度不超过 。至于前导零，我们可以记录当前位置的前导零有多少个，记为 ，那么贡献为 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
string l, r, s; 
string cal(int posl, int posr) {
  string res;
  for (int i = posl; i <= posr; i++) {
    res += s[i];
  }
  return res;
} 
bool Isgreater(string a, string b) { // a > b
  if (a.size() > b.size()) return true;
  if (a.size() < b.size()) return false;
  for (int i = 0; i < a.size(); i++) {
    if (a[i] > b[i]) {
      return true;
    } else if (a[i] < b[i]) {
      return false;
    }
  }
  return false;
}
bool Isless(string a, string b) { // a < b
  if (a.size() < b.size()) return true;
  if (a.size() > b.size()) return false;
  for (int i = 0; i < a.size(); i++) {
    if (a[i] < b[i]) {
      return true;
    } else if (a[i] > b[i]) {
      return false;
    }
  }
  return false;
}
void solve() {
  cin >> l >> r >> s;
  int n = l.size(), m = r.size(), k = s.size();
  int pos = 0, leadzero = 0;
  ll ans = 0;
  while (pos + n - 1 < k) {
    if (s[pos] == '0') {
      leadzero++;
    } else {
      int left = pos + n - 1, right = min(k - 1, pos + m - 1);
      string Lres = cal(pos, left), Rres = cal(pos, right);
      while (Isgreater(l, Lres) && left < right) {
        left++, Lres += s[left];
      }
      while (Isgreater(Rres, r) && right >= left) {
        right--; Rres.pop_back();
      }
      //cout << "pos:" << pos << ' ' << "left:" <<left << ' ' << "right:" << right << '\n';
      if (!Isgreater(Rres, r) && !Isless(Lres, l) && right >= left) {
        ans += right - left + 1;
        ans += 1LL * leadzero * (right - left + 1);
      }
      leadzero = 0;
    }
    pos++;
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int T = 1; //cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}