CERC2018简要题解

发表于 更新于 分类于

题目大部分$\rm LOJ$有中文翻译，我就在那里做了。

链接： https://loj.ac/problems/search?keyword=cerc2018 。

A. The ABCD Murderer

利用$\rm AC$自动机求出以串中每个字符结尾的最大单词的长度，$\rm dp$一下就好了。

我好像写的好复杂。。。没必要用线段树转移，单调队列就行了。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 3e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

char s[maxn],t[maxn];
int n,m,tr[maxn][26],fail[maxn],cnt,vis[maxn],fa[maxn],dep[maxn],f[maxn],g[maxn],h[maxn];

void ins() {
    int now=0,len=strlen(t+1);
    for(int i=1;i<=len;i++) {
        int r=t[i]-'a';
        if(!tr[now][r]) tr[now][r]=++cnt,fa[cnt]=now,dep[cnt]=dep[now]+1;
        now=tr[now][r];
    }vis[now]=1;
}

void build_fail() {
    queue<int > q;
    for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
    while(!q.empty()) {
        int x=q.front();q.pop();
        if(vis[x]) h[x]=dep[x];
        else h[x]=h[fail[x]];
        for(int i=0;i<26;i++)
            if(tr[x][i]) {
                fail[tr[x][i]]=tr[fail[x]][i];
                q.push(tr[x][i]);
            } else tr[x][i]=tr[fail[x]][i];
    }
}

void get_suf() {
    int x=0;
    for(int i=1;i<=n;i++) 
        x=tr[x][s[i]-'a'],f[i]=h[x];
}

#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)

struct segment_tree {
    int t[maxn<<2];

    void modify(int p,int l,int r,int x,int v) {
        if(l==r) return t[p]=v,void();
        if(x<=mid) modify(ls,l,mid,x,v);
        else modify(rs,mid+1,r,x,v);
        t[p]=min(t[ls],t[rs]);
    }

    int query(int p,int l,int r,int x,int y) {
        if(x<=l&&r<=y) return t[p];
        int ans=1e9;
        if(x<=mid) ans=min(ans,query(ls,l,mid,x,y));
        if(y>mid) ans=min(ans,query(rs,mid+1,r,x,y));
        return ans;
    }
}T;

int main() {
    read(m);scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=m;i++) scanf("%s",t+1),ins();
    build_fail();
    get_suf();
    for(int i=1;i<=n;i++) {
        if(f[i]==i) g[i]=1;
        else if(f[i]) g[i]=T.query(1,1,n,i-f[i],i-1)+1;
        else g[i]=1e9;
        T.modify(1,1,n,i,g[i]>1e9?1e9:g[i]);
    }write(g[n]>=1e9?-1:g[n]);
    return 0;
}

C. Clockwork ||ange

注意到答案最大为$6$次，爆搜$6$层，加个记忆化剪枝，把$01$串压缩一下就过了。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long
#define ull unsigned ll 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 42;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,ans=6;ull all;
char ss[maxn];
map<ull,int > t;

void dfs(int x,int c,ull s) {
    if(x>=ans) return ;
    if(s==all) {ans=min(ans,x);return ;}
    if(c>=n) return ;
    if(t[s]) return ;t[s]=1;
    for(int k=1;k<n;k++) dfs(x+1,c<<1,s|((s>>(k&31))>>(k&32)));
}

int main() {
    // int st=clock();
    ull x=0;
    scanf("%s",ss+1);if(ss[1]=='0') return puts("-1"),0;
    n=strlen(ss+1);all=(1ull<<n)-1;
    for(int i=1;i<=n;i++) x=x<<1|(ss[i]-'0');
    dfs(0,1,x);write(ans);
    // cerr<<(lf)(clock()-st)/1e3<<endl;
    return 0;
}

E. Trees Gump

每次选出最靠左边的一个点，然后把这个点当做根，然后剩下的点极角排序，根据每个儿子子树大小一路划分过去就好了。

