蓝桥杯真题练习【第十一届】【省赛】【B组】

成绩分析子串分值和

四舍五入用了这个：
n u m num num四舍五入到小数点后n位
n u m = ( f l o o r ( n u m + 5 × 1 0 − n + 1 ) × 100 ) / 100 num=(floor(num+5×10^-n+1^)×100)/100 num=(floor(num+5×10−n+1)×100)/100
或者
n u m = ( c e i l ( n u m − 5 × 1 0 − n + 1 ) × 100 ) / 100 num=(ceil(num-5×10^-n+1^)×100)/100 num=(ceil(num−5×10−n+1)×100)/100

#include
using namespace std;
const int N=1e5+10;
int a[N];
int maxx=0,minn=100;
int main(){
    int n;cin>>n;
    double all=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxx=max(maxx,a[i]),minn=min(minn,a[i]);
        all+=a[i];
    }
    double eval=(floor((all/n+0.005)*100)/100);
    printf("%dn%dn%.2lf",maxx,minn,eval);
    return 0;
}

回文日期
感觉枚举会超时，所以通过打表将全部合法的回文日期和ABABBABA型日期保存下来（升序），然后二分查找。

先判断日期是否合法，再判断是否为回文

#include
using namespace std;
int a[10];
int n1=9899;
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool legal(int year,int month,int day){
    if((year%4==0&&year%100!=0)||year%400==0)mon[2]++;
    if(month>0&&month<13&&day>0&&day 
保存ABABBABA型的日期
 
#include
using namespace std;
const int n1=354;
int a[n1]={打表出来的n1个回文日期};
int b[10];
int main(){
    freopen("output.txt","w",stdout);
    int cnt=0;
    for(int i=0;i 
直接输出表中的答案
 
#include
using namespace std;
const int n1=354;
const int n2=12;
int a[n1]={打表出来的n1个回文日期};
int b[n2]={打表出来的n2个ABABBABA型的日期};
int main(){
    int date;cin>>date;
    cout< 
子串分值和 
子串无法枚举，有很多情况都是重复的，因为一个子串后再加上一个字符形成新的子串，如果该字符已经在原来的子串中出现过了，那么新子串的分值和原来一样，否则应该在原子串的分值基础上加1。应该就是由这个基本的子串间转换删除冗余时间和空间来获得答案。
 考虑dp，由小的子串形成新的字符。用到dp首先用目标状态来确定状态设置和状态转移方程。最终的答案是由整个字符串的子串的分值和，我们设
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       dp[i]
      
     
    dp[i]为以
    
     
      
       
        i
       
      
      
       i
      
     
    i为结尾 位置的子串分值和。最后
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        n
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       dp[n-1]
      
     
    dp[n−1]即为答案。用上面的子串间转换来确定状态转移方程：前面
    
     
      
       
        i
       
       
        −
       
       
        1
       
      
      
       i-1
      
     
    i−1个的子串分值和已经求得，现在多了一个字符，以递增的新子串个数枚举包含新加的字符而产生的新子串：
 包含一个字符的新子串：1
 包含两个字符的新子串 ：若
    
     
      
       
        s
       
       
        t
       
       
        r
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        =
       
       
        =
       
       
        s
       
       
        t
       
       
        r
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       str[i-1]==str[i]
      
     
    str[i−1]==str[i]，则答案为1，否则答案为2
 …
 考虑到数据范围是
    
     
      
       
        1
       
       
        e
       
       
        5
       
      
      
       1e5
      
     
    1e5，因此查找长度的复杂度应该缩小，我思考了一个复杂度为O(nlog2n)的做法：二分＋st表。因为是静态的，并且在考虑新子串时需要计算
    
     
      
       
        第
       
       
        i
       
      
      
       第i
      
     
    第i个字符是否有出现过，考虑使用st表。二分查找最后一个位置
    
     
      
       
        k
       
      
      
       k
      
     
    k，使得从第
    
     
      
       
        0
       
      
      
       0
      
     
    0个位置到第
    
     
      
       
        k
       
      
      
       k
      
     
    k个位置字符
    
     
      
       
        s
       
       
        t
       
       
        r
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       str[i]
      
     
    str[i]的出现次数为0，则从
    
     
      
       
        k
       
       
        +
       
       
        1
       
      
      
       k+1
      
     
    k+1到
    
     
      
       
        i
       
       
        −
       
       
        1
       
      
      
       i-1
      
     
    i−1，
    
     
      
       
        s
       
       
        t
       
       
        r
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       str[i]
      
     
    str[i]没有出现，因此可由
 其实还是隔开了很多的字符，最后一个出现
    
     
      
       
        s
       
       
        t
       
       
        r
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       str[i]
      
     
    str[i]的位置，后面的将答案*2,前面的答案不变。