2025.7.25 测试 总结

—— From nfls Summer Camp

目录

• T4 （easy+,98%）
• T5 （mid,40%）
• T6 （mid,95%）
• T7 （mid+,80%）
• T8 （hard,0%）
• 总结

T4 （easy+,98%）

link
思路
看到题目只是要求最后一个数，考虑只维护后面的数，序列长什么样没必要管。类似指针的做法，用一个变量模拟指针，记录每个新加的数的父亲，以及每个版本所存储的最后一个数的地址。

反思
从题目问题入手，题目操作很明确，可以直接利用指针模拟。着重往题目要求的的地方想，没必要记录的尽量抛弃。

代码

#includeusing namespace std;const int maxq=5e5+5;int a[maxq],fa[maxq];string st; map<int,int>mp;int main(){int q; cin>>q;int now=0,cnt=0;while(q--){cin>>st;if(st==\"ADD\"){int x; cin>>x;a[++cnt]=x,fa[cnt]=now;now=cnt;}else if(st==\"DELETE\") now=fa[now];else if(st==\"SAVE\"){int x; cin>>x;mp[x]=now;}else{int x; cin>>x;now=mp[x];}cout<<(now?a[now]:-1)<<\" \";}return 0;}

T5 （mid,40%）

link
题意
求一个由 . 和 # 组成的 $n$ 行 $m$ 列的矩阵中所有全是 . 的子矩形的面积和。
$1\le n,m\le 2000$

思路
枚举每一行，考虑这一行和上面几行组成的子矩形对答案的贡献。
设枚举到位置 $(i,j)$ ，计算以 $(i,j)$ 为右下角所围成的子矩形的面积和。这需要知道第 $i$ 行中每个位置向上连续的 . 的数量，记为 h i , j h_{i,j} hi,j​ ，这很好知道。然后考虑从第 $j$ 列往前可以与那些列围城宽为 h i , j h_{i,j} hi,j​ 的子矩形，那就只需要知道离 $j$ 最近的 < h i , j \\lt h_{i,j} <hi,j​ 的位置即可，想到用 单调栈 维护 h i , j h_{i,j} hi,j​ 。然后就手动计算即可。复杂度均摊 $O(nm)$ 。

反思
没有想到计算所有矩形的面积和可以拆开每一行处理，总结脑废了。注意在草稿纸上先理清思路，注意细节！！！

代码

#include#define ll long longusing namespace std;const int maxn=2005;int stk[maxn];ll h[maxn],f[maxn];string st;int main(){int n,m; cin>>n>>m;ll ans=0;for(int i=1;i<=n;i++){cin>>st;for(int j=1;j<=m;j++){if(st[j-1]==\'.\') h[j]++;else h[j]=0;}int now=0;for(int j=1;j<=m;j++){while(now>=1&&h[stk[now]]>=h[j]) now--;f[j]=f[stk[now]];for(int k=now;k>=1;k--)f[j]+=(1+h[stk[k]])*h[stk[k]]/2*(j-stk[now])*(stk[k]-stk[k-1]);f[j]+=(1+h[j])*h[j]/2*(1+j-stk[now])*(j-stk[now])/2;stk[++now]=j;ans+=f[j];}}cout<<ans;return 0;}

T6 （mid,95%）

link
思路
普通 DP + 线段树优化 。

反思
场上没注意到最大值可能为负，得了 〇 ，警钟！！！

T7 （mid+,80%）

题意
给一个数组 a 1 , a 2 ,..., a n a_1,a_2,...,a_n a1​,a2​,...,an​ , 你希望固定尽量少的元素, 满足对于剩下未固定的元素 a x a_x ax​ , 它左右都有固定的元素。令 a l , a r a_l,a_r al​,ar​ 是左右两边最靠近它的固定的元素, 能满足 a l ≤ a x ≤ a r a_l \\le a_x \\le a_r al​≤ax​≤ar​ 或 a l ≥ a x ≥ a r a_l \\ge a_x \\ge a_r al​≥ax​≥ar​ 。输出最少的固定元素的个数。   0≤n≤1 0 5 ,1≤ a i ≤1 0 9 0 \\le n \\le 10^5 ,1 \\le a_i \\le 10^9 0≤n≤105,1≤ai​≤109

思路1
根据题目可以知道：数列中的最大最小值是一定要被固定的。证明很简单。那么夹在两个值中间的那段数就已经合法了。所以如果一个区间的数若两端分别是这些数的最大最小值，那么这个区间的数合法。扩展到剩下的两端的数，如果最大值已经固定那么就找最小值也固定，反之同理。可以递归处理答案，用线段树查找区间最大最小值即可。
具体可参考 这篇题解 ，懒得调代码了 。

思路2 （其实 思路1 更清晰易懂一点）
首先可以得到一个 O( n 2 ) O(n^2) O(n2) 的 DP 暴力。设 f i f_i fi​ 表示前 $i$ 个数保证合法下最少需要固定多少个元素（第 $i$ 个必须选）。具体大致如下：

int n; cin>>n;for(int i=1;i<=n;i++) cin>>a[i];f[1]=1;for(int i=1;i<n;i++){int ma=0,mi=1e9;for(int j=i+1;j<=n;j++){if((a[i]<=mi&&ma<=a[j])||(a[j]<=mi&&ma<=a[i])) f[j]=min(f[j],f[i]+1);else if(mi<a[i]&&a[i]<ma) break;ma=max(ma,a[j]),mi=min(mi,a[j]);}}cout<<f[n];

但其实再加上一点贪心，对于当前位置，找到左边最大的数的位置，再在这两个数绕出的区间中找到区间中的最小值，从最小值到当前位置这一段就都合法了。

反思
这道题其实不难，场上都没看，发现性质后就很好做了。所以最主要是根据题目和样例找到特定的有用的隐形条件。

T8 （hard,0%）

link
还没看也不想看……

总结

这场模拟赛其实也没有很难，但是主播代码能力真的太篛了，简单暴力都要调。
对题目的感知也没有很迅速，对题境的深入挖掘没有很准确。没睡够占一部分原因🤭
当然还要注意时间的把控。