蓝桥杯 5.字符串

蓝桥杯 5.字符串

文章目录

  • 蓝桥杯 5.字符串
    • KMP&字符串哈希
    • Manacher
    • 编程138-148
    • 字典树基础
    • 01Trie
    • 编程149-155

KMP&字符串哈希

KMP算法

  • 字符串匹配算法, 用于匹配**模式串P(短)和文本串S(长)**中出现的所有位置, 例如, S = “ababac”, P = “aba”, 那么出现的所有位置就是1和3
  • 初学KMP时, 只需记住和学会使用模板即可, 对其原理不需要过度深究
  • KMP算法将原本O(n^2)的字符串匹配算法优化到了O(n), 其中精髓在于next数组(仅与模式串P有关), next数组表示此时模式串下标失配时应该移动到的位置, 也表示最长的相同真前后缀的长度
// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可
char s[N], p[M];
int nex[M];
int n = strlen(s + 1), m = strlen(p + 1);
nex[0] = nex[1] = 0; // 初始化
for(int i = 2, j = 0; i <= m; i++){// 不断匹配p[i]和p[j + 1]while(j && p[i] != p[j + 1]) j = nex[j]; // 失配if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)
}// 通过next数组进行匹配
for(int i = 1, j = 0; i <= n; i++){while(j && s[i] != p[j + 1]) j = nex[j]; // 失配if(s[i] == p[j + 1]) j++;if(j == m) // 成功匹配一次
}

例题讲解

image-20250224175120346

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N];
char s[N], p[N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> p >> s;// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可int nex[N];int n = strlen(s + 1), m = strlen(p + 1);nex[0] = nex[1] = 0; // 初始化for(int i = 2, j = 0; i <= m; i++){// 不断匹配p[i]和p[j + 1]while(j && p[i] != p[j + 1]) j = nex[j]; // 失配if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}ll ans = 0;// 通过next数组进行匹配for(int i = 1, j = 0; i <= n; i++){while(j && s[i] != p[j + 1]) j = nex[j]; // 失配if(s[i] == p[j + 1]) j++;if(j == m) ans++; // 成功匹配一次}cout << ans << "\n";return 0;
}

字符串哈希

  • (基于进制的)字符串Hash本质上是用一个数字表示一段字符串, 从而降低字符串处理的复杂度
  • 这个数字是一个很大的数字, 采用unsigned int 类型, 可以自然溢出, 从而简化了去模的部分
  • 还需要一个进制数base, 用于规定这个数字的进制
  • Hash数组h[i]表示字符串s[1~i]的Hash值, 采用类似前缀和的形式以便于求出任意一个子串的Hash值
// 字符串Hash初始化:
typedef unsigned long long ull;
const ull base = 131; // base一般为一个质数
ull h[N];
char s[N];
for(int i = 1; i <= n; i++) h[i] = h[i - 1] * base + s[i] - 'A' + 1;// 获取子串s[l]~s[r]的Hash:
ull getHash(int l, int r){return h[r] - h[l - 1] * b[r - l + 1]; // b[i]表示base的i次方(预处理)
}

例题讲解

  • 还是上一道题, 1.斤斤计较的小Z
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef unsigned long long ull;
const ull base = 131; // base一般为一个质数
ull h1[N], h2[N], b[N];
char s[N], p[N];// 获取子串s[l]~s[r]的Hash:
ull getHash(ull h[], int l, int r){return h[r] - h[l - 1] * b[r - l + 1]; // b[i]表示base的i次方(预处理)
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> p >> s;int nex[N];int n = strlen(s + 1), m = strlen(p + 1);b[0] = 1;// 字符串Hash初始化:for(int i = 1; i <= n; i++) {b[i] = b[i - 1] * base;h1[i] = h1[i - 1] * base + (int)p[i];h2[i] = h2[i - 1] * base + (int)s[i];}int ans = 0;for(int i = 1; i + m - 1 <= n; i++){if(getHash(h1, 1, m) == getHash(h2, i, i + m - 1)) ans++;}cout << ans << "\n";return 0;
}

