深信服笔试9.1

算法卷是3道题

9/1笔试

第一题，给一个字符串，计算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进制