A题_题目描述

给定一段字符串S，问有多少字串由KICK开头，START结尾

算法1

(遍历) $O(n)$

C++ 代码

#include<stdio>
using namespace std;
long long res = 0; kick = 0;
int solve(string &s){
    for (int i = 0; i < s.length; i++){
        if (s[i] == 'K' && s[i+1] == 'I' && s[i+2] == 'C' && s[i+3] == 'K')
            kick ++;
        if (s[i] == 'S' && s[i+1] == 'T' && s[i+2] == 'A' && s[i+3] == 'R' && S[i+4] == 'T')
            res += kick;
    }
    return res;
}

Kadane Algorithms

第二题 待续

在一个非负矩阵，选任意位置为起点。只能左上和右下移动，并且累计路径和。
求最大路径和。

思路

其实只有一条直线要考虑。统计对角线数字之和

c++代码

int solve(int &N){
    vector<long long> count(N + N);
    long long res = 0;
    for (int i = 0; i< N; ++i){
        for (int j = 0; j < N; ++ j){
            int x;
            cin >> x;
            count[i - j + N] += x; //避免是负的，数组这样不会越界
            res = max(res, count[i - j + N]);
        }
    }
    return res;
}

Python版

def solve(N, A):
    count = [0] * N * 2
    for i in range(N):
        for j in range(N):
            count[i - j] += A[i][j]
    return max(count)

Kadane Algorithms

第三题 Merge Cards 合并卡片

题目

N堆石子，每次可以merge相邻a和b，获得分数a+b
求最后得分的期望是多少

思路

DP 优化

[暴力法TLE: dp[i][j] 表示合并从A[i]到A[j]的得分期望, 对于区间(i, j). 枚举最后一次merge位置]
[优化]
begin[i] 表示，所有从A[i] 开始区间期望和
end[j] 表示，所有从A[j] 结束的区间期望和
对于区间(i, j), 需要(begin[i] + end[j]) / (j - i)
得到merge合并之前的分数期望，
最后加上最后一次merge的分数psum[j + 1] - psum[i]
$O(N^2)$ 空间同时间

c++

double solve(){
    for (int i = 0; i < n ; ++i){
        psum[i + 1] = psum[i] + A[i];
        b[i] = e[i] = 0;
    }
    for (int k = 2; k <= n; ++k){
        for (int i = 0, j = k -1; j < n; ++ i; ++ j){
            dp[i][j] = (b[i] + e[j]) / (k -1) + psum[j + 1] - psum[i];
            b[i] += dp[i][j];
            e[j] += dp[i][j];
        }
    }
    return dp[0][n - 1];
}

更好解法 看A[i]对res结果的贡献系数

最边上的数，调和级数求和
中间的数，（更有可能被merge多次）贡献系数越大

double solve(){
    double res = 0;
    for (int i = 0; i + 1 < n; ++ i){
        for (int j = 0; j <= i; ++ j){
            res += 1. / (i - j + 1) * A[j]; //贡献系数取决于A[i]到A[j]的距离，越靠近贡献越大，最近的最大1，然后1/2, 1/4... 即调和级数求和
        }
        for (int j = i + 1; j < n; ++ j){
            res += 1. / (j - i) * A[j];
        }
    }
    return res;
}

第四题 组合锁 Combination Lock

一会写