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
#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>= k\) 的区间数量。
我们先找到一个前缀满足 \(mex>=k\) (及区间内包含所有从 \(0 ~->~ k-1\) 的数字)。
然后控制右指针往右走,同时左指针往右走(在不影响条件: \(mex>=k\) 的情况下),则答案为 \((n-l+1)*(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