191101-模拟测试11

T1 queue

题目描述

解析

一道智障题目（话说我没做出来，是不是更智障 ） 对于第一个规定，预处理出所有组的最大公约数，然后每次询问直接计算是不是最大公约数的因数即可 对于第二个规定，预处理出所有组中最小的值的平方根即可

题解

#include<bits/stdc++.h> using namespace std; long long a[1000009],d,x,b,k,minx,n,q,stnd; long long read() { int f=1; long long re=0; char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-') { f=-1; ch=getchar(); } for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0'; return re*f; } long long gcd(long long x,long long y) { if(y==0) return x; return gcd(y,x%y); } int main() { n=read(); minx=1e18; for(int i=1;i<=n;i++) { a[i]=read(); minx=min(minx,a[i]); } q=read(); d=a[1]; for(int i=2;i<=n;i++) d=gcd(d,a[i]); long long k=sqrt(minx); if(k*k==minx) stnd=k; else stnd=k+1; for(int i=1;i<=q;i++) { x=read(); b=read(); if(b==1) { if(d%x==0) printf("Yes\n"); else printf("No\n"); } if(b==2) { if(x>=stnd) printf("No\n"); else printf("Yes\n"); } } return 0; }

T2

题目描述

解析

题目描述一大堆，但其实题意非常简单，即统计与询问部分出现次数相同的元素种数相同的子串个数。（注意数组清空的技巧，不要全memset）

题解

#include<bits/stdc++.h>//正解 #define M 2009 using namespace std;//bj[]表示询问字串的出现次数相同的元素个数 int vis[M],bj[M],cnt[M],tot[M],num[M],ans,n,m,t,q,l,r,len; char s[M];//num[]表示查找子串的出现次数相同的元素个数 inline int read() { int f=1; int re=0; char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-') { f=-1; ch=getchar(); } for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0'; return re*f; } bool check() { bool pd=0; for(int i=1;i<=m;i++) if(num[tot[i]]!=bj[tot[i]]) { pd=1; break; } if(pd) return false; return true; } int main() { t=read(); while(t--) { n=read(); q=read(); scanf("%s",s+1); for(register int i=1;i<=q;i++) { for(int j=0;j<26;j++) { vis[j]=0; cnt[j]=0; } ans=0; m=0; l=read(); r=read(); len=r-l+1; for(register int j=l;j<=r;j++) { vis[s[j]-'a']++; bj[vis[s[j]-'a']-1]--; bj[vis[s[j]-'a']]++; } for(register int j=1;j<=n;j++) if(bj[j]) { num[j]=0;//对该次要使用的数组清空 tot[++m]=j; } for(register int j=1;j<=len;j++) { cnt[s[j]-'a']++; num[cnt[s[j]-'a']-1]--; num[cnt[s[j]-'a']]++; } if(check()) ans++; for(register int j=len+1;j<=n;j++) { cnt[s[j]-'a']++; num[cnt[s[j]-'a']-1]--; num[cnt[s[j]-'a']]++; cnt[s[j-len]-'a']--; num[cnt[s[j-len]-'a']+1]--; num[cnt[s[j-len]-'a']]++; if(check()) ans++; } printf("%d\n",ans); for(register int j=1;j<=m;j++) { bj[tot[j]]=0; tot[j]=0; } } } return 0; }

T3 forever

解析

简化题意

关于$f_i$：本质就是求以$i$为根的子树的$\sum a_i$。

关于路径：本质就是可以从$i$出发，到达任何不在以$i$为根的子树里的，权值比$i$小的节点。

题解

首先，我们考虑如何计算$f_i$ 这是一个经典的入门树形dp问题，直接按照含义转移即可 $f_i=a_i+\sum f_j$($j$是$i$的子节点)

然后，我们考虑如何来计算$g_i$ 由于按位或运算每一个二进制位是互不干扰的，所以我们可以对于每一个二进制位分别考虑答案是多少，再累加起来。

所以，我们现在来一位位考虑。

一个关于按位或的基础性质：如果这些数当中有一个在这一位上是1，那按位或起来的结果在这一位上就是1；否则是0。

