时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

Andi likes numbers and sequences, especially, sign sequences. A sign sequence is a sequence which consists of -1 and 1. Andi is a curious person, thus, he wants to build a sign sequence which length is N (the positions are numbered from 1 to N, inclusive).

However, Andi also likes some challenges. Therefore, he prefilled some positions in the sequence with -1 or 1 (the number in these positions cannot be changed). Andi also wants the sequence to fulfill K constraints.

For each constraint, there are 3 numbers: Ai, Bi, and Ci. This means that the sum of numbers which position is in the range Ai,Bi (inclusive) must be at least Ci.

Sounds confusing, right? It is not done yet. Since there can be many sequences that fulfill all the criteria above, Andi wants the sequence to be lexicographically smallest. Sequence X is lexicographically smaller than sequence Y if and only if there exists a position i where Xi < Yi and Xj = Yj for all j < i.

Find the sequence Andi wants.

输入

Input begins with a line containing two integers: N K (1≤N≤100000; 0≤K≤100000) representing the length of the sequence and the number of constraints, respectively. The second line contains N integers: Pi (-1≤Pi≤1). If Pi = 0, then the ith position in the sequence is not prefilled, otherwise the ith position in the sequence is prefilled by Pi. The next K lines, each contains three integers: Ai Bi Ci (1≤Ai≤Bi≤N;-N≤Ci≤N) representing the ith constraint.

输出

Output contains N integers (each separated by a single space) in a line representing the sequence that Andi wants if there exists such sequence, or “Impossible” (without quotes) otherwise.

样例输入

3 2

0 0 0

1 2 2

2 3 -1

样例输出

1 1 -1

先把0全部变成-1，然后区间按照从后往前更新，区间内部从前往后吧能改为1的改到零界就可以了,用线段树维护区间，查询区间就可以了

#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5+10;
struct node
{
    int l,r,val;
    bool operator < (const node &a)const{
        if(r==a.r) return l<a.l;
        return r<a.r;
    }
}q[maxn];
int ans[maxn];
int sum[maxn<<2];
bool flag[maxn];
void build(int rt,int l,int r){
    if(l==r){
        if(ans[l]==1){
            sum[rt]=1;
        }
        else {
            sum[rt]=-1;
        }
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int rt,int l,int r,int p,int v){
    if(l==r){
        sum[rt]+=v;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)update(rt<<1,l,mid,p,v);
    else update(rt<<1|1,mid+1,r,p,v);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int query(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        return sum[rt];
    }
    int mid=(l+r)>>1;
    if(y<=mid)return query(rt<<1,l,mid,x,y);
    else if(x>mid)return query(rt<<1|1,mid+1,r,x,y);
    else return query(rt<<1,l,mid,x,mid)+query(rt<<1|1,mid+1,r,mid+1,y);
}
int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for (int i = 1; i <=n ; ++i)
    {
        scanf("%d",ans+i);
        if(!ans[i]){
            ans[i]=-1;
            flag[i]=true;
        }
    }
    build(1,1,n);
    //cout<<"build succes"<<endl;
    for (int i = 1; i <= k; ++i){
        scanf("%d %d %d",&q[i].l,&q[i].r,&q[i].val);
        //cout<<q[i].l<<" "<<q[i].r<<" "<<q[i].val<<endl;
    }
    sort(q+1,q+1+k);
    //cout<<"sort sucxes"<<endl;
    bool fflag=false;
    for(int i=1;i<=k;i++){
        //cout<<"query start "<<q[i].l<<q[i].r<<endl;
        int number=query(1,1,n,q[i].l,q[i].r);
        //cout<<"query succes "<<number<<endl;
        if(number>=q[i].val) continue;
        int num=q[i].val-number;
        int tmpl=q[i].l,tmpr=q[i].r;
        while(num>0&&tmpl<=tmpr){
            if(flag[tmpr]){
                flag[tmpr]=false;
                ans[tmpr]=1;
                update(1,1,n,tmpr,2);
                //cout<<"update succes"<<endl;
                num-=2;
            }
            tmpr--;
        }
        if(num>0){
            fflag=true;
            break;
        }
    }
    //cout<<"break"<<endl;
    if(fflag) cout<<"Impossible"<<endl;
    else{
        for(int i=1;i<n;i++)
            printf("%d ", ans[i]);
        printf("%d\n", ans[n]);
    }
    return 0;
}

时间限制: 1 Sec 内存限制: 128 MB Special Judge

提交 状态 题面

题目描述

