1941. Scary Martian Word

这道题一个长度为3的字符串视为一个火星文字母（ASCII 33-122），给出一个火星人认为恐怖的单词（由火星字母组成）

然后给你一篇文章问你火星人认为恐怖的单词个数（可以乱序）

嗯，一开始题意理解错了。。。然后就错了

彬神说……是双端队列

然后写了，感觉自己真是对对对的……

嗯，过度自信，起始忽略了一个条件。

做法，因为是三个单词 122+122*10+122*100 也就差不多了

然后哈希。数组标记，

懒得写了……

贴代码……

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <map>

#include <queue>

#include <stack>

#include <set>

#include <string>

#include <sstream>

using namespace std;

typedef long long ll;

const double ESP = 10e-;

const int MAXN =  + ;

int vis[MAXN];

int num[MAXN];

int arr[MAXN];

int n;

char word[MAXN*+];

int main(){

//    freopen("input.txt","r",stdin);

    int ans = ;

    memset(num,,sizeof(num));

    n = ;

    gets(word);

    int len = strlen(word);

    for(int i = ;i < len;i+=){

        int tt = (word[i]-) + (word[i+]-)*+(word[i+]-)*;

        num[tt]++;

        if(num[tt] == ){

            n++;

        }

    }

    gets(word);

    len = strlen(word);

    memset(arr,-,sizeof(arr));

    int cnt = ;

    for(int i = ;i < len;i+=){

        int tt = (word[i]-) + (word[i+]-)*+(word[i+]-)*;

        if(num[tt]){

            arr[cnt++] = tt;

        }

    }

    int l = ;

    int r = ;

    memset(vis,,sizeof(vis));

    int nn = ;

    while(l < cnt && r < cnt){

        if(arr[r] != -){

            vis[ arr[r] ]++;

            if(vis[arr[r]] == num[arr[r] ]){

                nn++;

            }else if(vis[ arr[r] ] > num[ arr[r] ]){

                while(l < cnt && arr[l] != arr[r]){

                    if(vis[arr[l] ] == num[arr[l] ]){

                        nn--;

                    }

                    vis[ arr[l] ]--;

                    l++;

                }

                vis[ arr[l]]--;

                l++;

            }

            if(nn == n){

                ans++;

                vis[arr[l]]--;

                nn--;

                l++;

            }

            r++;

        }else{

            nn = ;

            memset(vis,,sizeof(vis));

            r++;

            l = r;

        }

    }

    printf("%d\n",ans);

    return ;

}

不写注释的果然不是好程序员……

巴特西

1941. Scary Martian Word

最新文章

热门文章