URAL 1941

比赛的时候三个点没有优化成功。其实也没有想到哈希成数。然后就变成了只要一个长度和scary相等的区间内所有数字个数都是相等的。那么就是符合题意的。于是。为了不TLE我们不能对txt每个位置遍历 的同时还对scary每个位置遍历。

这个代码好有智慧。数据不极端的情况下是不会超时的。

#include<stdio.h>

#include<string.h>

#include<iostream>

using namespace std;

#define maxn 2000010

#define maxm 32010

char txt[maxn], sc[maxm];  // 输入的字符串

int th[], sh[];   // th[]存txt中每个字符的值是多少.sh[]数组存scary字符串中每个字符对应值有多少个。

int main()

{

    while(gets(sc))

    {

        int cnt1 = , cnt2 = ;

        memset(sh, , sizeof(sh));

        memset(th, , sizeof(th));

        int len = strlen(sc);

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

        {

            int temp = sc[i] - ;

            sh[temp]++;

            cnt1++;

        }

        gets(txt);

        len = strlen(txt);

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

        {

            int temp = txt[i] - ;

            th[cnt2] = temp;

            cnt2++;

        }

        int st = ; // 从第一个点依次遍历从每个点开始到此后cnt1区间是不是对应值个数相等。

        int ans = ;

        for (int i=; i<cnt2; ++i)

        {

            sh[th[i]]--;

            while (sh[th[i]]<) //比较过程中遇见一个个数不足 或者 scary里没出现的字符起点就要从这里开始

            {

                sh[th[st]]++;   //同时起点前面那些都回溯没有访问过

                st++;

            }

            if (i-st+ == cnt1)  //如果此时长度和scary相同。一定就是个数相同.ans++;

            {

                ans++;

                sh[th[st]]++;

                st++;

            }

        }

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

    }

    return ;

}

L哦哦K