当前位置: 首页 > news >正文

20251003国庆模拟3

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>= 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

http://www.hskmm.com/?act=detail&tid=23745

相关文章:

  • 20251002国庆模拟2
  • ハレハレヤ
  • 4-创建索引和约束 - 实践
  • 2025十一集训——Day2做题
  • 核聚变:Commonwealth Fusion Systems
  • 占个位置~
  • AI元人文系列文章:价值决策芯片——为机器安上一颗“透明的心”
  • 30天JavaScript挑战 - 从零基础到精通的完整学习指南
  • 题解:AT_agc057_c [AGC057C] Increment or Xor
  • 占个位置
  • 使用 Copilot AI + Blazor 编一个五子棋游戏
  • 关于VMware虚拟机如何下载-2025.10.3
  • 国庆集训做题10.1 - 10.3
  • 玳瑁的嵌入式日记---0928(ARM--UART) - 指南
  • 解决Visual Studio中无法使用scanf和C++万能头的问题
  • 英文笔记
  • 解码红黑树
  • 10/3
  • Advanced Computer Graphics
  • Netflix确保数亿用户观影体验的“事件”管理是如何构建与实践的?
  • 为什么词嵌入可以和位置编码相加
  • 【比赛记录】2025CSP-S模拟赛57
  • 实用指南:软件设计师——04 操作系统
  • 20251001国庆模拟
  • 线段树合并 [POI 2011] ROT-Tree Rotations
  • CSS的选择器 - 指南
  • C# Net9的模块初始化器(Module Initializer)
  • 离线轻量大模型,Ollama部署到docker方法
  • 应用拓扑讲义整理 Chapter 6. 单纯复形(Simplicial Complexes)
  • 完整教程:华为麒麟9010、9020、9030、9040系列芯片的性能参数及其与高通芯片的对比