A binary string is a non-empty sequence of 0’s and 1’s, e.g., 010110, 1, 11101, etc. The edit distance of two binary strings S and T, denoted by edit(S,T), is the minimum number of single-character edit (insert, delete,or substitute) to modify S into T. For example, the edit distance of 0011 and 1100 is 4, i.e. 0011->011 ->11->110->1100. The edit distance of 1100101 and 1110100 is 2, i.e. 1100101->1110101->1110100.

Ayu has a binary string S. She wants to find a binary string with the same length as S that maximizes the edit distance with S. Formally, she wants to find a binary string Tmax such that |S| = |Tmax| and edit(S,Tmax)≥edit(S,T’) for all binary string T’ satisfying |S| = |T’|.

She needs your help-> However, since she wants to make your task easier, you are allowed to return any binary string T with the same length as S such that the edit distance of S and T is more than half the length of S. Formally, you must return a binary string T such that |S| = |T| and edit(S,T) > |S|/2 .

Of course, you can still return Tmax if you want, since it can be proven that edit(S,Tmax) > |S|/2 for any binary string S. This also proves that there exists a solution for any binary string S. If there is more than one valid solution, you can output any of them.

输入

Input contains a binary string S (1≤|S|≤2000).

输出

Output in a line a binary string T with the same length as S that satisfies edit(S,T) > |S|/2.

样例输入

0011

样例输出

1100

提示

As illustrated in the example above, the edit distance of 0011 and 1100 is 4. Since 4 > 4/2 , 1100 is one of the valid output for this sample.

大水题

#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    char s[2010];
    scanf("%s",s);
    int len=strlen(s);
    int Zreo=0,One=0;
    for(int i=0;i<len;i++){
        if(s[i]=='0') Zreo++;
        else One++;
    }
    if(Zreo>One){
        for(int i=0;i<len;i++){
            putchar('1');
        }
        putchar('\n');
    }
    else if(Zreo<One){
        for(int i=0;i<len;i++){
            putchar('0');
        }
        putchar('\n');
    }
    else{
        if(s[0]=='1'){
            putchar('0');
            for(int i=1;i<len;i++){
                putchar('1');
            }
            putchar('\n');
        }
        else{
            putchar('1');
            for(int i=1;i<len;i++){
                putchar('0');
            }
            putchar('\n');
        }
    }
    return 0;
}

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

The year is 1902. Albert Einstein is working in the patent office in Bern. Many patent proposals contain egregious errors; some even violate the law of conservation of energy. To make matters worse, the majority of proposals make use of non-standard physical units that are not part of the metric system (or not even documented). All proposals are of the following form:

• Every patent proposal contains n energy converters.
• Every converter has an unknown input energy unit associated with it.
• Some energy converters can be connected: If converter a can be connected to converter b such that one energy unit associated with a is turned into c input units for b, then this is indicated by an arc in the proposal. The output of a can be used as input for b if and only if such an arc from a to b exists.

Einstein would like to dismiss all those proposals out of hand where the energy converters can be chained up in a cycle such that more energy is fed back to a converter than is given to it as input, thereby violating the law of conservation of energy.

Einstein’s assistants know that he is born for higher things than weeding out faulty patent proposals. Hence, they take care of the most difficult cases, while the proposals given to Einstein are of a rather restricted form: Every admissible patent proposal given to Einstein does not allow for a cycle where the total product of arc weights exceeds 0.9. By contrast, every inadmissible patent proposal given to Einstein contains a cycle where the the number of arcs constituting the cycle does not exceed the number of converters defined in the proposal, and the total product of arc weights is greater or equal to 1.1.

Could you help Einstein identify the inadmissible proposals?

输入

The input consists of:

• one line with two integers n and m, where

– n (2 ≤ n ≤ 800) is the number of energy converters;

– m (0 ≤ m ≤ 4000) is the number of arcs.

• m lines each containing three numbers ai , bi , and ci , where

– ai and bi (1 ≤ ai , bi ≤ n) are integers identifying energy converters;

– ci (0 < ci ≤ 5.0) is a decimal number indicating that the converter ai can be connected to the converter b i such that one input unit associated with ai is converted to ci units associated with bi . The number ci may have up to 4 decimal places.

输出

Output a single line containing inadmissible if the proposal given to Einstein is inadmissible, admissible otherwise.

样例输入

2 2

1 2 0.5

2 1 2.3

样例输出

inadmissible

题意：给出一个有向图，在其中找环，如果存在一个环，使得这个环的的边权值乘起来大于1的话，这个环就不满足能量守恒，就输出”inadmissible”,否则就是满足的，输出”admissible”。

