首页 algorithm 杂杂的算法知识

模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 1e5 + 10;//字符串长度
int son[N][30], cnt[N], idx;
void insert(string x)
{
	int p = 0;
	for(auto i: x)
	{
		int u = i - 'a';
		if(!son[p][u]) son[p][u] = ++idx;
		p = son[p][u];
	}
	cnt[p]++;
}
int query(string x)
{
	int p = 0;
	for(auto i: x)
	{
		int u = i - 'a';
		if(son[p][u]) p = son[p][u];
		else return 0;
	}
	return cnt[p];
}

# 最大异或对

143. 最大异或对 - AcWing 题库

对于二进制求异或最大的题目 ⇒\Rightarrow TrieTrie 树

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10, M = N * 31;
int son[M][2], idx;
void insert(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i--)
    {
    	int u = (x >> i) & 1;
    	if(!son[p][u]) son[p][u] = ++idx;
    	p = son[p][u];
	}
}
int query(int x)
{
	int p = 0, res = 0;
	for(int i = 30; i >= 0; i--)
	{
		int u = (x >> i) & 1;
		if(son[p][!u])
		{
			p = son[p][!u];
			res = res * 2 + 1;
		}
		else
		{
			p = son[p][u];
			res = res * 2;
		}
	}
	return res;
}
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i], insert(a[i]);
    int res = 0;
	for(int i = 0; i < n; i++) res = max(res, query(a[i]));     
	cout << res;
    return 0;
}

# 宝石商店

1007 宝石商店

在一定区间取异或最大值

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10, M = N * 30;
int son[M][2], idx;
vector<vector<int>> indices(M); // 存储每个节点对应的数字索引

void insert(int x, int id) 
{
    int p = 0;
    indices[p].push_back(id);
    for(int i = 29; i >= 0; i--) 
	{
        int u = (x >> i) & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
        indices[p].push_back(id);
    }
}

bool has_index_in_range(int p, int l, int r) 
{
    auto& vec = indices[p];
    auto it = lower_bound(vec.begin(), vec.end(), l);
    return it != vec.end() && *it <= r;
}

int query(int l, int r, int x) 
{
    int p = 0, res = 0;
    for(int i = 29; i >= 0; i--) 
	{
        int u = (x >> i) & 1;
        
        // 优先选择相反的位
        if(son[p][!u] && has_index_in_range(son[p][!u], l, r)) 
		{
            p = son[p][!u];
            res = res * 2 + 1;
        } 
        else if(son[p][u] && has_index_in_range(son[p][u], l, r)) 
		{
            p = son[p][u];
            res = res * 2;
        } 
        else 
		{
            return -1; // 没有满足条件的数字
        }
    }
    return res;
}

void solve() 
{
    // 重置全局变量
    memset(son, 0, sizeof son);
    for(auto& v : indices) v.clear();
    idx = 0;
    
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++) 
	{
        cin >> a[i];
        insert(a[i], i + 1); // 使用1-based索引
    }
    
    // 预处理排序所有indices以便二分查找
    for(auto& v : indices) 
	{
        sort(v.begin(), v.end());
    }
    
    while(q--) 
	{
        int l, r, x;
        cin >> l >> r >> x;
        cout << query(l, r, x) << '\n';
    }
}

signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}