寒假训练第四周训练报告

发表于 更新于 分类于

Part 1.训练题题解

寒假算法训练（二）字符串算法

#Algo0201.# 【模板】字符串哈希

题目描述

题目需要求出给定字符串中是否有重复的，利用桶存储字符串的Hash，并判断该Hash是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
char s[2001];
int n,ans;
const int N=100005;
int a[43961944];

struct Hash
{
    const int Mod1=43961944,u1=131;
    int h1[N],b1[N];
    void build(char *s)
    {
        b1[0]=1;
        for (int i=1;i<=strlen(s+1);i++)
        {
            b1[i]=b1[i-1]*u1%Mod1;
            h1[i]=(h1[i-1]*u1+s[i]-48)%Mod1;
        }
    }

    int getHash(int l,int r)
    {
        return (h1[r]-h1[l-1]*b1[r-l+1]%Mod1+Mod1)%Mod1;
    }
}Hash;

int main()
{
    CI n;
    F(i,1,n)
    {
        CI (s+1);
        Hash.build(s);
        int h=Hash.getHash(1,strlen(s+1));
        if (a[h]==0) 
        {
            a[h]=1;
            ans++;
        }
    }
    CO ans L;  
    return 0;
}

#Algo0202.# 【模板】KMP字符串匹配

题目描述

本题利用KMP算法，输出模式串匹配的位置，并在结尾打印next数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int n,m,nxt[1000006];
char a[1000006],b[1000006];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI (a+1)>>(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    nxt[1]=0;
    int j=0;
    for (int i=2;i<=m;i++)
    {
        while (b[i]!=b[j+1]&&j>0)
            j=nxt[j];
        if (b[i]==b[j+1])
        {
            j++;
            nxt[i]=j;
        }
    }

    j=0;
    for (int i=0;i<n;i++)
    {
        while (a[i+1]!=b[j+1]&&j>0)
            j=nxt[j];
        if (a[i+1]==b[j+1]) j++;
        if (j==m) cout<<i+1-m+1<<endl;
    }
    for (int i=1;i<=m;i++)
        cout<<nxt[i]<<" ";
    cout<<endl;
    return 0;
}

#Algo0203.# Censoring S

题目描述

本题利用KMP查找模式串的同时，用一个栈来记录答案，并用top指针指向栈顶，同时用一个栈f来记录字符串每位的j指针位置。当匹配到模式串后，top数组后移模式串的位数，同时将j指针调整到f栈栈顶记录的位置处。这样就可以在匹配到一个字符串后，将j指针还原到上一次匹配的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int n,m,nxt[1000006],f[1000006];
char a[1000006],b[1000006],c[1000006];

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI (a+1)>>(b+1);
    n=strlen(a+1);
    m=strlen(b+1);
    nxt[1]=0;
    int j=0;
    for (int i=2;i<=m;i++)
    {
        while (b[i]!=b[j+1]&&j>0)
            j=nxt[j];
        if (b[i]==b[j+1])
        {
            j++;
            nxt[i]=j;
        }
    }

    int top=0;
    for (int i=0;i<n;i++)
    {
        c[++top]=a[i+1];
        // cout<<top<<c[top]<<endl;
        while ((a[i+1]!=b[j+1])&&j>0)
            j=nxt[j];

        if (a[i+1]==b[j+1]) j++;
        f[top]=j;
        if (j==m) top-=m,j=f[top];
    }
    c[++top]='\0';
    cout<<(c+1)<<endl;
    return 0;
}

#Algo0204.# 无线传输

题目描述

字符串有一个循环节构成，求循环节的最小长度。输出这个字符串的next数组，不难发现，当循环节开始循环时，next值从1逐个增加，并在末尾处，next值表示该数组循环了多少位。将字符串总长度减去最后一位的next就能得到循环节的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n,m,nxt[1000006],ans=0;
char b[1000006];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI m;
    CI (b+1);
    m=strlen(b+1);
    nxt[1]=0;
    int j=0;
    for (int i=2;i<=m;i++)
    {
        while (b[i]!=b[j+1]&&j>0)
            j=nxt[j];
        if (b[i]==b[j+1])
        {
            j++;
            nxt[i]=j;
        }
    }

    cout<<m-nxt[m]<<endl;
    return 0;
}

Part 2.Codeforces题解

题目链接：https://codeforces.com/contest/1931

A. Recovering a Small String

难度：800

将a记为1，b记为2，以此类推。给出一个3-78之间的一个数，求出一个字典序最小的3个字母，使得这3个字母相加等于给定的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int t,x,a,b,c;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI x;
        F(i,1,26)
            F(j,1,26)
                F(k,1,26)
                    if (i+j+k==x)
                    {
                        cout<<(char)(i-1+'a')<<(char)(j-1+'a')<<(char)(k-1+'a')<<endl;
                        goto l;
                    }
        l:
        x++;   
    }
    return 0;
}

B. Make Equal

难度：800

给出一个数组，数组的每个数都可以分一部分给后面的数，问最后是否能够让每个数都相等。

先求出数组的总和并求出平均值，从头遍历数组，同时用一个变量x记录当前数字加x后比均值多出多少，然后将x加上当前数字并减去均值，如果图中出现变量x加上当前数字后依然小于均值，则最后无法做到每个数都相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int t,a[200005],sum,n,avg,x,f;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        sum=x=0;
        f=1;
        CI n;
        F(i,1,n)
        {
            CI a[i];
            sum+=a[i];
        }
        avg=sum/n;
        F(i,1,n)
        {
            if (a[i]+x>=avg) x=a[i]+x-avg;
            else
            {
                f=0;
                break;
            }
        }
        if (f) CO "YES" L;
        else CO "NO" L;
    }
    return 0;
}

C. Make Equal Again

难度：1000

给出一个数组，修改这些数组中的连续的一串数，使得数组中每个数都相等，求出最小的修改数量。

为了得到最小的修改数量，可以分别求出这组数中开头和结尾相同值有多少，如果开头和结尾相等，则用总长度减去开头和结尾相等值的长度；否则用总长度减去开头和结尾中较长的一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int t,n,a[200005];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n;
        F(i,1,n)
            CI a[i];
        int l1=a[1],l2=1,r1=a[n],r2=1;
        F(i,2,n)
            if (a[i]==l1) l2++;
            else break;
        FD(i,n-1,1)
            if (a[i]==r1) r2++;
            else break;
        if (l1==r1) CO max(0,n-l2-r2) L;
        else CO min(n-l2,n-r2) L;
    }
    return 0;
}

D. Divisible Pairs

难度：1300

找到题目中要求的数组，需要找出在前面中是否存在一个数满足(x-a%x)%x，a%y。

用一个字典，键为pair，存储的是(a%x,a%y），值为当前pair出现的次数。如果能找到((x-a%x)%x,a%y)，则将ans加上该键对应的值。然后将当前数(a%x,a%y)加入到字典中，如果已存在，则将值+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LL t,n,x,y,a,ans;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        ans=0;
        map<pair<LL,LL>,int> s;
        CI n>>x>>y;
        F(i,1,n)
        {
            CI a;
            if (s.find(make_pair((x-a%x)%x,a%y))!=s.end()) ans+=s.find(make_pair((x-a%x)%x,a%y))->second;
            if (s.find(make_pair(a%x,a%y))!=s.end()) s[make_pair(a%x,a%y)]++;
            else s.insert(make_pair(make_pair(a%x,a%y),1));
        }
        CO ans L;
    }
    return 0;
}