最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

AcWing. 1165.单词环

来源：博客园

传送门


(相关资料图)

解题思路

\(\qquad\)我们一开始可以得出一个建图的思路，对于每个字符串我们把它们当成图中的一个点，然后能“接龙”的字符串之间连一条边，在这张图上跑\(01\)分数规划。这样貌似是可以的，但是我们看一下这张图有多么庞大：它的点数\(N\)的上限可以达到\(10^5\)，而边数应该是\(A_{N}^{2}\)近似于\(N^2\)也就是差不多\(10^{10}\)，这显然是一个光建图就会超时的时间复杂度，我们不可以采用。

\(\qquad\)稍加思考我们可以得到另一个思路：将能接龙的字符串的首尾\(2\)位看做是点，连有向边，有向边的边权是这个字符串的长度。

\(\qquad\qquad\qquad\quad\Large\color{Red}{ --但是为什么可以这样做呢--}\)

\(\qquad\)我们经过观察，可以得到这样一个结论：\(\qquad\)在本题中，只要两个字符串的首尾和长度相同，就可以看做是同一个字符串

上述结论的推导：

假设有两个字符串，\(\large s_{1}\)和\(\large s_{2}\)，我们的图中（第一个\(TLE\)礼包图）中存在这样的一个环：

\(\qquad \qquad\qquad\large c_1->c_2->c_3->c_4->s_1->c_5->c_6\)

当我们将\(\large s_2\)带进去的时候，由于\(\large s_2\)的首尾和\(\large s_1\)都是相同的，所以\(\ \large s_2\)必然可以和\(\ \large c_4\)以及\(\ \large c_5\)连接。然后由于点的数量不变，而边的权重又都相同，那自然平均值不变，所以这个环：

\(\qquad \qquad\qquad\large c_1->c_2->c_3->c_4->s_2->c_5->c_6\)

和上面的环是等价的。

01分数规划的解题思路

这题要求出一个环，使得这个环（点的个数是\(pcnt\)）的\(\LARGE \frac{\sum w_i}{pcnt}\)最大。

一样的用二分的思路，我们想要二分出这个最大值，假设当前二分的值是\(mid\)

当\(mid

将上式进行一点变形：\(\qquad\qquad\qquad\qquad\qquad \LARGE mid\times pcnt < \sum w_i\)\(\qquad\)

\(\qquad\qquad\qquad\qquad\qquad \LARGE mid\times pcnt - \sum w_i < 0\)

然后它就成了熟悉的负环题了，用\(SPFA\)判个环就好了

代码

#include #include using namespace std;const int N = 1e5 + 10, M = 700;int h[M], e[N], w[N], ne[N], idx;double dist[M];int st[M], ring, n;string str;void add(int a, int b, int c) {    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;}void dfs(int cur, double x) {    st[cur] = 1;    for (int i = h[cur]; ~i; i = ne[i])     {        int j = e[i]; double W = x - w[i];        if (dist[j] > dist[cur] + W)         {            dist[j] = dist[cur] + W;            if (st[j] == 1) {                ring = true ;                break ;            }            dfs(j, x);            if (ring) return ;        }    }    st[cur] = 2;}bool check(double x) {    ring = 0;    memset(st, 0, sizeof st);    memset(dist, 0, sizeof dist);        for (int i = 1; i <= 676; i ++ )     {        if (st[i]) continue ;        if (ring) break ;        dfs(i, x);    }        return ring;}int main() {    while (scanf("%d", &n), n)    {        idx = 0;        memset(h, -1, sizeof h);                for (int i = 1; i <= n; i ++ )         {            cin >> str;            int len = str.size();            int a = (str[0] - "a") * 26 + str[1] - "a";            int b = (str[len - 2] - "a") * 26 + str[len - 1] - "a";            add(a + 1, b + 1, len);        }                if (!check(0)) puts("No solution");        else         {            double l = 0, r = 1e5;            while (r - l > 1e-4)             {                double mid = (l + r) / 2;                if (check(mid)) l = mid;                else r = mid;            }            printf("%.2lf\n", r);        }            }        return 0;}

关键词： 可以得出 我们看一下 时间复杂度