csps-模拟7980题解

题面：https://www.cnblogs.com/Juve/articles/11712702.html

树：

我太sb了不知道DROT是1，还在sb找根

记录一个fa[]数组，表示x的祖先中第一个智商比x大的，用栈维护

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define re register

 using namespace std;

 const int MAXN=1e5+;

 int n,q,w[MAXN],sta[MAXN],top=,rb[MAXN],topp=,fa[MAXN],deep[MAXN];

 int to[MAXN<<],nxt[MAXN<<],pre[MAXN],cnt=;

 inline void add(re int u,re int v){

     ++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;

 }

 void dfs(int x,int f){

     deep[x]=deep[f]+;

     int res=;

     while(w[x]>w[sta[top]]){

         rb[++topp]=sta[top];

         --top,++res;

     }

     fa[x]=sta[top];

     sta[++top]=x;

     for(int i=pre[x];i;i=nxt[i]){

         int y=to[i];

         if(y==f) continue;

         dfs(y,x);

     }

     --top;

     while(res){

         sta[++top]=rb[topp--];

         --res;

     }

 }

 signed main(){

     scanf("%d%d",&n,&q);

     for(re int i=;i<=n;++i) scanf("%d",&w[i]);

     for(re int i=,u,v;i<n;++i){

         scanf("%d%d",&u,&v);

         add(u,v),add(v,u);

     }

     w[]=0x7fffffff;sta[++top]=;

     dfs(,);

     for(re int i=,u,v,c,res;i<=q;++i){

         scanf("%d%d%d",&u,&v,&c);

         res=;

         if(c<w[u]) c=w[u],++res;

         while(deep[u]>=deep[v]){

             if(c<w[u]) c=w[u],++res;

             u=fa[u];

         }

         if(c<w[v]) ++res;

         printf("%d\n",res);

     }

     return ;

 }

环：

我没脸抄的方程

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 const int MAXN=1e5+,mod=1e9+;

 int n,e,p[MAXN],q[MAXN],ans;

 int q_pow(int a,int b,int p){

     int res=;

     while(b){

         if(b&) res=res*a%p;

         a=a*a%p;

         b>>=;

     }

     return res;

 }

 signed main(){

     scanf("%lld%lld",&n,&e);

     for(int i=;i<=n;++i) q[i]=n-;

     for(int i=,u,v;i<=e;++i){

         scanf("%lld%lld",&u,&v);

         ++p[u],--q[u],--q[v];

     }

     ans=n*(n-)%mod*(n-)%mod*q_pow(,mod-,mod)%mod;

     for(int i=;i<=n;++i){

         int res=p[i]*(p[i]-)%mod*q_pow(,mod-,mod)%mod+p[i]*q[i]%mod*q_pow(,mod-,mod)%mod+q[i]*(q[i]-)%mod*q_pow(,mod-,mod)%mod;

         ans=(ans-res+mod)%mod;

     }

     printf("%lld\n",ans);

     return ;

 }

礼物：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 #define re register

 using namespace std;

 const int mod=1e9+,MAXN=1e7+,MAXM=1e7+;

 int n,a[MAXN],b[MAXN],ans;

 inline int q_pow(re int a,re int b,re int p){

     int res=;

     while(b){

         if(b&) res=res*a%p;

         a=a*a%p;

         b>>=;

     }

     return res;

 }

 int fac[MAXM<<],inv[MAXM<<];

 inline void get_c(re int N){

     fac[]=fac[]=inv[]=;

     for(int i=;i<=N;++i) fac[i]=fac[i-]*i%mod;

     inv[N]=q_pow(fac[N],mod-,mod);

     for(int i=N-;i>=;--i) inv[i]=inv[i+]*(i+)%mod;

 }

 inline int C(re int n,re int m){

     if(m>n) return ;

     if(n==m) return ;

     return fac[n]*inv[m]%mod*inv[n-m]%mod;

 }

 int maxx=,tong[MAXM<<],bas=1e7+;

 signed main(){

     scanf("%lld",&n);

     for(re int i=;i<=n;++i){

         scanf("%lld%lld",&a[i],&b[i]);

         maxx=max(maxx,a[i]+b[i]);

     }

     get_c(maxx*+);

     for(int i=;i<=n;++i){

         for(int t=-a[i];t<=b[i];++t) ans=(ans+tong[t+bas]*C(a[i]+b[i],a[i]+t)%mod)%mod;

         for(int t=-b[i];t<=a[i];++t) tong[t+bas]=(tong[t+bas]+C(a[i]+b[i],a[i]-t))%mod;

     }

     printf("%lld\n",*ans%mod);

     return ;

 }