Manacher

回文串的性质

  • 类似AABAA, 对于每个i具有s[i] = s[n + 1 - i]的字符串
  • 回文半径: 对于一个回文中心i, 如果他的半径为r, 如果他为奇数长度的回文串的中心, 则说明[i - r + 1, i + r - 1]为一个回文串, 如果i是偶数长度的回文中心, 则回文半径没有意义(Manacher算法会解决这个问题)
  • 回文的递归性质: 某个点的回文半径相比关于某个回文中心的点的回文半径一定相等或更大

Manacher算法

  • ABBA没有回文半径, Manacher就是将所有的回文串转换成奇数长度的回文串, 方法是在字符串中间和头尾插入特殊字符, 转换后变成了^#A#B**#B#A$, 这个回文串是以黑色#**为回文中心, 以5为回文半径的, 它就表示原回文串中的回文长度为5-1=4
  • 位置i的回文半径以p[i]表示, 意思是在转换后的字符串中[i-p[i]+1, i+p[i]-1]是回文的

image-20250224203718876

image-20250224204600117

int c = 0, r = 0; // 初试都从0开始
for(int i = 1; i <= 2 * n + 1; i++){p[i] = i < r ? min(r - i, p[2 * c - i]) : 1;// 如果p[i]可以更大, 就持续更新while(s[i + p[i]] == s[i - p[i]]) p[i]++;// 如果此时i可以作为一个更好的c, 就替换if(i + p[i] > r) c = i, r = i + p[i];
}

例题讲解

image-20250224213138138

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
int p[N];
char s[N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> s + 1;int c = 0, r = 0; // 初试都从0开始int n = strlen(s + 1);// 添加符号, 使其成为Manacher字符串for(int i = 2 * n + 1; i >= 1; i--){s[i] = (i & 1) ? '#' : s[i >> 1];}s[0] = '^', s[2 * n + 1] = '$';for(int i = 1; i <= 2 * n + 1; i++){p[i] = i < r ? min(r - i, p[2 * c - i]) : 1;// 如果p[i]可以更大, 就持续更新while(s[i + p[i]] == s[i - p[i]]) p[i]++;// 如果此时i可以作为一个更好的c, 就替换if(i + p[i] > r) c = i, r = i + p[i];}int ans = 0;for(int i = 1; i <= 2 * n + 1; i++){ans = max(ans, p[i] - 1);}cout << ans << "\n";return 0;
}

编程138-148

image-20250224224252879

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p;
int nex[N];void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可nex[0] = 0; // 初始化for(int i = 1, j = 0; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;cin >> p;int ans = 0;getNext(p);for(int i = 0; i < p.size(); i++){ans = max(ans, nex[i]);}cout << ans << "\n";return 0;
}

image-20250225083049199

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
string p;
ll nex[N], ans;void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可int j = 0;nex[0] = 0; // 初始化for(int i = 1; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}ll find(ll x){if(!nex[x]) return x + 1;else return nex[x] = find(nex[x] - 1);
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n >> p;getNext(p);for(int i = 0; i < p.size(); i++){if(nex[i]) ans += (i + 1) - find(i);}cout << ans << "\n";return 0;
}

