csps模拟93序列，二叉搜索树，走路题解

题面：

模拟93考得并不理想，二维偏序没看出来，然而看出来了也不会打

序列：

对a，b数列求前缀和，那么题意转化为了满足$suma[i]>=suma[j]$且$sumb[i]>=sumb[j]$的最大$i-j+1$值

那么就是二维偏序，那么按a排序，把b塞到树状数组里

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<cstdlib>

 #include<ctime>

 #define int long long

 using namespace std;

 const int MAXN=5e5+;

 int n,ans=,sta[MAXN],top=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){

         if(ch=='-') f=-;

         ch=getchar();

     }

     while(ch>=''&&ch<=''){

         x=(x<<)+(x<<)+ch-'';

         ch=getchar();

     }

     return x*f;

 }

 struct node{

     int a,b,id;

     friend bool operator < (node p,node q){

         return p.a==q.a?p.b<q.b:p.a<q.a;

     }

 }val[MAXN];

 int lowbit(int x){

     return x&-x;

 }

 int c[MAXN];

 void update(int pos,int val){

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

         c[i]=min(c[i],val);

     }

 }

 int query(int pos){

     int res=0x3f3f3f3f3f3f3f3f;

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

         res=min(res,c[i]);

     }

     return res;

 }

 signed main(){

     n=read();

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

         val[i].a=read();

         val[i].a+=val[i-].a;

         val[i].id=i;

     }

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

         val[i].b=read();

         val[i].b+=val[i-].b;

         sta[++top]=val[i].b;

     }

     sort(val+,val+n+);

     sort(sta+,sta+top+);

     top=unique(sta+,sta+top+)-sta-;

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

         val[i].b=lower_bound(sta+,sta+top+,val[i].b)-sta;

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

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

         int res=query(val[i].b);

         ans=max(ans,val[i].id-res);

         update(val[i].b,val[i].id);

     }

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

     return ;

 }

二叉搜索树：

区间dp，设f[i,j]表示考虑区间[i,j]的贡献，则f[i,j]=min(f[i,k-1]+f[k+1,j]+a[i,j])

然后发现k有决策单调性，所以我们记录一个dp数组，dp[i,j]表示f[i,j]是由那一个k转移而来，然后对于每一个i,j，枚举k的范围就变成了dp[i+1,j]到dp[i,j-1]

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define int long long

 using namespace std;

 const int MAXN=;

 int n,ans=,sum[MAXN],f[MAXN][MAXN],dp[MAXN][MAXN];

 struct node{

     int x,id;

     friend bool operator < (node p,node q){

         return p.x==q.x?p.id>q.id:p.x>q.x;

     }

 }a[MAXN];

 int min(int p,int q){

     return p<q?p:q;

 }

 signed main(){

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

     scanf("%lld",&n);

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

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

         a[i].id=i;

         sum[i]=sum[i-]+a[i].x;

         f[i][i]=a[i].x;

         dp[i][i]=i;

     }

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

         for(int j=;j<i;++j) f[i][j]=;

     }

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

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

             int j=i+l-;

             for(int k=dp[i][j-];k<=dp[i+][j];++k){

                 if(f[i][j]>=f[i][k-]+f[k+][j]+sum[j]-sum[i-]){

                     f[i][j]=f[i][k-]+f[k+][j]+sum[j]-sum[i-];

                     dp[i][j]=k;

                 }

             }

         }

     }

     printf("%lld\n",f[][n]);

     return ;

 }

走路：分治消元

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 const int MAXM=1e5+,mod=;

 int n,m,du[],cnt[][],inv[MAXM],a[][],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;

 }

 void solve(int l,int r){

     if(l==r){

         ans[l]=(a[][n+]+mod)%mod;

         return ;

     }

     int t[][];

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

         for(int j=;j<=n+;++j)

             t[i][j]=a[i][j];

     }

     int mid=(l+r)>>;

     for(int x=mid+;x<=r;++x){

         int invv=q_pow(a[x][x],mod-,mod);

         for(int i=;i<=n+;++i) (a[x][i]*=invv)%=mod;

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

             if(i==x) continue;

             invv=a[i][x];

             for(int j=l;j<=r;++j){

                 a[i][j]=(a[i][j]-a[x][j]*invv+mod)%mod;

             }

             a[i][n+]=(a[i][n+]-a[x][n+]*invv+mod)%mod;

         }

     }

     solve(l,mid);

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

         for(int j=;j<=n+;++j)

             a[i][j]=t[i][j];

     }

     for(int x=l;x<=mid;++x){

         int invv=q_pow(a[x][x],mod-,mod);

         for(int i=;i<=n+;++i) (a[x][i]*=invv)%=mod;

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

             if(i==x) continue;

             invv=a[i][x];

             for(int j=l;j<=r;++j){

                 a[i][j]=(a[i][j]-a[x][j]*invv%mod+mod)%mod;

             }

             a[i][n+]=(a[i][n+]-a[x][n+]*invv%mod+mod)%mod;

         }

     }

     solve(mid+,r);

 }

 signed main(){

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

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

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

         ++du[u],++cnt[u][v];

     }

     for(int i=;i<=m;++i) inv[i]=q_pow(i,mod-,mod);

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

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

             a[i][j]=cnt[i][j]*q_pow(du[i],mod-,mod)%mod;

         }

         a[i][n+]=-;

         --a[i][i];

     }

     solve(,n);

     for(int i=;i<=n;++i) printf("%lld\n",ans[i]);

     return ;

 }

巴特西

csps模拟93序列，二叉搜索树，走路题解

最新文章

热门文章