NOIP Analog Test 13

It's okay with the exam, but there's room for T3 to improve (I can't see the problem yet && I didn't get 4 points for the sample).

Expected score: 80+40+0=120

Actual score: 80+85+4=169

Black line on one face.High T2 scores are the reason data are more water.

Anyway, it's right to divide up the violence first.

T1 Matrix Game

Water?I don't think so, n, m 1e9!23333 But it seems that I can follow the thinking of battalion commander 2. All in all, I'm too dished. Why is the dish the original sin?

The first easy-to-deduce sub-ans=H[i]*L[j]* (m*(i-1)+j) (1<=i<=n, 1<=j<=m)

Consider expanding simplification ans=H[i]*L[j]*m*(i-1)+L[j]*j

Found that_L[j]*j can be handled

_L[j]*m*(i-1) can be pushed forward

And then...AC

 1 #include<bits/stdc++.h>
 2 #define MAXN 1000005
 3 #define int long long
 4 using namespace std;
 5 const int mod=1000000007;
 6 int h[MAXN],l[MAXN];
 7 signed main()
 8 {
 9     int n,m,k,tot=0,base=0,now=0,ans=0;
10     scanf("%lld%lld%lld",&n,&m,&k);
11     for(int i=1;i<=n;i++)h[i]=1;
12     for(int i=1;i<=m;i++)l[i]=1;
13     while(k--)
14     {
15         char opt;cin>>opt;
16         int x,y;
17         scanf("%lld%lld",&x,&y);
18         if(opt=='R')(h[x]*=y)%=mod;
19         else (l[x]*=y)%=mod;
20     }
21     for(int i=1;i<=m;i++)(tot+=l[i]*i)%=mod,(base+=l[i])%=mod;
22     for(int i=1;i<=n;i++)
23     {
24         (ans+=h[i]*(now+tot)%mod)%=mod;
25         (now+=base*m)%=mod;
26     }
27     cout<<ans<<endl;
28     return 0;
29 }
AC Code

 

T2 Jump House

I haven't got an A yet. The 85-point violence is good.

Primarily how to optimize the simulation blablabla blabla

T3 Graceful Sequence

ST tables maintain weights, and blocking is an excellent way to optimize.

Be sure to read the topic carefully.

This question can be first maintained with the ST table, that is, to find the maximum and minimum values for the current interval, to find the target location using the maintained weight ST table, and to update the current max and min using the target location

However, this is done by the card and can be optimized in blocks.

Lemmar:

For an interval R, the optimal answer of its subinterval must be the subinterval of its optimal answer.