image-20250225092804059

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p, t;
ll nex[N], ans;
vector<ll> pre(N + 2), suf(N + 1);void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可int j = 0;nex[0] = 0; // 初始化for(int i = 1; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}// 通过next数组进行匹配
int KMP(string p, string s, vector<ll> &f){int a = -1;memset(nex, 0, sizeof(nex));getNext(s);for(int i = 0, j = 0; i < p.size(); i++){while(j && s[j] != p[i]) j = nex[j - 1]; // 失配if(s[j] == p[i]) j++;f[i] = j;if(j == s.size()) j = nex[j - 1]; // 成功匹配一次}return a;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, m, k; cin >> n >> m >> k >> p >> t;KMP(p, t, pre);reverse(p.begin(), p.end());reverse(t.begin(), t.end());KMP(p, t, suf);reverse(suf.begin(), suf.begin() + n);map<ll, ll> mp;for(int i = 0; i < n; i++){mp[suf[i]]++;}for(int i = 0; i < n; i++){mp[suf[i]]--;if(mp[m - pre[i]]){cout << "Yes\n";return 0;}}cout << "No\n";return 0;
}

image-20250225093617100

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
string p, t;
ll nex[N], ans;void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可int j = 0;nex[0] = 0; // 初始化for(int i = 1; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> p;getNext(p);ll tmp = p.size() - nex[p.size() - 1]; // 最小周期if(tmp != p.size() && p.size() % tmp == 0){ // 必须是周期的整数倍(不是的话就不能拼接成完整的字符串, 所以为1), 且和周期不相等, 相等则为1cout << p.size() / tmp; // 总长度/最小周期 == 最多子串的数量} else {cout << 1;}return 0;
}

142诗歌双联之谜 跟上面的诗歌双联一样, 而且比上面的题还弱了

image-20250225112351780

image-20250225095728817

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 5;
const ll INF = 1e14 + 9;
string s, p;
// char s[N], p[N];
ll nex[N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n >> s >> p;s += s;s = " " + s;p = " " + p;ll m = n; n <<= 1;for(int i = 1; i <= n; i++){if(islower(s[i])){s[i] = toupper(s[i]);} else {s[i] = tolower(s[i]);}}nex[0] = 0; // 初始化for(int i = 2, j = 0; i <= m; i++){// 不断匹配p[i]和p[j + 1]while(j && p[i] != p[j + 1]) j = nex[j]; // 失配if(p[i] == p[j + 1]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}ll ans = INF;for(int i = 1, j = 0; i <= n; i++){while(j && s[i] != p[j + 1]) j = nex[j]; // 失配if(s[i] == p[j + 1]) j++;if(j == m) {// 成功匹配一次ans = min({ans, i - m, 2 * m - i});// ans = min(ans, i - m);}}if(ans == INF) cout << "No\n";else cout << "Yes\n" << ans << "\n";return 0;
}

image-20250225131849521

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string p;
ll nex[N], f[N];void getNext(string &p){// 计算next数组的方式就是用P自己去匹配自己, 只需要掌握模板即可nex[0] = 0; // 初始化for(int i = 1, j = 0; i < p.size(); i++){// 不断匹配p[i]和p[j + 1]while(j > 0 && p[i] != p[j]) j = nex[j - 1]; // 失配if(p[i] == p[j]) j++; // 从while出来后要么j = 0, 要么p[i] == p[j+1] , 如果匹配成功, 则j后移nex[i] = j; // i如果匹配失败就回到j, 因为此时p[1~j]=p[i-j+1~i]或j=0(回到最初的地方重新开始匹配)}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n >> p;ll ans = 0;getNext(p);for(int i = 0; i < n; i++){f[i] = 1;}for(int i = n; i >= 0; i--){f[nex[i] - 1] += f[i];}for(int i = 0; i < n; i++){ans += f[i];}cout << ans << "\n";return 0;
}

image-20250225145916491

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 200010;
const int base = 131; // base一般为一个质数
ull h1[N], h2[N], p[N];
int n;
char s[N];// 获取子串s[l]~s[r]的Hash:
ull getHash1(int l, int r){return h1[r] - h1[l - 1] * p[r - l + 1];
}
ull getHash2(int l, int r){l = n - l + 1, r = n - r + 1;return h2[r] - h2[l - 1] * p[r - l + 1]; // 得到反转字符串的Hash值
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> s + 1;n = strlen(s + 1) * 2 + 1;// 添加符号, 使其成为Manacher字符串for(int i = n - 1; i; i -= 2){s[i + 1] = 'z' + 1;s[i] = s[i / 2];}s[1] = 'z' + 1;p[0] = 1;for(int i = 1, j = n; i <= n; i++, j--){ // 处理Hashh1[i] = h1[i - 1] * base + s[i] - 'a' + 1;h2[i] = h2[i - 1] * base + s[j] - 'a' + 1;p[i] = p[i - 1] * base;}int ans = 0;for(int i = 1; i <= n; i++){int l = 0, r = min(i - 1, n - i);while(l < r){int mid = l + r + 1 >> 1;if(getHash1(i - mid, i - 1) != getHash2(i + mid, i + 1)) {r = mid - 1;} else {l = mid;}}int len = i - l - 1;if(getHash1(1, len) == getHash2(n, n - len + 1)){if(s[i - l] <= 'z') ans = max(ans, l + 1 + len / 2 * 2);else ans = max(ans, l + len / 2 * 2);}len = n - (i + l);if(getHash1(1, len) == getHash2(n, n - len + 1)){if(s[i - l] <= 'z') ans = max(ans, l + 1 + len / 2 * 2);else ans = max(ans, l + len / 2 * 2);}}cout << ans << "\n";return 0;
}

