4-2 补题 第九次训练

H.String Problem

题意：输入一个字符串，求其最大表示法和最小表示法分别在字符串中出现的次数。
分析：先求出最小，最大表示法，然后将s复制一遍(只复制len-1个字符)，分别把最小，最大表示跑一边kmp，输出答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e6+5;
char s[maxn],t1[maxn],t2[maxn];
int Next1[maxn],Next2[maxn];
int Getmin(char *s,int len);            //最小表示法求取
int Getmax(char *s,int len);            //最大表示法求取
void GetNext(char *s,int Next[],int len);
int Gettimes(char *s,char *t,int len1,int len2,int Next[]);
int main(){
    while (~scanf ("%s",s+1)){
        int len = strlen(s+1);
        int minx = Getmin(s+1,len),maxx = Getmax(s+1,len);
        for (int i=1;i<len;i++)     s[i+len] = s[i];
        for (int i=1,j1=minx,j2=maxx;i<=len;i++,j1++,j2++){
            t1[i] = s[j1];
            t2[i] = s[j2];
        }
        GetNext(t1,Next1,len);      GetNext(t2,Next2,len);
        printf ("%d %d %d %d\n",minx,Gettimes(s,t1,len*2-1,len,Next1),maxx,Gettimes(s,t2,len*2-1,len,Next2));
    }
    return 0;
}
void GetNext(char *s,int Next[],int len){
    for (int i=2,j=0;i<=len;i++){
        while (j && s[i]!=s[j+1])   j = Next[j];
        if (s[i]==s[j+1])   j++;
        Next[i] = j;
    }
    return;
}
int Gettimes(char *s,char *t,int len1,int len2,int Next[]){
    int ans = 0;
    for (int i=1,j=0;i<=len1;i++){
        while (j && s[i]!=t[j+1])   j = Next[j];
        if (s[i]==t[j+1])   j++;
        if (j==len2){
            ans++;
            j = Next[j];
        }
    }
    return ans;
}
int Getmin(char *s,int len){
    int i=0,j=1,k=0;
    while (i<len && j<len && k<len){
        int t = s[(i+k)%len] - s[(j+k)%len];
        if (!t) k++;
        else{
            if (t>0)    i = i+k+1;
            else    j = j+k+1;
            if (i==j)   j++;
            k = 0;
        }
    }
    return min(i,j)+1;
}
int Getmax(char *s,int len){
    int i=0,j=1,k=0;
    while (i<len && j<len && k<len){
        int t = s[(i+k)%len] - s[(j+k)%len];
        if (!t) k++;
        else{
            if (t<0)    i = i+k+1;
            else    j = j+k+1;
            if (i==j)   j++;
            k = 0;
        }
    }
    return min(i,j)+1;
}

J. Query

题意：给出两个字符串，若干次询问，每次询问要么更改某个字符串的某个字符的值，要么询问两字符串从下标i开始有多少了连续字符相等。
分析：可以用树状数组，1表示两字符串该位置相同，0表示不同，统计区间内1的数量sum(i)，当sum(r)-sum(l-1)==r-l+1时，说明l-r区间内的字符都相等，利用二分求答案。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6+6;
int c[maxn];
char s1[maxn],s2[maxn],s[20];
inline int lowbit(int i){return i&(-i);}
int sum(int i){       //求前i为的和
    int ans = 0;
    while (i){
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}
void update(int i,int k,int len){
    while (i<=len){
        c[i] += k;
        i += lowbit(i);
    }
    return;
}
int search(int l,int r){
    int mid = (l+r)/2;
    while (l!=r){
        mid = (l+r)/2 + ((l+r)&1);
        if (sum(mid)-sum(l-1)==mid-l+1)   l = mid;
        else    r = mid-1;
    }
    return s1[l]==s2[l]?l:l-1;
}
int main(){
    int t,cases=0;
    scanf ("%d",&t);
    while (t--){
        memset(c,0,sizeof c);
        printf ("Case %d:\n",++cases);
        scanf ("%s %s",s1+1,s2+1);
        int len = min(strlen(s1+1),strlen(s2+1)),q,x,y,flag;
        int l,r;
        char ch;
        for (int i=1;i<=len;i++)    if (s1[i]==s2[i])
            update(i,1,len);
        scanf ("%d",&q);
        while (q--){
            scanf ("%d",&flag);
            if (flag==1){
                scanf ("%d %d %c",&x,&y,&ch);   y++;
                if (y>len)  continue;
                int tmp = (s1[y]==s2[y]);
                if (x==1)   s1[y] = ch;
                else    s2[y] = ch;
                if (s1[y]==s2[y] && !tmp)   update(y,1,len);
                else if (s1[y]!=s2[y] && tmp)    update(y,-1,len);
            }else{
                scanf ("%d",&x);    x++;
                if (x>len)  continue;
                printf ("%d\n",search(x,len)-x+1);
            }
        }
    }
    return 0;
}