【CSP-S 2019模拟】题解

T1：

$O(n^2)$枚举后用逆元算第三个即可 用$hashtable$存即可 脑残写了个奇奇妙妙的$n^{2}log$$wa3$个$T3$个

#include<bits/stdc++.h> using namespace std; #define cs const #define re register #define pb push_back #define pii pair<int,int> #define fi first #define se second #define bg begin #define ll long long cs int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0;bool f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;} template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;} int mod; inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);} inline void Add(int &a,int b){a+=b-mod,a+=a>>31&mod;} inline int dec(int a,int b){a-=b;return a+(a>>31&mod);} inline void Dec(int &a,int b){a-=b,a+=a>>31&mod;} inline int mul(int a,int b){static ll r;r=1ll*a*b;return r>=mod?r%mod:r;} inline void Mul(int &a,int b){static ll r;r=1ll*a*b;a=r>=mod?r%mod:r;} inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;} inline int Inv(int x){return ksm(x,mod-2);} struct Map{ static cs int Mod=2718343; int key[Mod],val[Mod]; Map(){memset(key,-1,sizeof(key));} inline int nxt(int p){ return p+1==Mod?0:p+1; } inline void insert(int k){ int p=k%Mod; for(;~key[p]&&key[p]!=k;p=nxt(p)); key[p]=k,val[p]++; } inline int find(int k){ int p=k%Mod; for(;~key[p]&&key[p]!=k;p=nxt(p)); if(key[p]!=k)return 0; return val[p]; } }mp,mp2; cs int N=2505; int n,a[N],inv[N],cnt,ans; int main(){ #ifdef Stargazer freopen("lx.in","r",stdin); #endif n=read(),mod=read(); for(int i=1;i<=n;i++){ a[i]=read(); } sort(a+1,a+n+1); for(int i=1;i<=n;i++){ mp2.insert(a[i]); } cnt=unique(a+1,a+n+1)-a-1; mp.insert(a[1]%mod); for(int i=1;i<=cnt;i++)inv[i]=Inv(a[i]%mod); for(int i=2;i<=cnt;i++){ for(int j=i+1;j<=cnt;j++){ int iv=mul(inv[i],inv[j]); ans+=mp.find(iv); } mp.insert(a[i]%mod); } for(int i=1;i<=cnt;i++)if(mp2.find(a[i])>1){ int iv=mul(inv[i],inv[i]); ans+=mp.find(iv); if(mul(mul(a[i],a[i]),a[i])==1)ans--; } for(int i=1;i<=cnt;i++){ if(mp2.find(a[i])>=3&&mul(mul(a[i],a[i]),a[i])==1)ans++; } cout<<ans;return 0; }

T2：

发现大概就是一个有限制的二维偏序 从大往小排序后 $f[i][j]$表示前$i$个放了$j$个的最长长度 枚举上一个更新即可 发现第二维没有用处 可以把前面的答案离线加进去线段树维护$max$即可

