头像

Mrhh

西南科技大学


访客:11574

离线:1小时前


分享 扫描线

Mrhh
22小时前

鸡肋算法只能解决下列一种问题, 但难度却很大.
实例讲解



活动打卡代码 AcWing 247. 亚特兰蒂斯

Mrhh
22小时前

Analysis

  • 即此测试用例中所有矩形的面积并,注意如果一片区域被多个地图包含,则在计算总面积时只计算一次
线段树维护一个cnt, 表示区间被多少个矩形覆盖, **cnt>0, hi就加上该区间长度**
  • 1≤n≤10000, 0≤x1<x2≤100000, 0≤y1<y2≤100000
10000*100000=1e9, 不需要开longlong

Thoughts

将扫描线拉开, 二分建线段树, 每个区间节点维护两个信息,
cnt: 该段区间被多少矩形(所有矩形, 包括前面的矩形)覆盖次数,
len: 区间内被当前(不算之前的矩形竖边, 类似sum, 是由子节点算来的, 与父节点无关)矩形竖边覆盖的最大长度。(区间查询, like区间和)
当扫描线扫过矩形的右竖边时, 我们可以知道竖边之后, 就没有面积了。
扫描线扫到的矩形左竖边, 对应的竖边在y轴上的区间所有点+1, 右竖边则-1. (每个矩形就相当于是一次区间修改, 我们可以将其转化为竖边的边权, 左竖边边权为1, 右为-1)

Notices

区间修改无需懒标记 -> 这道题特别特殊, 并不是说所有的扫描线的的题都不需要pushdown

query: 每次查询(计算相邻两条扫描线之间的面积大小)都是查询整条扫描线上覆盖的区域(根节点), query(1, l, r)就直接返回了, 就不需要pushdown了

modify:
区间加:
1. 加之前区间值为0(加之前没有矩形覆盖该区间), 那么也就是说tr[u].cnt == 0, pushdown函数中, 为0就不需要操作了, 故可以省略;
2. 加之前区间值为正, 那你加了值, 区间矩形覆盖数cnt依然大于0, 我们只统计cnt>0的区间, 所以只要你大于0, 是多少都无所谓; (而像其他线段树区间修改的题, 值的变化会影响查询和ans的值)
区间减: 所有操作成对且重合(错开就不行了)出现, 先加后减, 所以区间值肯定大于等于0
1. 减之后值为0, 该点的cnt是由pushup(如果cnt==0, len就用子区间算, 如果大于0, 就用节点的len)子区间算得的, 而查询时子区间的值没有变动所以, 会重新更新回来, 自然也就不需要pushdown了;
2. 减之后值依然为正, 同上, 只要为正即可。

离散化
因为坐标可能为浮点数, 所以区间上的点可能无穷多个.

线段树数组需要开8倍
N为区间中点的个数, n个线段, 每个线段2个点, 点数为2n, 数组空间开4 * 2n

本题的坐标系并不影响求面积, 所以我们也可以通过正常建点, 建系求解, 见code

区间建点 (原因见代码注释)
23.png

Time complexity

$O(nlogn)$ (n段需要n次查询, 根节点的len, 每次查询logn)

Accepted Code

/*
 * 这颗线段树开始所有维护的节点属性都是0
 */

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;

struct seg
{
    double x, y1, y2;
    int k;
}segs[N * 2]; // 一个矩形两条竖边权值不同
struct sgt
{
    int l, r;
    int cnt;
    double len;
}tr[N * 8];
vector<double> ys;

int find (double y)
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

bool operator < (const seg &a, const seg &b)
{
    return a.x < b.x;
}

void pushup (int u)
{
    if(tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    else if (tr[u].l != tr[u].r)
    {
        tr[u].len = tr[u<<1].len + tr[u<<1|1].len;
    }
    else tr[u].len = 0;
}

void build (int u, int l, int r)
{
    tr[u] = {l, r, 0, 0}; // 所有点都一样只是看他有没有儿子节点
    if(l != r)
    {
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid + 1, r);
        // 这里不需要pushup, 因为这颗新建线段树的cnt, len都为0, 不想一般的线段树的叶子节点的sum是有值的
    }
}

