蓝桥杯官网 试题 PREV-255 历届真题 蓝肽子序列【第十一届】【决赛】【研究生组】【C++】【Java】【Python】三种解法
2023-09-14 09:05:03 时间
为帮助大家能在6月18日的比赛中有一个更好的成绩,我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。
今年的最大目标就是能为【一亿技术人】创造更高的价值。
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
C++
# include <stdio.h>
# include <string.h>
char temp[1005];
char s1[1005][1005]; //下标从1到cnt
char s2[1005][1005];
int cnt1,cnt2;
int dp[1005][1005];
int main()
{
gets(temp);
int cnt=0;
for(int i=0;i<strlen(temp);++i)
{
if(temp[i]>='A'&&temp[i]<='Z')
{
cnt=0;
s1[++cnt1][cnt++]=temp[i];
}
else
{
s1[cnt1][cnt++]=temp[i];
}
}
gets(temp);
cnt=0;
for(int i=0;i<strlen(temp);++i)
{
if(temp[i]>='A'&&temp[i]<='Z')
{
cnt=0;
s2[++cnt2][cnt++]=temp[i];
}
else
{
s2[cnt2][cnt++]=temp[i];
}
}
for(int i=1;i<=cnt1;++i)
{
for(int j=1;j<=cnt2;++j)
{
if(strcmp(s1[i],s2[j])==0)dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
}
}
printf("%d",dp[cnt1][cnt2]);
return 0;
}
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String text1 = in.nextLine();
String text2 = in.nextLine();
int n = text1.length();
int m = text2.length();
String[] s1 = new String[1000];
int index1 = 0;
int cnt1 = 0;
for(int i=1;i<n;i++){
char c = text1.charAt(i);
if(c>='A'&&c<='Z'){
s1[cnt1]=text1.substring(index1,i);
index1=i;
cnt1++;
}
}
s1[cnt1++]=text1.substring(index1,n);
String[] s2 = new String[1000];
int index2 = 0;
int cnt2 = 0;
for(int i=1;i<m;i++){
char c = text2.charAt(i);
if(c>='A'&&c<='Z'){
s2[cnt2]=text2.substring(index2,i);
index2=i;
cnt2++;
}
}
s2[cnt2++]=text2.substring(index2,m);
int[][] dp = new int[cnt1+1][cnt2+1];
for(int i=1;i<cnt1+1;i++){
for(int j=1;j<cnt2+1;j++){
if(s1[i-1].equals(s2[j-1])){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
System.out.println(dp[cnt1][cnt2]);
}
}
Python
def f(s,t):
S = [0] #存放s划分后的蓝肽
S_Up = [] #记录s中大写字母的下标
T = [0] #存放s划分后的蓝肽
T_Up = [] #记录t中大写字母的下标
for i in range(len(s)):
if 'A' <= s[i] <= 'Z':
S_Up.append(i)
S_Up.append(len(s)) #此处要在最后再添加一个s的长度,以便后面划分字符串
for i in range(len(t)):
if 'A' <= t[i] <= 'Z':
T_Up.append(i)
T_Up.append(len(t)) #此处要在最后再添加一个t的长度,以便后面划分字符串
for i in range(len(S_Up)-1): #对s划分蓝肽
l = S_Up[i]
r = S_Up[i+1]
S.append(s[l:r])
for i in range(len(T_Up)-1): #对t划分蓝肽
l = T_Up[i]
r = T_Up[i+1]
T.append(t[l:r])
n = len(S)
m = len(T)
dp = [[0 for j in range(m)] for i in range(n)] #查找最长子序列
for i in range(1,n):
for j in range(1,m):
if S[i] == T[j]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i][j-1],dp[i-1][j])
print(dp[n-1][m-1])
if __name__ == '__main__':
s = input().strip()
t = input().strip()
f(s,t)
相关文章
- python处理xps文件_如何在Windows 10系统中处理XPS文件
- 我用python算出了同事的身份证号码!
- 基于python的安全帽识别安全帽检测可以检测图片,视频流,有界面[通俗易懂]
- python中sqrt函数用法_Python : sqrt() 函数
- java分前端后端吗_Java Web属于前端还是后端
- Java 和 Python 有哪些区别?「建议收藏」
- java与python-如何对比Python和Java,只需三分钟告诉你!
- Java版五子棋小游戏(java控制台)
- python读取pkl_Python读取文件的一段内容
- python怎样读取文件夹里的图片_python图片处理及识别
- 交通标志识别Python+TensorFlow(QT界面+WEB界面)
- python把数字转换为字符串_python中将列表转化为字符串
- java字符串转换为json对象6_Json对象与Json字符串的转化、JSON字符串与Java对象的转换…
- win32api python 手册_windows api如何使用
- python json.loads 中文_Python 的完美 json loads
- Python中12个常用模块的使用教程
- Python 实现DNS查询放大攻击
- Python实现批量上传excel
- 简单的电子邮件爬虫Python代码详解编程语言
- Python class定义类,Python类的定义(入门必读)
- 程序Linux命令调用Java程序实现交互(linux命令java)
- Linux下搭建 Java 开发环境(linux搭建java环境)
- 如何在Linux系统下有效地启动Java程序,让你的代码在Linux中也能正常运行?(linux下启动java)
- 深入浅出 使用 Java 连接 Neo4j(java连接neo4j)
- 下的应用玩转Python:Linux下的Python应用之旅(python在linux)
- Linux下从系统卸载Python(linux下卸载python)
- 的应用Java在Oracle数据库中的重要性及应用(java在oracle里)
- Python中使用MySQL数据库的操作技巧(mysql_python)