班班最大了

用户名：dotcpp0607166

访问量：7475

签　名：

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

等　　级
排　　名	125
经　　验	7730
参赛次数	2
文章发表	35
年　　龄	3
在职情况	待业
学　　校	贺州学院
专　　业	数据

　　自我简介：

谢谢大家，让大家见笑了

TA的其他文章

C++简便易懂，STL简便做法
浏览：109

数组的距离
浏览：73

愤怒的牛，二分解法
浏览：221

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

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

　　作者: 班班最大了　　　　发表时间：2024-04-27 01:14:39 浏览：110　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

班班最大了

TA的其他文章

你可能喜欢

C语言考试练习题_保留字母（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

C二级辅导-阶乘数列（C语言代码）

【排队买票】（C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

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

评论区

精彩推荐

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

哥德巴赫曾猜测（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

1908题解

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

计算质因子（Java代码）

Manchester- A+B for Input-Output Practice (VII)

10进制 VS 2进制

班班最大了

TA的其他文章

你可能喜欢

C语言考试练习题_保留字母 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

C二级辅导-阶乘数列 （C语言代码）

【排队买票】 （C语言代码）

WU-蓝桥杯算法提高VIP-Quadratic Equation （C++代码）

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

评论区

精彩推荐

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

1908题解

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

计算质因子 （Java代码）

Manchester- A+B for Input-Output Practice (VII)

10进制 VS 2进制

C语言考试练习题_保留字母（C语言代码）

C二级辅导-阶乘数列（C语言代码）

【排队买票】（C语言代码）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

哥德巴赫曾猜测（C语言代码）

计算质因子（Java代码）