With this, we can divide the blocks (number of blocks is k) and work out the answer between the k^2 blocks, running fast.

  1 #include<bits/stdc++.h>
  2 #define MAXN 100005
  3 #define min(a,b) ((a<b)?(a):(b))
  4 #define max(a,b) ((a>b)?(a):(b))
  5 using namespace std;
  6 int mn[20][MAXN],mx[20][MAXN],mh[MAXN],a[MAXN],n,mnpos[20][MAXN],mxpos[20][MAXN],ans1[2005][2005],ans2[2005][2005],t;
  7 int bl[MAXN];
  8 vector<int>ld;
  9 void pre()
 10 {
 11     for(int i=1;i<=n;i++)
 12         for(int j=17;j>=0;j--)
 13             if(i>=(1<<j)) 
 14             {
 15                 mh[i]=j;
 16                 break;
 17             }
 18     for(int i=1;i<=17;++i)
 19         for(int j=1;j<=n;++j)
 20         {
 21             mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
 22             mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
 23             mnpos[i][j]=min(mnpos[i-1][j],mnpos[i-1][j+(1<<(i-1))]);
 24             mxpos[i][j]=max(mxpos[i-1][j],mxpos[i-1][j+(1<<(i-1))]);
 25         }
 26     return ;
 27 }
 28 inline int Rd()
 29 {
 30     int x=0;char c=getchar();
 31     while(c>'9'||c<'0')c=getchar();
 32     while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
 33     return x;
 34 }
 35 inline int gmax(int l,int r)
 36 {
 37     return max(mx[mh[r-l+1]][l],mx[mh[r-l+1]][r-(1<<mh[r-l+1])+1]);
 38 }
 39 inline int gmin(int l,int r)
 40 {
 41     return min(mn[mh[r-l+1]][l],mn[mh[r-l+1]][r-(1<<mh[r-l+1])+1]);
 42 }
 43 inline int qmax(int l,int r)
 44 {
 45     return max(mxpos[mh[r-l+1]][l],mxpos[mh[r-l+1]][r-(1<<mh[r-l+1])+1]);
 46 }
 47 inline int qmin(int l,int r)
 48 {
 49     return min(mnpos[mh[r-l+1]][l],mnpos[mh[r-l+1]][r-(1<<mh[r-l+1])+1]);
 50 }
 51 int main()
 52 {
 53     n=Rd();
 54     t=pow(n,0.7);
 55     for(int i=1;i<=n;i++) 
 56     {
 57         a[i]=Rd();
 58         mn[0][i]=mx[0][i]=a[i];
 59         mnpos[0][a[i]]=mxpos[0][a[i]]=i;
 60     }
 61     int p=0,tot=0;
 62     while(p<n)
 63     {
 64         ld.push_back(p+1);
 65         for(int i=1;i<=t;i++)bl[p+i]=tot;
 66         p+=t;
 67         tot++;
 68     }
 69     pre();
 70     memset(ans1,0x3f,sizeof(ans1));
 71     memset(ans2,-0x3f,sizeof(ans2));
 72     for(int i=0;i<ld.size();i++)
 73         for(int j=i;j<ld.size();j++)
 74         {
 75             int l,r;
 76             l=ld[i];
 77             r=ld[j];
 78             int nowmin=gmin(l,r),nowmax=gmax(l,r);
 79             int pl=qmin(nowmin,nowmax),pr=qmax(nowmin,nowmax);
 80             while(l>pl||r<pr)
 81             {
 82                 if(l>pl)
 83                 {
 84                     nowmin=min(nowmin,gmin(pl,l));
 85                     nowmax=max(nowmax,gmax(pl,l));
 86                     l=pl;
 87                 }
 88                 if(r<pr)
 89                 {
 90                     nowmin=min(nowmin,gmin(r,pr));
 91                     nowmax=max(nowmax,gmax(r,pr));
 92                     r=pr;
 93                 }
 94                 pl=qmin(nowmin,nowmax);pr=qmax(nowmin,nowmax);
 95             }
 96             ans1[i][j]=l;ans2[i][j]=r;
 97         }
 98     int Q;
 99     Q=Rd();
100     while(Q--)
101     {
102         register int l,r,ll,rr;
103         l=Rd();r=Rd();
104         ll=bl[l]+1;rr=bl[r]-1;
105         int nowmin=gmin(l,r),nowmax=gmax(l,r);
106         int pl=qmin(nowmin,nowmax),pr=qmax(nowmin,nowmax);
107         while(l>pl||r<pr)
108         {
109             ll=bl[l]+1;rr=bl[r]-1;
110             if(l>pl)
111             {
112                 nowmin=min(nowmin,gmin(pl,l));
113                 nowmax=max(nowmax,gmax(pl,l));
114                 l=pl;
115                 l=min(l,ans1[ll][rr]);//The answer is to update dynamically. Note that this sentence can't be written before, otherwise there will be errors
116             }
117             if(r<pr)
118             {
119                 nowmin=min(nowmin,gmin(r,pr));
120                 nowmax=max(nowmax,gmax(r,pr));
121                 r=pr;
122                 r=max(r,ans2[ll][rr]);
123             }
124             pl=qmin(nowmin,nowmax);pr=qmax(nowmin,nowmax);
125         }
126         printf("%d %d\n",l,r);
127     }
128     return 0;
129 }
View Code

(%%%%%%znsbc)

Next refueling, focus on analyzing the key nature of the topic

Scoring in Examination by Combining Different Methods

Tags: PHP

Posted on Tue, 06 Aug 2019 15:40:33 -0700 by hashim