复杂度$O(n^2\log n)$。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int head[maxn],tot,sz[maxn],n,f[maxn],rev[maxn];
struct edge{int to,nxt;}e[maxn<<1];

struct P {
    int x,y,id;

    P operator - (const P &r) const {return (P){x-r.x,y-r.y};}
    ll operator * (const P &r) const {return 1ll*x*r.y-y*r.x;}
};

void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}

void dfs(int x,int fa) {
    sz[x]=1;f[x]=fa;
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=fa) dfs(e[i].to,x),sz[x]+=sz[e[i].to];
}

int cmp1(P x,P y) {return x.x<y.x||(x.x==y.x&&x.y<y.y);}

P pp;

int cmp(P x,P y) {return (x-pp)*(y-pp)>0;}

void solve(int x,vector<P > t) {
    sort(t.begin(),t.end(),cmp1);
    auto xx=t.begin();xx++;pp=t[0];
    sort(xx,t.end(),cmp);
    rev[x]=t[0].id;
    int p=1;
    for(int i=head[x];i;i=e[i].nxt) {
        int v=e[i].to;if(v==f[x]) continue;
        vector<P > tt;tt.clear();
        for(int w=p;w<p+sz[v];w++) tt.pb(t[w]);
        solve(v,tt);p+=sz[v];
    }
}

void dfs2(int x,int fa) {
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=fa) printf("%lld %lld\n",rev[x]-1,rev[e[i].to]-1),dfs2(e[i].to,x);
}

signed main() {
    vector<P > a;read(n);
    for(int i=1,x,y;i<n;i++) read(x),read(y),x++,y++,ins(x,y),ins(y,x);
    dfs(1,0);
    for(int i=1,x,y;i<=n;i++) read(x),read(y),a.pb((P){x,y,i});
    solve(1,a);
    dfs2(1,0);
    return 0;
}

I. The Silence of the Lamps

显然可以$n\log n$枚举约数处理出以每个数为乘积的方案数，前缀和之后就可以$O(1)$回答了。

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
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int f[maxn],g[maxn];

void gen() {
    int n=1e6;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i) if(i<j/i) g[j]++;
    for(int i=1;i<=n;i++)
        for(int j=i,t;j<=n;j+=i) {
            f[j]+=g[t=j/i];
            if(j!=1&&t%i==0&&t/i!=i) f[j]--;
        }
    for(int i=1;i<=n;i++) f[i]/=3,f[i]+=f[i-1];
}

int main() {
    gen();int t;read(t);
    for(int x,i=1;i<=t;i++) read(x),write(f[x]);
    return 0;
}

J. Matrice

如果只有一种方向，那么直接$\rm dp$就好了，否则就把矩阵翻转一下做四次。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e3+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

char s[maxn][maxn];
int n,m,p[maxn][maxn],f[maxn][maxn];

int calc() {
    for(int i=1;i<=n;i++)
        for(int j=m;j;j--)
            if(s[i][j]==s[i][j+1]) p[i][j]=p[i][j+1]+1;
            else p[i][j]=1;
    for(int i=1;i<m;i++) f[2][i]=(s[1][i]==s[2][i]&&s[2][i]==s[2][i+1])+1;
    for(int i=3;i<=n;i++)
        for(int j=1;j<m;j++)
            if(s[i][j]==s[i-1][j]) f[i][j]=min(f[i-1][j]+1,p[i][j]);
            else f[i][j]=1;
    int res=0;
    for(int i=2;i<=n;i++)
        for(int j=1;j<m;j++) res+=f[i][j]-1;
    return res;
}

int main() {
    int ans=0;read(n),read(m);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    ans+=calc();
    for(int i=1;i<=n;i++) reverse(s[i]+1,s[i]+m+1); 
    ans+=calc();
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n/2;i++) swap(s[i][j],s[n-i+1][j]);
    ans+=calc();
    for(int i=1;i<=n;i++) reverse(s[i]+1,s[i]+m+1);
    ans+=calc();write(ans);
    return 0;
}