最长不下降子序列：

n有1e12，但值域150，发现它是循环的，处理循环节即可

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 const int MAXN=1e6+;

 int n,t,a,b,c,d,p[MAXN],ans=,maxx=,cc[MAXN];

 int lowbit(int x){

     return x&(-x);

 }

 void update(int pos,int val){

     for(int i=pos;i<=maxx;i+=lowbit(i)){

         cc[i]=max(cc[i],val);

     }

 }

 int query(int pos){

     int res=;

     for(int i=pos;i>;i-=lowbit(i)){

         res=max(res,cc[i]);

     }

     return res;

 }

 int vis[MAXN];

 signed main(){

     scanf("%lld%lld%lld%lld%lld%lld",&n,&t,&a,&b,&c,&d);

     if(n<=){

         p[]=maxx=t;

         for(int i=;i<=n;++i){

             p[i]=(p[i-]*p[i-]%d*a%d+b*p[i-]%d+c%d)%d;

             maxx=max(p[i],maxx);

         }

         ++maxx;

         for(int i=;i<=n;++i){

             int res=query(p[i]+)+;

             update(p[i]+,res);

             ans=max(ans,res);

         }

         printf("%lld\n",ans);

         return ;

     }

     p[]=maxx=t;

     vis[t]=;

     int pos=,q=;//q:xunhuanchangdu

     for(int i=;i<=n;++i){

         p[i]=(p[i-]*p[i-]%d*a%d+b*p[i-]%d+c%d)%d;

         maxx=max(p[i],maxx);

         if(vis[p[i]]){

             pos=i;

             q=i-vis[p[i]];

             break;

         }

         vis[p[i]]=i;

     }

     ++maxx;

     if(!pos){

         //cout<<pos<<endl;

         for(int i=;i<=n;++i){

             int res=query(p[i]+)+;

             update(p[i]+,res);

             ans=max(ans,res);

         }

         printf("%lld\n",ans);

         return ;

     }else{

         int len=n-vis[p[pos]]+;

         int xh=len/q;//xunhuanjici

         int ys=len%q;//yuji

         for(int i=;i<=pos-;++i){

             int res=query(p[i]+)+;

             update(p[i]+,res);

             ans=max(ans,res);

         }

         for(int k=;k<=q;++k){

             for(int i=pos;i<=min(n,pos+q-);++i){

                 p[i]=p[i-q];

                 int res=query(p[i]+)+;

                 update(p[i]+,res);

                 int tmp=i-pos+;

                 res=res+xh-k-+(tmp<=ys);

                 ans=max(ans,res);

             }

             pos=pos+q;

         }

         printf("%lld\n",ans);

         return ;

     }

     return ;

 }

完全背包问题：