146-148没写

字典树基础

朴素字符串查找

  • 给n个字符串s1~sn, 再给1个字符串t, 如何快速查找t是否在s中出现过
  • 朴素的方法是循环遍历s1~sn, 并比较si是否和t相等即可, 但是这个时间复杂度会比较大, 可能会超时

字典树

  • 字典树也叫Trie树, 是一种树形结构, 其中每个节点可以存储(当然也可以不存储)一些变量用于表示该字符串的数量, 下图中节点上的数字表示结点编号, 每条边表示一个字符
  • 建立一棵这样的树
int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 2; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)
  • 编写insert函数, 用于将一个字符串s加入进去
void insert(char s[]){ // 长度为n的字符串s插入到trie中int n = strlen(s + 1);int x = 1; // 从1开始往下走for(int i = 1; i <= n; i++){// 先检查x是否存在s[i]的边if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = idx++;x = nex[x][s[i] - 'a']; // x移动到新点上}cnt[x]++;
}
  • 编写一个check函数, 用于判断某个字符串在trie中的出现的次数
int check(char s[]){int n = strlen(s + 1);int x = 1;for(int i = 1; i <= n; i++) x = nex[x][s[i] - 'a'];return cnt[x];
}

image-20250225150840886

例题讲解

image-20250225194822820

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e6 + 5;int nex[N][26];
int cnt[N];
int idx = 2;void insert(char s[]){ // 长度为n的字符串s插入到trie中int x = 1; // 从1开始往下走for(int i = 1; s[i]; i++){// 先检查x是否存在s[i]的边if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = idx++;x = nex[x][s[i] - 'a']; // x移动到新点上}cnt[x]++;
}bool check(char s[]){int x = 1;for(int i = 0; s[i]; i++) x = nex[x][s[i] - 'a'];return x;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, m; cin >> n >> m;for(int i = 1; i <= n; i++){char s[N]; cin >> s + 1;insert(s);}for(int y = 1; y <= m; y++){char t[N]; cin >> t;cout << (check(t) ? "Y" : "N") << "\n";}return 0;
}

01Trie

介绍

image-20250225195251885

image-20250225195724410

插入

image-20250225200024615

查询

image-20250225200834947

例题讲解

image-20250225202143690

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 32 * 1e5 + 6, M = 1e5 + 9;
int a[M], prefix[M];
int son[N][2], tot = 1;void insert(int x){int o = 1;for(int i = 30; i >= 0; i--){int y = x >> i & 1;if(!son[o][y]) son[o][y] = ++tot;o = son[o][y];}
}
int query(int x){int o = 1, res = 0;for(int i = 30; i >= 0; i--){int y = x >> i & 1;if(son[o][!y]) o = son[o][!y], res |= (1 << i);else o = son[o][y];}return res;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];}for(int i = 1; i <= n; i++){prefix[i] = prefix[i - 1] ^ a[i];}insert(0);int ans = 0;for(int i = 1; i <= n; i++){ans = max(ans, query(prefix[i]));insert(prefix[i]);}cout << ans << "\n";return 0;
}

编程149-155

