深信服9.14笔试

1. 求最大公约数

#include <bits/stdc++.h>
using namespace std;

int a, b;
int solution() {
    while (a != b) {
        while (a > b) a = a - b;
        while (b > a) b = b - a;
    }
    return a;
}

int main() {
    while (cin >> a >> b) {
        cout << solution() << "\n";
    } 
}

2. 病毒...

#include <bits/stdc++.h>
using namespace std;

int n, x;
int solution(vector<int>& nums) {
    vector<pair<int, int>> diff; diff.reserve(n);
    for (const auto& num : nums) {
        int left = num - x < 0 ? 0 : num - x;
        int right = num + x;
        diff.push_back({left, right});
    }
    vector<pair<int, int>> overlap;
    overlap.push_back(diff[0]);
    for (int i = 1; i < n; ++i) {
        int left = max(overlap.back().first, diff[i].first);
        int right = min(overlap.back().second, diff[i].second);
        if (left <= right) {
            overlap.back().first = left;
            overlap.back().second = right;
        } else {
            overlap.push_back(diff[i]);
        }
    }
    return overlap.size() - 1;
}

int main() {
    while (cin >> n >> x) {
        vector<int> nums(n, 0);
        for (int i = 0; i < n; ++i)
            cin >> nums[i];
        cout << solution(nums) << "\n";
    }
}

3. 包含最长全1字串个数

#include <bits/stdc++.h>
using namespace std;

long long mod = 1000000007;

int solution(const string& s) {
    int n = s.size();
    int i = 0, j = -1;
    vector<int> dp(n, 0);
    dp[0] = s[0] - '0';
    int mx_len = dp[0];
    for (int i = 1; i < n; ++i) {
        if (s[i] == '1') {
            if (s[i - 1] == '1')
                dp[i] = dp[i - 1] + 1;
            else 
                dp[i] = 1;
        } else {
            dp[i] = 0;
        }
        if (dp[i] > mx_len)
            mx_len = dp[i];
    }
    if (mx_len == 0)
        return 0;
    vector<pair<int, int>> intervals;
    for (int i = 0; i < n; ++i) {
        if (dp[i] == mx_len) {
            intervals.push_back({i - mx_len + 1, i});
        }
    }
    long long  ans = 0;
    int pre_left = -1;
    for (const auto& interval : intervals) {
        auto left = interval.first;
        auto right = interval.second;
        long long cur = (long long)(left - pre_left) * (n - right);
        ans += cur;
        pre_left = left;
    }
    return ans % mod;
}

int main() {
    int n;
    while (cin >> n) {
        string s; cin >> s;
        cout << solution(s) << "\n";
    }
    return 0;
}