当前位置: 首页 > news >正文

赛前训练4 extra 字典树

A

板子。

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=1e6+5,M=48;
int n,m,tot;
string s[N];
int trie[N][M],exist[N];void insert(string s){int cur=0;for(int i=0;i<s.size();i++){int ch=s[i]-'a';if(!trie[cur][ch])trie[cur][ch]=++tot;cur=trie[cur][ch];}exist[cur]++;
}
int search(string s){int cur=0,ans=0;for(int i=0;i<s.size();i++){int ch=s[i]-'a';if(!trie[cur][ch])return ans;cur=trie[cur][ch];ans+=exist[cur];}return ans;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>s[i],insert(s[i]);while(m--){string t;cin>>t;cout<<search(t)<<'\n';}return 0;
}

B

01-trie 板子。

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=3e6+5;
int n,tot;
int a[N],trie[N][2];void insert(int x){int cur=0;for(int i=31;i>=0;i--){int k=(x>>i)&1;if(!trie[cur][k])trie[cur][k]=++tot;cur=trie[cur][k];}
}
int search(int x){int ans=0,cur=0;for(int i=31;i>=0;i--){int k=(x>>i)&1;if(trie[cur][k^1])ans+=(k^1)<<i,cur=trie[cur][k^1];elseans+=k<<i,cur=trie[cur][k];}return ans;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i],insert(a[i]);int ans=-1e18;for(int i=1;i<=n;i++){int now=search(a[i])^a[i];ans=max(ans,now);}cout<<ans;return 0;
}

C

见题解。

D

考虑到异或是不进位的加法,说明 \(x \in [0,2 \times 10^6]\)

我们枚举 \(x\),这样 \(x,k\) 都能定下来,于是只要确定有多少个 \(a_i\)

\(a_i\) 全部扔进 01-trie 里头,画一下图分析,可分两种情况:若 \(k\) 当前位为 \(1\),则 \(x\) 的当前位的那个分支上的 \(a_i\) 全都可以选,我们仅需找另外一侧的;若为 \(0\),则必须走 \(x\) 的当前位的那个分支。

注意,最后需要加上恰好 \(= k\) 的情形。

实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=3e7+5;
int n,k,tot;
int a[N],trie[N][2],cnt[N];void insert(int x){int cur=0;for(int i=31;i>=0;i--){int xi=(x>>i)&1;if(!trie[cur][xi])trie[cur][xi]=++tot;cur=trie[cur][xi];cnt[cur]++;}
}
int search(int x){int cur=0,ans=0;for(int i=31;i>=0;i--){int xi=(x>>i)&1,ki=(k>>i)&1;if(ki)ans+=cnt[trie[cur][xi]],cur=trie[cur][xi^1];elsecur=trie[cur][xi];if(!cur)return ans;}if(cur)ans++;return ans;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i],insert(a[i]);int ans=-1e18;for(int x=0;x<=(int)(2e6);x++)ans=max(ans,search(x));cout<<ans;return 0;
}

总结:

  • 01-trie 画图与分析技巧:从高到低位依次对齐 01-trie 的每一层,分析如何在树上走(通常需要分类讨论)。
http://www.hskmm.com/?act=detail&tid=23110

相关文章:

  • CF1450E Capitalism
  • 二分图最大匹配 匈牙利算法
  • 2025 年脱硫剂厂家 TOP 企业品牌推荐排行榜,氧化铁,羟基氧化铁,常温氧化铁,沼气,天然气,煤气,煤层气,液化气,二氧化碳,氨气脱硫剂公司推荐
  • 2025 年砝码厂家 TOP 企业品牌推荐排行榜,不锈钢,标准,校准,天平,无磁,锁型,蓬莱,铸铁,定制,单双钩砝码公司推荐!
  • Java 在Word 文档中添加批注:高效文档协作的利器 - 指南
  • 2025雨棚生产厂家 TOP 企业品牌推荐排行榜,西安,陕西,西北推拉雨棚,推拉,移动,活动,户外,电动伸缩雨棚推荐这十家公司!
  • 关于整除分块
  • 2025 年木工机械设备厂家 TOP 企业品牌推荐排行榜,深度剖析木工机械设备推荐这十家公司!
  • Python语言自动玩游戏的消消乐游戏程序代码3QZQ
  • Python语言自动玩游戏的数字拼图游戏程序代码ZXQMQZQ
  • 如何找出集合的两个子集使得和相等?
  • Python语言自动玩游戏的俄罗斯方块游戏程序代码QZQ
  • Spring AI(七)Spring AI 的RAG搭建集合火山向量模型+阿里云Tair(企业版)
  • Python语言自动玩游戏的数字拼图游戏程序代码QZQ
  • 赛前训练4 字符串哈希
  • 英语
  • 处处吻
  • ThreadLocal原理与使用详解
  • WinCC监控框架实战解析:打通物联网网关的关键步骤
  • 2025国庆Day1
  • 2025 年包装印刷厂家 TOP 企业品牌推荐排行榜,西安,陕西,咸阳包装印刷,礼盒,定制,设计,优质,品质,环保,生产包装印刷公司推荐!
  • 2025 绝对式编码器厂家 TOP 企业品牌推荐排行榜,增量绝对式编码器,多圈绝对式编码器,二进制绝对式编码器 /ssi 绝对式编码器,拉线绝对式编码器公司推荐!
  • 2025 编码器厂家 TOP 企业品牌推荐排行榜,无磁,光学,脉冲,绝对型,伺服,机械多圈,工业,二进制,拉线编码器公司推荐
  • 2025 年玻璃钢水箱厂家 TOP 企业品牌推荐排行榜,30 吨,订做,消防,专业,方形,拼装式,屋顶,大型玻璃钢水箱推荐这十家公司!
  • 禁止DataGridView自动根据数据源的结构生成列
  • 2025 年压球机厂家 TOP 企业品牌推荐排行榜,新型,高压,节能,双螺旋干粉,对辊,煤粉,超低压压球机公司推荐!
  • 2025 年磨粉机厂家 TOP 企业品牌推荐排行榜,新型磨粉机,超细磨粉机,立式双动力磨粉机,节能磨粉机公司推荐!
  • 2025 年等离子清洗机厂家 TOP 企业品牌推荐排行榜,大气,真空,宽幅,微波,自动化,常压,低温,大腔体,射频,DBD,介质阻挡放电等离子清洗机公司推荐!
  • 完整教程:如何优雅的布局,height: 100% 的使用和 flex-grow: 1 的 min-height 陷阱
  • MyBatis缓存架构深度拆解:从PerpetualCache的LRU陷阱到Redis分布式二级缓存防穿透实战 - 详解