思路：第一看数据，5**800，可能会爆掉，所以对权值取lg，题就变成了找边权值累加之和为正值的。dfs跑最长路，然后如果跑到之前跑到过的点，就说明成环了，看这次跑到的权值与之前的权值比较，如果这次跑到的权值比上次的大，说明跑这个环值变大了，是一个正环。

#pragma GCC optimize(2)
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN = 4010;
int cnt,head[MAXN],reach[MAXN],vas[MAXN],n,m;
struct node
{
    int to,next;
    double val;
}edge[MAXN];
void addedge(int a,int b,double v){
    edge[++cnt].val=v;
    edge[cnt].to=b;
    edge[cnt].next=head[a];
    head[a]=cnt;
}
int vis[MAXN];
double sum[MAXN];
bool dfs(int u){
    reach[u]=1;
    vis[u]=1;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        double w=edge[i].val;
        if(sum[u]+w>sum[v]){
            sum[v]=sum[u]+w;
            if(vis[v]) return true;
            if(dfs(v)) return true;
        }
    }
    vis[u]=0;
    return false;
}
int a,b;
double v;
int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d %d %lf",&a,&b,&v);
        addedge(a,b,log(v));
    }
    bool flag=false;
    for(int i=1;i<=n;i++){
        if(!reach[i]){
            if(dfs(i)){
                flag=true;
                break;
            }
        }
    }
    if(flag) cout<<"inadmissible"<<endl;
    else cout<<"admissible"<<endl;
}

时间限制: 1 Sec 内存限制: 128 MB

题面 提交 状态

题目描述

Three friends like to play the following game. The first friend chooses a string S. Then the second friend constructs a new string T that consists of two copies of the string S. finally, the third friend inserts one letter at the beginning, the end or somewhere inside the string T, thereby creating a string U.

You are given the string U and your task is to reconstruct the original string S.

输入

The first line of the input contains N（2 ≤ N ≤ 2000001）, the length of the final string U. The string U itself is given on the second line. It consists of N uppercase English letters (A, B, C, . . . , Z).

输出

Your program should print the original string S. However, there are two exceptions:

1.If the final string U could not have been created using the above procedure, you should print NOT POSSIBLE.

2.If the original string S is not unique, you should print NOT UNIQUE.

样例输入

7

ABXCABC

样例输出

ABC

#pragma GCC optimize(2)
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6+10;
const int p = 131;
ull num[maxn],Hash[maxn];
ull pos=-1,S,L,R;
char str[maxn],ans[maxn];
int n,mid;
ull get_hash(int l,int r){
    return (ull)Hash[r] - (ull)Hash[l-1] * num[r-l+1];
}
int main()
{
    scanf("%d",&n);
    scanf("%s",str+1);
    num[0]=1;
    for(int i=1;i<=n;i++){
        num[i]=num[i-1]*p;
        Hash[i]=Hash[i-1]*p+str[i]-'A'+1;
    }
    mid = n>>1;
    if(n %2 ==0){
        printf("NOT POSSIBLE\n");
        return 0;
    }
    for(int i=1;i<=mid;i++){
        L=get_hash(1,i-1)*num[mid-i+1]+get_hash(i+1,mid+1);
        R=get_hash(mid+2,n);
        if(L==R){
            if(pos==-1||S==R){
                pos = i;
                S = R;
            }
            else{
                printf("NOT UNIQUE\n");
                return 0;
            }
        }
    }
    L=Hash[mid];
    R=Hash[n]-Hash[mid+1]*num[mid];
    if(L==R){
        if(pos==-1||S==L){
            pos=mid+1;
            S=L;
        } else{
            printf("NOT UNIQUE\n");
            return 0;
        }
    }
    for( int i=mid+2;i<=n;i++){
        L=Hash[mid];
        R=get_hash(mid+1,i-1)*num[n-i]+get_hash(i+1,n);
        if(L==R){
            if(pos==-1||S==R){
                pos = i;
                S = R;
            }
            else{
                printf("NOT UNIQUE\n");
                return 0;
            }
        }
    }
    if(pos==-1){
        printf("NOT POSSIBLE\n");
        return 0;
    }
    int len = n>>1,cnt=0;
    for(int i=1;i<=n&&len;i++){
        if(i==pos)
            continue;
        ans[cnt++]=str[i];
        len--;
    }
    ans[cnt]='\0';
    printf("%s\n",ans);
    return 0;
}

时间限制: 1 Sec 内存限制: 128 MB

题面 提交 状态

题目描述

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:

Step1. Connect the father’s name and the mother’s name, to a new string S.

Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).

