思路与算法

一个可参与相连的单词对应从其前两个字母到后两个字母的一条有向边，边权为整个单词长度；重叠部分仍算两次，因此环串平均长度正是有向环平均边权。两个字母只有26²=676种。同一对端点的较短单词永远不优于较长者，只保留最大权。长度1单词没有所要求的两个字符前缀/后缀，不能构成这种相连关系，忽略其边而不把长度范围擅改为至少2。将图分成SCC，单点且无自环的块不含环。对一个有K个点的SCC，dp[l][v]为从任意起点出发、恰走l条边到v的最大总权，dp[0][v]=0。枚举1..K层。Karp定理给出该SCC最大平均环为max_v min_{0<=l<K}(dp[K][v]-dp[l][v])/(K-l)。所有SCC取最大，没有含环块则输出No solution。

正确性说明

首尾相连条件与有向边首尾衔接条件逐字相同，所以环串与有向闭合游走互相对应。任意闭合游走可分解为简单有向环，其平均权是各环均值的按边数加权平均，因此最优值一定能由一个有向环达到。替换平行边为最长单词不改变端点或环合法性，只会增加总长度，故可压缩。同一环全在某个SCC内，分块取最大完整覆盖。DP归纳得到每层所有长度恰l的最佳游走权；对强连通块使用Karp最大平均环定理，差分斜率的先取最小、再取最大，精确刻画能够反复延伸的最大循环平均收益。块内权值及DP值都是整数，最后才作除法，并按原题0.01绝对误差特判。

复杂度

令L为全部输入字符数，V=676，块j有Kj点、Ej条压缩边。读入O(L)，初始化及扫描矩阵O(V²)，SCC O(V+E)。Karp转移O(ΣKjEj)，斜率枚举O(ΣKj²)。总空间O(V²+max Kj²+E)，加上单词缓冲O(1000)，不保存全部输入单词。即便n=100000且每个词长1000，程序流式读入。

易错点

这是最大平均长度而非最大总长度，不是最短环。重叠的两字符没有从单词长度中扣除。要保留自环，也要正确处理全部无环、平行边和多组输入0结束。不能仅用四舍五入后的字符串答案严格比对；原题明确允许绝对误差0.01。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n && n) {
        const int V = 676, NEG = -1000000000;
        vector<vector<int>> w(V, vector<int>(V, NEG));
        vector<vector<int>> g(V), rg(V);
        string row;
        getline(cin, row);
        for (int i = 0; i < n; i++) {
            string s;
            getline(cin, s);
            if (!s.empty() && s.back() == '\r')
                s.pop_back();
            if (s.empty()) {
                --i;
                continue;
            }
            if (s.size() < 2)
                continue;
            int u = (s[0] - 'a') * 26 + s[1] - 'a',
                v = (s[s.size() - 2] - 'a') * 26 + s.back() - 'a';
            w[u][v] = max(w[u][v], (int)s.size());
        }
        for (int u = 0; u < V; u++)
            for (int v = 0; v < V; v++)
                if (w[u][v] != NEG) {
                    g[u].push_back(v);
                    rg[v].push_back(u);
                }
        vector<char> vis(V);
        vector<int> ord;
        function<void(int)> dfs = [&](int u) {
            vis[u] = 1;
            for (int v : g[u])
                if (!vis[v])
                    dfs(v);
            ord.push_back(u);
        };
        for (int i = 0; i < V; i++)
            if (!vis[i])
                dfs(i);
        vector<int> co(V, -1);
        vector<vector<int>> cc;
        function<void(int, int)> assign = [&](int u, int c) {
            co[u] = c;
            cc[c].push_back(u);
            for (int v : rg[u])
                if (co[v] < 0)
                    assign(v, c);
        };
        for (int i = V - 1; i >= 0; i--)
            if (co[ord[i]] < 0) {
                cc.push_back({});
                assign(ord[i], cc.size() - 1);
            }
        long double ans = -1;
        for (auto &nodes : cc) {
            int k = nodes.size();
            if (k == 1 && w[nodes[0]][nodes[0]] == NEG)
                continue;
            vector<int> id(V, -1);
            for (int i = 0; i < k; i++)
                id[nodes[i]] = i;
            vector<tuple<int, int, int>> edges;
            for (int u : nodes)
                for (int v : g[u])
                    if (id[v] >= 0)
                        edges.emplace_back(id[u], id[v], w[u][v]);
            vector<vector<int>> dp(k + 1, vector<int>(k, NEG));
            fill(dp[0].begin(), dp[0].end(), 0);
            for (int l = 1; l <= k; l++)
                for (auto e : edges) {
                    int u, v, z;
                    tie(u, v, z) = e;
                    if (dp[l - 1][u] != NEG)
                        dp[l][v] = max(dp[l][v], dp[l - 1][u] + z);
                }
            for (int v = 0; v < k; v++) {
                long double z = 1e30;
                for (int l = 0; l < k; l++)
                    if (dp[l][v] != NEG)
                        z = min(z, (long double)(dp[k][v] - dp[l][v]) / (k - l));
                ans = max(ans, z);
            }
        }
        if (ans < 0)
            cout << "No solution\n";
        else
            cout << fixed << setprecision(8) << ans << '\n';
    }
}