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

南京大学考研机试题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服务器租用&#xff1f; 对于网络时代来说&#xff0c;是需要很多设备才能维持的&#xff0c;比如说多ip服务器就是互联网时代常见的设备&#xff0c;所以我们需要对多ip服务器有足够的了解&#xff0c;这样才能更好的获取互联网上的信息&#xff0c;满足我们工作…...

(动手学习深度学习)第13章 实战kaggle竞赛:树叶分类

文章目录 实战kaggle比赛&#xff1a;树叶分类1. 导入相关库2. 查看数据格式3. 制作数据集4. 数据可视化5. 定义网络模型6. 定义超参数7. 训练模型8. 测试并提交文件 竞赛技术总结1. 技术分析2. 数据方面模型方面3. AutoGluon4. 总结 实战kaggle比赛&#xff1a;树叶分类 kagg…...

vue中shift+alt+f格式化防止格式掉其它内容

好处就是使得提交记录干净&#xff0c;否则修改一两行代码&#xff0c;习惯性按了一下格式化快捷键&#xff0c;遍地飘红&#xff0c;下次找修改就费时间 1.点击设置图标-设置 2.点击这个转成配置文件 {"extensions.ignoreRecommendations": true,"[vue]":…...

WPS导出的PDF比较糊,和原始的不太一样,将带有SVG的文档输出为PDF

一、在WPS的PPT中 你直接输出PDF可能会导致一些问题&#xff08;比如照片比原来糊&#xff09;/ 或者你复制PPT中的图片到AI中类似的操作&#xff0c;得到的照片比原来糊&#xff0c;所以应该选择打印-->高级打印 然后再另存为PDF 最后再使用AI打开PDF文件再复制到你想用…...

Linux /etc/hosts文件

Linux的 /etc/hosts 文件用于静态地映射主机名到 IP 地址。 通常用于本地网络中的名称解析&#xff0c;它可以覆盖 DNS 的设置。当你访问一个域名时&#xff0c;系统会首先检查 /etc/hosts 文件&#xff0c;如果找到了匹配项&#xff0c;就会使用该 IP 地址&#xff0c;否则会…...

webpack学习-3.管理输出

webpack学习-3.管理输出 1.简单练手2.设置 HtmlWebpackPlugin3.清理 /dist 文件夹4.manifest5.总结 1.简单练手 官网的第一个预先准备&#xff0c;是多入口的。 const path require(path);module.exports {entry: {index: ./src/index.js,print: ./src/print.js,},output: …...

【Go语言反射reflect】

Go语言反射reflect 一、引入 先看官方Doc中Rob Pike给出的关于反射的定义&#xff1a; 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 座城市&#xff0c;从 0 到 n-1 编号&#xff0c;其间共有 n-1 条路线。因此&#xff0c;要想在两座不同城市之间旅行只有唯一一条路线可供选择&#xff08;路线网形成一颗树&#xff09;。去年&#xff0c;交通运输部决定重新规划路线&#xff0c…...

自动数据增广论文笔记 | AutoAugment: Learning Augmentation Strategies from Data

谷歌大脑出品 paper: https://arxiv.org/abs/1805.09501 这里是个论文的阅读心得&#xff0c;笔记&#xff0c;不等同论文全部内容 文章目录 一、摘要1.1 翻译1.2 笔记 二、(第3部分)自动增强:直接在感兴趣的数据集上搜索最佳增强策略2.1 翻译2.2 笔记 三、跳出论文&#xff0c…...

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桌面

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f3a5;系列专栏&#xff1a;《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;…...

java--枚举

1.枚举 枚举是一种特殊类 2.枚举类的格式 注意&#xff1a; ①枚举类中的第一行&#xff0c;只能写一些合法的标识符(名称)&#xff0c;多个名称用逗号隔开。 ②这些名称&#xff0c;本质是常量&#xff0c;每个常量都会记住枚举类的一个对象。 3.枚举类的特点 ①枚举类的…...

JVM垃圾回收机制GC

一句话介绍GC&#xff1a; 自动释放不再使用的内存 一、判断对象是否能回收 思路一&#xff1a;引用计数 给这个对象里安排一个计数器&#xff0c; 每次有引用指向它&#xff0c; 就把计数器1&#xff0c; 每次引用被销毁&#xff0c;计数器-1&#xff0c;当计数器为0的时候…...

详解JAVA中的@ApiModel和@ApiModelProperty注解

目录 前言1. ApiModel注解2. ApiModelProperty注解3. 实战 前言 在Java中&#xff0c;ApiModel和ApiModelProperty是Swagger框架&#xff08;用于API文档的工具&#xff09;提供的注解&#xff0c;用于增强API文档的生成和展示。这两者搭配使用更佳 使用两者注解&#xff0c;…...

TiDB专题---2、TiDB整体架构和应用场景

上个章节我们讲解了TiDB的发展和特性&#xff0c;这节我们讲下TiDB具体的架构和应用场景。首先我们回顾下TiDB的优势。 TiDB的优势 与传统的单机数据库相比&#xff0c;TiDB 具有以下优势&#xff1a; 纯分布式架构&#xff0c;拥有良好的扩展性&#xff0c;支持弹性的扩缩容…...

性能调优入门

从公众号转载&#xff0c;关注微信公众号掌握更多技术动态 --------------------------------------------------------------- 一、性能定律和数理基础 1.三个定律法则 (1)帕累托法则 我它也被称为 80/20 法则、关键少数法则&#xff0c;或者八二法则。人们在生活中发现很多…...

JavaWeb | 验证码 、 文件的“上传”与“下载”

目录&#xff1a; 验证码 和 文件的“上传”与“下载”1.验证码1.1在JSP上开发验证码 2.“文件上传” 和 “文件下载”2.1“文件上传 ”2.2“文件下载” 验证码 和 文件的“上传”与“下载” 1.验证码 验证码&#xff1a;就是由服务器生成的一串随机数字或符号形成一幅图片&am…...

服务器感染了.halo勒索病毒,如何确保数据文件完整恢复?

导言&#xff1a; 随着科技的不断发展&#xff0c;网络安全问题日益突出&#xff0c;而.halo勒索病毒正是这个数字时代的一大威胁。本文将深入介绍.halo勒索病毒的特点&#xff0c;解释在受到攻击后如何有效恢复被加密的数据文件&#xff0c;并提供一些建议以预防未来可能的威…...

docker安装elasticsearch8.5.0和kibana

服务器环境&#xff0c;centos7 一、安装elasticsearch 1. 创建一个es和kibana通用的网络 docker network create es-net 2. 拉取es镜像&#xff0c;这里选择8.5.0版本 docker pull elasticsearch:8.5.03. 创建挂载目录&#xff0c;并授权 mkdir /usr/local/install/ela…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...