【JZOJ4936】【NOIP2017GDKOI模拟1.12】c

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

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);            }        }    }}