Hile_Meow's Blog

2020吉林省赛

2021-11-01 分类 组队训练 作者 Hile_Meow ~5.16K 字

NEERC之后的减压省赛，差点被碰到绝活题的瓜队爆杀。由于签到题太多，题解只写几道有价值的。

D. Trie

AC自动机fail树上dfs序建可持久化线段树。

考虑AC自动机的fail指针指向的一定是其后缀（瓜队：丝薄套路题），所以可以在fail树上用dfs序建一棵线段树方便更新和查询，此时

  • 对于1操作，等价于给出$k$个区间，将区间的并$+1$（多个区间取并集，不会有人不会吧）
  • 对于2操作，等价于询问某点的值
Code
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int n,m,q[N],dfn[N],R[N],cnt;
vector<int> G[N];
struct ACAutomaton{
    int trie[N][26],tot;
    int nx[N];
    void init(){
        for(int i=0;i<=tot;i++){
            nx[i]=0;
            for(int j=0;j<26;j++)
                trie[i][j]=0;
        }
        tot=0;
    }
    void insert(int x,int y){
        if(!trie[x][y]){
            trie[x][y]=++tot;
        }
    }
    void getnx(){
        queue<int> q;
        for(int i=0;i<26;i++){
            if(trie[0][i]){
                q.push(trie[0][i]);
                G[1].push_back(trie[0][i]+1);
            }
        }
        while(q.size()){
            int rt=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                int u=trie[rt][i],v=nx[rt];
                if(!u){
                    // trie[rt][i]=trie[nx[rt]][i];
                    continue;
                }
                q.push(u);
                while(v&&!trie[v][i])v=nx[v];
                nx[u]=trie[v][i];
                G[nx[u]+1].push_back(u+1);
            }
        }
    }
}AC;
void dfs(int u,int fa=0){
    dfn[u]=++cnt;
    for(auto v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    R[u]=cnt;
}
struct SegmentTree{
    #define lson o<<1,l,mid
    #define rson o<<1|1,mid+1,r
    int val[N<<2],tag[N<<2],vis[N<<2];
    void build(int o,int l,int r){
        tag[o]=val[o]=0,vis[o]=-1;
        if(l==r)return;
        int mid=l+r>>1;
        build(lson);
        build(rson);
    }
    void pd(int o,int k){
        tag[o]+=k;
        val[o]+=k;
    }
    void pushdown(int o){
        pd(o<<1,tag[o]);
        pd(o<<1|1,tag[o]);
        tag[o]=0;

    }
    void update(int o,int l,int r,int L,int R,int X){
        if(L<=l&&r<=R){
            pd(o,X);
            return;
        }
        pushdown(o);
        int mid=l+r>>1;
        if(L<=mid)update(lson,L,R,X);
        if(R>mid)update(rson,L,R,X);
    }
    int query(int o,int l,int r,int L,int R,int res=0){
        if(L<=l&&r<=R)return val[o];
        pushdown(o);
        int mid=l+r>>1;
        if(L<=mid)res+=query(lson,L,R);
        if(R>mid)res+=query(rson,L,R);
        return res;
    }
}S;
void update(int x){
    vector<pair<int,int>> p;
    for(int i=1;i<=x;i++){
        p.push_back({dfn[q[i]],R[q[i]]});
    }
    sort(p.begin(),p.end());
    int L=p[0].first,R=p[0].second;
    for(auto i:p){
        int l=i.first,r=i.second;
        if(i.first>R){
            S.update(1,1,n,L,R,1);
            L=i.first,R=i.second;
        }
        R=max(R,i.second);
    }
    S.update(1,1,n,L,R,1);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        AC.init();
        cnt=0;
        for(int i=1;i<=n;i++){
            G[i].clear();
        }
        for(int i=2,x;i<=n;i++){
            char ch;
            scanf("%d %c",&x,&ch);
            AC.insert(x-1,ch-'a');
        }
        AC.getnx();
        dfs(1);
        S.build(1,1,n);
        scanf("%d",&m);
        while(m--){
            int op,x;
            scanf("%d%d",&op,&x);
            if(op==1){
                for(int i=1;i<=x;i++){
                    scanf("%d",q+i);
                }
                update(x);
            }else{
                printf("%d\n",S.query(1,1,n,dfn[x],dfn[x]));
            }
        }
    }
}

H. Curious

数论。属于是莫反裸题了，用$c_i$表示$i$在$a$中的出现次数，则有

$\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=x]c_ic_j$

$=\sum_{i=1}^{\frac{n}{x}}\sum_{j=1}^{\frac{n}{x}}[gcd(i,j)=1]c_{ix}c_{jx}$

$=\sum_{i=1}^{\frac{n}{x}}\sum_{j=1}^{\frac{n}{x}}\sum_{d|gcd(i,j)}\mu(d)c_{ix}c_{jx}$

$=\sum_{d=1}^{\frac{n}{x}}\mu(d)\sum_{i=1}^{\frac{n}{xd}}\sum_{j=1}^{\frac{n}{xd}}c_{ixd}c_{jxd}$

$O(n\log n)$预处理后面那一块，然后对于每一个$x$调和级数暴力算答案，总复杂度$O(n\log n)$。

I. World Tree

贪心，dp。首先考虑树形dp，但是不会处理同层子树选择的优先级，考虑最优子结构贪心：

设

J. Situation

博弈，记忆化搜索。一共$2\times3^9$种状态，每种状态会转移到后继最值，复杂度$O(2\times9\times3^9)$，不熟悉的话可以补一补17女生赛的J题。

M. Upanishad

数据结构。首先考虑如果询问改成求区间内所有出现次数为奇数的数的异或和，那么答案就是该区间的异或和，所以，$出现次数为偶数的数的异或和=区间异或和\oplus区间set的异或和$，关键就是求出区间所有数的$set$。

考虑离线，枚举区间右端点，记录某数最后出现的位置，然后更新到树状数组上同时消除之前的影响以保证每个数只会出现一次，对于每个询问用树状数组求区间异或和即可。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2021-11-02