同余系最短路，咕咕

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define int long long

 using namespace std;

 const int MAXN=;

 int n,m,l,c,v[MAXN],pos,minn=0x3f3f3f3f3f3f3f3f;

 int dis[],cnt[];

 queue<int>q;

 bool in[];

 void spfa(){

     memset(dis,0x3f,sizeof(dis));

     memset(cnt,0x3f,sizeof(cnt));

     dis[]=cnt[]=;

     in[]=;

     q.push();

     while(!q.empty()){

         int x=q.front();

         q.pop();

         in[x]=;

         for(int i=;i<=n;++i){

             int y=(x+v[i])%minn;

             if(v[i]>=l&&cnt[x]>=c) break;

             if(dis[y]>dis[x]+v[i]){

                 dis[y]=dis[x]+v[i];

                 if(v[i]>=l) cnt[y]=cnt[x]+;

                 if(!in[y]) q.push(y),in[y]=;

             }else if(dis[y]==dis[x]+v[i]){

                 if(cnt[y]>cnt[x]+(v[i]>l)){

                     cnt[y]=cnt[x]+;

                     if(!in[y]) q.push(y),in[y]=;

                 }

             }

         }

     }

 }

 signed main(){

     scanf("%lld%lld",&n,&m);

     for(int i=;i<=n;++i){

         scanf("%lld",&v[i]);

         minn=min(minn,v[i]);

     }

     scanf("%lld%lld",&l,&c);

     sort(v+,v+n+);

     spfa();

     for(int i=,x;i<=m;++i){

         scanf("%lld",&x);

         if(dis[x%minn]<=x) puts("Yes");

         else puts("No");

     }

     return ;

 }

最近公共祖先：

想到了正解，但不会维护subtree(fa[x])-subtree(x)的信息

考虑dfs序，更新时减去子树x即可

重复染的点可以直接break

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 const int MAXN=1e5+;

 int n,m,w[MAXN];

 bool vis[MAXN];

 int to[MAXN<<],nxt[MAXN<<],pre[MAXN],cnt=;

 void add(int u,int v){

     ++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;

 }

 int in[MAXN],out[MAXN],fa[MAXN],dfn=;

 void dfs(int x){

     in[x]=++dfn;

     for(int i=pre[x];i;i=nxt[i]){

         int y=to[i];

         if(y==fa[x]) continue;

         fa[y]=x;

         dfs(y);

     }

     out[x]=dfn;

 }

 int tr[MAXN<<],laz[MAXN<<];

 void down(int k){

     tr[k<<]=max(tr[k<<],laz[k]);

     tr[k<<|]=max(tr[k<<|],laz[k]);

     laz[k<<]=max(laz[k<<],laz[k]);

     laz[k<<|]=max(laz[k<<|],laz[k]);

     laz[k]=;

 }

 void update(int k,int l,int r,int opl,int opr,int val){

     if(opl<=l&&r<=opr){

         tr[k]=max(tr[k],val);

         laz[k]=max(laz[k],val);

         return ;

     }

     if(laz[k]) down(k);

     int mid=(l+r)>>;

     if(opl<=mid) update(k<<,l,mid,opl,opr,val);

     if(opr>mid) update(k<<|,mid+,r,opl,opr,val);

     tr[k]=max(tr[k<<],tr[k<<|]);

 }

 int query(int k,int l,int r,int opt){

     if(l==r) return tr[k];

     if(laz[k]) down(k);

     int mid=(l+r)>>;

     if(opt<=mid) return query(k<<,l,mid,opt);

     else return query(k<<|,mid+,r,opt);

 }

 signed main(){

     scanf("%lld%lld",&n,&m);

     for(int i=;i<=n;++i){

         scanf("%lld",&w[i]);

     }

     for(int i=,u,v;i<n;++i){

         scanf("%lld%lld",&u,&v);

         add(u,v),add(v,u);

     }

     dfs(),vis[]=;

     for(int i=;i<=m;++i){

         char opt[];

         int v,ans;

         scanf("%s%lld",opt,&v);

         if(opt[]=='M'){

             update(,,n,in[v],out[v],w[v]);

             vis[v]=;

             while(vis[fa[v]]!=){

                 update(,,n,in[fa[v]],in[v]-,w[fa[v]]);

                 update(,,n,out[v]+,out[fa[v]],w[fa[v]]);

                 v=fa[v];

             }

         }else{

             ans=query(,,n,in[v]);

             if(!ans) ans=-;

             printf("%lld\n",ans);

         }

     }

     return ;

 }

巴特西

csps-模拟7980题解

最新文章

热门文章