【JZOJ4936】【NOIP2017GDKOI模拟1.12】c

2017-01-13 08:17:41来源:CSDN作者:crybymyself人点击

第七城市

Description

这里写图片描述

Data Constraint

这里写图片描述

Solution

这道题咋一看很难做。但要注意一个问题:询问串之和小于2105。那么在1s内我们最多能跑500n,那么询问要大于500每一个串的长度至少也要400。所以我们可以预处理字符串长度小于400的情况。每一个询问,我们判断一下他的长度是否超过400,超过就暴力一下,否则直接输出就好了。

Code

#include<iostream>#include<cmath>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=2e5+7;int f[301][300],g[maxn];int n,i,t,j,k,l,m;char s[maxn],p[maxn];int main(){    freopen("c.in","r",stdin);    freopen("c.out","w",stdout);    scanf("%s/n",s+1);    n=strlen(s+1);    scanf("%d/n",&m);    for (i=1;i<=n;i++)        g[i]=g[i-1]+s[i]-48;    if (m<=300){        for (i=1;i<=m;i++){            scanf("%s/n",p+1);            t=strlen(p+1);k=0;            for (j=1;j<=t;j++)                k+=p[j];            k-=48*t;l=0;            for (j=t;j<=n;j++)                if (g[j]-g[j-t]==k) l++;            printf("%d/n",l);        }    }else{        for (i=1;i<=300;i++)            for (j=i;j<=n;j++)                f[i][g[j]-g[j-i]]++;        for (i=1;i<=m;i++){            scanf("%s/n",p+1);            t=strlen(p+1);k=0;            for (j=1;j<=t;j++)                k+=p[j];            k-=48*t;            if (t<=300) printf("%d/n",f[t][k]);            else{                l=0;                for (j=t;j<=n;j++)                    if (g[j]-g[j-t]==k) l++;                printf("%d/n",l);            }        }    }}
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台