考得还算可以，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了
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 }
T2 跳房子
我还没A，85分暴力很不错。
主要是如何优化模拟blablabla
T3 优美序列
ST表可以维护权值，分块是优化的极好方式。
看题目的时候一定要认真。
这个题首先可以用ST表维护，即对于当前区间求出最大最小值，在利用维护的权值ST表搞出目标位置，利用目标位置更新当前max和min
但这种做法会被卡，可以用分块优化。
引理：
对于一个区间R，它的子区间的最优答案一定是它的最优答案的子区间。
利用这个我们可以先分块，（设块数为k）再处理出这k^2个块之间的答案，跑的飞快。
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]);//答案是要动态更新，注意这句话不能写到前面，不然会出错
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 }
(%%%%%%znsbc)
下次加油，注重分析题目关键性质
考试要综合各种方法骗分
原文：https://www.cnblogs.com/hzoi-kx/p/11308123.html