20251003国庆模拟3

__H_J_M__ · 2025-10-03 20:20:58 · 个人记录

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 个是否能匹配

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

ACcode

#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 总结

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