深信服笔试9.1
算法卷是3道题
9/1笔试
第一题，给一个字符串，计算swr子串个数（子串是可以是不连续的字符串，但是保持前后字符顺序）
例如wsswrrw返回4，sswwrr返回8
***只需要遍历每个w，统计每个w前s的个数，和每个w后r的个数，然后相乘，加到最后结果里面
第一题，给一个字符串，计算swr子串个数（子串是可以是不连续的字符串，但是保持前后字符顺序）
例如wsswrrw返回4，sswwrr返回8
***只需要遍历每个w，统计每个w前s的个数，和每个w后r的个数，然后相乘，加到最后结果里面
也就是分别统计从0到第i位，有几个s，从最后一位到第i位，有几个r
应该是这样吧😅考完了才想到
int find_swr(string s)
{
int result = 0;
int md = 1000000009;
int n = s.length();
vector<int> s_left(n + 2, 0);
vector<int> r_right(n + 2, 0);
vector<int> w_idx;
for (int i = 1; i <= n; i++)
{
if (s[i - 1] == 's')
s_left[i] = s_left[i - 1] + 1;
else
s_left[i] = s_left[i - 1];
if (s[n- i + 1] == 'r')
r_right[n - i + 1] = r_right[n - i + 1 + 1] + 1;
else
r_right[n - i + 1] = r_right[n - i + 1 + 1];
if (s[i - 1] == 'w')
{
w_idx.push_back(i);
}
}
int idx = 0;
for (int i = 0; i < w_idx.size(); i++)
{
idx = w_idx[i];
result = (result + (s_left[idx] * r_right[idx]) % md) % md;
}
return result;
} ***是NC397 统计子序列数的简单版本第二题，输入N行表示N个人愿意去旅游的时间段，每行一个A和B是一个人愿意旅游的时间段（在时间段A,A +1,A+2,…,B内这个人都愿意去旅游），A<B<1000000，都是正整数，求如何找到一个时间，让尽量多人愿意去旅游，输出这个时间能满足几个人的意愿。
一个人愿意去的是[A:B]，把他们映射到bit中，所有人的都映射，然后统计bit的最大值
要O(n)的复杂度得用前缀和，对数组arr[A:B]加1，首先arr[A]+=1，然后arr[B+1]-=1，表示这个加1的区间是从A到B；然后做一次前缀和就能回复出来这个全部加1的区间。
int main()
{
int T = 0;
cin>>T;
int N = 0, A = 0, B = 0;
int mini = 100000007, maxi = -1;
int cuum = 0;
for(int i=0;i<T;i++)
{
vector<int> arr(1000005,0);
vector<int> vec(1000005,0);
cin>>N;
for(int j=0;j<N;j++)
{
cin>>A;
cin>>B;
if(A<mini)
mini = A;
if(B>maxi)
maxi = B;
arr[A]+=1;
arr[B+1]-=1;
}
cuum = 0;
for(int i=mini;i<=maxi;i++)
{
cuum+=arr[i];
vec[i] = cuum;
}
cout<<*max_element(vec.begin(), vec.end())<<endl;
}
return 0;
}
第三题进制转换为5进制
查看12道真题和解析
中移(苏州)软件技术有限公司工作强度 29人发布