image-20250226194440596

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 5;
string s;
map<string, ll> mp;int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;for(int i = 1; i <= n; i++){cin >> s;mp[s]++;}for(auto it : mp){if(it.second >= 2){cout << 1 << "\n";return 0;}}cout << 0 << "\n";return 0;
}

image-20250226201953849

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
string s[N];
int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 0; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)void insert(string &s){ // 长度为n的字符串s插入到trie中int n = s.length();int x = 0; // 从1开始往下走for(int i = 0; i < n; i++){// 先检查x是否存在s[i]的边if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = ++idx;x = nex[x][s[i] - 'a']; // x移动到新点上cnt[x]++;}}int check(string &s){int n = s.length();int x = 0, dep = 0, mx = 0;for(int i = 0; i < n; i++){x = nex[x][s[i] - 'a'];dep++;if(cnt[x] >= 2){mx = max(mx, dep);}} return mx;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;for(int i = 1; i <= n; i++){cin >> s[i];insert(s[i]);}for(int i = 1; i <= n; i++){cout << check(s[i]) << "\n";}return 0;
}

image-20250226203331654

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 5;
string s[N];
string t[N];
int nex[N][27]; // nex[i][0]表示从结点i出发, 边为a的下一个结点地址
int cnt[N]; // cnt[i]表示以结点i结尾的字符串数量
int idx = 0; // 内存池, 用于动态开点
// 初始时, 只有一个结点1(作为根节点)void insert(string &s){ // 长度为n的字符串s插入到trie中int n = s.length();int x = 0; // 从1开始往下走for(int i = 0; i < n; i++){// 先检查x是否存在s[i]的边if(!nex[x][s[i] - 'a']) nex[x][s[i] - 'a'] = ++idx;x = nex[x][s[i] - 'a']; // x移动到新点上cnt[x]++;}}int check(string &s){int n = s.length();int x = 0, dep = 0, mx = 0;for(int i = 0; i < n; i++){if(nex[x][s[i] - 'a']){x = nex[x][s[i] - 'a']; // 能走就走} else {return 0; // 走不了则0}} return cnt[x];}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n, m; cin >> n >> m;for(int i = 1; i <= n; i++){cin >> s[i];insert(s[i]);}for(int i = 1; i <= m; i++){cin >> t[i];cout << check(t[i]) << "\n";}return 0;
}

image-20250226210303571

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 32 * 1e5 + 6, M = 1e5 + 9;
int a[M], prefix[M];
int son[N][2], tot = 1;void insert(int x){int o = 1;for(int i = 30; i >= 0; i--){int y = x >> i & 1;if(!son[o][y]) son[o][y] = ++tot;o = son[o][y];}
}
int query(int x){int o = 1, res = 0;for(int i = 30; i >= 0; i--){int y = x >> i & 1;if(son[o][!y]) o = son[o][!y], res |= (1 << i);else o = son[o][y];}return res;
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll n; cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];insert(a[i]);}ll q; cin >> q;for(int i = 1; i <= q; i++){ll x; cin >> x;cout << query(x) << "\n";}return 0;
}

153-155没写

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/24498.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

TEMU标签超简单制作方法，三步快速合成TEMU标签

TEMU标签超简单制作方法，三步快速合成TEMU标签

这个标签编辑工具使用方法很简单&#xff0c;零基础小白也能合成TEMU标签/跨境合规标签。 第一步&#xff1a;选择一个符合需求的标签 这个工具提供了非常多的标签模板&#xff0c;选择一个自己编辑即可。 第二步&#xff1a;编辑标签内容 提供了超多自定义编辑功能&…
阅读更多...
ChatGPT入驻Safari，AI搜索时代加速到来

ChatGPT入驻Safari，AI搜索时代加速到来

2月25日&#xff0c;人工智能领域巨头OpenAI宣布了一项重磅更新&#xff1a;为其广受欢迎的ChatGPT应用新增Safari浏览器扩展功能&#xff0c;并支持用户将ChatGPT设置为Safari地址栏的默认搜索引擎。这一举措标志着OpenAI在将ChatGPT整合进用户日常网络浏览体验方面迈出了重要…
阅读更多...
auto.js例子之WebView多页面浏览器

