T1 最小值

水题，直接遍历即可，注意看题目要求的输出格式，一开始没注意在这里 WA 了一发。
时间复杂度 $O(n)$

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    int a, b;
    int minA = 0, minB = 0;
    while( n -- ){
        cin >> a >> b;
        if(minA == 0 && minB == 0){
            minA = a;
            minB = b;
        }else if(minA * b > a * minB){
            minA = a;
            minB = b;
        }
    }

    double res = m*minA*1.0/minB;
    printf("%.6f", res);

    return 0;
}

T2 出现次数

KMP 的模板题，每次匹配完成的时候记录的变量加一即可。
时间复杂度 $O(qn)$

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1010;

char s[N], t[N];

int ne[N];
int n, m, q;

int patternMatch(int l, int r){

    int res = 0;
    for(int i = 2, j = 0; i<= m; i ++){
        while(j > 0 && t[j+1] != t[i])j = ne[j];
        if(t[j+1] == t[i])j ++;
        ne[i] = j;
    }

    for(int i = l, j = 0; i <= r; i ++){
        while(j > 0 && t[j+1] != s[i])j = ne[j];
        if(t[j+1] == s[i])j ++;
        if( j == m ){
            res ++;
            j = ne[j];
        }
    }

    return res;
}

int main(){
    scanf("%d%d%d", &n, &m, &q);
    scanf("%s%s", s+1, t+1);
    int l, r;
    while( q -- ){
        scanf("%d%d", &l, &r);
        cout << patternMatch(l, r) << endl;
    }

    return 0;
}

T3 满二叉树等长路径

二叉树的结构为分治的想法提供了天然的便利。我首先考虑了一下分治的做法。
base case 是 trivial 的，即只有一个节点的满二叉树，显然此时答案是 0.
对于一个有左右子树的二叉树来说，如果已经递归解决了左右子树的问题，那么原问题的解就是对于左右子树的解再加上当前根节点到左右子树的叶子节点的距离之差，即 (ldis + height[leftSubTree] - rdis - height[rightSubTree]). 其中 ldis 和 rdis 分别是当前根节点到左右儿子的距离。
算法复杂度分析
$T(n) = 2T(n/2) + O(1)$
画出递归树可以解得：
$T(n) = O(n)$
这里的 n 不是题目中的 n，而是二叉树的节点数目。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 1 << 11;
int n;
int t[N];
int height[N];

bool isleaf(int root){
    if(root * 2 <= (1<<(n+1)) || root * 2 + 1 <= (1 << (n+1)))return false;
    return true;
}

int dfs(int root){
    if(isleaf(root)){
        height[root] = 0;
        return 0;
    }
    int lcost = dfs(2*root);
    int rcost = dfs(2*root+1);
    int ldis = t[2*root];
    int rdis = t[2*root+1];
    int res = abs(height[2*root] + ldis - height[2*root+1] - rdis);
    res += lcost + rcost;
    height[root] = max(height[2*root] + ldis, height[2*root+1] + rdis);
    return res;
}

int main(){
    scanf("%d", &n);
    for(int i = 2; i < (1<<(n+1)); i++){
        scanf("%d", &t[i]);
    }
    cout << dfs(1) << endl;

    return 0;
}