2020超级码力复赛-A

2020超级码力复赛-A

十月 03, 2020

密钥

题意

给出一个长度为1e6的只包含0~9的串

定义某个区间的val=出现最多的数的次数-出现最少的数的次数

求所有子区间中最大的val

​

题解

我们枚举出现次数最多和最少的那个数,假设为A和B

那么 原字符串 中若第i位为A则替换成1,为B则替换为-1 其余则置为0

于是这个问题被转化成了最大子段和问题 可以用经典$On$解法解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    /**
     * @param s: number string
     * @return: Find the key
     */
    int key(string &s) {
        int n=s.size();
        int maxn=0;
        for(int a=0;a<9;a++){
            for(int b=0;b<9;b++){
                int temp=0,numa=0,numb=0;
                for(int i=0;i<n;i++){
                    if(s[i]-'0'==a)numa++;
                    else if(s[i]-'0'==b)numb++;
                    if(numa>=numb&&numb)temp=max(temp,numa-numb);
                    else if(numa<numb)numa=numb=0;
                    ///最大子段和On解法的关键
                    ///当目前子段和<=0那么直接舍弃
                    ///因为它对后面的和无贡献
                    ///而当前子段的后半部分则是负贡献
                }
                maxn=max(maxn,temp);
            }
        }
        return maxn;
    }
};