void modify (int u, int l, int r, int k)
{
    if(tr[u].l >= l && tr[u].r <= r) 
    {
        tr[u].cnt += k;
        pushup(u);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u<<1, l, r, k);
        if(r > mid) modify(u<<1|1, l, r, k);
        pushup(u);
    }
}

int main ()
{
    int T = 1;
    while(cin >> n, n)
    {
        ys.clear();
        int j = 0;
        for(int i = 1 ; i <= n ; i ++ )
        {
            double x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            segs[j ++ ] = {x1, y1, y2, 1};
            segs[j ++ ] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);
        }

        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        build(1, 0, ys.size() - 2); // 区间点, 数量还要少一个

        sort(segs, segs + n * 2);

        double res = 0;
        for(int i = 0; i < n * 2; i ++ ) // 模拟扫描线扫描
        {
            if(i > 0) res += tr[1].len * (segs[i].x - segs[i - 1].x); // 第一根线不算 只需要查根节点
            /*
            假如我们要将区间1~5全部加上一个数, 一般的线段树是维护编号为1,2,3,4,5这五个点, 加上这个数, 
            但是本题是要将这个区间的所有点全部修改, 也就是说如果线段树中区间节点中的节点还是一个点的话, 
            那么modify(1~5), 进去之后, modify(1~2), modify(3~5), 那么也就是说2~3这段区间并没有被修改,
            因此, 我们通过将区间节点的中的节点, 定义为一段编号到编号加1的区间, 即可解决
            即根节点区间l = y1~y2 + y2~y3 + ... + (yn-1~yn), 所以下面区间右端点要减1, l~r, yl~yr-1
            */
            modify(1, find(segs[i].y1), find(segs[i].y2) - 1, segs[i].k);
        }

        cout << "Test case #" << T ++ << endl;
        printf("Total explored area: %.2lf\n", res);
        puts("");
    }

    return 0;
}



Mrhh
1天前
#include <iostream>

using namespace std;

typedef long long ll;

const int N = 100010;

int n, m;

struct sgt
{
    int l, r; // 编号
    ll sum;
    ll add;
}tr[N * 4]; // 数的个数的4倍
int w[N];

void pushup (int u)
{
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void pushdown (int u)
{
    sgt &root = tr[u];
    sgt &lc = tr[u<<1];
    sgt &rc = tr[u<<1|1];

    if(root.d)
    {
        lc.add += root.add; lc.sum += (ll)(lc.r - lc.l + 1) * root.add;
        rc.add += root.add; rc.sum += (ll)(rc.r - rc.l + 1) * root.add;
        root.add = 0;
    }
}

void build (int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[r], 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid + 1, r);
        pushup(u);
    }
}

void modify (int u, int l, int r, int d) // 类似query操作的思想
{
    if (tr[u].l >= l && tr[u].r <= r) // 将区间分成几段来修改
    {
        /*
        区间修改logn的优化点: 
        这段区间在查询区间[l, r]内部了, 那么就可以把这段区间的sum加上d, 而不需要再对其子区间进行加减了, 因为查询区间[l, r]时, 当查询到这里时, 就会返回了, 从而达到一个优化作用. 
        当其他更小的区间修改操作时, 再通过该区间节点add, pushdown.
        */
        tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u<<1, l, r, d);
        if(r > mid) modify(u<<1|1, l, r, d);
        pushup(u);
    }
}

ll query (int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u); // 当查询的区间很小时, 我们就需要更新该点了, 将其前面的所有祖宗节点的add加上. 现查询现修改
    int mid = tr[u].l + tr[u].r >> 1;
    ll sum = 0;
    if(l <= mid) sum = query(u<<1, l, r);
    if(r > mid) sum += query(u<<1|1, l, r);
    return sum;
}

