大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
T1:背单词(bzoj4567)
题解
关键词：trie树 贪心
题意有些难懂，简单解释一下。
对于在位置 x x 的单词：
- 单词没有后缀，吃
x
颗泡椒- 所有后缀在 1 1 ~
x−1
中出现，且后缀最靠后位置为 y y ，吃
x−y
颗泡椒 - 有后缀出现在 x x 以后，吃
n2
颗泡椒 -
显然最后一种情况是不优的，那么保证所有单词出现在它的后缀以后即可。
将单词reverse建立一颗“后缀”trie树，即从根出发的任意一条向下路径为某个单词的后缀。按深度遍历保证了不会出现第三种情况。
剩下的就是贪心了，我们将trie树上代表单词终止点的结点取出来建一棵虚树，把每个点的子节点按子树大小排序，在dfs时先遍历子树size大的显然最优。
一道看似简单的题，实际上代码还是有点技巧的(时间标记，前驱等等，打WA了几次)。
代码
#include<bits/stdc++.h> #define RI register using namespace std; typedef long long ll; const int N=510050; int n,cnt,len,sz[N],bel[N]; int ch[N][26],ed[N],tim[N],bs;ll ans; vector<int>son[N]; char s[N]; inline bool cmp(const int&x,const int&y){ return sz[x]>sz[y];} inline void build(int u) { if(ed[u]) { son[bel[u]].push_back(u); bel[u]=u; } for(RI int i=0;i<26;++i) if(ch[u][i]){ bel[ch[u][i]]=bel[u]; build(ch[u][i]); } } inline void getsz(int u) { sz[u]=ed[u]; for(RI int i=son[u].size()-1;~i;--i){ getsz(son[u][i]); sz[u]+=sz[son[u][i]]; } sort(son[u].begin(),son[u].end(),cmp); } inline void dfs(int dep,int u,int pre) { if(ed[u]) { tim[u]=++bs; ans+= pre? tim[u]-tim[pre]:bs; pre=u; } for(RI int i=son[u].size()-1;~i;--i) dfs(dep+1,son[u][i],pre); } int main(){ RI int i,j,u,alp; scanf("%d",&n); for(i=1;i<=n;++i){ scanf("%s",s+1); len=strlen(s+1); for(u=0,j=len;j>=1;--j){ alp=s[j]-'a'; if(!ch[u][alp]) ch[u][alp]=++cnt; u=ch[u][alp]; } ed[u]=1; } build(0); getsz(0); dfs(0,0,0); printf("%lld\n",ans); }
T2:幸运数字(bzoj4568)
题解
关键词：线性基 倍增LCA
线性基是可以 O(logGi) O ( l o g G i ) 建立和合并的。所以倍增LCA中同样可以存储节点 i i 到第
2j
次幂个祖先的链上的线性基。熟悉线性基的话，很快就能码出来了。时间复杂度 O((n+m)log2Gi) O ( ( n + m ) l o g 2 G i ) 。
代码
#include<bits/stdc++.h> #define RI register #define gc getchar() #define si isdigit(c) using namespace std; typedef long long ll; const int N=2e4+100; int n,m,F[N][16],d[N]; int head[N],to[N<<2],nxt[N<<2],tot; ll bin[62],ans; struct P{ ll bs[62]; }f[N][16],tp,v[N]; char c; template<class T> inline void rd(T &x) { c=gc;x=0; for(;!si;c=gc); for(;si;c=gc) x=x*10+(c^48); } inline void lk(int u,int v) {to[++tot]=v;nxt[tot]=head[u];head[u]=tot;} inline P merge(P a,P b) { RI int i,j;ll res; for(i=60;~i;--i){ res=b.bs[i]; for(j=i;~j && res;--j) if(res&bin[j]){ if(!a.bs[j]) a.bs[j]=res; res^=a.bs[j]; } } return a; } void dfs(int x) { RI int i,j; for(i=1;bin[i]<=d[x];++i) F[x][i]=F[F[x][i-1]][i-1]; for(i=1;bin[i]<=d[x];++i) f[x][i]=merge(f[x][i-1],f[F[x][i-1]][i-1]); for(i=head[x];i;i=nxt[i]){ j=to[i];if(j==F[x][0]) continue; F[j][0]=x;f[j][0]=merge(v[x],v[j]); d[j]=d[x]+1;dfs(j); } } inline P get(int x,int y) { tp=v[x]; if(d[x]<d[y]) swap(x,y); RI int i,t=d[x]-d[y]; for(i=0;bin[i]<=t;++i) if(t&bin[i]){ tp=merge(tp,f[x][i]); x=F[x][i]; } if(x==y) return tp; for(i=14;~i;--i) if(F[x][i]!=F[y][i]){ tp=merge(tp,f[x][i]); tp=merge(tp,f[y][i]); x=F[x][i];y=F[y][i]; } tp=merge(tp,merge(f[x][0],f[y][0])); return tp; } int main(){ RI int i,j,k,x,y;ll val; bin[0]=1; for(i=1;i<=60;++i) bin[i]=bin[i-1]<<1; rd(n);rd(m); for(i=1;i<=n;++i){ rd(val);for(j=60;~j;--j) if(val&bin[j]) {v[i].bs[j]=val;break;} } for(i=1;i<n;++i){rd(x);rd(y);lk(x,y);lk(y,x);} dfs(1); for(;m;--m){ ans=0; rd(x);rd(y); get(x,y); for(i=60;~i;--i) ans=max(ans,ans^tp.bs[i]); printf("%lld\n",ans); } }
T3:萌萌哒(bzoj4569)
关键词：倍增优化并查集
传送门
T4:妖怪(bzoj4570)
关键词： 凸包
传送门
T5:美味(bzoj4571)
题解
关键词：主席树 拆位
因为每次只需要选择最优的一道菜，所以可以拆二进制位对所有菜的评价值建主席树， ai<105 a i < 10 5 ，建立范围为 [0,aimax] [ 0 , a i m a x ] 每次往最优的区间走查询这段区间中是否能取到0/1，从高位到低位逐位选择即可。
想到拆位就比较好做的一道题。时间复杂度 O(mlog2n) O ( m log 2 n ) 。
代码
#include<bits/stdc++.h> #define RI register #define gc getchar() #define si isdigit(c) #define mid (((l)+(r))>>1) using namespace std; const int N=2e5+10,mx=(1<<18)-1; int now,n,m,qb,qx,ql,qr,des,bin[25]; int rt[N],ls[N*20],rs[N*20],sz[N*20],tot; char c; inline void rd(int &x) { c=gc;x=0; for(;!si;c=gc); for(;si;c=gc) x=x*10+(c^48); } inline void build(int pre,int &nw,int l,int r,int pos) { nw=++tot;sz[nw]=sz[pre]+1; if(l==r) return; if(pos<=mid){ rs[nw]=rs[pre]; build(ls[pre],ls[nw],l,mid,pos); }else{ ls[nw]=ls[pre]; build(rs[pre],rs[nw],mid+1,r,pos); } } inline bool get(int pre,int nw,int l,int r,int L,int R) { if(L<=l && r<=R) return (sz[nw]-sz[pre]>0); bool re=false; if(L<=mid) re=get(ls[pre],ls[nw],l,mid,L,R); if(!re && R>mid) re=get(rs[pre],rs[nw],mid+1,r,L,R); return re; } int main(){ RI int i,j,l,r; bin[0]=1;for(i=1;i<=20;++i) bin[i]=bin[i-1]<<1; rd(n);rd(m); for(i=1;i<=n;++i){ rd(j); build(rt[i-1],rt[i],0,mx,j); } for(;m;--m){ rd(qb);rd(qx);rd(ql);rd(qr); des=mx&(~qb);now=0; for(i=17;~i;--i){ if(!(qb&bin[i])) now^=bin[i]; l=max(now-qx,0);r=(now|(bin[i]-1))-qx; if(r<0 || (!get(rt[ql-1],rt[qr],0,mx,l,r))) now^=bin[i]; } printf("%d\n",now^qb); } }
T6:围棋(bzoj4572)
关键词：轮廓线DP
传送门
总结
考点：
字符串 × × 1
倍增 × × 2
计算几何 × × 1
线性基/二进制拆位 × × 2
简单数据结构(简单主席树) × × 1
DP(轮廓线) × × 1倍增/二进制位出现频率较高？
数据结构较基础？
DP D P 普遍毒瘤？
算几年年出现？T1,2,5不能错
T3是一道不可多得的思维好题
T4算几还需要多加练习
T6轮廓线DP还不熟练，考试码不出来(似乎是道压轴题，雾)
思维题偏少
- 所有后缀在 1 1 ~
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/159350.html原文链接：https://javaforall.net
