Part 1 题目列表

Part 2 考试时间线

8:00 开题，T1 一眼 DP，推了几分钟式子后直接开些。

8:40 看见时间复杂都是

\mathcal O(n^2m)

，十分的小，自己造了一个

n=2000,m=2000

的数据，然后获得了

8s

的优异成绩，于是赶紧写了一个优化。

9:40 爽炸天，写了一个小时 T2 却发现读题读错了，觉得 T2 写的有一点太久了，所以就决定先看 T3。

11:00 爽的没有天了，写了一个和 GYC 的做法类似的线段树做法，但是后两个大样例一直过不去，后来最后半个小时才发现了减法的 BUG，但没有时间改了。

11:20 花了 20 分钟写了 T4 的暴力，由于太急了，直接用 system("fc ") 比较，完全没有发现 1 3 5 7 9···· 的神奇性质。

11:50 最后半个小时打了 T1 的对拍，出来全是错，差点给我急死了，结果是暴力写错了。

12:00 整理文件，提交！！！

Part 3 题目分析

呜呜呜！！！我不想再写 TJ 了！！！

T1

很明显的 DP, 这里把我考试时写的挂上来：

设

f_{i,j}

为匹配

s

的前

i

个，

t

的前

j

个是否能匹配

$t_{j}$ 为字母，如果 $t_{j}=s_{i}$ , $f_{i,j}=f_{i-1,j-1}$
$t_{j}$ 为 '.', $f_{i,j}=f_{i-1,j-1}$
$t_{j}$ 为 '*', 枚举 $k$ , 如果从 $k$ 到 $i$ 皆为一个字母， $f_{i,j}=f_{k,j-1}$

ACcode

CPP

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int T;
int n,m;
string s,t;
int sum[2005][2005];
int f[2005][2005];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/

/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		memset(f,0,sizeof f);
		memset(sum,0,sizeof f);
		f[0][0]=1;
		cin>>s>>t;
		n=s.size(),m=t.size();
		s=' '+s,t=' '+t;
		int ans=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(t[j]>='a'&&t[j]<='z'){
					if(t[j]==s[i])
						f[i][j]|=f[i-1][j-1];
				}else if(t[j]=='.'){
					f[i][j]|=f[i-1][j-1];
				}else{
					f[i][j]|=f[i][j-1];
					f[i][j]|=sum[i][j-1];
//					for(int k=i;k>=1;k--){//以前的暴力
//						if(s[k]!=s[i])
//							break;
//						f[i][j]|=f[k][j-1];
//					}
				}
				if(s[i]==s[i-1]){//新的暴力
					sum[i][j]=(sum[i-1][j]|f[i][j]);
				}else{
					sum[i][j]=f[i][j];
				}
			}
			if(f[i][m]>=1) ans++;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

T2

这道题我们可以使用双指针查询

mex \ge k

的区间数量。

我们先找到一个前缀满足

mex \ge k

（及区间内包含所有从

0 ~ \to ~ k-1

的数字）。

然后控制右指针往右走，同时左指针往右走（在不影响条件：

mex \ge k

的情况下），则答案为

(n-l+1) \times (r'-r)

。

并且这道题要做一个优化，按 w 排序，如果

w+m \le ans

则不需要计算，否则每一次加一。

Part 4 总结

题目	预期得分	实际得分	主要算法	失分原因	改进方法
匹配 (match)	100	100	DP 动态规划	···	···
方阵 (mex)	20	0	双指针 + 思维（也可以用二分 + 卡长）	万恶之源 —— $memset()$	手写清空
合并 (merge)	40	40	贪心 + 线段树	没有调出来	在真正完成之前先判断方法的可行性和不足
数列 (sequence)	20	20	数学 + 单调栈	还好拿到了暴力分	···

预计总分：100 + 20 + 40 + 20 = 180 实际得分：100 + 0+40 + 20 = 160

20251003国庆模拟3

文章操作