int main ()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++ ) cin >> w[i];
    build(1, 1, n);

    char op[2];
    int l, r, d;

    while(m -- )
    {
        cin >> op >> l >> r;
        if(*op == 'C')
        {
            int d;
            cin >> d;
            modify(1, l, r, d);
        }
        else printf("%lld\n", query(1, l, r));
    }

    return 0;
}



Mrhh
2天前

min,max运算重要结论

1 + 1/2 + 1/3 + … + 1/n 数列和

快速计算log2(10 ^ x)

整除(gcd)

  • 如果a|b, a|c, 那么a|(b - c), a|(b + c)



Mrhh
2天前

注意了, 最长连续子段, 连续不一定是升序啊!!!

Accepted Code

/*
结构体维护变量:
- 求最大子段和需要子区间的最大后缀和, 最大前缀和(tmax = max(left_tmax, right_tmax, left_rmax+right_lmax)
- 求最大前后缀和需要区间和(lmax = left_sum+right_lmax, left_lmax)
*/

#include <iostream>

using namespace std;

const int N = 500010; // 区间长度(区间数的个数)

int n, m;

struct sgt
{
    int l, r; // 编号
    int sum; // 区间和
    int qmax; // 最大前缀和
    int hmax; // 最大后缀和
    int tmax; // 最大连续子段和
}tr[N * 4];
int w[N];

void pushup (sgt &u, sgt &l, sgt &r)
{
    u.sum = l.sum + r.sum;
    u.qmax = max(l.qmax, l.sum + r.qmax);
    u.hmax = max(r.hmax, r.sum + l.hmax);
    u.tmax = max(max(l.tmax, r.tmax), l.hmax + r.qmax);
}

void pushup (int u)
{
    pushup(tr[u], tr[u<<1], tr[u<<1|1]);
}

void build (int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[l], w[l], w[l], w[l]};
    else
    {
        tr[u] = {l, r}; // 区间的特性就要通过他的子节点来算了
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid + 1, r);
        pushup(u);
    }
}

void modify (int u, int id, int v)
{
    if(tr[u].l == id && tr[u].r == id) tr[u] = {id, id, v, v, v, v};
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(id <= mid) modify(u<<1, id, v);
        else modify(u<<1|1, id, v);
        pushup(u);
    }
}

sgt query (int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if(l > mid) return query(u<<1|1, l, r);
    else if(r <= mid) return query(u<<1, l, r);
    else
    {
        sgt ans1 = query(u<<1, l, r);
        sgt ans2 = query(u<<1|1, l, r);
        sgt res;
        pushup(res, ans1, ans2);
        return res;
    }
}

int main ()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++ ) cin >> w[i];
    build(1, 1, n); // 注意l, r是编号, 不是值

    sgt ans;
    while(m -- )
    {
        int k, x, y;
        cin >> k >> x >> y;

        if(k == 1)
        {
            if(x > y) swap(x, y);
            ans = query(1, x, y);
            cout << ans.tmax << endl;
        }
        else modify(1, x, y);
    }

    return 0;
}


活动打卡代码 AcWing 1275. 最大数

Mrhh
2天前

RMQ算法解决区间最大值, 只能解决静态区间最大值(即查询时数不会变了)。
动态区间最大值(相对静态而言的, 比如123, 当前查询整个区间的最大值为3, 当我插入第四个数4时, 区间最值就变化了)需要用线段树来求解。

Analysis

  • 添加操作:向序列后添加一个数,序列长度变成 n+1;
等价于先开足够大的区间, 再修改

Accepted Code

#include <iostream>

using namespace std;

const int N = 200010;

int m, p;

struct
{
    int l, r, v;
}tr[N * 4];

void pushup (int u) // 子节点修改父节点信息
{
    tr[u].v = max(tr[u<<1].v, tr[u<<1|1].v);
}

void build (int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    if(l == r) return ;
    int mid = l + r >> 1;
    build(u<<1, l, mid), build(u<<1|1, mid + 1, r);
}

