携程笔试 9/7

写一下t4的题解，前面几题都比较简单就不写了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);i++)

int main() {
    string s; cin >> s;
    int n = s.size();
    ll res = 0;
    vector<int> dp(n+1); // cnt of 0
    rep(i, 0, n) {
        dp[i+1] = s[i] == '0'? dp[i]+1:dp[i];
    }
    rep(i, 0, n+1) {
        dp[i] = 2*dp[i]-i;
    }
    stack<int> stk;
    ll sum = 0;
    rep(i, 0, n+1) {
        while(stk.size() > 0 && dp[stk.top()] >= dp[i]) {
            stk.pop();
        }
        res += stk.size(); 
        stk.push(i);
    }
    cout << res << endl;
    return 0;
}

要求0的数量严格大于1，用dp记录一下0的数量，下标从1开始，减的时候不用考虑边界情况。

对于[i,j]如果满足条件，必要条件是2*(dp[j]-dp[i-1]) > j-i+1，转换一下就是2*dp[j]-j>2*dp[i-1]-i+1，所以可以把dp的含义设置为2倍的0的数量减掉index。

随后发现题目要求就是对于每一个j，找出满足j>i&&dp[j] < dp[i]的i的数量，于是显然用单调栈可以解决。