9.14 深信服笔试编程题题解
// 先占个坑，题解笔试结束发
1. 第一题求最大公约数，c++和python都有现成的库可以用。C++（__gcd(int, int)）， python（math.gcd(int, int)），也可以自己实现一个，并不难。
2. 贪心
输入n和一个长度为n的子串。
输出模1e9+7
#深信服笔试题##深信服笔试##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;
} 3. 一个长度为n的01串，求出包含最长连续1的子串的个数。输入n和一个长度为n的子串。
输出模1e9+7
// 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;
} 