#include<bits/stdc++.h> using namespace std; #define cs const #define re register #define pb push_back #define pii pair<int,int> #define fi first #define se second #define bg begin #define ll long long cs int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0;bool f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;} template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;} cs int N=100005; int n,m,t[N]; struct node{ int w,v; friend inline bool operator <(cs node &a,cs node &b){ return a.w==b.w?a.v>b.v:a.w>b.w; } }p[N]; namespace Seg{ int mx[N<<2]; #define lc (u<<1) #define rc ((u<<1)|1) #define mid ((l+r)>>1) void clear(int u,int l,int r){ mx[u]=0;if(l==r)return; clear(lc,l,mid),clear(rc,mid+1,r); } inline void pushup(int u){ mx[u]=max(mx[lc],mx[rc]); } void update(int u,int l,int r,int p,int k){ if(l==r){chemx(mx[u],k);return;} if(p<=mid)update(lc,l,mid,p,k); else update(rc,mid+1,r,p,k); pushup(u); } int query(int u,int l,int r,int st,int des){ if(st<=l&&r<=des)return mx[u]; int res=0; if(st<=mid)chemx(res,query(lc,l,mid,st,des)); if(mid<des)chemx(res,query(rc,mid+1,r,st,des)); return res; } #undef lc #undef rc #undef mid } vector<int>upd[N]; int f[N],b[N],cnt; inline void solve(){ n=read(); for(int i=1;i<=n;i++)p[i].w=read(),p[i].v=read(),b[i]=p[i].v; sort(p+1,p+n+1); sort(b+1,b+n+1),cnt=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++)p[i].v=lower_bound(b+1,b+cnt+1,p[i].v)-b; m=read(); for(int i=1;i<=m;i++)t[i]=read(); sort(t+1,t+m+1); reverse(t+1,t+m+1); for(int pos=0,i=1;i<=n;i++){ while(pos<m&&p[i].w<=t[pos+1]){ for(int j=0;j<upd[pos].size();j++) Seg::update(1,1,cnt,p[upd[pos][j]].v,f[upd[pos][j]]); pos++; } if(p[i].w<=t[pos]){ f[i]=Seg::query(1,1,cnt,p[i].v,cnt)+1; if(f[i]<pos)Seg::update(1,1,cnt,p[i].v,f[i]); else upd[f[i]+1].pb(i); } } int res=0; for(int i=1;i<=n;i++)chemx(res,f[i]); for(int i=1;i<=n+1;i++)upd[i].clear(),f[i]=0; Seg::clear(1,1,n); cout<<res<<'\n'; } int main(){ int T=read(); while(T--)solve(); return 0; }

T3：

想到了$dp$，但是在算重的地方脑残了，只需要强制当前新加进去的子树的根的编号最小即可

其实顺着考试想的算重可以枚举子树个数$k$ 最后只需要除以$k!$实际上也是最终答案

然后就可以推出$zy$的$Exp$做法了

#include<bits/stdc++.h> using namespace std; #define cs const #define re register #define pb push_back #define pii pair<int,int> #define fi first #define se second #define bg begin #define ll long long cs int RLEN=1<<20|1; inline char gc(){ static char ibuf[RLEN],*ib,*ob; (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob)?EOF:*ib++; } inline int read(){ char ch=gc(); int res=0;bool f=1; while(!isdigit(ch))f^=ch=='-',ch=gc(); while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc(); return f?res:-res; } template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;} template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;} cs int mod=998244353; inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);} inline void Add(int &a,int b){a+=b-mod,a+=a>>31&mod;} inline int dec(int a,int b){a-=b;return a+(a>>31&mod);} inline void Dec(int &a,int b){a-=b,a+=a>>31&mod;} inline int mul(int a,int b){static ll r;r=1ll*a*b;return r>=mod?r%mod:r;} inline void Mul(int &a,int b){static ll r;r=1ll*a*b;a=r>=mod?r%mod:r;} inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;} inline int Inv(int x){return ksm(x,mod-2);} cs int N=505; int fac[N],ifac[N]; int f[N][N]; int wr[N],k,n,L,R; inline void init(){ fac[0]=ifac[0]=1; for(int i=1;i<N;i++)fac[i]=mul(fac[i-1],i); ifac[N-1]=Inv(fac[N-1]); for(int i=N-2;i;i--)ifac[i]=mul(ifac[i+1],i+1); } inline int C(int n,int m){return n<m?0:mul(fac[n],mul(ifac[m],ifac[n-m]));} int main(){ #ifdef Stargazer freopen("lx.cpp","r",stdin); #endif init(); n=read(),k=read(); for(int i=1;i<=k;i++)wr[read()]=1; L=read(),R=read(); for(int i=1;i<=n;i++)f[i][1]=1; for(int j=2;j<=n;j++){ for(int i=1;i<=n;i++) for(int k=1;k<=i-1;k++) Add(f[j][i],mul(f[j][i-k],mul(f[j-1][k],C(i-2,k-1)))); for(int i=1;i<=n;i++)if(wr[i])f[j][i]=0; } for(int i=L;i<=R;i++){ cout<<dec(f[i][n],f[i-1][n])<<" "; } }

总结：

代码能力稀撇 脑子还蠢 情况总是考虑不全

这样下去可能真的$noip$就退役了