int query (int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if(l <= mid) v = query(u<<1, l, r);
    if(r > mid) v = max(v, query(u<<1|1, l, r));

    return v;
}

void modify (int u, int id, int value)
{
    if(tr[u].l == id && tr[u].r == id) tr[u].v = value;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(id <= mid) modify(u<<1, id, value);
        else modify(u<<1|1, id, value);
        pushup(u);
    }
}

int main ()
{
    int n = 0;
    cin >> m >> p;
    build(1, 1, m);

    int k = 0, mmax = 0;
    while(m -- )
    {
        char op[2];
        scanf("%s", op);

        cin >> k;
        if(*op == 'Q')
        {
            mmax = query(1, n - k + 1, n);
            printf("%d\n", mmax);
        }
        else
        {
            modify(1, n + 1, (mmax + k) % p);
            n ++ ;
        }
    }

    return 0;
}



Mrhh
2天前

区间维护问题

动态维护 (对区间维护问题的两个操作求和和修改的时间复杂度做一个均衡, 使得总复杂度降低, 同时支持两种操作)

修改和维护时间复杂度都是$O(logn)$, 但是线段树常数大一些$O(4logn)$, 树状数组$O(logn)$

  • 线段树: 维护的是任意区间和, 以及区间最值。
  • 树状数组: 能维护前缀区间的最值和前缀和, 可求任意区间和, 但是不能维护任意区间最值。
    因为1~10的最大值和1~5的最大值取一个max, 它不一定是5~10的最大值。
    线段树与树状数组的区别

静态维护 (只维护, 不能够在中途添加元素, 开始就给定区间元素, 要实现也是可以暴力做动态维护的, 但是由于修改的时间复杂度过高会导致时间复杂度很高, 不考虑, 要动态维护就用数据结构)

  • RMQ: 维护任意区间最值
  • 前缀和算法: 维护前缀区间和, 前缀区间最值, 可求任意区间和.

区间操作问题

  • 贪心


分享 线段树

Mrhh
2天前

定义:除开最后一层是满二叉树
存储形式:一维数组(堆的储存形式)
算法原理: 我们将查询区间分成几段, 在线段树中找到这几段区间, 根据这几段区间的属性(比如最大值), 求出查询区间的属性(最值). 线段树中的分段必定不会重叠, 按照算法查询下去, 最后合格的几段拼在一起正好就是查询区间. (这个可以画图理解一下, 同时从原理上也是很好理解的, 因为线段树上划分的区间都无重叠, 那你两路合格的区间也一定没有重叠)
算法时间复杂度
因为线段树是每次二分直到分到某一个值为止, 二分时间复杂度就是它的时间复杂度。
区间, 单点修改: $O(4logn)$
查询: $O(4logn)$
所有操作
1. pushup
2. pushdown(维护懒标记, 延迟标记)
3. modify -> 单点(不需要懒标记也能logn, 该算法根本不需要用到懒标记), 区间(会用到pushdown, 不用的话时间复杂度无法保证logn) $O(logn)$
4. query $O(logn)$
5. build(将一段区间初始化为线段树)
线段树基本要素
1. 结构体节点(结构体节点中的需要维护的变量, 根据我们看父节点的特性, 需要子节点的哪些特性才能够求出来, 那么结构体就需要维护那些特性, 当然查询的变量时一定要存的)
2. 父节点 x >> 1
3. 右子节点 x << 1
4. 左子节点 x << 1 | 1
注意事项

  • 线段树的储存数组大小一般开4 * N的空间。
  • 子区间无交集, 分界点为下取整。

区间修改<利用查询操作的思想和懒标记实现logn时间复杂度>
1. 使用前提: 懒标记只有在需要将区间所有数改变为某个数的时候才必须用, 当对区间加减操作时, 可以用差分解决, 懒标记能不用尽量不用, 因为容易错且复杂。
2. 时间复杂度: $O(logn)$
3. 实例讲解
1.png
注意查询操作的一点小变化, 查询区间小于所有已修改区间时, 现查询现修改~
4. F.A.Q
- 什么是懒标记? 懒标记其实就是线段树中一个结构体节点中需要累加维护的变量, 我们通过pushdown操作来维护.

