弗莱

用户名：1435075261

访问量：6034

签　名：

马梅，我还喜欢你，是不是有点可笑

等　　级
排　　名	1193
经　　验	2988
参赛次数	0
文章发表	27
年　　龄	0
在职情况	学生
学　　校	野鸡大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-夺宝奇兵（C语言，动态规划）
浏览：56

蓝桥杯2020年第十一届省赛真题-子串分值-贡献值法（C）
浏览：313

编写题解 1436: 蓝桥杯2014年第五届真题-地宫取宝 dfs vs dp
浏览：83

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

蓝桥杯2020年第十一届省赛真题-子串分值-贡献值法（C）

　　作者: 弗莱　　　　发表时间：2022-04-06 17:17:45 浏览：313　|　评论：1　

原题链接：蓝桥杯2020年第十一届省赛真题-子串分值

###### ### ## 算法描述：究其根本，是一种减少时间复杂度的算法——减少不必要的比较和存储步骤算法描述：究其根本，是一种减少时间复杂度的算法——减少不必要的比较和存储步骤

------------

我们可以通过求每个字符对数列的贡献度来解决问题，**每个字符的贡献度都是等于该字符距离上一个和它一样的字符之间的个数乘以它到字符串末尾的个数。**

以题例 ababc 为例子，这五个字符每个字符的贡献度分别为：

a:  1*2=2；

b:  2*2=4；

a:2*3=6；

b:  2*2=4；

c:  5*1=5

所以正好加起来等于21；

------------

#include<stdio.h>
    #include<string.h>
    int main()
    {
    	char a[100000]={0};//输入字串
    	int len,sum=0;//记录长度和个数和
    	scanf("%s",a);
    	len=strlen(a);
    	for(int i=0;i<len;i++)//遍历
    	{
    		char temp=a[i];//基准点
    		int qwq1=1,qwq2=1,index=i;
    		for(int j=index;j>=0;j--)//向左遍历比较
    		{
    			if(a[j]!=temp)
    			{
    				qwq1++;
    				if(j==0)
    				{
    					break;
    				}
    			}
    			if(a[j]==temp&&j!=index)
    			{
    				break;
    			}
    		}
    		for(int j=index;j<len;j++)//向右遍历比较
    		{
    			if(a[j]!=temp)
    			{
    				qwq2++;
    				if(j==len-1)
    				{
    					break;
    				}
    			}
    			if(a[j]==temp&&j!=index)
    			{
    				break;
    			}
    		}
    		int gx=qwq1*qwq2;//公式（左右相乘）
    		sum+=gx;			
    	}
    	printf("%d\n",sum);
    	return 0;
    }

0.0分

3 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

绽放青春

为什么题例ababc官网上题例答案是28，你的代码运行结果是21，把你的代码提交到官网上测试结果是正确，为什么会这样？

2024-01-13 11:05:40

弗莱

TA的其他文章

你可能喜欢

剪格子（C语言代码）

人民币问题（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

校门外的树（C语言代码）

蓝桥杯2020年第十一届省赛真题-子串分值-贡献值法（C）

评论区

精彩推荐

破解简单密码（C语言代码）

分糖果（C++代码）

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

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

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

有关字符，字符串的输入输出函数说明

Tom数（C语言代码）

简单的事情（C语言代码）

矩阵转置（C语言代码）

简单的a+b （C语言代码）

弗莱

TA的其他文章

你可能喜欢

剪格子 （C语言代码）

人民币问题 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

校门外的树 （C语言代码）

蓝桥杯2020年第十一届省赛真题-子串分值-贡献值法（C）

评论区

精彩推荐

破解简单密码 （C语言代码）

分糖果 （C++代码）

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

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

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

有关字符，字符串的输入输出函数说明

Tom数 （C语言代码）

简单的事情 （C语言代码）

矩阵转置 （C语言代码）

简单的a+b （C语言代码）

剪格子（C语言代码）

人民币问题（C语言代码）

校门外的树（C语言代码）

　　评论区

破解简单密码（C语言代码）

分糖果（C++代码）

Tom数（C语言代码）

简单的事情（C语言代码）

矩阵转置（C语言代码）