第十五届蓝桥杯C++B组第二场真题-前缀总分

394 阅读 0 评论 0 点赞

##思路
由于每改变一个字符，对其与其它n-1个字符串的前缀长度都有影响，所以我们需要记录改变前任意两个字符串的前缀长度和其对于每一个位置的后缀情况，当改变后使前缀长度变长的同时，我们还需要考虑其后缀是否也能加到前缀里
```
#include <bits/stdc++.h>
using namespace std;
const int N = 200+10;
int n,ji;
string a[N];
int pre[N][N],suf[N][N][N];                        //记录任意两个字符串的前缀，以及任意两个字符串在当前位置下的后缀长度
int find(int c,int d){                             //去寻找当前的最长公共子串长度 
	int min_size=min(a[c].size(),a[d].size());
	for(int i=0;i<min_size;i++){
		if(a[c][i]!=a[d][i]) return i;
	}
	return min_size;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){                      //枚举任意两个字符串之间的最长公共前缀
			if(i==j) continue;
			pre[i][j]=find(i,j);
			if(j<i) ji+=pre[i][j];                  //记录当前情况下(即未改变前)的前缀总分 
			for(int k=min(a[i].size(),a[j].size())-1;k>=0;k--){
				if(a[i][k]==a[j][k]) suf[k][i][j]=suf[k+1][i][j]+1; //记录任意两个字符串的公共后缀长度 
				else suf[k][i][j]=0;
			}
		}
	}
	int ans=ji;                                      //先把当前情况下(即未改变前)的前缀总分赋值给答案，方便后续比较 
	for(int i=1;i<=n;i++){                           //遍历所有的字符串i 
		for(int j=0;j<a[i].size();j++){              //遍历所有字符串的每一个位置 
			for(char k='a';k<='z';k++){              //枚举所有改变情况 
				if(k!=a[i][j]){                      //当改变后的字符和原字符不同时进行分析 
					int t=ji;                        //先记录当前前缀总分 
					for(int l=1;l<=n;l++){           //遍历对每一个字符串i和字符串l进行比较 
						if(i!=l){                    //当字符串i和l不是同一字符串时 
							t-=pre[i][l];            //先把两字符串原来的总分减掉 
							if(pre[i][l]<j) t+=pre[i][l];   //如果两字符串最长公共前缀长度比其短，即不用改变，加回之前的总分 
							else if(pre[i][l]==j && k==a[l][j]) t+=pre[i][l]+1+suf[j+1][i][l];    //当它们最长公共前缀正好到这的前一个，刚好变换后的字符和另一个字符串相同，则把它们之前的前缀总分加一并加上它们的相同后缀长度 
							else t+=j;               //否则就把当前值加回去 
						}
					}
					ans=max(ans,t);
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}
```

0.0分

1 人评分

本文分类：文章列表
浏览次数：394 次浏览
发布日期：2024-04-27 01:14:39
本文链接：https://blog.dotcpp.com/a/104693

上一篇 > 第十五届蓝桥杯C++B组第二场真题-传送门
下一篇 > 第十五届蓝桥杯C++B组第二场真题-遗迹

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

第十五届蓝桥杯C++B组第二场真题-前缀总分

评论列表共有 0 条评论

发表评论取消回复

第十五届蓝桥杯C++B组第二场真题-前缀总分

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复