Example: Father=’ala’, Mother=’la’, we have S = ‘ala’+’la’ = ‘alala’. Potential prefix-suffix strings of S are {a’, ‘ala’, ‘alala’}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)

输入

The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.

Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.

输出

For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby’s name.

样例输入

ababcababababcabab

aaaaa

样例输出

2 4 9 18

1 2 3 4 5

#pragma GCC optimize(2)
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn = 4e5+5;
const int p = 71;
char s[maxn];
ull a,b,tmp;
bool flag = false;
int main(){
    while(~scanf("%s",s)){
        //cout<<s<<endl;
        int len = strlen(s);
        tmp=1,a=0,b=0;
        flag=false;
        for(int i=0,j=len-1;i<len;i++,j--){
            a = a * p + (s[i] - 'a' + 1) ;
            b = (s[j] - 'a' + 1) * tmp +b;
            if (a==b){
                if(flag) putchar(' ');
                printf("%d",i+1);
                flag = true;
            }
            tmp *= p;
        }
        putchar('\n');
    }
    return 0;
}

时间限制: 1 Sec 内存限制: 128 MB

题面 提交 状态

题目描述

Given two strings a and b we define a * b to be their concatenation. For example, if a = “abc” and b = “def” then a * b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a * (a^n).

输入

Each test case is a line of input representing s, a string of printable characters.

输出

For each s you should print the largest n such that s = a^n for some stringa. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

样例输入

abcd

aaaa

ababab

.

样例输出

1

4

3

后缀数组 连续重复字串

穷举字符串S的⻓ k，然后判断是否满⾜。判断的时候，先看字符串L的⻓度能否被k整除，再看suffix(1)和suffix(k+1)的最⻓公共前缀是否等于n-k。在询问最⻓公共前缀的时候，suffix(1)是固定的，所以RMQ问题没有必要做所有的预处理，只需求出height数组中的每⼀个数到heigh[trank[1]]之间的最⼩值即可。整个做法的时间复杂度为O(n)。

记得开o2优化，不然会T

#pragma GCC optimize(2)
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
using namespace std;
const int MAXN = 1000005;
const int inf = 1000000007;
int wa[MAXN*3],wb[MAXN*3],wv[MAXN*3],wss[MAXN*3];
int sa[MAXN*3],Rank[MAXN*3],height[MAXN*3],r[MAXN*3];
char s[MAXN];
int query[MAXN];
int c0(int *r,int a,int b){
    return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b){
    if(k==2){
        return r[a]<r[b]||(r[a]==r[b]&&c12(1,r,a+1,b+1));
    }
    else{
        return r[a]<r[b]||(r[a]==r[b]&&wv[a+1]<wv[b+1]);
    }
}
void sort(int *r,int *a,int *b,int n,int m){
    int i;
    for(i=0;i<n;i++){
        wv[i]=r[a[i]];
    }
    for(i=0;i<m;i++){
        wss[i]=0;
    }
    for(i=0;i<n;i++){
        wss[wv[i]]++;
    }
    for(i=1;i<m;i++){
        wss[i]+=wss[i-1];
    }
    for(i=n-1;i>=0;i--){
        b[--wss[wv[i]]]=a[i];
    }
}
void dc3(int *r,int *sa,int n,int m){
    int i,j,*rn=r+n;
    int *san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
    r[n]=r[n+1]=0;
    for(i=0;i<n;i++){
        if(i%3!=0){
            wa[tbc++]=i;
        }
    }
    sort(r+2,wa,wb,tbc,m);
    sort(r+1,wb,wa,tbc,m);
    sort(r,wa,wb,tbc,m);
    for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++){
        rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
    }
    if(p<tbc){
        dc3(rn,san,tbc,p);
    }
    else{
        for(int i=0;i<tbc;i++){
            san[rn[i]]=i;
        }
    }
    for(i=0;i<tbc;i++){
        if(san[i]<tb){
            wb[ta++]=san[i]*3;
        }
    }
    if(n%3==1){
        wb[ta++]=n-1;
    }
    sort(r,wb,wa,ta,m);
    for(i=0;i<tbc;i++){
        wv[wb[i]=G(san[i])]=i;
    }
    for(i=0,j=0,p=0;i<ta&&j<tbc;p++){
        sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
    }
    for(;i<ta;p++){
        sa[p]=wa[i++];
    }
    for(;j<tbc;p++){
        sa[p]=wb[j++];
    }
}
void getheight(int *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=0; i<n; i++)
        r[i]=s[i];
    r[i]=0;
    dc3(r,sa,n+1,128);
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
}