区间问题 – Segment tree, BIT, RMQ, 前缀和, 贪心
线段树与树状数组的区别




Mrhh
3天前

假设数组长度为n。

线段树和树状数组的基本功能都是在某一满足结合律的操作(比如加法,乘法,最大值,最小值)下,O(logn)的时间复杂度内修改单个元素并且维护区间信息。

不同的是,树状数组只能维护前缀“操作和”(前缀和,前缀积,前缀最大最小),而线段树可以维护区间操作和。

但是某些操作是存在逆元的,这样就给人一种树状数组可以维护区间信息的错觉:维护区间和,模质数意义下的区间乘积,区间xor和。能这样做的本质是取右端点的前缀和,然后对左端点左边的前缀和的逆元做一次操作,所以树状数组的区间询问其实是在两次前缀和询问。

所以我们能看到树状数组能维护一些操作的区间信息但维护不了另一些的:最大/最小值,模非质数意义下的乘法,原因在于这些操作不存在逆元,所以就没法用两个前缀和做。

而线段树就不一样了,线段树直接维护的就是区间信息,所以一切满足结合律的操作都能维护区间和,并且lazy标记的存在还能使线段树能够支持区间修改,这点是树状数组做不到的。

可以说树状数组能做的事情其实是线段树的一个子集,大多数情况下使用树状数组真的只是因为它好写并且常数小而已。

不过随着zkw线段树的普及,树状数组仅有的两点优势也不复存在了……估计要成为时泪了吧。



活动打卡代码 AcWing 1165. 单词环

Mrhh
5天前

知识点总结

Fullibility

  1. 建图: 如果我们将每个字符串看作一个点, 那么边数最坏10^10, 点数10^5, 无论是时间空间任何一种算法必将爆掉

Solution

  1. build the graph
    12.png
    因为最多10^5个字符串嘛~

  2. 01分数规划
    第一个串能与第二个串相连,第二个串能与第三个串相连,第三个串能与第一个串相连,我们按照此顺序相连,便形成了一个环串,长度为 5+7+10=22(重复部分算两次),总共使用了3个串,所以平均长度是 22/3≈7.33。

max(Σwi / k)
- 确定二分区间
0 ~ 1000 * k / k
- 求最大值得到check不等式
Σwi / k > mid
=> Σwi > k * mid
=> Σwi - k * mid > 0
=> Σ(wi - mid * 1) > 0 -> 即正环 最长路边数大于n-1

优化点1: 如果mid为0的时候, wi都为负, 最终l = r = 0, 平均长度为0, 即无环, 直接输出no solution

当queue超时时, 我们不妨试一下将spfa的queue改成stack, 有时候搜索的顺序可能影响找到负环的快慢

Queue Accepted Code (track way)

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1010, M = 100010, K = 1010; // K是顶点的值, N是顶点的在队列中的编号, 即顶点个数

int n; // 边数

int h[K], e[M], ne[M], w[M], idx;
int q[N], cnt[K];
double dis[K];
bool vis[K];
vector<int> p;

void add (int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa_check (double mid)
{
    memset(cnt, 0, sizeof cnt);
    memset(vis, 0, sizeof vis);

    int hh = 0, tt = 0;
    for(int i = 0 ; i < p.size() ; i ++ )
    {
        q[tt ++ ] = p[i];
        vis[p[i]] = 1;
    }

    int count = 0;
    while(hh != tt)
    {
        int t = q[hh ++ ];
        if(hh == N) hh = 0;
        vis[t] = 0;

        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(dis[j] < dis[t] + w[i] - mid)
            {
                dis[j] = dis[t] + w[i] - mid;
                cnt[j] = cnt[t] + 1;

                if(cnt[j] >= p.size()) return true;  // 这个地方的数量是大于等于顶点的数量, 因为n个顶点最多n - 1条边

                if(!vis[j])
                {
                    // 入队几次路径就被更新了几次  原因见基础课spfa求最短路
                    if( ++ count > 3 * p.size()) return true; // 优化点2 track kn这个k呢 全靠试....
                    vis[j] = 1;
                    q[tt ++ ] = j;
                    if(tt == N) tt = 0;
                }
            }
        }
    }

    return false;
}

