南京大学考研机试题DP
3. dp 求子序列的个数
https://www.acwing.com/problem/content/description/3716/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;
const int N = 1e4 + 10 , mod = 1000000007;
int T;
char s[N] , p[N];
int f[N];
int n , m;
/*
首先求公共子序列问题想到 DP
写出 F[i][j] 函数的含义:
s数组中由前i个字符构成的子序列 和P数组中前j个字符构成的子串构成的集合
// 字串和子序列不同的含义是字串是连续的 , 子序列可以不连续
分析状态转移:
1. 包含 s[i] 当且仅当 s[i] = p[j]
f[i][j] = f[i - 1][j - 1] 从上一个状态转移而来
上一个状态是由s中前 i - 1 个字符构成的子序列和 p 中前 j - 1 个字符构成的字串
2. 不包含 s[i] f[i][j] = f[i - 1][j]
优化空间
发现需要优化 f[i][j] = f[i - 1][j] + f[i - 1][j - 1]
我们发现 f[i][j] = f[i - 1][j] 从 i - 1 层计算得到
f[i][j] = f[i - 1][j - 1] 由 i - 1 层计算得到
如果我们从小到大枚举 j 那么 第 i - 1层的 f[j - 1] 会被 第 i 层的覆盖
所以 我们需要从 m - 0 枚举 j (为什么到 0 因为 f[0] 也是一种方案)
优化时间
分析时间复杂度 o(n ^ 2 * Q) > 1e9 我们依然是两维
其次我们发现依然 TLE
但我们知道 只有当 s[i] = p[j] 的时候才会更新
所以我们只需要将 s[i] = p[j] 的元素枚举即可
开一个 vector 存 b 中每一个字母出现的下标
第一层枚举 S 的时候只需要 第二层枚举 b[s[i] - 'a'] 也就是 p 和 s 相同的下标就可以了
*/
int main()
{
cin >> T;
while(T --)
{
cin >> s + 1 >> p + 1;
n = strlen(s + 1);
m = strlen(p + 1);
memset(f , 0 , sizeof f);
f[0] = 1;
vector<int> b[26];
for(int i = m ; i ; i --)
b[p[i] - 'a'].push_back(i);
for(int i = 1 ; i <= n ; i ++)
for(auto j : b[s[i] - 'a'])
{
if(s[i] == p[j])
f[j] = (f[j] + f[j - 1]) % mod;
}
cout << f[m] << endl;
}
return 0;
}
相关文章:
南京大学考研机试题DP
3. dp 求子序列的个数 https://www.acwing.com/problem/content/description/3716/ #include <iostream> #include <cstring> #include <algorithm> #include <unordered_set> #include <vector> using namespace std; const int N 1e4 10…...
如何进行多ip服务器租用?
如何进行多ip服务器租用? 对于网络时代来说,是需要很多设备才能维持的,比如说多ip服务器就是互联网时代常见的设备,所以我们需要对多ip服务器有足够的了解,这样才能更好的获取互联网上的信息,满足我们工作…...
(动手学习深度学习)第13章 实战kaggle竞赛:树叶分类
文章目录 实战kaggle比赛:树叶分类1. 导入相关库2. 查看数据格式3. 制作数据集4. 数据可视化5. 定义网络模型6. 定义超参数7. 训练模型8. 测试并提交文件 竞赛技术总结1. 技术分析2. 数据方面模型方面3. AutoGluon4. 总结 实战kaggle比赛:树叶分类 kagg…...
vue中shift+alt+f格式化防止格式掉其它内容
好处就是使得提交记录干净,否则修改一两行代码,习惯性按了一下格式化快捷键,遍地飘红,下次找修改就费时间 1.点击设置图标-设置 2.点击这个转成配置文件 {"extensions.ignoreRecommendations": true,"[vue]":…...
WPS导出的PDF比较糊,和原始的不太一样,将带有SVG的文档输出为PDF
一、在WPS的PPT中 你直接输出PDF可能会导致一些问题(比如照片比原来糊)/ 或者你复制PPT中的图片到AI中类似的操作,得到的照片比原来糊,所以应该选择打印-->高级打印 然后再另存为PDF 最后再使用AI打开PDF文件再复制到你想用…...
Linux /etc/hosts文件
Linux的 /etc/hosts 文件用于静态地映射主机名到 IP 地址。 通常用于本地网络中的名称解析,它可以覆盖 DNS 的设置。当你访问一个域名时,系统会首先检查 /etc/hosts 文件,如果找到了匹配项,就会使用该 IP 地址,否则会…...
webpack学习-3.管理输出
webpack学习-3.管理输出 1.简单练手2.设置 HtmlWebpackPlugin3.清理 /dist 文件夹4.manifest5.总结 1.简单练手 官网的第一个预先准备,是多入口的。 const path require(path);module.exports {entry: {index: ./src/index.js,print: ./src/print.js,},output: …...
【Go语言反射reflect】
Go语言反射reflect 一、引入 先看官方Doc中Rob Pike给出的关于反射的定义: Reflection in computing is the ability of a program to examine its own structure, particularly through types; it’s a form of metaprogramming. It’s also a great source of …...
LC-1466. 重新规划路线(DFS、BFS)
1466. 重新规划路线 中等 n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,…...
自动数据增广论文笔记 | AutoAugment: Learning Augmentation Strategies from Data
谷歌大脑出品 paper: https://arxiv.org/abs/1805.09501 这里是个论文的阅读心得,笔记,不等同论文全部内容 文章目录 一、摘要1.1 翻译1.2 笔记 二、(第3部分)自动增强:直接在感兴趣的数据集上搜索最佳增强策略2.1 翻译2.2 笔记 三、跳出论文,…...
CTF 7
信息收集 存活主机探测 arp-scan -l 端口探测 nmap -sT --min-rate 10000 -p- 192.168.0.5 服务版本等信息 nmap -sT -sV -sC -O -p22,80,137,138,139,901,5900,8080,10000 192.168.0.5Starting Nmap 7.94 ( https://nmap.org ) at 2023-11-02 21:23 CST Stats: 0:01:30 elaps…...
无公网IP环境Windows系统使用VNC远程连接Deepin桌面
🔥博客主页: 小羊失眠啦. 🎥系列专栏:《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞👍收藏⭐评论✍️ 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,…...
java--枚举
1.枚举 枚举是一种特殊类 2.枚举类的格式 注意: ①枚举类中的第一行,只能写一些合法的标识符(名称),多个名称用逗号隔开。 ②这些名称,本质是常量,每个常量都会记住枚举类的一个对象。 3.枚举类的特点 ①枚举类的…...
JVM垃圾回收机制GC
一句话介绍GC: 自动释放不再使用的内存 一、判断对象是否能回收 思路一:引用计数 给这个对象里安排一个计数器, 每次有引用指向它, 就把计数器1, 每次引用被销毁,计数器-1,当计数器为0的时候…...
详解JAVA中的@ApiModel和@ApiModelProperty注解
目录 前言1. ApiModel注解2. ApiModelProperty注解3. 实战 前言 在Java中,ApiModel和ApiModelProperty是Swagger框架(用于API文档的工具)提供的注解,用于增强API文档的生成和展示。这两者搭配使用更佳 使用两者注解,…...
TiDB专题---2、TiDB整体架构和应用场景
上个章节我们讲解了TiDB的发展和特性,这节我们讲下TiDB具体的架构和应用场景。首先我们回顾下TiDB的优势。 TiDB的优势 与传统的单机数据库相比,TiDB 具有以下优势: 纯分布式架构,拥有良好的扩展性,支持弹性的扩缩容…...
性能调优入门
从公众号转载,关注微信公众号掌握更多技术动态 --------------------------------------------------------------- 一、性能定律和数理基础 1.三个定律法则 (1)帕累托法则 我它也被称为 80/20 法则、关键少数法则,或者八二法则。人们在生活中发现很多…...
JavaWeb | 验证码 、 文件的“上传”与“下载”
目录: 验证码 和 文件的“上传”与“下载”1.验证码1.1在JSP上开发验证码 2.“文件上传” 和 “文件下载”2.1“文件上传 ”2.2“文件下载” 验证码 和 文件的“上传”与“下载” 1.验证码 验证码:就是由服务器生成的一串随机数字或符号形成一幅图片&am…...
服务器感染了.halo勒索病毒,如何确保数据文件完整恢复?
导言: 随着科技的不断发展,网络安全问题日益突出,而.halo勒索病毒正是这个数字时代的一大威胁。本文将深入介绍.halo勒索病毒的特点,解释在受到攻击后如何有效恢复被加密的数据文件,并提供一些建议以预防未来可能的威…...
docker安装elasticsearch8.5.0和kibana
服务器环境,centos7 一、安装elasticsearch 1. 创建一个es和kibana通用的网络 docker network create es-net 2. 拉取es镜像,这里选择8.5.0版本 docker pull elasticsearch:8.5.03. 创建挂载目录,并授权 mkdir /usr/local/install/ela…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
