Hexo

Posted on

Preface

Content

Problem

Solution

树状数组、线段树、主席树

划分树

二叉搜索树、$$Treap$$

$$Splay$$树

WBLT

SBT

AVL 树

B 树，B+ 树

替罪羊树

Leafy Tree

笛卡尔树

红黑树、左偏红黑树

手指树

霍夫曼树

$$Chtholly$$树

Example

Remark

Posted on Edited on

Posted on Edited on

Posted on Edited on

Posted on Edited on

Posted on

Preface

A. Division

题源：CF1444A

题意：

给定若干组询问$$(p,q)$$，找出最大的，整除$$p$$的，不被$$q$$整除的整数$$x$$;

思路：

分解质因数$$p=\prod_{t=1}^{s}p_t^{\alpha_t}, q=\prod_{t=1}^{s}p_t^{\beta_t}$$,那么$$x={\max_{1\le i\le t}}({p_i^{\beta_i-1}\prod_{t=1,t\neq i}^{s}p_t^{\alpha_t}})$$;

模板为质因数分解的模板，在质因数分解的过程中同时寻找最大值；

本以为会超时，结果根本没有，可能数据没用毒瘤质数来卡吧；

AC 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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e9+7;

void solve(){
    ll p;
    ll q;
    cin>>p>>q;
    if(p%q!=0) {
        cout<<p<<endl;
        return;
    }
    ll ans=0;
    for(ll k=2;k*k<=q;k++){
        if(q%k!=0) continue;
        ll y=1;
        while(q%k==0) {
            y*=k;
            q/=k;
        }
        ll x=1;
        while(p%x==0) x*=k;
        x/=k;
        ll tmp=p/x*y/k;
        if(tmp>ans) ans=tmp;
    }
    if(q>1) {
        ll x=1;
        while(p%x==0) x*=q;
        x/=q;
        ll tmp=p/x;
        if(tmp>ans) ans=tmp;
    }
    cout<<ans<<endl;
    return;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}

B. Logistical Questions

题源：CF566C

题意：

思路：

AC code：

1

C. Lucky Array

题源：CF121E

题意：

思路：

AC code：

1

D. Is It a Cat?

题源：CF1800A

题意：

模拟题；

注意猫叫声音的结构已经给定，逐个判断每个字母的所在的串是否按顺序出现，同时保证不要有别的字母；

思路：

AC 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
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
bool ismM(char x){
    return x=='m'||x=='M';
}
bool iswW(char x){
    return x=='w'||x=='W';
}
bool iseE(char x){
    return x=='e'||x=='E';
}
bool isoO(char x){
    return x=='o'||x=='O';
}
int main ()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int t;
    cin>>t;
    while(t--)
    {
        int ans=0;
        int n;
        cin>>n;
        string s;
        cin>>s;
        int cnt=0;
        int i=0;
        for(i=0;i<n;i++){
            if(!ismM(s[0])) break;

            if(ismM(s[i])){
                if(cnt==0) cnt++;
                else{
                    if(!ismM(s[i-1])) break;
                }
            }
            else if(iseE(s[i])){
                if(cnt==1) cnt++;
                else{
                    if(!iseE(s[i-1])) break;
                }
            }
            else if(isoO(s[i])){
                if(cnt==2) cnt++;
                else{
                    if(!isoO(s[i-1])) break;
                }
            }
            else if(iswW(s[i])){
                if(cnt==3) cnt++;
                else{
                    if(!iswW(s[i-1])) break;
                }
            }
            else break;
        }
        if(i==n&&cnt==4) ans=1; 
        if(ans==1) printf("YES\n");
        else printf("NO\n");
        
    }
    return 0;
}

E. Merge Sort

题源：CF873D

题意：

思路：

Ac code:

1

F. Guess the K-th Zero (Hard version)

题源：CF1250F2

题意：

思路：

交互题；

Ac code:

1

G. Sum Over Zero

题源：CF1788E

题意：

