头像

Collapsar

Decease.




离线:1小时前



#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct  edge
{
        int to,nxt,val;
}e[N<<1];
int head[N],tot,n,ans,val[N<<5],a[N<<5][2],f[N];
bool vis[N];

void add( int u,int v,int w )
{
        e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].val=w;
}

void dfs( int x )
{
        vis[x]=1;
        for ( int i=head[x]; i; i=e[i].nxt )
                if ( !vis[e[i].to] )
                {
                        f[e[i].to]=f[x]^e[i].val; dfs( e[i].to );
                }
}

void insert( int x,int y,int now )
{
        if ( y<0 ) { val[x]=now; return; }
        int z=(now>>y)&1;
        if ( !a[x][z] ) a[x][z]=++tot;
        insert( a[x][z],y-1,now );
}

int search( int x,int y,int now )
{
        if ( y<0 ) return val[x];
        int z=(now>>y)&1;
        if ( a[x][z^1] ) return search( a[x][z^1],y-1,now );
        else return search( a[x][z],y-1,now );
}

int main()
{
        scanf( "%d",&n );
        for ( int i=1,u,v,w; i<n; i++ )
        {
                scanf( "%d%d%d",&u,&v,&w ); u++; v++;
                add( u,v,w ); add( v,u,w );
        }

        dfs( 1 ); tot=1; ans=0;
        insert( 1,30,0 );
        for ( int i=1; i<=n; i++ )
        {
                ans=max( ans,f[i]^search(1,30,f[i]) );
                insert( 1,30,f[i] );
        }

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



题目大意

给定 n 个模式串,m次询问,每次给出一个文本串,问这些模式串在文本串的前缀里出现了几次。

思路

对于 “前缀” 和字符串,很容易想到用 Trie 去做。与模板不同的是查询内容不一样。
首先,对 n个模式串构建 Trie树,并且记录 endpos,也就是 Trie 的当前节点是多少个模式串的结尾。
然后,由于每次查询的是前缀,就在 Trie 里面遍历文本串,累加途径的每个节点的 endpos 值即可,不能继续就退出。

(作为一道练手题是很好的选择,但是对于正式比赛而言,这样不给 n 和 m的范围还是有点不负责任的……万一 Trie 就不能用了呢)

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
char s[N];

int tr[N][26],cnt=1,endpos[N];
struct Trie
{
        void insert( char *s )
        {
                int p=1,len=strlen(s);
                for ( int i=0; i<len; i++ )
                {
                        int ch=s[i]-'a';
                        if ( tr[p][ch]==0 ) cnt++,tr[p][ch]=cnt;
                        p=tr[p][ch];
                }
                endpos[p]++;
        }
        int find( char *s )
        {
                int p=1,len=strlen(s),res=0;
                for ( int i=0; i<len; i++ )
                {
                        int ch=s[i]-'a'; p=tr[p][ch];
                        if ( p==0 ) return res;
                        res+=endpos[p];
                }
                return res;
        }
}T;

int main()
{
        scanf( "%d%d\n",&n,&m );
        while ( n-- )
                scanf( "%s\n",s ),T.insert( s );
        while ( m-- )
                scanf( "%s\n",s ),printf( "%d\n", T.find( s ) );
}


活动打卡代码 AcWing 142. 前缀统计

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
char s[N];

int tr[N][26],cnt=1,endpos[N];
struct Trie
{
        void insert( char *s )
        {
                int p=1,len=strlen(s);
                for ( int i=0; i<len; i++ )
                {
                        int ch=s[i]-'a';
                        if ( tr[p][ch]==0 ) cnt++,tr[p][ch]=cnt;
                        p=tr[p][ch];
                }
                endpos[p]++;
        }
        int find( char *s )
        {
                int p=1,len=strlen(s),res=0;
                for ( int i=0; i<len; i++ )
                {
                        int ch=s[i]-'a'; p=tr[p][ch];
                        if ( p==0 ) return res;
                        res+=endpos[p];
                }
                return res;
        }
}T;

int main()
{
        scanf( "%d%d\n",&n,&m );
        while ( n-- )
                scanf( "%s\n",s ),T.insert( s );
        while ( m-- )
                scanf( "%s\n",s ),printf( "%d\n", T.find( s ) );
}


活动打卡代码 AcWing 141. 周期

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,nxt[N];
char s[N];

int main()
{
        int cas=0;
        while ( scanf( "%d",&n ) && n )
        {
                scanf( "%s",s+1 );
                printf( "Test case #%d\n",++cas );

                for ( int i=2,j=0; i<=n; i++ )
                {
                        while ( j && s[i]!=s[j+1] ) j=nxt[j];
                        if ( s[i]==s[j+1] ) j++;
                        nxt[i]=j;
                }

                for ( int i=2; i<=n; i++ )
                        if ( i%(i-nxt[i])==0 && nxt[i] )
                                printf( "%d %d\n",i,i/(i-nxt[i]) );
                printf( "\n" );
        }
}


活动打卡代码 AcWing 140. 后缀数组

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int x[N],y[N],c[N],sa[N],rk[N],height[N],wei[30],n,m;
char s[N];

void SA() 
{
    for ( int i=1; i<=n; i++ ) 
        ++c[x[i]=s[i]]; 
    for ( int i=2; i<=m; i++ ) 
        c[i]+=c[i-1];  
    for ( int i=n; i>=1; i-- ) 
        sa[c[x[i]]--]=i;
    for ( int k=1; k<=n; k<<=1 ) 
    {
        int num=0;
        for ( int i=n-k+1; i<=n; i++ ) 
            y[++num]=i; 
        for ( int i=1; i<=n; i++ ) 
            if ( sa[i]>k ) y[++num]=sa[i]-k;  
        for ( int i=1; i<=m; i++ ) 
            c[i]=0;
        for ( int i=1; i<=n; i++ ) 
            ++c[x[i]];  
        for ( int i=2; i<=m; i++ ) 
            c[i]+=c[i-1];   
        for ( int i=n; i>=1; i-- ) 
            sa[c[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);
        x[sa[1]]=1; num=1;
        for ( int i=2; i<=n; i++ )
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
        if ( num==n ) break;
        m=num;
    }
    for ( int i=1; i<=n; i++ ) 
        printf( "%d ",sa[i]-1 );
}

void get_height() 
{
    int k=0;
    for ( int i=1; i<=n; i++ ) 
        rk[sa[i]]=i;
    for ( int i=1; i<=n; i++ ) 
    {
        if ( rk[i]==1 ) continue;
        if ( k ) --k;   //h[i]>=h[i-1]-1;
        int j=sa[rk[i]-1];
        while ( j+k<=n && i+k<=n && s[i+k]==s[j+k] ) ++k;
        height[rk[i]]=k;    //h[i]=height[rk[i]];
    }
    putchar(10);
    for ( int i=1; i<=n; i++ ) 
        printf( "%d ",height[i] );
}

int main() 
{
        scanf( "%s",s+1 );
//  gets( s+1 );

    n=strlen( s+1 ); m=122; 
    SA();
    get_height();
}



题目大意

给定一个长度为$ n$ 的字符串$S$(下标 $0\to n-1$ ),我们可以用整数 $k(0≤k<n)$ 表示字符串 $S$ 的后缀 $S(k~n-1)$ 。

把字符串 $S$ 的所有后缀按照字典序排列,排名为$i$ 的后缀记为 $SA[i]$ 。

我们考虑排名为 $i$ 的后缀与排名为 $i-1$ 的后缀,把二者的最长公共前缀的长度记为 $Height[i]$ 。

求出 $SA$与 $Height$ 这两个数组。

思路

后缀数组的模板。

简单来说,就是给你一个字符串,让你对他的n个后缀按字典序进行排序

sa[i] 代表排名为i的后缀的第一个字母在原串中出现的位置,rk[i] 代表从i位置开始的后缀的排名

x[i] 代表后缀i的第一关键字的排名,y[i] 代表第二关键字排名为i的,在以第一关键字排序的排名

c[i] 为基数排序用的桶

正常求后缀排名是 $O(n^2)$ 的

我们通过倍增来将其优化为 $O(nlogn)$

abdae 的后缀为: e ae dae bdae abdae

设通过一轮基数排序成功比较出了第一个字母 $O(n)$ ,

可以发现,每个后缀的第二个字母就是下一个后缀的第一个字母,而第一个字母已经求出,那么就优化了复杂度。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int x[N],y[N],c[N],sa[N],rk[N],height[N],wei[30],n,m;
char s[N];

void SA() 
{
    for ( int i=1; i<=n; i++ ) 
        ++c[x[i]=s[i]]; //c是桶,x[i]是第i个元素的第一关键字
    for ( int i=2; i<=m; i++ ) 
        c[i]+=c[i-1];  //做c的前缀和,我们就可以得出每个关键字最多是在第几名
    for ( int i=n; i>=1; i-- ) 
        sa[c[x[i]]--]=i;
    for ( int k=1; k<=n; k<<=1 ) 
    {
        int num=0;
        for ( int i=n-k+1; i<=n; i++ ) 
            y[++num]=i; //y[i]表示第二关键字排名i的数,第一关键字的位置
                        //第n-k+1到第n位是没有第二关键字的 所以排名在最前面
        for ( int i=1; i<=n; i++ ) 
            if ( sa[i]>k ) y[++num]=sa[i]-k;  //排名为i的数 在数组中是否在第k位以后
//如果(sa[i]>k) 那么可作为别人的2nd关键字,就把它1st关键字的位置添加进y,i枚举第二关键字的排名,靠前的先入队
        for ( int i=1; i<=m; i++ ) 
            c[i]=0;
        for ( int i=1; i<=n; i++ ) 
            ++c[x[i]];  //上一次循环已经算出了这次的第一关键字 所以直接加
        for ( int i=2; i<=m; i++ ) 
            c[i]+=c[i-1];   //第一关键字排名为1~i的数个数 
        for ( int i=n; i>=1; i-- ) 
            sa[c[x[y[i]]]--]=y[i],y[i]=0;
//因为y的顺序是按照第二关键字的顺序来排的
//第二关键字靠后的,在同一个第一关键字桶中排名越靠后
//基数排序
        swap(x,y);
        x[sa[1]]=1; num=1;
        for ( int i=2; i<=n; i++ )
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
//因为sa[i]已经排好序了,所以可以按排名枚举,生成下一次的第一关键字
        if ( num==n ) break;
        m=num;
    }
    for ( int i=1; i<=n; i++ ) 
        printf( "%d ",sa[i]-1 );
}

void get_height() 
{
    int k=0;
    for ( int i=1; i<=n; i++ ) 
        rk[sa[i]]=i;
    for ( int i=1; i<=n; i++ ) 
    {
        if ( rk[i]==1 ) continue;//第一名height为0
        if ( k ) --k;   //h[i]>=h[i-1]-1;
        int j=sa[rk[i]-1];
        while ( j+k<=n && i+k<=n && s[i+k]==s[j+k] ) ++k;
        height[rk[i]]=k;    //h[i]=height[rk[i]];
    }
    putchar(10);
    for ( int i=1; i<=n; i++ ) 
        printf( "%d ",height[i] );
}

int main() 
{
        scanf( "%s",s+1 );
//  gets( s+1 );

    n=strlen( s+1 ); m=122; //n表示原字符串长度,m表示字符个数,ascll('z')=122
    SA();
    get_height();
}



#include <bits/stdc++.h>
using namespace std;
const int N=22000010;
char s[N],str[N];
int pos[N];

int init()              //处理原字符串
{
        int len=strlen(s); 
        str[0]='@'; str[1]='#';         //@是防止越界
        int j=2;
        for ( int i=0; i<len; i++ )
                str[j++]=s[i],str[j++]='#';
        str[j]='\0'; return j;
}

int manacher()
{
        int ans=-1,len=init(),mx=0,id=0;
        for ( int i=1; i<len; i++ )
        {
                if ( i<mx ) pos[i]=min( pos[id*2-i],mx-i );             //situation1
                else pos[i]=1;                                  //situation2
                while ( str[i+pos[i]]==str[i-pos[i]] ) pos[i]++;                //扩展  
                if ( pos[i]+i>mx ) mx=pos[i]+i,id=i;            //update id
                ans=max( ans,pos[i]-1 );
        }
        return ans;
}

int main()
{
        int cnt=0;
        while ( scanf( "%s",s) && s[0]!='E' ) 
                printf( "Case %d: %d\n",++cnt,manacher() );
}



题目大意

求一个字符串的最长回文子串长度,多测。

解题思路

是 Manacher 算法的模板题。

Manacher

解决问题

最长回文子串:给定一个字符串,求它的最长回文子串长度。

复杂度是 $O(n)$ 的。

原理

从中心扩展延伸的方法的缺陷:处理字符串长度的奇偶性带来的对称轴不确定问题

解决方案,对原来的字符串进行处理,在首尾和所有空隙插入一个无关字符,插入后不改变原串中回文的性质,但串长都变成了奇数.

定义:回文半径:一个回文串中最左或最右位置的字符到其对称轴的距离 ,用 $p[i]$ 表示第 $i$ 个字符的回文半径.

    char : # a # b # c # b # a #
    p[i] :   1 2 1 2 1 6 1 2 1 2 1
p[i] - 1 : 0 1 0 1 0 5 0 1 0 1 0
       i :      1 2 3 4 5 6 7 8 9 10 11

显然,最大的 $p[i]−1$ 就是答案

插入完字符之后对于一个回文串的长度为 原串长度*2+1,等于 这个回文串回文半径*2+1,显然相等。

这样问题就转换成了怎样快速的求出 $p$.用 $mx$ 表示所有字符产生的最大回文子串的最大右边界, $id$ 表示产生这个边界的对称轴位置。

未命名.jpg
设已经求出了$p[1…7]$ ,当 $i<mx$ ,因为 $id$ 被更新过了,而 $i$ 是 $id$ 之后的位置,第 $i$ 个字符一定落在 $id$ 右边。

记 串i 表示以 i 为对称轴的回文串,j和id同理。

情况1:i < mx

利用回文串的性质,对于 $i$ ,可以找到一个关于 $id$ 对称的位置 $j=id∗2−i$ ,进行加速查找
(1)
未命名.jpg
显然 $p[i]=p[j]$ ,串 $i$ 不可以再向两边扩张。如果可以的话,$p[j]$ 也可以再扩张,而 $p[j]$ 已经确定了。
(2)
未命名.jpg
此时 $p[i]=p[j]$ ,与(1)不同的是,串 $i$ 是可以再扩张的。
(3)
未命名.jpg
此时 $p[i]=mx−i$ ,这时只能确定 串i 在 $mx$ 以内的部分是回文的,并不能确定串i 和 串j 相同。
同样,这时串i 是不可以再向两端扩张的。
未命名.jpg
如果可以扩张,如图,则 $d=c$ ,根据对称性 $c=b$ ,又因为 $a=b$ ,所以 $a=d$ ,串 $id$ 可以继续扩张,但 $p[id]$ 已经固定了.

情况2:i >= mx

5c7a2e7240b38.jpg
$p[i]=1$

代码

#include <bits/stdc++.h>
using namespace std;
const int N=22000010;
char s[N],str[N];
int pos[N];

int init()              //处理原字符串
{
        int len=strlen(s); 
        str[0]='@'; str[1]='#';         //@是防止越界
        int j=2;
        for ( int i=0; i<len; i++ )
                str[j++]=s[i],str[j++]='#';
        str[j]='\0'; return j;
}

int manacher()
{
        int ans=-1,len=init(),mx=0,id=0;
        for ( int i=1; i<len; i++ )
        {
                if ( i<mx ) pos[i]=min( pos[id*2-i],mx-i );             //situation1
                else pos[i]=1;                                  //situation2
                while ( str[i+pos[i]]==str[i-pos[i]] ) pos[i]++;                //扩展  
                if ( pos[i]+i>mx ) mx=pos[i]+i,id=i;            //update id
                ans=max( ans,pos[i]-1 );
        }
        return ans;
}

int main()
{
        int cnt=0;
        while ( scanf( "%s",s) && s[0]!='E' ) 
                printf( "Case %d: %d\n",++cnt,manacher() );
}


活动打卡代码 AcWing 138. 兔子与兔子

Collapsar
11天前
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
//const ll P=1e9+7;
const ull base=131;     //挺好用的一个hash base 
const int N=1e6+10;
int m;
ull sum[N],powe[N];
char s[N];

int main()
{
    scanf( "%s",s+1 );

    powe[0]=1; int len=strlen(s+1);
    for ( int i=1; i<=len; i++ )
    {
        //sum[i]=(sum[i-1]*base+(s[i]-'a'+1))%P;
        sum[i]=(sum[i-1]*base+(s[i]-'a'+1));        //字符串hash前缀和 
        powe[i]=powe[i-1]*base;                 //其实可以把字符串hash理解为base进制数 
        //powe[i]=powe[i-1]*base%P;
    }

    scanf( "%d",&m );
    while ( m-- )
    {
        int l1,l2,r1,r2; scanf( "%d%d%d%d",&l1,&r1,&l2,&r2 );
        //ll res1=sum[r1]-sum[l1-1]*powe[r1-l1+1]%P;
        ull res1=sum[r1]-sum[l1-1]*powe[r1-l1+1];
        ull res2=sum[r2]-sum[l2-1]*powe[r2-l2+1];
        //ll res2=sum[r2]-sum[l2-1]*powe[r2-l2+1]%P;
        if ( res1==res2 ) printf( "Yes\n" );
        else printf( "No\n" );
    }
}



Collapsar
11天前

题目大意

给定一个DNA序列,每个字符为26个小写字母之一。
有 $m$ 个询问,每次指定两个子串,问是否一样。

思路

显然的字符串hash+前缀和。
关于字符串前缀和:
其实可以理解成base进制数,每次多一位就 *base ,相当于左移一位,然后加上个位;
然后比较两个相等,就把左端点之前一个乘到右端点那一位,然后相减,不理解可以拿十进制模拟一下。

代码

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
//const ll P=1e9+7;
const ull base=131;     //挺好用的一个hash base 
const int N=1e6+10;
int m;
ull sum[N],powe[N];
char s[N];

int main()
{
    scanf( "%s",s+1 );

    powe[0]=1; int len=strlen(s+1);
    for ( int i=1; i<=len; i++ )
    {
        //sum[i]=(sum[i-1]*base+(s[i]-'a'+1))%P;
        sum[i]=(sum[i-1]*base+(s[i]-'a'+1));        //字符串hash前缀和 
        powe[i]=powe[i-1]*base;                 //其实可以把字符串hash理解为base进制数 
        //powe[i]=powe[i-1]*base%P;
    }

    scanf( "%d",&m );
    while ( m-- )
    {
        int l1,l2,r1,r2; scanf( "%d%d%d%d",&l1,&r1,&l2,&r2 );
        //ll res1=sum[r1]-sum[l1-1]*powe[r1-l1+1]%P;
        ull res1=sum[r1]-sum[l1-1]*powe[r1-l1+1];
        ull res2=sum[r2]-sum[l2-1]*powe[r2-l2+1];
        //ll res2=sum[r2]-sum[l2-1]*powe[r2-l2+1]%P;
        if ( res1==res2 ) printf( "Yes\n" );
        else printf( "No\n" );
    }
}

后记

一开始是想用 $1e9+7$ 作为模数的,因为听说 $ull$ 很容易被搞掉,而且我只写了单哈希。
不过后来不知道为啥取模取出锅了……调不出来还是用了。(详见代码注释掉的几行)
如果有人会取模做法的话求教qwq