这次终于考得稍微好一点了，因为题比较简单，但是没能A掉T1，T2和T3的暴力也没打好，希望下次加油。
传送门
其实是很简单的一道题，一看到题，我们很明显的可以想到 O ( n ² ) O(n²) O(n²)的暴力算法，每一次询问就枚举所有数，检验是否合法，由暴力我们可以想到优化，如情况 2 2 2，每一组马的数量都会有一个最小的阈值，我们开方向下取整找到这个值，取 m i n min min即可，而情况 1 1 1则必须满足每行马的个数 a a a为每一组马数的约数，即找所有数的最大公约数即可。
代码：
#include<bits/stdc++.h> #define ll long long #define db double #define re register #define cs const using namespace std; inline ll read() { ll x=0,f=1; char ch; while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return f*x; } ll n,w[700005],q,a,b,num,ans,minn=1e16,gcd=1e16; bool mark; int main() { freopen("queue.in","r",stdin); freopen("queue.out","w",stdout); n=read(); for(re ll i=1;i<=n;++i) { w[i]=read(); gcd=__gcd(gcd,w[i]); minn=min(minn,(long long)floor(sqrt(w[i]))); } q=read(); while(q--) { a=read(); b=read(); if(b==1) { mark=0; if(n>=9500) { if(gcd<a) puts("No"); else puts("Yes"); } else { for(re ll i=1;i<=n;++i) if(w[i]%a) { puts("No"); mark=1; break; } if(!mark) puts("Yes"); } } else { if(a>minn) puts("No"); else puts("Yes"); } }传送门
这道题，实质上就是是一个桶套桶，再加上滑动窗口的查询即可，而两渊相似的条件我们可以转化为出现的元素种类相同，每种出现的元素的个数相同，出现相同次数的元素的个数相同(读起来有点绕，多读几次就好了)，一个桶装每种元素出现个数，另一个桶装该元素出现次数为 i i i的次数， 而另一个很巧妙的一点是，用队列存储标本，每次比较，就从前出队，从后入队即可(pmh巨佬想出来的orz)
代码：
#include<bits/stdc++.h> #define ll long long #define db double #define re register #define cs const using namespace std; inline int read() { int x=0,f=1; char ch; while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return f*x; } int numm,l,r; int t,n,mm,cnt[5000],num[30],sample[5000]; char ch[3000]; queue<int>q; bool cmp() { for(re int i=1;i<=numm;++i) { int x=q.front(); q.pop(); q.push(x); if(sample[x]!=cnt[x]) return false; } return true; } int main() { t=read(); while(t--) { n=read(); mm=read(); scanf("%s",ch+1); while(mm--) { memset(sample,0,sizeof(sample)); while(!q.empty()) q.pop(); l=read(); r=read(); for(re int i=l;i<=r;++i) ++num[ch[i]-'a']; numm=0; for(re int i=0;i<26;++i) { if(!sample[num[i]]) { ++numm; q.push(num[i]); } ++sample[num[i]]; } memset(num,0,sizeof(num)); cnt[0]=26; r=r-l+1; for(re int i=1;i<=r;++i) { --cnt[num[ch[i]-'a']]; ++num[ch[i]-'a']; ++cnt[num[ch[i]-'a']]; } int ans=0; if(cmp()) ++ans; for(re int i=r+1;i<=n;++i) { --cnt[num[ch[i-r]-'a']]; --num[ch[i-r]-'a']; ++cnt[num[ch[i-r]-'a']]; --cnt[num[ch[i]-'a']]; ++num[ch[i]-'a']; ++cnt[num[ch[i]-'a']]; if(cmp()) ++ans; } printf("%d\n",ans); memset(num,0,sizeof(num)); memset(cnt,0,sizeof(cnt)); } } }传送门
这道题，有一个很明显的性质，就是父节点的魅力值一定大于子节点的魅力值，所以路径必定是从下往上，绝不会往下走，而他的终点也必须是小于他的，所以，我们可以用树上剖分来做，先dfs求出每个点的魅力值，按魅力值从小到大排序，之后开始查找，用线段树来维护即可。
代码：
#include<bits/stdc++.h> #define int long long #define db double #define re register #define cs const #define mid (l+r)/2 #define N 4500005 using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read() { int x=0,f=1; char ch; while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=nc(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=nc(); } return f*x; } int first[N],net[N],to[N],dep[N],top[N]; int size[N],f[N],son[N],fa[N],pos[N],idx[N],tree[N]; int tot,n,str,times,x,y; struct node { int id; int f,g; }www[N]; bool cmp1(cs node &x,cs node &y) { return x.f<y.f; } bool cmp2(cs node &x,cs node &y) { return x.id<y.id; } void add_point(int x) { pos[x]=++times; idx[times]=x; } void add_edge(int x,int y) { net[++tot]=first[x]; first[x]=tot; to[tot]=y; } void dfs1(int x) { size[x]=1; for(re int e=first[x];e;e=net[e]) { int v=to[e]; if(v!=fa[x]) { fa[v]=x; dep[v]=dep[x]+1; dfs1(v); size[x]+=size[v]; f[x]+=f[v]; if(size[son[x]]<size[v]) son[x]=v; } } www[x].f=f[x]; } void dfs2(int x) { if(son[x]) { add_point(son[x]); top[son[x]]=top[x]; dfs2(son[x]); } for(re int e=first[x];e;e=net[e]) { int v=to[e]; if(v!=fa[x]&&v!=son[x]) { add_point(v); top[v]=v; dfs2(v); } } } void update(int k,int l,int r,int x,int y) { if(l==r&&r==x) { tree[k]=y; return; } if(x<=mid) update(k<<1,l,mid,x,y); else update(k<<1|1,mid+1,r,x,y); tree[k]=tree[k<<1]|tree[k<<1|1]; } int query(int k,int l,int r,int x,int y) { if(x>r||y<l) return 0; if(x<=l&&r<=y) return tree[k]; if(y<=mid) return query(k<<1,l,mid,x,y); else { if(x>mid) return query(k<<1|1,mid+1,r,x,y); else return query(k<<1,l,mid,x,mid)|query(k<<1|1,mid+1,r,mid+1,y); } } signed main() { n=read(); str=read(); for(re int i=1;i<n;++i) { x=read(); y=read(); add_edge(x,y); add_edge(y,x); } for(re int i=1;i<=n;++i) f[i]=read(),www[i].id=i; top[str]=str; add_point(str); dfs1(str); dfs2(str); sort(www+1,www+1+n,cmp1); int last=1; for(re int i=1;i<=n;i=last) { www[i].g=query(1,1,n,1,pos[www[i].id]-1)|query(1,1,n,pos[www[i].id]+size[www[i].id],n); while(www[i].f==www[i+1].f) { ++i; www[i].g=query(1,1,n,1,pos[www[i].id]-1)|query(1,1,n,pos[www[i].id]+size[www[i].id],n); } for(re int j=last;j<=i;++j) update(1,1,n,pos[www[j].id],www[j].f); last=i+1; } sort(www+1,www+1+n,cmp2); for(re int i=1;i<=n;++i) printf("%lld ",www[i].g); }