首页 > 其他分享 >[蓝桥杯 2016 省 A] 密码脱落--最长公共子序列题解

[蓝桥杯 2016 省 A] 密码脱落--最长公共子序列题解

时间:2024-09-01 11:52:53浏览次数:12  
标签:-- 题解 样例 蓝桥 ## 公共 序列 最长 回文

题目复述:

题目链接:[蓝桥杯 2016 省 A] 密码脱落 - 洛谷

# [蓝桥杯 2016 省 A] 密码脱落

## 题目描述

X 星球的考古学家发现了一批古代留下来的密码。

这些密码是由 A、B、C、D 四种植物的种子串成的序列。

仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的回文串)。

由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

你的任务是:

给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

## 输入格式

输入一行,表示现在看到的密码串。(长度不大于 $1000$)

## 输出格式

要求输出一个正整数,表示至少脱落了多少个种子。

## 样例 #1

### 样例输入 #1

```
ABCBA
```

### 样例输出 #1

```
0
```

## 样例 #2

### 样例输入 #2

```
ABDCDCBABC
```

### 样例输出 #2

```
3
```

## 提示

蓝桥杯 2016 年省赛 A 组 I 题。

最长公共子序列-代码:

#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    string s1 = s;
    reverse(s1.begin(), s1.end());
    int dp[1005][1005];
    memset(dp,0,sizeof(dp));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (s[i-1] == s1[j-1])
            {
                dp[i][j] = dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << n - dp[n][n];
    return 0;
}

最长公共子序列--思路介绍: 

这题看上去很简单,但其实要搞懂还是需要一定的做题积累的,不然很难看出来这道题到底想考什么,提到回文串,大家都知道是从左往右和从右往左一样,所以可以换句话说,如果原串是S,那么将S进行首尾颠倒后得到S1,那么S应该等于S1,这样就可以证明这是回文串。

这道题需要大家知道一个概念--“最长公共子序列”,【模板】最长公共子序列 - 洛谷,不然的话可能很难做出这道题来。为什么要用到这个概念,就是我上面提到的,颠倒后的S1等于S则证明是回文串,那么由于这道题是将回文串进行涂抹,不妨举个例子,假设原来的回文串是ABCDCBA,我们抹去第一个B,原串变成A_CDCBA,颠倒后变成ABCDC_A,我们再来找一下两个的最长公共子序列,发现是ACDCA,正好把删去的一个B给省略了,也就是说找到最长公共子序列可以完美避开这种被抹去一个数的情况,如果两个数都被抹去了,那干脆不用找它了,如果都没被抹去,正好会被计算进最长公共子序列中;

所以最后的答案便是原串的长度n减去最长公共子序列的长度,上面的例子中n=6,最长公共子序列=5,所以答案为1正好是缺的那个B!

所以本题的告诉大家,提到回文的时候可以想想最长公共子序列是否可以解决,吃一堑长一智~

标签:--,题解,样例,蓝桥,##,公共,序列,最长,回文
From: https://blog.csdn.net/qq_73848829/article/details/141752268

相关文章

  • 校园便利|基于SprinBoot+vue的校园便利平台(源码+数据库+文档)
    校园便利平台基于SprinBoot+vue的校园便利平台一、前言二、系统设计三、系统功能设计 系统前台实现系统首页功能用户后台管理功能管理员功能实现四、数据库设计 五、核心代码 六、论文参考七、最新计算机毕设选题推荐八、源码获取:博主介绍:✌️大厂码农|毕设......
  • 开学第一周9.1周日学习日记
    算法cf1989ABCDhttps://codeforces.com/contest/1989B最长公共子序列 //相当于枚举以b[i]为起点遍历a的最长公共子序列 //因为是子序列所以abacccab即使后面先取了第一个a也不影响最长长度#include<bits/stdc++.h>usingnamespacestd;voidsolve() { stringa......
  • ctfhub-web-SSRF通关攻略
    一、内网访问1.打开ctfhub给的环境地址2.观察题目发现让我们访问127.0.0.1下的flag.php在地址栏后面有一个url参数 ?url=http://127.0.0.1/flag.php 提交即可二、伪协议读取文件1.打开ctfhub给的环境2.观察题目发现让我们读取flag.php文件读取文件用到的协议是......
  • 方法
    方法的定义方法是程序中最小的执行单元。main()方法也叫主方法。方法必须先定义,然后才能调用。方法的定义要写在main()的外面,类的里面。main()也是方法,方法不能嵌套定义。方法的编写顺序和执行顺序无关,执行顺序要根据调用顺序来看。方法名遵循驼峰法。方法与方法之间是......
  • C++:std::thread 和 pthread
            在C++中,线程的实现主要有两种方式:使用C++11标准库中的std::thread和POSIX线程库(pthread)。这两种方式各有优缺点,适用于不同的场景。以下是对这两种方式的详细比较和示例代码。std::thread示例代码#include<iostream>#include<thread>#include<chrono>......
  • C++:std::this_thread::sleep_for 和 sleep
            在C++中,std::this_thread::sleep_for和sleep函数都可以用来使当前线程暂停执行一段时间,但它们有一些重要的区别。以下是对这两种方法的详细比较:std::this_thread::sleep_for定义:std::this_thread::sleep_for是C++11标准库中的一个函数,用于使当前线程暂停执......
  • STM32硬件篇:W25Q64
    W25Q64简介W25Qxx系列是一种低成本、小型化、使用简单(使用SPI通信协议)的非易失性(掉电不丢失)存储器,常用于数据存储、字库存储、固件程序存储等场景。【注意】W25Qxx芯片只支持SPI的模式0和模式3。存储介质:NorFlash(闪存)时钟频率:80MHz/160MHz(DualSPI)/320MHz(QuadSPI)------......
  • 初识Arduino
    什么是ArduinoArduino是一款便捷灵活、方便上手的开源电子原型平台。它包含硬件部分(即各种型号的Arduino板)、软件部分(即ArduinoIDE),以及其Arduino社区平台。Arduino由一个欧洲开发团队于2005年冬季开发,成员包括MassimoBanzi、DavidCuartielles、TomIgoe、GianlucaMartino......
  • 史上最全秒杀+优化——两万字
    秒杀全局唯一id@ComponentpublicclassRedisIdWorker{@ResourceprivateStringRedisTemplatestringRedisTemplate;/***开始时间戳*publicstaticvoidmain(String[]args){*LocalDateTimebeginTime=LocalDateTime......
  • C++面向对象编程(OOP)教程
    C++面向对象编程(OOP)教程在C++中,面向对象编程(OOP)是一种编程范式,它基于“对象”的概念来设计软件。OOP强调将数据(属性)和操作这些数据的方法(行为)封装在一起,形成对象。这种封装提高了代码的模块化、可重用性和可维护性。C++通过类(Class)、对象(Object)、继承(Inheritance)、封装(Encapsu......