Score of sub series of previous test questions and [11th] [provincial competition] [group B]

Substring score and full decomposition method

---

One 、 Complete title

Two 、 Specific ideas

1. Recurrence of violence

Using the idea of recursion , Find each string , And count the score of each string , Finally, carry out statistical accumulation , Get the result , The order of the string is ：

1. First , A complete string , Remove the last character of a complete string at a time
2. Again , Remove the first character of the string , repeat 1 The operation of
3. repeat 2 Until the string is empty

After finding each substring , Just count the number of characters

2. Statistical contribution value

Normally, the string should be viewed horizontally line by line , Let's open our minds , Look up , Look how many times the characters appear in each column , Count the times , I found a schematic diagram on the Internet ：

source ：https://img-blog.csdnimg.cn/20210413181240678.png

We can sum up the formula ：

• When the character first appears ： Number of occurrences =( Subscript +1)x( String length - Subscript )
• An obsolete character appears before this character ： Number of occurrences =( String length - Subscript )x( The current position - Where it happened before )

3、 ... and 、 Write code

1. Recurrence of violence

#include <stdio.h>
#include <string.h>

#define MAX 100000// Maximum length 

int difStr(char s[],int len)// Find the score of the string 
{
    
    if(len==0) return 0;// The end condition 

    int i,cnt=0;
    int a[26]={
    0};// Whether statistics exist 

    for(i=0;i<len;i++) a[s[i]-'a']++;// Count 
    for(i=0;i<25;i++) if(a[i]!=0) cnt++;// Count the number of different letters 

    cnt+=difStr(s,len-1);// Recursive implementation 
    return cnt;// Returns the score of this string 
}

int f(char s[],int len)// Count the scores and of all strings 
{
    
    if(len==0) return 0;// The end condition 

    int sum=0;// Score sum 

    sum+=difStr(s,len);// Find the string score of this round of recursion and 

    sum+=f(s+1,len-1);// Recursively find the sum of other strings 
    return sum;// Returns the score and of all strings 
}

int main()
{
    
    char s[MAX];// Open array 
    int sum,len;

    scanf("%s",&s);// Input string 

    len=strlen(s);// Find the length of the input string 
    
    printf("%d",f(s,len));// Print the results 

    return 0;
}

2. Statistical contribution value

#include<stdio.h>
#include<string.h>

#define MAX 100000// Maximum length 

typedef long long int LLint;

int main()
{
    
    LLint i,len,sum=0;
    int a[26]={
    0}; // Used to count the number of characters 
    char s[MAX];

    scanf("%s",s);// Input string 

    len=strlen(s);// Find the length of the input string 

    // Find the sum of string scores 
    for(i=0;i<len;i++)
    {
    
        if(a[s[i]-'a']==0)// Judge whether the character has appeared 
        {
    
            sum=sum+(i+1)*(len-i);// Add up the values of individual characters 
            a[s[i]-'a']=i+1;// Where to save characters 
        }
        else
        {
    
            sum=sum+(i+1-a[s[i]-'a'])*(len-i);// Characters that have appeared before , Now the value that appears again 
            a[s[i]-'a']=i+1;// Update location 
        }
    }

    printf("%lld",sum);// Printout 
    return 0;
}

Four 、 Evaluation results

1. Recurrence of violence

It's just past 50% Test point of , Later test points will time out

2. Statistical contribution value

---

5、 ... and 、 Summarize and evaluate

In conclusion, we can see that , Although the idea of recursive method is clear , Write simple , But it's more violent, and the time complexity is higher ; And the method of statistical contribution value , It's not easy to think of , But it's very simple .
therefore , If we live in a picture , Always jump out , Take a look at the picture , Jumping back , Instead of working hard , Sometimes choice is more important than effort .

If you have any questions, you are welcome to point out
The Blue Bridge Cup series will continue to be updated , Welcome to your attention , Learning together