auto.js例子之WebView多页面浏览器

"ui";ui.layout(<vertical><horizontal id"webs" layout_weight"1"></horizontal><button id"one" text"第一个" /><button id"two" text"第二个" /><button id"…
阅读更多...
创建虚拟环境的方法

创建虚拟环境的方法

虚拟环境 python解释器 第三方包&#xff1b; 在系统中&#xff0c;一个虚拟环境就是一个文件夹&#xff0c;改动文件夹名字不行&#xff0c;因为已经写入了部分脚本中&#xff0c;如activate等启动程序中&#xff1b; Virtualenv 安装&#xff1a;pip install virtualenv…
阅读更多...
SQL注入（order by，limit），seacms的报错注入以及系统库的绕过

SQL注入（order by，limit），seacms的报错注入以及系统库的绕过

一、若information_schema被过滤了&#xff0c;应该如何绕过 简介&#xff1a; information_schema 是一个非常重要的系统数据库&#xff0c;它在SQL标准中定义&#xff0c;并且被许多关系型数据库管理系统&#xff08;RDBMS&#xff09;如MySQL、PostgreSQL等支持。这个库提供…
阅读更多...
HAL库串口发送函数 加 接收函数

HAL库串口发送函数 加 接收函数

数据类型 一个字节8个比特位&#xff0c;串口发送函数的第三个参数&#xff0c;写入的是数据的数量&#xff0c;以字节为单位。 ​/* exact-width signed integer types */ typedef signed char int8_t; typedef signed short int int16_t; typedef signed…
阅读更多...
Linux：进程信号（二.信号的保存与处理、递达、volatile关键字、SIGCHLD信号）

Linux：进程信号（二.信号的保存与处理、递达、volatile关键字、SIGCHLD信号）

目录 1.信号保存 1.1递达、未决、阻塞等概念 1.2再次理解信号产生与保存 1.3信号集操作函数 sigset_t类型 sigemptyset() 函数 sigismember()函数 sigaddset ()函数 sigdelset() 函数 sigprocmask()系统调用 sigpending()系统调用 2.信号的处理/递达 2.1信号处理时…
阅读更多...
【JavaEE】SpringMVC获取HTTP中的元素

【JavaEE】SpringMVC获取HTTP中的元素

目录 一、获取URL中的参数PathVariable二、上传⽂件RequestPart三、获取Cookie/Session3.1 HttpServletRequest和 HttpServletResponse3.2 获取Cookie3.2.1 使用HttpServletRequest3.2.2 使用注解CookieValue 3.3 设置session3.4 获取session3.4.1 使用HttpServletRequest3.4.2…
阅读更多...
React低代码项目：用户登陆

React低代码项目：用户登陆

吐司问卷&#xff1a;用户登陆 Date: February 17, 2025 4:12 PM (GMT8) JWT **概念&#xff1a;**登陆成功后&#xff0c;服务端返回一个 token JWT组成&#xff1a; JWT 由三个部分组成&#xff1a;头部&#xff08;Header&#xff09;、载荷&#xff08;Payload&#xf…
阅读更多...
集合与反射

集合与反射

一、集合体系 集合一共分为两部分&#xff1a;Collection&#xff08;单列集合&#xff09;每个元素&#xff08;数据&#xff09;只包含一个值。 Map&#xff08;双列集合&#xff09;每个元素包含两个值&#xff08;键值对&#xff09;。 二、ArrayList和LinkedList的区别 数…
阅读更多...
ubuntu：桌面版磁盘合并扩容

ubuntu：桌面版磁盘合并扩容

下载gparted磁盘编辑器 apt-get install gparted 打开gparted 更改目标分区大小 当遇到这个报错时&#xff0c;需要在命令行执行原分区的挂载指令 查看该分区信息 记住该目录&#xff0c;并在命令行执行 mount -o remount -rw /# 示例&#xff1a;mount -o remount -rw /v…
阅读更多...
全国各省山峰分布SHP数据详解及其在科学研究与旅游规划中的应用

全国各省山峰分布SHP数据详解及其在科学研究与旅游规划中的应用

一、引言 在中国这片广袤无垠的土地上&#xff0c;山峰作为自然界的壮丽景观&#xff0c;不仅构成了大地的骨架&#xff0c;更承载着丰富的自然资源和深厚的文化底蕴。 全国各省山峰分布SHP数据&#xff0c;作为一种地理信息系统&#xff08;GIS&#xff09;中的矢量数据格式…
阅读更多...
向量数据库milvus部署

向量数据库milvus部署

官方文档 Milvus vector database documentationRun Milvus in Docker (Linux) | Milvus DocumentationMilvus vector database documentation 按部署比较简单&#xff0c;这里说一下遇到的问题 一&#xff1a;Docker Compose 方式部署 1、镜像无法拉取,(docker.io被禁) …
阅读更多...
Java 基础面试题

Java 基础面试题

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…
阅读更多...
清华大学《AIGC发展研究3.0》

清华大学《AIGC发展研究3.0》

大家好&#xff0c;我是吾鳴。 AIGC已经爆火好长一段时间了&#xff0c;特别是DeepSeek的爆火&#xff0c;直接让很多之前没有体会过推理模型的人可以免费的使用上推理模型&#xff0c;同时DeepSeek产品形态也是全球首创&#xff0c;就是直接把AI的思考过程展示给你看&#xff…
阅读更多...
苹果CMS泛目录站群架构：无缓存刷新技术的SEO实战

苹果CMS泛目录站群架构：无缓存刷新技术的SEO实战

一、技术背景与行业痛点 传统泛目录站群系统普遍依赖静态缓存机制&#xff0c;导致两个核心问题&#xff1a; 缓存臃肿&#xff1a;运行3-6个月后缓存文件可达数百GB量级&#xff0c;严重影响服务器性能内容僵化&#xff1a;缓存机制导致页面TDK&#xff08;标题/描述/关键词…
阅读更多...
iview table组件中修改按钮时 要注意是否真的修改了值

iview table组件中修改按钮时 要注意是否真的修改了值

如图所示&#xff0c; switch按钮的默认值用dj来控制&#xff0c;但是如果没有加事情去修改切换后的值的话&#xff0c;那么他只会修改本身的显示值&#xff0c;但是我们需要跟着修改的列表数据的dj值是不会修改的&#xff0c;所以要注意&#xff0c;一定要加上事情去修改确定的…
阅读更多...
Go中slice和map引用传递误区

Go中slice和map引用传递误区

背景 关于slice和map是指传递还是引用传递&#xff0c;很多文章都分析得模棱两可&#xff0c;其实在Go中只有值传递&#xff0c;但是很多情况下是因为分不清slice和map的底层实现&#xff0c;所以导致很多人在这一块产生疑惑&#xff0c;下面通过代码案例分析slice和map到底是…
阅读更多...
Linux网络基础（协议 TCP/IP 网络传输基本流程 IP VS Mac Socket编程UDP）

Linux网络基础（协议 TCP/IP 网络传输基本流程 IP VS Mac Socket编程UDP）

文章目录 一.前言二.协议协议分层分层的好处 OSI七层模型TCP/IP五层(或四层)模型为什么要有TCP/IP协议TCP/IP协议与操作系统的关系(宏观上是如何实现的)什么是协议 三.网络传输基本流程局域网(以太网为例)通信原理MAC地址令牌环网 封装与解包分用 四.IP地址IP VS Mac地址 五.So…
阅读更多...
python-leetcode-乘积最大子数组

python-leetcode-乘积最大子数组

152. 乘积最大子数组 - 力扣&#xff08;LeetCode&#xff09; class Solution:def maxProduct(self, nums: List[int]) -> int:if not nums:return 0max_prod nums[0]min_prod nums[0]result nums[0]for i in range(1, len(nums)):if nums[i] < 0:max_prod, min_prod…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023