【題解】Codeforces 1295B. Infinite Prefixes

【題目敘述】https://codeforces.com/contest/1295/problem/B

  • 逐字掃描輸入字串,並計算目前為止的前綴和 (d)。
  • 將出現過的前綴和數字及其出現次數,紀錄於 mp。同時記下最大值 (mx) 及最小值 (mn)。
  • 字串掃描完畢,需再次更新 mx、mn,確保數字正確。此時的 d 為整個字串的和 (balance)。
  • 當 d = 0,
    • 且mn <= x <= mx:有無限多種前綴可以符合要求。
    • 否則:無解。
  • 當 d != 0,
    • 如果 x = 0:empty string 是可能解,ans++。
    • 檢查 [mn, mx] 區間所有數 (i),如果 (x-i) / d >= 0 (正負號相同),且 (x-i) % d == 0:ans += mp[i]。
#include <iostream>
#include <map>
using namespace std;
 
int t, n, x, d, mx, mn, b, ans;
map <int, int> mp;
string s;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> x;
        d = 0;
        mx = 0;
        mn = 0;
        mp.clear();
        cin >> s;
        for (int i = 0; i < n; i++){
            if (s[i] == '0'){
                mn = min(mn, d);
                d++;
                mp[d]++;
            }else{
                mx = max(mx, d);
                d--;
                mp[d]++;
            }
        }
        mn = min(mn, d);
        mx = max(mx, d);
        if (d == 0){
            if (mn <= x && x <= mx) cout << "-1\n";
            else cout << "0\n";
            continue;
        }
        ans = 0;
        if (x == 0) ans++;
        for (int i = mn; i <= mx; i++){
            if ((x-i) % d == 0 && (x-i) / d >= 0) ans += mp[i];
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends