20191102 校内模拟

T1 极好的问题

不是很难的题，考场上抽了，有一个细节挂了只有 $80$ 分。

由于要求本质不同的三元组 $(x,y,z)$ 数量，我分了三种情况：

$(a,a,a)$。直接判一下即可。$(a,a,b)$。$O(n^2)$ 枚举 $a,b$ 判断即可。$(a,b,c)$。我的做法是枚举 $b,c$，把 $b$ 之前的 $a$ 的逆元加进 map 里，然后直接询问就可以了。

考场上由于怕 map 跑的太慢，就手写了哈希表。

#include<bits/stdc++.h> using namespace std; const int N=2505; int n,P,a[N],b[N],num[N]; int add(int x,int y) {return x+y>=P?x+y-P:x+y;} int dec(int x,int y) {return x-y< 0?x-y+P:x-y;} int mul(int x,int y) {return 1ll*x*y>=P?1ll*x*y%P:x*y;} int power(int a,int b){ int ans=1; for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a); return ans; } int Inv(int x) {return power(x,P-2);} void Max(int &x,int y) {if(x<y)x=y;} void Min(int &x,int y) {if(x>y)x=y;} namespace Hash_Table{ const int N=1e6+10,mod=1e6+3; int t,first[N],v[N],w[N],nxt[N]; void add(int x,int y){ nxt[++t]=first[x],first[x]=t,v[t]=y,w[t]=1; } void ADD(int x,int val){ int pos=x%mod; for(int i=first[pos];i;i=nxt[i]) if(v[i]==x) {w[i]+=val;return;} add(pos,x); } int Query(int x){ int pos=x%mod; for(int i=first[pos];i;i=nxt[i]) if(v[i]==x) return w[i]; return 0; } } using namespace Hash_Table; int m,tot; int main(){ scanf("%d%d",&n,&P); for(int i=1,x;i<=n;++i){ scanf("%d",&x); if(x%P) a[++tot]=x; } sort(a+1,a+tot+1); for(int i=1;i<=tot;++i){ a[i]==a[i-1]?num[m]++:(b[++m]=a[i],num[m]=1); } int ans=0; for(int i=1;i<=m;++i){ for(int j=i+1;j<=m;++j) ans+=Query(mul(b[i],b[j])); ADD(Inv(b[i]%P),1); } for(int i=1;i<=m;++i){ if(num[i]>=3) ans+=(power(b[i],3)==1); for(int j=1;j<=m;++j) if(i!=j&&num[i]>=2) ans+=(mul(mul(b[i],b[i]),b[j])==1); } printf("%d\n",ans); return 0; }

---

T2 背包问题

按照 $w$ 排序之后，这就有点像 LIS 问题了，但是有背包容量的限制。

一个显然的贪心是，如果我们选了 $k$ 个物品，那么用容量最大的 $k$ 个背包会最优。

那么按照背包容量从大到小排序，物品按照 $w$ 从大到小排序。由于还有 $v$ 的限制，我们需要树状数组来存答案。每次更新答案的时候在树状数组里查 $\ge v$ 部分的最大答案，判断背包的限制然后更新答案即可。

时间复杂度 $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 in() {return Read<int>();} } using IO::in; const int N=1e5+5; int n,m,k,bag[N],d[N]; struct node{int w,v;}p[N]; bool operator<(const node &p,const node &q) {return (p.w==q.w)?p.v>q.v:p.w>q.w;} void discrete(){ sort(d+1,d+n+1),k=unique(d+1,d+n+1)-d-1; for(int i=1;i<=n;++i) p[i].v=lower_bound(d+1,d+k+1,p[i].v)-d; } void Max(int &x,int y) {if(x<y)x=y;} void Min(int &x,int y) {if(x>y)x=y;} namespace BIT{ int bit[N]; #define lowbit(x) (x&(-x)) void Clear() {memset(bit,0,sizeof(bit));} void add(int x,int val) {for(;x;x-=lowbit(x))Max(bit[x],val);} int Query(int x,int ans=0) {for(;x<=k;x+=lowbit(x))Max(ans,bit[x]);return ans;} #undef lowbit } int main(){ int T=in(); while(T--){ n=in(); for(int i=1;i<=n;++i){ p[i].w=in(),p[i].v=in(),d[i]=p[i].v; } sort(p+1,p+n+1),discrete(); m=in(); for(int i=1;i<=m;++i) bag[i]=in(); sort(bag+1,bag+m+1,greater<int>()); int pos=0,ans=0; BIT::Clear(); for(int i=1;i<=n;++i){ while(pos<m&&bag[pos+1]>=p[i].w) ++pos; int now=min(BIT::Query(p[i].v)+1,pos); BIT::add(p[i].v,now),Max(ans,now); } printf("%d\n",ans); } return 0; }

---

T3 子树问题

计数类 $dp$ 题。永远都想不到。。

设 $f[i][j]$ 表示有 $i$ 节点的深度不超过 $d$ 的有根树的数量。先不考虑限制，则：

$$f[i][j]=\sum _{k=1}^{i-1}f[i-k][j]\times f[k][j-1]\times \left(\genfrac{}{}{0ex}{}{i-2}{j-1}\right)$$

后面乘的组合数就是给这些点分配标号。

对于数量限制的点，直接把 $f[i][j]$ 置成 $0$ 即可。

最后 $d$ 的答案就是 $f[n][d]-f[n][d-1]$。

时间复杂度 $O(n^3)$。

#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 in() {return Read<int>();} } using IO::in; const int N=505,P=998244353; int n,k,ban[N],L,R,C[N][N],f[N][N]; int add(int x,int y) {return x+y>=P?x+y-P:x+y;} int dec(int x,int y) {return x-y< 0?x-y+P:x-y;} int mul(int x,int y) {return 1ll*x*y>=P?1ll*x*y%P:x*y;} void prework(){ C[0][0]=1; for(int i=1;i<=n;++i){ C[i][0]=C[i][i]=1; for(int j=1;j<i;++j) C[i][j]=add(C[i-1][j],C[i-1][j-1]); } } int main(){ n=in(),k=in(),prework(); for(int i=1,x;i<=k;++i) ban[in()]=1; L=in(),R=in(); f[1][1]=ban[1]?0:1; for(int d=2;d<=n;++d){ for(int i=1;i<=n;++i){ if(i==1) {f[i][d]=1;continue;} for(int j=1;j<i;++j) f[i][d]=add(f[i][d],mul(mul(f[i-j][d],f[j][d-1]),C[i-2][j-1])); } for(int i=1;i<=n;++i) if(ban[i]) f[i][d]=0; } for(int i=L;i<=R;++i) printf("%d ",dec(f[n][i],f[n][i-1])); return 0; }