SP2885 WORDRING - Word Rings 题解
题目链接:SP2885 WORDRING - Word Rings
题意:
如果字符串 \(A\) 的结尾两个字符与字符串 \(B\) 的开头两个字符相匹配,我们称 \(A\) 与 \(B\) 能 “ 相连 ” ( 注意: \(A\) 与 \(B\) 能相连,不代表 \(B\) 与 \(A\) 能相连 )
当若干个串首尾 “ 相连 ” 成一个环时,我们称之为一个环串(一个串首尾相连也算)
我们希望从给定的全小写字符串中找出一个环串,使这个环串的平均长度最长
intercommunicational alkylbenzenesulfonate tetraiodophenolphthalein
如上例:第一个串能与第二个串相连,第二个串能与第三个串相连,第三个串又能与第一个串相连。按此顺序连接,便形成了一个环串。
长度为 \(20+21+24=65\) ( 首尾重复部分需计算两次 ) ,总共使用了 \(3\) 个串,所以平均长度是 \(65/3\approx 21.6667\)
输入格式:
多组数据 每组数据第一行一个整数 \(n\) ,表示字符串数量 接下来 \(n\) 行每行一个长度小于等于 \(1000\) 的字符串 读入以 \(n=0\) 结束
输出格式:
若不存在环串,输出
No solution.
。否则输出最长的环串平均长度。
吐了,一个初值没赋调了半天。
注意到每个字符串其实只有开头结尾的几个字符有用
直接把这两个字符组成的串看作结点,不难发现不超过 \(26^2 = 676\) 个结点
比如 \(\tt{aabbcdcdcab}\) 就是 \(\tt{aa}\) 向 \(\tt{ab}\) 连一条边,边权为 \(11\) 。
看上去是找个最长的环,但是因为是平均值,
所以这道题就变成经典的 \(\tt{01}\)
分数规划了,虽然稍微有一丢丢不同
\(\tt{01}\) 分数规划的精髓就在于二分比值,使原本同一事物的两个属性合并。
设环 \(C\) 的答案为 \[ \bar{w} = \dfrac{1}{k}(w_1+w_2+\cdots+w_k)> M \] 则不等式等价于 \[ (M-w_1) + (M-w_2)+\cdots+(M-w_k) < 0 \] 很好,我们有了新的边权,找负环就好啦!
这个二分边界么,如果有负环,那就 \(l \leftarrow \mathrm{mid}\) ,否则 \(r \leftarrow \mathrm{mid}\)
时间复杂度 \(O(-n|\Sigma|\log \epsilon)\)
然后这道题愉快地卡了我好久,然后顺便练习了一下卡常
代码1:(bfs版,实测1.78s
)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define INF 0x3f3f3f3f
#define N ((int)(888))
#define M ((int)(1e5+15))
const double eps=1e-3;
const int tot=750;
int encode(int a,int b){return (a-'a')*26+b-'a'+1;}
void up(int &x,int y) {x < y ? x = y : 0;}
void down(int &x,int y) {x > y ? x = y : 0;}
bitset<N> vis;
int n,mx,cnt[N];
double d[N]; char s[M];
vector< pair<int,int> > g[N];
void addEdge(int u,int v,int w)
{
g[u].push_back({v,w});
}
void clear()
{
mx=0;
for(int i=1; i<=tot; i++) g[i].clear();
}
bool spfa(double mid)
{
vis=0; queue<int> q; d[0]=0;
for(int i=1; i<=tot; i++) cnt[i]=0,d[i]=INF;
q.push(0);
while(!q.empty())
{
int u=q.front(); q.pop();
vis[u]=0;
for(auto it : g[u])
{
int v=it.first; double w=mid-it.second;
if(d[v] > d[u] + w)
{
d[v] = d[u] + w;
if(!vis[v])
{
if(++cnt[v] > tot) return 1;
q.push(v); vis[v]=1;
}
}
}
}
return 0;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cout << fixed << setprecision(3);
while(cin >> n && n)
{
clear();
for(int i=1,u,v,w; i<=n; i++)
{
cin >> s; w=strlen(s);
if(w<2) continue;
u=encode(s[0],s[1]);
v=encode(s[w-2],s[w-1]);
addEdge(u,v,w); up(mx, w);
}
for(int i=1; i<=tot; i++) addEdge(0,i,0);
double l,r,mid;
for(l=0,r=mx; r-l>eps;)
{
mid = (l + r) * 0.5;
spfa(mid) ? l = mid : r = mid;
}
l < eps ? (cout << "No solution.\n") : (cout << l << '\n');
}
return 0;
}
代码2:(Bellman-Ford,未卡常,实测2.87s
)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define INF 0x3f3f3f3f
#define N ((int)(1e3+15))
#define M ((int)(1e5+15))
const double eps=1e-4;
const int tot=777;
int encode(int a,int b){return a * 26 + b - 2619 + 10;}
void up(int &x,int y) {x < y ? x = y : 0;}
void down(int &x,int y) {x > y ? x = y : 0;}
int n,mx,pos=1,head[N];
double d[N]; char s[M];
struct Edge{int u,v,w,next;} e[M];
void addEdge(int u,int v,int w)
{
e[++pos]={u,v,w,head[u]};
head[u]=pos;
}
void clear()
{
mx=0; pos=1;
memset(head,0,sizeof(head));
}
bool work(double mid)
{
for(int i=1; i<=tot; i++) d[i]=0;
for(int k=1; k<=tot; k++)
for(int i=2; i<=pos; i++)
{
int u=e[i].u,v=e[i].v; double w=mid-e[i].w;
if(d[v] > d[u] + w) d[v]=d[u]+w;
}
for(int i=2; i<=pos; i++)
{
int u=e[i].u,v=e[i].v; double w=mid-e[i].w;
if(d[v] > d[u] + w) return 1;
}
return 0;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cout << fixed << setprecision(5);
while(cin >> n && n)
{
clear();
for(int i=1,u,v,w; i<=n; i++)
{
cin >> s; w=strlen(s);
if(w<2) continue;
u=encode(s[0],s[1]);
v=encode(s[w-2],s[w-1]);
addEdge(u,v,w); up(mx, w);
}
double l,r,mid;
for(l=0,r=mx; r-l>eps;)
{
mid = (l+r)/2;
work(mid) ? l = mid : r = mid;
}
l < eps ? (cout << "No solution.\n") : (cout << l << '\n');
}
return 0;
}