[프로그래밍 문제] 바이러스 검출(뉴커넷)

제목 링크:https://www.nowcoder.com/questionTerminal/6f0d16fc06274f44af8913d182668037소 그물
샤오밍은 최근에 바이러스 자동 검출을 하고 있다. 샤오밍은 일부library의 코드 세그먼트의 2진법 표시에 서브열을 포함하고 k개 1이 있으면 잠재적인 바이러스가 있을 수 있다는 것을 발견했다.library의 2진법은 매우 크고 서브열이 많을 수 있으며 인공 분석이 불가능하다는 것을 나타낸다. 그래서 그는 도대체 몇 개의 서브열이 조건을 충족시키는지 프로그램을 써서 먼저 계산하려고 한다.만약 하위 문자열의 내용이 같지만 시작이나 끝 위치가 다르면 다른 하위 문자열로 여겨진다.주:자열은 틀림없이 연속적이다.예를 들어 "010"에는 "0,"1","0","01","10","010"등 6개의 하위 문자열이 있는데 첫 번째 줄은 하나의 정수 k로 하위 문자열에 k개의 1이 있으면 바이러스일 수 있음을 나타낸다. 그 중에서 0<=k<=10000000
두 번째 줄은 리브라리의 코드 부분의 이진 표시인 문자열이다.문자열 길이 <= 1000 000입니다.또한 문자열에는 "0"또는 "1"만 포함됩니다.출력 설명: k개 1만 포함하는 하위 문자열의 개수를 충족시키는 정수를 출력합니다.Sample 입력 1 1010 출력 6 조건에 맞는 하위 문자열은 "1", "1", "10", "01", "10", "010"입니다.초보적인 생각: 폭력적인 해답을 구하고 각 자열을 두루 훑어보고 각 자열에 1이 포함된 개수를 구하면 쉽게 생각할 수 있다. 이것은 3층 순환이 필요하고 시간은 반드시 초과된다. 50%AC밖에 없다.사고방식 개선: 사실 생각을 바꾸고 0을 버리고 보지 않는다. 우리가 해야 할 일은 연속적인 k의 1구간을 찾은 다음에 이 구간의 앞뒤 연속적인 0의 개수를 통해 현재 구간이 요구에 부합되는 몇 개의 자열을 구성할 수 있는지 판단하는 것이다.그러므로 우리는 두 개의 벡터를 설정할 수 있다. 하나는 v1이 1의 위치를 저장하고, 다른 하나는 1의 앞에 있는 0의 수량을 저장할 수 있다. (마지막 값은 끝에 0의 수량이고, 주어진 문자열의 끝이 1이면 0이다.)앞의 생각에 따라 우리는 길이가 k인 창을 이용하여 v1에서 미끄러지고 v2에 따라 어느 1의 앞이나 뒤의 0의 개수를 얻는다(조건을 충족시키는 1의 개수로 구성할 수 있는 문자열의 수량은 좌우 양쪽의 0의 수량에 의해 결정된다. 예를 들어 왼쪽 3개의 0, 오른쪽 4개의 0을 자유롭게 조합하면 (3+1)*(4+1)=20개, 사고방식은 우객망 평론구역에 참고한다).

#include 
#include 
using namespace std;
int main(){
    int k;
    long long num = 0;   //         0，     
    string s;
    char c = ' ';
    vector<int> loc,zeros;  //loc    1   ，zeros   1  0   
    cin>>k;
    cin>>s;
    long long count = 0;
    for(int i = 0;i < s.length();++i){
        c = s[i];
        if(c == '1'){
            loc.push_back(i);
            zeros.push_back(count);
            count = 0;  //   1   0   ，  
        } else{
            count++;
        }
    }
    if( c == '1') zeros.push_back(0);   //      1     0   
    else    zeros.push_back(count);
    if( k == 0){
        long long val = 0;
        for(int i = 0;i < s.length();++i){
            c = s[i];
            if(c == '0') val++;
            else{
                num += (val * (val + 1) / 2);
                val = 0;
            }
        }
        if(c == '0'){
            num += (val * (val + 1) / 2);
        }
    } else if (k > loc.size()) num = 0;
    else{
        for (int i = 0; i + k - 1 < loc.size(); ++i) {
            num += ((zeros[i] + 1) * (zeros[i+k] + 1));
        }
    }
    cout<<num;
    return 0;
}