深信服笔试09.01
算法A卷
一共3个编程题
1. 日志分析
输入：正整数 T，紧接着是 T 行字符串
输出：T 行，每个日志的潜在攻击数，结果对 1e9+7 取模。
求攻击次数，攻击次数就是字符串中包含 “swr”。 比如 输入 “swr” ，输出 1 ；输入“rws” ，输出 0
思路：
统计每个w字符 的前缀 r字符个数 和后缀 s 个数
#include<bits/stdc++.h>
using namespace std;
int main()
{
const int mod = 1e9+7;
int T;cin>>T;
while(T--){
string s;cin>>s;
int n = s.size();
long ans = 0;
vector<int>pre(n+1),next(n+1);
for(int i=0;i<n;++i){
if(s[i]=='s')pre[i+1]=pre[i]+1;
else pre[i+1]=pre[i];
}
for(int i=n-1;i>=0;--i){
if(s[i]=='r')next[i]=next[i+1]+1; else next[i]=next[i+1];
}
for(int i=0;i<n;++i){
if(s[i]=='w')ans+=((long)pre[i]*next[i])%mod;
}
cout<<ans<<'\n';
}
return 0;
} 2. 旅游人数 输入n。表示一共n个员工旅行，每个员工都有特定时间段。
之后是 n 行，每行两个正整数a, b，表示一位员工方便旅游的时间段为 [a, b]。
问最多可以同时让多少位员工觉得方便，就是输出某个时间方便人数最多的数量。
思路：
用数组表示每个时间段人数，对输入的每个区间[a,b]进行累加1，然后遍历人数，找到最大即为答案。
因为每次都会进行区间累加，如果一次次遍历效率很低。
构建差分数组，数组num[i]代表对前一个nums[i-1]的人数差。
例如 数组 x = [1,3,6,2,4] 差分数组则是 nums = [1,2,3,-4,2]
那么对区间[0,2]都+1的话，只要对数组nums操作即可：nums[0]+=1; nums[2+1]-=1; 即 nums = [2,2,3,-5,2]
之后对数组 nums 进行还原就得到了更新后的人数，即 nums[i] = nums[i]+nums[i-1]; （为了判断下标越界，多开一个空间即可）。
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<int>nums(1e6+5);
int n;cin>>n;
int a,b;
for(int i=0;i<n;++i)
{
cin>>a>>b;
nums[a]+=1;
nums[b+1]-=1;
}
int ans = 0;
for(int i=1;i<nums.size();++i)
{
nums[i]+=nums[i-1];
ans = max(ans,nums[i]);
}
cout<<ans<<'\n';
return 0;
} 3. 五进制模拟 非常简单，模拟即可。
欢迎各位交流。
#深信服笔试题#