int main ()
{
    char str[1010];
    while(cin >> n, n)
    {
        memset(h, -1, sizeof h);
        memset(vis, 0, sizeof vis); // 必要 因为当spfa_check函数return true的时候, 其实队列没有全部弹出的, 从而vis数组有可能不全为0
        p.clear(); // 必要的 很容易理解
        for(int i = 0 ; i < n ; i ++ )
        {
            cin >> str; // 注意string是不能这样读入的, 而字符数组可以。string s; cin >> s + 1; ❌
            int len = strlen(str);

            if(len >= 2)
            {
                int a = (str[0] - 'a') * 26 + str[1] - 'a';
                int b = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
                if(!vis[a]) p.push_back(a), vis[a] = 1;
                if(!vis[b]) p.push_back(b), vis[b] = 1;
                add(a, b, len);
            }
        }

        if(!spfa_check(0)) puts("No solution"); // 优化点1
        else
        {
            double l = 0, r = 1010;
            while(r - l > 1e-4)
            {
                double mid = (l + r) / 2;
                if(spfa_check(mid)) l = mid;
                else r = mid;
            }

            printf("%lf\n", r);
        }
    }

    return 0;
}

Stack Accepted Code (no track way)

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1010, M = 100010, K = 1010; // K是顶点的值, N是顶点的在队列中的编号, 即顶点个数

int n; // 边数

int h[K], e[M], ne[M], w[M], idx;
int st[N], cnt[K]; // stack, queue都不需要清空了, 因为自动覆盖
double dis[K];
bool vis[K];
vector<int> p;

void add (int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa_check (double mid)
{
    memset(cnt, 0, sizeof cnt);
    memset(vis, 0, sizeof vis);

    int tt = 0;
    for(int i = 0 ; i < p.size() ; i ++ )
    {
        st[++ tt] = p[i];
        vis[p[i]] = 1;
    }

    while(tt)
    {
        int t = st[tt -- ];
        vis[t] = 0;

        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(dis[j] < dis[t] + w[i] - mid)
            {
                dis[j] = dis[t] + w[i] - mid;
                cnt[j] = cnt[t] + 1;

                if(cnt[j] >= p.size()) return true;

                if(!vis[j])
                {
                    vis[j] = 1;
                    st[++ tt] = j;
                }
            }
        }
    }

    return false;
}

int main ()
{
    char str[1010];
    while(cin >> n, n)
    {
        memset(h, -1, sizeof h);
        memset(vis, 0, sizeof vis); // 必要 因为当spfa_check函数return true的时候, 其实队列没有全部弹出的, 从而vis数组有可能不全为0
        p.clear(); // 必要的 很容易理解
        for(int i = 0 ; i < n ; i ++ )
        {
            cin >> str; // 注意string是不能这样读入的, 而字符数组可以。string s; cin >> s + 1; ❌
            int len = strlen(str);

            if(len >= 2)
            {
                int a = (str[0] - 'a') * 26 + str[1] - 'a';
                int b = (str[len - 2] - 'a') * 26 + str[len - 1] - 'a';
                if(!vis[a]) p.push_back(a), vis[a] = 1;
                if(!vis[b]) p.push_back(b), vis[b] = 1;
                add(a, b, len);
            }
        }

        if(!spfa_check(0)) puts("No solution"); // 优化点1
        else
        {
            double l = 0, r = 1010;
            while(r - l > 1e-4)
            {
                double mid = (l + r) / 2;
                if(spfa_check(mid)) l = mid;
                else r = mid;
            }

            printf("%lf\n", r);
        }
    }

    return 0;
}