20191101 校内模拟

T1 曾经排队

挺水的。

询问 $1$：所有 $c_i$ 都是 $a$ 的倍数。记一下所有 $c_i$ 的最大公约数即可。询问 $2$：对于所有的 $c_i$ 都有 $a\le \lceil \frac{c_i}{a}\rceil$。记一下最小的 $c_i$ 判一下即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; namespace IO{ const int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline char gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } template<typename T> inline T Read(){ char c=gc();T x=0,f=1; while(!isdigit(c)) f^=(c=='-'),c=gc(); while( isdigit(c)) x=((x+(x<<2))<<1)+(c^48),c=gc(); return f?x:-x; } inline int gi() {return Read<int>();} inline ll gl() {return Read<ll >();} } using IO::gi; using IO::gl; const int N=7e5+5; int n,q,type; ll val,Gcd=0,mn=1e18; ll gcd(ll x,ll y) {return y?gcd(y,x%y):x;} void Min(ll &x,ll y) {if(x>y)x=y;} int main(){ n=gi(); for(int i=1;i<=n;++i){ ll x=gl(); Gcd=gcd(Gcd,x),Min(mn,x); } q=gi(); while(q--){ val=gl(),type=gi(); if(type==1) puts(Gcd%val?"No":"Yes"); else{ if(val>=1e9) puts("No"); else puts(mn<=val*val?"No":"Yes"); } } return 0; }

---

T2 元素世界

这就是一道模拟题。

考虑两个串相似的条件是，字母出现次数 的个数相同。

例如 abbcc 和 becbe，出现两次的字母都有 $2$ 个，出现一次的字母都只有 $1$ 个，因此它们相似。

于是根据这个模拟就可以了。

时间复杂度 $O(Tnq\times 26)$。

#include<bits/stdc++.h> using namespace std; const int N=2005; int T,n,q,l,r,len; int cnt1[26],cnt2[26],num1[N],num2[N]; char S[N]; vector<int>p; bool check(){ for(int i=0;i<p.size();++i) if(num1[p[i]]^num2[p[i]]) return false; return true; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d%s",&n,&q,S+1); while(q--){ scanf("%d%d",&l,&r),p.clear(),len=r-l+1; for(int i=l;i<=r;++i) cnt1[S[i]-'a']++,cnt2[S[i-l+1]-'a']++; for(int i=0;i<26;++i) num1[cnt1[i]]++,num2[cnt2[i]]++; for(int i=0;i<26;++i) if(cnt1[i]) p.push_back(cnt1[i]); int ans=check(); for(int i=r-l+2;i<=n;++i){ int &L=cnt2[S[i-len]-'a'],&R=cnt2[S[i]-'a']; num2[L--]--,num2[L]++,num2[R++]--,num2[R]++,ans+=check(); } printf("%d\n",ans); for(int i=0;i<26;++i) num1[cnt1[i]]=num2[cnt2[i]]=0,cnt1[i]=0,cnt2[i]=0; } } return 0; }

---

T3 层层回忆

首先不难发现的是每个点的 $f$ 值是子树的 $a_i$ 和。

由于 $a_i$ 是正整数，可以发现，父亲节点的 $f$ 值严格大于子树中任意节点的 $f$ 值。

所以肯定不能往子树走，而往父亲走的话已经有了最大值的限制，我们只需保证当前点不是路径的最小值即可。

那么问题就转换成了，对于点 $x$，查询 $[1,{\mathrm{i}\mathrm{n}}_x-1]$ 以及 $[{\mathrm{o}\mathrm{u}\mathrm{t}}_x+1,n]$ 中 $f$ 值 $<f_x$ 的或和。

可以对 $f$ 从小到大排序，按照顺序加到权值线段树上，然后每个点查一查即可。

注意一下 $f$ 相等的$“$去重$”$。

时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h> using namespace std; namespace IO{ const int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline char gc(){ return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } template<typename T> inline T Read(){ char c=gc();T x=0,f=1; while(!isdigit(c)) f^=(c=='-'),c=gc(); while( isdigit(c)) x=((x+(x<<2))<<1)+(c^48),c=gc(); return f?x:-x; } inline int gi() {return Read<int>();} } using IO::gi; const int N=5e5+5; int n,rt,mx; int t,first[N],v[N<<1],nxt[N<<1]; void add(int x,int y){ nxt[++t]=first[x],first[x]=t,v[t]=y; } int tot,f[N],in[N],out[N],ans[N]; void dfs(int x,int fa){ in[x]=++tot; for(int i=first[x];i;i=nxt[i]){ int to=v[i]; if(to==fa) continue; dfs(to,x),f[x]+=f[to]; } out[x]=tot; } namespace SGT{ int Or[N<<2]; #define mid ((l+r)>>1) void Modify(int root,int l,int r,int pos,int val){ if(l==r) {Or[root]|=val;return;} if(pos<=mid) Modify(root<<1,l,mid,pos,val); else Modify(root<<1|1,mid+1,r,pos,val); Or[root]=Or[root<<1]|Or[root<<1|1]; } int Query(int root,int l,int r,int x,int y){ if(l>=x&&r<=y) return Or[root]; if(y<=mid) return Query(root<<1,l,mid,x,y); if(x> mid) return Query(root<<1|1,mid+1,r,x,y); return Query(root<<1,l,mid,x,y)|Query(root<<1|1,mid+1,r,x,y); } #undef mid } vector<int>Sort[3000005]; void Max(int &x,int y) {if(x<y)x=y;} int main(){ n=gi(),rt=gi(); for(int i=1,x,y;i<n;++i){ x=gi(),y=gi(),add(x,y),add(y,x); } for(int i=1;i<=n;++i) f[i]=gi(); dfs(rt,0); for(int i=1;i<=n;++i) Sort[f[i]].push_back(i),Max(mx,f[i]); for(int i=1;i<=mx;++i){ for(int j=0;j<Sort[i].size();++j){ int x=Sort[i][j]; if(in[x]>1) ans[x]|=SGT::Query(1,1,n,1,in[x]-1); if(out[x]<n) ans[x]|=SGT::Query(1,1,n,out[x]+1,n); } for(int j=0;j<Sort[i].size();++j){ int x=Sort[i][j]; SGT::Modify(1,1,n,in[x],f[x]); } } for(int i=1;i<=n;++i) printf("%d ",ans[i]); return 0; }