12.2.md

12.2-12.8 Learning Notes

Java

变量

写OJ题就public static

• 静态
• 实例
• 类

SecondMST

次小生成树

暴力枚举不在最小生成树中的边(u,v,w)（称为无用边）
求最小生成树中u-v的权值最大的边，用当前枚举到的无用边（称为关键边）替换权值最大的边，得到一棵生成树。
枚举所有无用边后，取最大的生成树即为次小生成树。

用倍增+LCA求u-v中权值最大的边 O(nlogn)（不包括求最小生成树的复杂度）

严格次小生成树

https://www.luogu.com.cn/problem/P4180 倍增时多维护一个u-v上的严格次大值

long long calSecondMax(long long maxn1, long long maxn2, long long secondmaxn1, long long secondmaxn2)
{
    if (maxn1 > maxn2)
    {
        return max(maxn2, max(secondmaxn1, secondmaxn2));
    }
    if (maxn1 < maxn2)
    {
        return max(maxn1, max(secondmaxn1, secondmaxn2));
    }
    if (maxn1 == maxn2)
    {
        return max(secondmaxn1, secondmaxn2);
    }
    return 0;
}
//dfs中初始化倍增数组
for (long long i = 1; (1 << i) <= depth[u]; i++)
    {
        f[u][i] = f[f[u][i - 1]][i - 1];
        wMax[u][i] = max(wMax[u][i - 1], wMax[f[u][i - 1]][i - 1]);
        wSecondMax[u][i] = calSecondMax(wMax[u][i - 1], wMax[f[u][i - 1]][i - 1], wSecondMax[u][i - 1], wSecondMax[f[u][i - 1]][i - 1]);
    }
//计算u-v最大边权
//keyweight是关键边长度
long long calUtoVMaxWeight(long long u, long long v, long long keyweight)
{
    long long umaxWeight = -INF;
    long long vmaxWeight = -INF;
    if (depth[u] < depth[v])
    {
        swap(u, v);
    }
    for (long long j = maxDepth; j >= 0; j--)
    {
        if (depth[u] > depth[v] && depth[f[u][j]] >= depth[v])
        {
            //当关键边长度=最大边权时，取严格次大值
            if (wMax[u][j] < keyweight)
                umaxWeight = max(umaxWeight, wMax[u][j]);
            else
                umaxWeight = max(umaxWeight, wSecondMax[u][j]);
            u = f[u][j];
        }
    }
    if (u == v)
        return umaxWeight;
    for (long long j = maxDepth; j >= 0; j--)
    {
        if (f[u][j] != f[v][j])
        {
            // 两种写法等价
            // 1.求四个数中的严格次小值
            // long long maxn = max(wMax[v][j], wMax[u][j]);
            // long long minx = min(wMax[v][j], wMax[u][j]);
            // if (maxn < keyweight)
            // {
            //     maxWeight = max(maxWeight, maxn);
            // }
            // else if (minx < keyweight)
            // {
            //     maxWeight = max(max(minx, maxWeight), max(wSecondMax[v][j], wSecondMax[u][j]));
            // }
            // else
            // {
            //     maxWeight = max(maxWeight, max(wSecondMax[v][j], wSecondMax[u][j]));
            // }

            // 2.LCA(u,v)左右子树分开来计算，最后再合并
            if (wMax[u][j] < keyweight)
                umaxWeight = max(umaxWeight, wMax[u][j]);
            else
                umaxWeight = max(umaxWeight, wSecondMax[u][j]);
            u = f[u][j];

            if (wMax[v][j] < keyweight)
                vmaxWeight = max(vmaxWeight, wMax[v][j]);
            else
                vmaxWeight = max(vmaxWeight, wSecondMax[v][j]);
            v = f[v][j];
        }
    }
    long long j = 0;
    if (wMax[u][j] < keyweight)
        umaxWeight = max(umaxWeight, wMax[u][j]);
    else
        umaxWeight = max(umaxWeight, wSecondMax[u][j]);

    if (wMax[v][j] < keyweight)
        vmaxWeight = max(vmaxWeight, wMax[v][j]);
    else
        vmaxWeight = max(vmaxWeight, wSecondMax[v][j]);
    return max(umaxWeight, vmaxWeight);
}

Opencv

install

visual studio is ok
vscode is hard to configure

color detection

https://www.opencv-srf.com/2010/09/object-detection-using-color-seperation.html

use HSV to select certain color
色调、饱和度、亮度

HUE is unique for that specific color distribution of that object
SATURATION and VALUE may be vary according to the lighting condition of that environment

You have to find the exact range of HUE values according to the color of the object
The SATURATION and VALUE is depend on the lighting condition of the environment as well as the surface of the object.

Morphological Dilation and Erosion

降噪算法
https://ww2.mathworks.cn/help/images/morphological-dilation-and-erosion.html

Dilation adds pixels to the boundaries of objects in an image, while erosion removes pixels on object boundaries.

The number of pixels added or removed from the objects in an image depends on the size and shape of the structuring element used to process the image

dilation

补漏洞
The value of the output pixel is the maximum value of all pixels in the neighborhood

erosion

去除小点
The value of the output pixel is the minimum value of all pixels in the neighborhood

调参游戏

holding self-driving boat competition

设计无人船比赛方案

locating and navigation

• IMU
• 超声波
• UWB
• CV
• DR算法

卡尔曼滤波

https://blog.csdn.net/u010720661/article/details/63253509
（假装自己看得懂）