int main()
{
    while(scanf("%s",s))
    {
        if(!strcmp(s,".")){
            break;
        }
        int n=strlen(s);
        getheight(r,sa,n);
        query[Rank[0]]=inf;
        int i;
        for(i=Rank[0]-1; i>=1; i--)
            query[i]=min(height[i+1],query[i+1]);
        for(i=Rank[0]+1; i<=n; i++)
            query[i]=min(height[i],query[i-1]);
        for(i=1; i<=n; i++)
            if(n%i==0&&query[Rank[i]]==n-i)
                break;
        printf("%d\n",n/i);
    }
    return 0;
}

时间限制: 1 Sec 内存限制: 128 MB

题面 提交 状态

题目描述

图书管理是一件十分繁杂的工作，在一个图书馆中每天都会有许多新书加入。为了更方便的管理图书（以便于帮助想要借书的客人快速查找他们是否有他们所需要的书），我们需要设计一个图书查找系统。

该系统需要支持 2 种操作：

add(s) 表示新加入一本书名为 s 的图书。

find(s) 表示查询是否存在一本书名为 s 的图书。

输入

第一行包括一个正整数 n（n≤30000），表示操作数。 以下n行，每行给出 2 种操作中的某一个指令条，指令格式为：

add s

find s

在书名s与指令（add，find）之间有一个隔开，我们保证所有书名的长度都不超过200。可以假设读入数据是准确无误的。

输出

对于每个 find(s) 指令，我们必须对应的输出一行 yes 或 no，表示当前所查询的书是否存在于图书馆内。

注意：一开始时图书馆内是没有一本图书的。并且，对于相同字母不同大小写的书名，我们认为它们是不同的。

样例输入

4

add Inside C#

find Effective Java

add Effective Java

find Effective Java

样例输出

no

yes

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
map<pll,bool> mmap;
const pll k(1e9+9,1e9+321);
const pll p(1e9+7,1e9+9);
const pll one(1ll,1ll);
const pll zero(0ll,0ll);

pll operator - (pll a,pll b){
    return make_pair((a.first - b.first + p.first)%p.first,(a.second - b.second + p.second)%p.second);
}
pll operator * (pll a,pll b){
    return make_pair((a.first * b.first)%p.first,(a.second * b.second)%p.second);
}
pll operator + (pll a,pll b){
    return make_pair((a.first + b.first)%p.first,(a.second + b.second)%p.second);
}
pll operator + (pll a,int b){
    return make_pair((a.first + b)%p.first,(a.second + b)%p.second);
}

pll Hash(char a[]){
    pll tmp = zero;
    for(int i=0;a[i]!='\n';i++)
        tmp = tmp*k + a[i];
    return tmp;
}
char a[500],b[20];
int main(){
    int n;
    cin>>n;
    while(n--){
        cin>>b;
        for(int i = 0;(a[i] = getchar())!='\n';i++);
        pll x = Hash(a);
        if(b[0]=='a')
            mmap[x] = true;
        else{
            mmap[x]?printf("yes\n"):printf("no\n");
        }
    }
    return 0;
}

时间限制: 1 Sec 内存限制: 128 MB

题面 提交 状态

题目描述

这是一道模板题。

给定一个字符串A和一个字符串B，求B在A中的出现次数。A和B中的字符均为英语大写字母或小写字母。

A中不同位置出现的B可重叠。

输入

输入共两行，分别是字符串A和字符串B。

输出

输出一个整数，表示B在A中的出现次数。

样例输入

复制样例数据

zyzyzyz

zyz

样例输出

3

提示

1≤A,B的长度≤106，A、B仅包含大小写字母。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 100;
const int temp = 71;
char a[maxn], b[maxn];
ll f[maxn];
int lena,lenb;
ll haxi[maxn],aa[maxn];
ll ans,cnt;
void fun(){
    f[1] = 71;
    for (int i = 2; i < maxn; i++)
        f[i] = f[i - 1] * temp;
}
int main() {
    fun();
    scanf("%s %s",a,b);
    lena =strlen(a);
    lenb = strlen(b);
    for(int i=lenb-1; i>=0; i--){
        ans=ans*temp;
        ans+=b[i];
    }
    for(int i=lena-1; i>=0; i--){
        haxi[i]=haxi[i+1]*temp;
        haxi[i]+=a[i];
    }
    for(int i=0;i<=lena-lenb;i++){
        aa[i]=haxi[i]-haxi[i+lenb]*f[lenb];
    }
    for(int i=0; i<=lena-lenb; i++){
        if(ans==aa[i]) cnt++;
    }
    printf("%lld\n", cnt);
    return 0;
}