算法题中的神技

神技

记录网上看到的，泛用性较强的解题神技，持续更新

前缀“乘”

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

往往前缀和，当用乘法表示加和时，是会很容易爆ll的，那么，我们可以通过 \(log\) 对数将乘法转换成加法，把之转化成真正的前缀“和“。尽管，我们无法得到精确的值，但用来作为条件判断已经足够了

前缀和求解转化为

$ ps[i] = ps[i-1]+log(nums[i])$

求 \([l,r]\) 的乘积小于 \(k\) 可表示为

\(ps[m]-ps[i-1]+10^{-10}<logk\)

double 类型只能保证 \(15\) 位有效数字是精确的。为了避免计算带来的误差，相减后要加上 \(10^{-10}\)（题目中的 double 数值整数部分的数字不超过 5 个） ，从而防止不等式两边数值相等却被判定为大于的情况。

浮点数的妙用

Problem - B - Codeforces

对于这个题，我们想要找到大于从最高处下滑的所需时间 \(tn\) ，又想让结果处靠近山底。

由于耗时的计算涉及浮点数精度，考虑精度的影响，又不想用其它整型的方法，这里有如下妙用：

对于一道题，存在浮点数 \(t\) ，题目的计算中，找到最小需要的精度，针对这道题，就是距离/速度的 \(c\) ，观察测试集的数值大小，距离最大为 \(1\) ，速度最大为 \(10^3\) ，也就是说，不会有相差为 \(10^{-3}\) 的答案，考虑到浮点数精度的影响，不妨再降低几个数量级，比如 \(10^{-6}\) 等，但太小也不行，若两个数在这个范围内，我们认为他们是相等的。

这里设 \(c\) 为允许的误差精度。

  • 想要找到大于等于 \(t\) 的一个数 \(a\) ，我们就允许 \(a\) + \(c\) > \(t\)

  • 想要找打小于等于 \(t\) 的一个数 \(a\) ，我们就允许 \(a-c<t\) （当然 \(a<t+c\) 也是可以的）

  • 通过第一个找到预备答案 \(ans\) 后，由于题目要求耗时相等且接近山底的数 \(a\) （第二种情况）

    • 想要保留第一个找到的数（从山底的滑梯开始遍历），让 \(ans-c < a\) ，否则，更新 \(ans\)

    • 想要保留最后找到的数，让 \(a-c < ans\) ，更新 \(ans\)

    • 若想要找到满足条件第 \(k\) 个数，可考虑使用 \(vector\) 记录，或者设置一个记录变量，此时要判断两数相等

  • 判断相等，对数 \(a\) 与 \(b\) ，同时满足 \(a+c > b\) 且 \(b+c > a\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>

using namespace std;
const int N = 1e3+10;
int h[N];
double tn;

double cal(int x){
    double t = 0;
    double v = 1.;
    for(int i=x;i>=1;i--){
        t += (h[i]-h[i-1])/v;
        v += (h[i]-h[i-1]);
    }
    return t;
}



int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> h[i];
    int l=1,r=n; //预处理h[n]的速度
    tn = cal(n);
    int ans = n;
    double anst = tn;
    bool flag = true;
    for(int i=1;i<n;i++){
        double c = cal(i);
        if(flag){
            if((c-1e-6)<tn){
                ans = i;
                anst = c;
                flag =false;
            }
        }
        else if(c<(anst-1e-6)){
            ans = i;
            anst = c;
        }
    }
    cout << ans;
    
}