首先，因为$g_i$是所有$f_j$值比$f_i$小的，且不在以$i$为根的子树中的fj的和。我们立马就会想到可以按照fi排序，那样我们按照$f_i$由小到大处理，统计到$f_i$的时候就可以统计出所有比$f_i$小的f，在当前处理的这一二进制位上1的个数cnt。

由于在$i$的子树中，所有节点的f值都小于$f_i$，所以我们这个cnt要减去以i为根的子树中（不包括i自己）在当前二进制位下1的个数$h_i$ 如果cnt大于0，我们就可以知道$g_i$在当前这一二进制位下是1。

至于$h_i$，使用类似于$f_i$的方法统计即可。

时间复杂度就是$O(nlogn$)

题解

#include<bits/stdc++.h> #pragma comment(linker, "/STACK:102400000,102400000") #define M 500009 using namespace std; long long cnt,in[M],out[M],n,imp,to[M*2],nxt[M*2],tot,first[M],ans[M],h[M][25],sum[M][25]; struct zb { long long x,num; }f[M]; bool comp(const zb &a,const zb &b) { return a.x<b.x; } long long read() { int f=1; long long re=0; char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-') { f=-1; ch=getchar(); } for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0'; return re*f; } void add(long long x,long long y) { nxt[++tot]=first[x]; first[x]=tot; to[tot]=y; } void dfs1(long long r,long long fa) { in[r]=++cnt; for(int i=first[r];i;i=nxt[i]) { long long v=to[i]; if(v==fa) continue; dfs1(v,r); f[r].x+=f[v].x; for(int k=0;k<=22;k++) h[r][k]+=(h[v][k]+((f[v].x&(1<<k))?1:0));//注意三目要在外面套一层括号 } out[r]=cnt; return; } int main() { int size=40<<20; freopen("forever.in","r",stdin); //freopen("forever.out","w",stdout); __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));//扩栈 long long x,y; n=read(); imp=read(); for(int i=1;i<=n-1;i++) { x=read(); y=read(); add(x,y); add(y,x); } for(int i=1;i<=n;i++) { f[i].x=read(); f[i].num=i; } dfs1(imp,0); sort(f+1,f+n+1,comp); for(int i=1;i<=n;i++) for(int j=0;j<=22;j++) sum[i][j]=sum[i-1][j]+(f[i].x&(1<<j)?1:0);//维护前缀和 for(int i=n;i>=1;i--) { int head=i; while(f[head].x==f[head-1].x) head--; for(int j=head;j<=i;j++) { int su=0; for(int z=0;z<=22;z++) { int cz=sum[head-1][z]-h[f[j].num][z]; su=(cz)?(su+(1<<z)):su; } ans[f[j].num]=su; } i=head; } for(int i=1;i<=n;i++) printf("%lld ",ans[i]); exit(0); }

$n^2$暴力代码

#include<bits/stdc++.h> #define M 500009 using namespace std; long long cnt,in[M],out[M],n,imp,to[M*2],nxt[M*2],tot,first[M],ans[M]; bool vis[M]; struct zb { long long x,num; }f[M]; bool comp(const zb &a,const zb &b) { return a.x<b.x; } long long read() { int f=1; long long re=0; char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-') { f=-1; ch=getchar(); } for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0'; return re*f; } void add(long long x,long long y) { nxt[++tot]=first[x]; first[x]=tot; to[tot]=y; } void dfs1(long long r,long long fa) { in[r]=++cnt; for(int i=first[r];i;i=nxt[i]) { long long v=to[i]; if(v==fa) continue; dfs1(v,r); f[r].x+=f[v].x; } out[r]=cnt; return; } int main() { //freopen("forever.in","r",stdin); //freopen("forever.out","w",stdout); long long x,y; n=read(); imp=read(); for(int i=1;i<=n-1;i++) { x=read(); y=read(); add(x,y); add(y,x); } for(int i=1;i<=n;i++) { f[i].x=read(); f[i].num=i; } dfs1(imp,0); sort(f+1,f+n+1,comp); for(int i=1;i<=n;i++) for(int j=1;j<i;j++) { if(in[f[j].num]>=in[f[i].num]&&in[f[j].num]<=out[f[i].num]) continue; if(f[j].x==f[i].x) continue; ans[f[i].num]|=f[j].x; } for(int i=1;i<=n;i++) printf("%lld ",ans[i]); return 0; }