9.14 深信服笔试编程题题解

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k; cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int m = v[i], M = v[i];
        int j = i;
        while (j+1 < n && max(M, v[j+1]) - min(m, v[j+1]) <= 2*k) {
            M = max(M, v[++j]);
            m = min(m, v[j]);
        }
        if (j < n-1)
            ans ++;
        i = j;
    }
    cout << ans << endl;
    return 0;
}

// 1.对于包含一个特定子串t的任意字符串，假设t的左边有l个字符，右边有r个字符，则
 //     满足条件的字符串的个数为 (l+1)*(r+1)。
// 2.对于此题，我们可以枚举每一个具有最长连续1的字符串把它当作上上一句话的t。
 //   有个要注意的地方是排除重复的串，自行体会代码中带注释地方的妙处。
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    string s; cin >> s;
    s = s.substr(0, n);
    vector<int> start{-1};
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') continue;
        int j = i;
        while (j+1 < n && s[j+1] == s[i]) j++;
        int cnt = j-i+1;
        if (maxLen < cnt) {
            maxLen = cnt;
            start = vector<int>{-1};
            start.push_back(i);
        } else if (maxLen == cnt) {
            start.push_back(i);
        }
        i = j;
    }
    start.push_back(n);
    const int MOD = 1e9+7;
    long long ans = 0;
    for (int i = 1, iend = start.size()-1; i < iend; i++) {
        // 仔细想想l和r为什么这么取
        int l = start[i]-start[i-1], r = n-(start[i]+maxLen-1);  
        ans = (ans += 1LL*l*r) % MOD;
    }
    cout << ans << endl;
    return 0;
}