Trie 董事会审查
最编程
2024-03-29 14:40:52
...
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 3e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}
int n,q,m;
const int M = 3e6+10;
int cnt = 1;
struct Trie{
int x[70],num;
}tree[M];
char s[M];
void pre()
{
for(int i=0;i<=cnt;++i){
for(int j=0;j<=69;++j){
tree[i].x[j] = 0;
}
tree[i].num = 0;
}
}
int getnum(char c)
{
if(c>='0'&&c<='9')return c-'0';
if(c>='a'&&c<='z')return c-'a'+10;
return c-'A'+37;
}
void insert()
{
int pos=1,len = strlen(s+1);
for(int i=1;i<=len;++i){
int num = getnum(s[i]);
if(!tree[pos].x[num])tree[pos].x[num] = ++cnt;
pos = tree[pos].x[num];
tree[pos].num++;
}
}
int find()
{
int pos = 1,len = strlen(s+1);
for(int i=1;i<=len;++i){
int num = getnum(s[i]);
if(!tree[pos].x[num])return 0;
pos = tree[pos].x[num];
}
return tree[pos].num;
}
void solve()
{
cin>>n>>q;
pre();cnt = 1;
while(n--){cin>>s+1;insert();}
while(q--){cin>>s+1;cout<<find()<<"\n";}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
cin>>_;
//_ = 1;
while(_--)solve();
return 0;
}
01trie
解决树上异或问题,维护根节点到每一个点的异或值,转化成O(n)*31 的查询问题
异或具有传递性
先看一道经典的板子
经典的O(n*31)
#include<iostream>
#include<cstring>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}
int n,q,m;
const int M = 2e6+10;
struct Trie{
int x[2],num;
}tree[M];
int cnt = 1;
// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){
// e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
// }
void insert(int x){
int pos = 1;
for(int i=30;i>=0;--i){
int t = x>>i&1;
if(!tree[pos].x[t])tree[pos].x[t] = ++cnt;
pos = tree[pos].x[t];
tree[pos].num++;
}
}
int find(int x){
int pos = 1;
int res = 0;
for(int i=30;i>=0;--i){
int t = x>>i&1;
if(tree[pos].x[!t]){res+=(1<<i);pos = tree[pos].x[!t];}
else pos = tree[pos].x[t];
}
return res;
}
int a[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
insert(a[i]);
}
int res = 0;
for(int i=1;i<=n;i++)res = max(res,find(a[i]));
cout<<res;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
//cin>>_;
_ = 1;
while(_--)solve();
return 0;
}
P4551 最长异或路径
注意边权下放的手法
再看一道经典的树上 其实就是上面的套个皮
推荐阅读
-
未经审查的风筝》全集下载及下载教程
-
亮点!实验动物伦理审查法规发生重大变化!
-
如懿传》派龚峰、陈曦进入万达电影董事会,放缓影院扩张步伐
-
R 基础知识和数据快速审查
-
开发高质量软件的秘密:代码审查、单元测试和持续集成
-
航空航天审查简介
-
像首席技术官一样思考:如何高效管理 30 人的研发团队?-管理越多越轻松。好的研发团队,应该是上拨下用,即下级对上级的向上管理;而不是反过来,总是向下管理,甚至是 CTO 做经理的事,经理做工程师的事,工程师最终会被当成实习生。如果是这样,就会越管越累,不仅团队无法成长,而且团队整天很忙还效率低下,问题一大堆。 有这样一个小故事:一位高级经理下班后帮忙倒垃圾,结果被老板训斥了一顿。这就好比首席技术官做了实习生自己该做的事。事情本身没有对错之分,只是从不同的角度有不同的理解。 古人云:"用人不疑,疑人不用"。在面对自己的研发团队时,应该相信他们能做好,授权一线开发人员充分发挥专业特长,不要限制他们的工作。但在相信他们的同时,也要进行二次确认,始终秉持 "我相信,但我要确认 "的原则和严谨的精神。因为每个人都会犯错和疏忽,通过发挥团队的智慧,团队犯错的机会就会大大减少。比如回归测试、代码审查、开发演示、变更审批等等。 如前所述,每个人都难免会犯错。但作为管理者,你所设计和商定的流程不能出错。管理者的每一个决定和沟通都应该经过深思熟虑。就像红绿灯的交通设计,某辆车不小心闯红灯可能会扣分,但红绿灯的设计一定要正确、人性化、统一。再比如,开发人员可能会因为疏忽大意写出 bug,但研发流程的设计和上线流程的发布不能有任何差错。因此,流程体系的设计,一方面要结合当前团队规模、业务特点和需要重点解决的问题来设计,另一方面也要在人员防错、效率提升、发挥团队集体智慧等维度进行综合考量。应该站在更高更抽象的角度去思考,不断思考一个倍受欢迎的园区应该如何设计,思考一个灵动、经典、永恒的建筑应该遵循怎样的模式,思考一个成功、优秀、卓越的研发团队应该需要怎样的流程和制度。 最后,反馈很重要。向上汇报很重要,向下反馈也很重要。能够保持顺畅的双向反馈和闭环管理,对研发团队的协作和沟通有着非常明显的积极作用。在向上汇报方面,要培养团队在正式汇报、会议汇报、私下沟通、书面总结、非正式场合等方面的沟通能力,提醒下属报喜也要报忧。凡事先记录,再跟进,最后反馈。反馈很重要,主动汇报更难得。 另一方面,同时也不要忽视向下反馈。好的爱,是双向的。团队也是如此,没有严格的上下级之分,只是分工和角色不同而已。作为管理者,不必总保持一种 "神秘感",让人 "捉摸不透 "才是牛。当团队做得好或有人做得好时,要记得在公开或私下场合给予肯定和赞许。业务有增长、业绩有提升时,别忘了给团队一些鼓励,或者安排一次下午茶或聚餐。在例会或正式会议上,也可以同步向大家传达一些重要信息和高层指示。"欲速则不达,欲远则同行"。 当向上汇报、向下反馈的沟通闭环形成后,同时结合前面研发过程的管理闭环,双管齐下,就能形成良性循环。如此反复,持之以恒,优秀卓越的研发团队,必将呈现。 能力、产出和效率 接下来,继续重复关于能力、产出和效率的话题。 站在不同的角色,以及一个企业经营、生存和发展所需要的基础上,我把研发生产力分为三个层次,分别是:一线员工关心的研发能力、管理层关心的软件产出和操作人员关心的企业生产效率。简单概括就是:既要把工作做好,又要能出成果,还要能帮企业赚钱。
-
首套机器人设计施工图通过官方审查,TransBIM 加速数字化建筑转型
-
我对构建人工智能的智能审查的浅薄理解
-
开发中的设计审查和规范审查