给你一个长度为$n$的序列 a[1..n]，现在请你找到这个序列的若干个不相交的合法子段;
对于你选择的一个子段$[x,y]$，其为一个合法子段当且仅当子段的区间和非负
$$
\sum_{i=x}^{y} a_i\ge 0
$$
对于一个合法的子段$S=[x,y]$，我们记 $f(S)=(y−x+1)$，且当子段 $S$为空时， $f(S)=0$;

对于你选择的这若干个不相交合法子段，请最大化$\sum_S f(S)$并输出这个最大值

思路：

Ac code：

1

H. Watto and Mechanism

题源：CF514C

题意

给出 $n$个已知字符串，$m$次询问，每次询问给出一个字符串，问上面 $n$个字符串中是否有一个字符串满足恰好有一个字母不同于询问的字符串;

$n,m≤3×10^5 ,n,m≤3×10^5$，其中所有字符串的字符属于{'a','b','c'}，且输入总长度不超过$6×10^5$

思路

在线询问字符串是否匹配，运用字典树可以高效处理这样的匹配问题；

由于字符串的匹配必须刚好存在一个字符的错误，因此查找算法可以改进为DFS搜索算法，出错之后错误数加1，继续向下搜索，错误数为2则开始回溯，搜到结尾满足条件则返回匹配成功；

建树不做优化的化可能会在Test19出现MLE，但是一开始的思路是手动开栈模拟递归，不太行会有WA;

其实注意到了匹配成功必须有两个字符串长度相等，可以按长度分类建立字典树，但是由于没写过树套树,所以不太敢想；

树套树写了也没过test19, 但是其实数据卡的好可以做到数据点的字符串长度都相同，这样优化就一般了；

最终发现函数传递没有引用，导致递归栈每次都需要把字符串的内容copy一遍，改传引用就过了；

Ac 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
# include <iostream>
# include <vector>
# include <string>
using namespace std;

class Trie {
public:
    # define ALPHABET_SIZE 3
    # define MAX_CAPACITY 600005

    int cnt; // 维护当前结点标号，头结点标号为0
    int next[MAX_CAPACITY][ALPHABET_SIZE];
    bool isEndOfWord[MAX_CAPACITY];  // 标记某结点结尾的字符串是否存在

    void insert(std::string& s) { 
        // TODO: 插入字符串s到Trie树中
        int n = s.length();
        int p = 0;
        for(int i = 0; i < n; i++) {
            int index = s[i] - 'a';
            if(next[p][index] == 0) next[p][index] = ++cnt;
            p = next[p][index];
        }
        isEndOfWord[p] = true;  // 每次插入完成时在这个字符串所代表的节点处打上标记
    }

    Trie(std::vector<std::string>&words) {
        // TODO: 构建Trie树
        for(auto &word : words) insert(word);
    }
    bool find(std::string&s) {
        // TODO: 查询字符串s是否在Trie树中
        int n = s.length();
        int p = 0;
        for(int i = 0; i < n; i++) {
            int index = s[i] - 'a';
            if(next[p][index] == 0) return false;
            p = next[p][index];
        }
        return isEndOfWord[p];
    }

    bool dfs(std::string& q, int i, int p, int err){
        if(err > 1) return false;
        if(i == q.length() ) return (err ==1) & isEndOfWord[p];
        bool res[ALPHABET_SIZE ]={false};
        for(int idx = 0; idx < ALPHABET_SIZE; idx++){
            if(next[p][idx] != 0){
                res[idx] = dfs(q, i+1, next[p][idx], err + (q[i]- 'a' != idx));
            }
        }
        bool ans = false;
        for(int idx = 0; idx < ALPHABET_SIZE; idx++) ans |= res[idx];
        return ans;
    }
};

int main(){
    # ifdef MYIO
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    # endif

    int n, m;
    cin >> n >> m;
    vector<string> patten(n);
    vector<string> query(m);
    for(int i = 0; i < n; i++) cin >> patten[i];
    for(int i = 0; i < m; i++) cin >> query[i];

    Trie trie(patten);
    for(auto &q : query) {
        if(trie.dfs(q, 0, 0, 0)) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Remark

Posted on Edited on

Posted on Edited on

Posted on Edited on

Posted on Edited on

0%