NOIP模拟测试13

考得还算可以，T3还有提升空间（没看清题&&样例没过拿了4分）。

期望得分：80+40+0=120

实际得分：80+85+4=169

一脸黑线。。。。。是数据比较水的原因，T2分都比较高

反正先把暴力分拿满就对了。

T1 矩阵游戏

水题吗？我觉得不是，n，m 1e9！ 23333不过好像沿用二营长的思路也可以过，总而言之是我太菜了，菜是原罪嘛。

首先易推出式子 ans=ΣH[i]*ΣL[j]*(m*(i-1)+j) (1<=i<=n,1<=j<=m)

考虑展开化简 ans=ΣH[i]*ΣL[j]*m*(i-1)+L[j]*j

发现ΣL[j]*j可以处理出来

而ΣL[j]*m*(i-1)可以递推出来

然后就。。。AC了

 #include<bits/stdc++.h>

 #define MAXN 1000005

 #define int long long

 using namespace std;

 const int mod=;

 int h[MAXN],l[MAXN];

 signed main()

 {

     int n,m,k,tot=,base=,now=,ans=;

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

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

     for(int i=;i<=m;i++)l[i]=;

     while(k--)

     {

         char opt;cin>>opt;

         int x,y;

         scanf("%lld%lld",&x,&y);

         if(opt=='R')(h[x]*=y)%=mod;

         else (l[x]*=y)%=mod;

     }

     for(int i=;i<=m;i++)(tot+=l[i]*i)%=mod,(base+=l[i])%=mod;

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

     {

         (ans+=h[i]*(now+tot)%mod)%=mod;

         (now+=base*m)%=mod;

     }

     cout<<ans<<endl;

     return ;

 }

AC代码

T2 跳房子

我还没A，85分暴力很不错。

主要是如何优化模拟blablabla

T3 优美序列

ST表可以维护权值，分块是优化的极好方式。

看题目的时候一定要认真。

这个题首先可以用ST表维护，即对于当前区间求出最大最小值，在利用维护的权值ST表搞出目标位置，利用目标位置更新当前max和min

但这种做法会被卡，可以用分块优化。

引理：

对于一个区间R，它的子区间的最优答案一定是它的最优答案的子区间。

利用这个我们可以先分块，（设块数为k）再处理出这k^2个块之间的答案，跑的飞快。

 #include<bits/stdc++.h>

 #define MAXN 100005

 #define min(a,b) ((a<b)?(a):(b))

 #define max(a,b) ((a>b)?(a):(b))

 using namespace std;

 int mn[][MAXN],mx[][MAXN],mh[MAXN],a[MAXN],n,mnpos[][MAXN],mxpos[][MAXN],ans1[][],ans2[][],t;

 int bl[MAXN];

 vector<int>ld;

 void pre()

 {

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

         for(int j=;j>=;j--)

             if(i>=(<<j))

             {

                 mh[i]=j;

                 break;

             }

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

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

         {

             mn[i][j]=min(mn[i-][j],mn[i-][j+(<<(i-))]);

             mx[i][j]=max(mx[i-][j],mx[i-][j+(<<(i-))]);

             mnpos[i][j]=min(mnpos[i-][j],mnpos[i-][j+(<<(i-))]);

             mxpos[i][j]=max(mxpos[i-][j],mxpos[i-][j+(<<(i-))]);

         }

     return ;

 }

 inline int Rd()

 {

     int x=;char c=getchar();

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

     while(c>=''&&c<=''){x=x*+c-;c=getchar();}

     return x;

 }

 inline int gmax(int l,int r)

 {

     return max(mx[mh[r-l+]][l],mx[mh[r-l+]][r-(<<mh[r-l+])+]);

 }

 inline int gmin(int l,int r)

 {

     return min(mn[mh[r-l+]][l],mn[mh[r-l+]][r-(<<mh[r-l+])+]);

 }

 inline int qmax(int l,int r)

 {

     return max(mxpos[mh[r-l+]][l],mxpos[mh[r-l+]][r-(<<mh[r-l+])+]);

 }

 inline int qmin(int l,int r)

 {

     return min(mnpos[mh[r-l+]][l],mnpos[mh[r-l+]][r-(<<mh[r-l+])+]);

 }

 int main()

 {

     n=Rd();

     t=pow(n,0.7);

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

     {

         a[i]=Rd();

         mn[][i]=mx[][i]=a[i];

         mnpos[][a[i]]=mxpos[][a[i]]=i;

     }

     int p=,tot=;

     while(p<n)

     {

         ld.push_back(p+);

         for(int i=;i<=t;i++)bl[p+i]=tot;

         p+=t;

         tot++;

     }

     pre();

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

     memset(ans2,-0x3f,sizeof(ans2));

     for(int i=;i<ld.size();i++)

         for(int j=i;j<ld.size();j++)

         {

             int l,r;

             l=ld[i];

             r=ld[j];

             int nowmin=gmin(l,r),nowmax=gmax(l,r);

             int pl=qmin(nowmin,nowmax),pr=qmax(nowmin,nowmax);

             while(l>pl||r<pr)

             {

                 if(l>pl)

                 {

                     nowmin=min(nowmin,gmin(pl,l));

                     nowmax=max(nowmax,gmax(pl,l));

                     l=pl;

                 }

                 if(r<pr)

                 {

                     nowmin=min(nowmin,gmin(r,pr));

                     nowmax=max(nowmax,gmax(r,pr));

                     r=pr;

                 }

                 pl=qmin(nowmin,nowmax);pr=qmax(nowmin,nowmax);

             }

             ans1[i][j]=l;ans2[i][j]=r;

         }

     int Q;

     Q=Rd();

     while(Q--)

     {

         register int l,r,ll,rr;

         l=Rd();r=Rd();

         ll=bl[l]+;rr=bl[r]-;

         int nowmin=gmin(l,r),nowmax=gmax(l,r);

         int pl=qmin(nowmin,nowmax),pr=qmax(nowmin,nowmax);

         while(l>pl||r<pr)

         {

             ll=bl[l]+;rr=bl[r]-;

             if(l>pl)

             {

                 nowmin=min(nowmin,gmin(pl,l));

                 nowmax=max(nowmax,gmax(pl,l));

                 l=pl;

                 l=min(l,ans1[ll][rr]);//答案是要动态更新，注意这句话不能写到前面，不然会出错

             }

             if(r<pr)

             {

                 nowmin=min(nowmin,gmin(r,pr));

                 nowmax=max(nowmax,gmax(r,pr));

                 r=pr;

                 r=max(r,ans2[ll][rr]);

             }

             pl=qmin(nowmin,nowmax);pr=qmax(nowmin,nowmax);

         }

         printf("%d %d\n",l,r);

     }

     return ;

 }

(%%%%%%znsbc)

下次加油，注重分析题目关键性质

考试要综合各种方法骗分

巴特西

NOIP模拟测试13

最新文章

热门文章