CSP-S模拟测试69 题解

一如既往的垃圾，又回到了那个场场垫底的自己，明明考场上都想到正解了，但是就是拿不到分，可能是互奶把rp用光了吧以后一定加强训练代码能力。

T1：

考场上一直yy矩阵快速幂，虽然自己矩阵快速幂一点都不会还是硬着头皮yy，发现不可做之后并没有及时转化思路，但其实自己预处理的数组就是正解。

切记：不仅矩阵快速幂是log的，普通快速幂也是2333

然后这题其实很水啊，我们设$dp[i][j]$为前$i$列放$j$个棋子的方案数，然后枚举最后一列放多少个棋子就好了。

转移方程为$dp[i][j]=\sum{dp[i-1][j-k]*C_n^k}$,这样转移m列显然不行，考虑性质，第$i$列和第$i+kn$列的摆放方式一定相同，所以后面的组合数乘还有多少这样的列就好了即${C_n^k}^{\frac{m-i}{n}+1}$,但这样的复杂度是$O(n^4logn)$的，发现组合数可以预处理，于是去掉了log

 #include<bits/stdc++.h>

 using namespace std;

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

 #define int long long

 int n,m,c,fac[N],inv[N];

 int f[][*],pre[][*];

 int min(int a,int b){

     return a<b?a:b;

 }

 int qpow(int a,int b){

     int ans=;

     while(b){

         if(b&) ans=ans*a%mod;

         b>>=;

         a=a*a%mod;

     }

     return ans%mod;

 }

 int C(int a,int b){

     return fac[a]*inv[b]%mod*inv[a-b]%mod;

 }

 signed main(){

     fac[]=;

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

     inv[]=qpow(fac[],mod-);

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

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

     f[][]=;

     for(int i=;i<=n;++i) for(int j=;j<=max(n,c);++j) pre[i][j]=qpow(C(n,j),(m-i)/n+)%mod;

 //    for(int i=1;i<=n;++i,cout<<endl) for(int j=1;j<=n;++j) cout<<pre[i][j];

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

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

             for(int k=;k<=min(n,j);++k){

                 (f[i][j]+=f[i-][j-k]*pre[i][k]%mod)%=mod;

 //                cout<<pre[i][k]<<" "<<qpow(C(n,k),(m-i)/n+1)<<endl;

             }

         }

     }

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

 }

 /*

 2 3 1

 */

chess

T2：

考场上先想到单调栈，但是后来成功理解错题意对拍5w组WA0 2333。

如果理解对题意的话单调栈就挺明显了吧，肯定要找它前面第一各比他大的，那么答案一定在这段区间中，有一个比较明显的贪心就是，最优决策点一定是在，高度最小的那个点，稍想一下就可以明白。

所以在弹栈的时候每次更新，高度最小的下标即可。

对于输入量大的题，快读真的很有必要。

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e7+;

 pair<int,int > s[N];

 int a[N],sta[N],top;

 inline int min(int a,int b){return a<b?a:b;}

 inline int max(int a,int b){return a>b?a:b;}

 inline int read(){

     register int p=;register char ch=getchar();

     while(ch<''||ch>'') ch=getchar();

     while(ch>=''&&ch<='') p=(p<<)+(p<<)+ch-,ch=getchar();

     return p;

 }

 int main(){

     int n;

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

     for(register int i=;i^n;++i) a[i]=read();

 //    for(int i=1;i<=n;++i) s[i].first=a[i],s[i].second=i;

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

     register int ans=;

     for(register int i=;i^n;++i){

         s[i]=make_pair(a[i],i);

         while(a[i]>=a[sta[top]]){

             s[i]=min(s[i],s[sta[top--]]);

         }ans=max(ans,i-s[i].second+);

         sta[++top]=i;

     }

     printf("%d",ans);

 }

array

T3：

回滚莫队裸题。

就维护两个数组now1，now2，分别代表x向左向右能伸展的最长连续值域。

分别用x+1，x-1更新。还有就是更新一下这整段区间的左右端点以保证以后更新答案正确，中间的不用更新因为不会在插入了。

当这个区间左端点和上一个区间左端点不一样时，直接清空你now1，now2数组。

做完了之后觉的理解更加深入了。

放个回滚莫队讲解链接

 #include<bits/stdc++.h>

 using namespace std;

 const int N=1e6+;

 int blo[N];

 int sta1[N],sta2[N],top;

 struct node{

     int l,r,id,ld;

     bool friend operator < (node a,node b){

         return blo[a.l]==blo[b.l]?(a.r<b.r):blo[a.l]<blo[b.l];

     }

 }ask[N];

 int now1[N],now2[N],a[N],ans[N];

 int main(){

 //freopen("ants1.in","r",stdin);

 //freopen("my.out","w",stdout);

     int n,m;

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

     int size=sqrt(n);

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

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

         scanf("%d%d",&ask[i].l,&ask[i].r);

         ask[i].id=i;

         ask[i].ld=(ask[i].l-)/size+;

     }

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

         for(int j=size*(i-)+;j<=size*i;++j) blo[j]=i;

     }

     sort(ask+,ask+m+);

     int r=,l=,res=;

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

         if(ask[i].ld!=ask[i-].ld){

             for(int j=;j<=n;++j) now1[j]=now2[j]=;

             res=;

             l=r=ask[i].ld*size;

         }

         while(ask[i].r>r){

             ++r;

             int x=a[r];

             now1[x]=now1[x+]+;

             now2[x]=now2[x-]+;

             int kh=now1[x]+now2[x]-;

             now1[x-now2[x]+]=kh;

             now2[x+now1[x]-]=kh;

             res=max(kh,res);

         }

         top=;

         int tmp=res;

         for(int j=ask[i].l;j<=min(ask[i].r,l);++j){

             int x=a[j];

             now1[x]=now1[x+]+;

             now2[x]=now2[x-]+;

             int kh=now1[x]+now2[x]-;

             sta1[++top]=x-now2[x]+;

             sta2[top]=now1[x-now2[x]+];

             sta1[++top]=x+now1[x]-;

             sta2[top]=now2[x+now1[x]-];

             now1[x-now2[x]+]=kh;

             now2[x+now1[x]-]=kh;

             tmp=max(kh,tmp);

         }

         for(int j=top;j;--j){

             if(j&) now1[sta1[j]]=sta2[j];

             else now2[sta1[j]]=sta2[j];

         }

         for(int j=ask[i].l;j<=min(l,ask[i].r);++j){

             now1[a[j]]=;

             now2[a[j]]=;

         }

         ans[ask[i].id]=tmp;

     }

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

 }

ants

巴特西

CSP-S模拟测试69 题解

最新文章

热门文章