题意
每组数据读入一个n和n个字符串。定义前2个与末尾2个字母相同可以连接。问使这个环串的平均长度最大。求这个最大值。不存在输出No solution。思路
平均值公式：$$Average=(E_1+E_2+…..+E_n)/n$$ $$Average*n=(E_1+E_2+…+E_n)$$ $$(E_1-Average)+(E_2-Average)+…+(E_n-Average)=0$$ 那么可以二分答案：
$$(E_1-Ans)+(E_2-Ans)+…+(E_n-Ans)\geq0$$
然后瞎搞spfa。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #define E 200010 #define eps 1e-3 using namespace std; inline int read(){ int res=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); return res*f; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x<10) putchar(x+'0'); else{ write(x/10); putchar(x%10+'0'); } } //queue<int> q; //set<int> s; //priority_queue<int> q1; //priority_queue<int,vector<int>,greater<int> > q2; //list<int> l; //stack<int> s; int n; string str[100010]; int fir[E],nxt[E],son[E],tot,cnt,Max; double w[E],dis[E],flag; int vis[E]; int f[6666]; void add(int x,int y,double z){++tot;son[tot]=y;nxt[tot]=fir[x];fir[x]=tot;w[tot]=z;} void spfa(int s,int v,double mid){ if(flag==1) return ; vis[s]=v; for(int i=fir[s];i;i=nxt[i]){ int to=son[i]; if(dis[s]+w[i]>dis[to]+mid){ dis[to]=dis[s]+w[i]-mid; if(dis[to]>Max){ flag=1; return ; } if(!vis[to]) spfa(to,v,mid); if(flag) return ; else if(vis[to]==v){ flag=1; return ; } } } vis[s]=0; } bool check(double mid){ flag=0; for(int i=0;i<=cnt;i++) dis[i]=0.0; memset(vis,0,sizeof(vis)); for(int i=1;i<=cnt;i++){ spfa(i,i,mid); if(flag==1) break; } return flag; } int main(){ // freopen("code.in","r",stdin);freopen("code.out","w",stdout); n=read(); while(n!=0){ for(int i=1;i<=n;i++) cin>>str[i]; memset(fir,0,sizeof(fir)); memset(f,0,sizeof(f)); tot=0;cnt=0;Max=0; for(int i=1;i<=n;i++){ int len=str[i].length(); Max=max(Max,len); int a=(str[i][0]-'a')*26+str[i][1]-'a'; int b=(str[i][len-2]-'a')*26+str[i][len-1]-'a'; if(!f[a]) f[a]=++cnt; int A=f[a]; if(!f[b]) f[b]=++cnt; int B=f[b]; add(A,B,(double)len); } Max*=n; double l=0,r=1000,ans=-1,mid; while(l+eps<r){ mid=(l+r)/2; if(check(mid)) l=mid,ans=mid; else r=mid; } if(ans!=-1) printf("%.2lf\n",ans); else puts("No solution"); n=read(); } return 0; } |
