是没A题的人里的最高分。但是有什么用吗。
三个最高的暴力，加起来也顶不过一个$AC$
一方面是思考不专注，另一方面是时间分配过于分散了。
每道题留的时间都不够长结果就一个都没想出来。
明明没怎么走神但是感觉还没怎么想呢抬头一看就10点了。然后就只能被迫去打暴力了。
改题效率也不高，看见$T2$的大数据结构就怂了，然后就一直耗着了。。。
T1：要换换名字
大意：给定$n$字符串，要求选定每个字符串的一个非空子序列，两两不同，最长的尽量短。输出方案。$n,maxlen le 300$
首先，一个粗暴地想法，就是对于每个字符串，向它的所有子序列连边，建出一个二分图，看是否能匹配$n$对。
然后发现，当一个串的子序列个数超过$n$时，这个串一定能在不与其它串冲突的情况下参与匹配。
所以我们只需要搜出每个串最短的$n$个子序列就可以了，最后跑网络流最大匹配就行。
搜子序列的话，维护$nxt[i][j][k]$表示第$i$个字符串位置$j$以后下一个字符$k$的位置。这东西倒着扫一遍即可得到。
然后就$BFS$每次扩展$26$个字符就好，可以发现这样就能得到长度递增，字典序递增的串了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 map<string,int>M; 4 int nxt[333][333][33],n,len[333],pc,q[333],cnt,mxf,fir[123456],l[999999],to[999999],ec=1,w[999999],d[123456],Q[123456]; 5 string qs[333],ans[333],res[99999];char s[333][333]; 6 vector<int>v[333]; 7 void link(int a,int b,int W){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;w[ec]=W;} 8 void con(int a,int b,int W){link(a,b,W);link(b,a,0);} 9 bool bfs(){ 10 for(int i=1;i<=cnt+n+1;++i)d[i]=cnt+n+2; 11 for(int h=1,t=1;h<=t;++h)for(int i=fir[Q[h]];i;i=l[i])if(d[to[i]]>d[Q[h]]+1&&w[i]) 12 d[Q[++t]=to[i]]=d[Q[h]]+1; 13 return d[cnt+n+1]<cnt+n+2; 14 } 15 int dfs(int p,int f){int r=f; 16 if(p==cnt+n+1)return f; 17 for(int i=fir[p];i&&r;i=l[i])if(w[i]&&d[to[i]]==d[p]+1){ 18 int x=dfs(to[i],1); 19 if(!x)d[to[i]]=0; 20 w[i]-=x;w[i^1]+=x;r-=x; 21 }return f-r; 22 } 23 int main(){ 24 scanf("%d",&n); 25 for(int i=1;i<=n;++i)scanf("%s",s[i]+1),len[i]=strlen(s[i]+1); 26 for(int i=1;i<=n;++i)for(int j=len[i];j;--j){ 27 for(int c=0;c<26;++c)nxt[i][j-1][c]=nxt[i][j][c]; 28 nxt[i][j-1][s[i][j]-'a']=j; 29 } 30 for(int i=1;i<=n;++i)for(int h=1,t=1;h<=t;++h)for(int c=0;c<26;++c)if(t-1<=n&&nxt[i][q[h]][c]){ 31 qs[++t]=qs[h]+(char)('a'+c);q[t]=nxt[i][q[h]][c]; 32 if(!M[qs[t]])M[qs[t]]=++cnt,res[cnt]=qs[t]; 33 v[i].push_back(M[qs[t]]); 34 } 35 for(int i=1;i<=cnt;++i)con(0,i,0); 36 for(int i=1;i<=n;++i)for(auto j:v[i])con(j,i+cnt,1); 37 for(int i=1;i<=n;++i)con(i+cnt,cnt+n+1,1); 38 for(int I=1;I<=n;++I){ 39 for(int i=fir[0];i;i=l[i])if(res[to[i]].size()==I)w[i]++; 40 while(bfs())mxf+=dfs(0,n); 41 if(mxf==n){ 42 cout<<I<<endl; 43 for(int i=fir[0];i;i=l[i])if(!w[i])for(int j=fir[to[i]];j;j=l[j]) 44 if(to[j]&&!w[j])ans[to[j]-cnt]=res[to[i]]; 45 for(int i=1;i<=n;++i)cout<<ans[i]<<endl; 46 return 0; 47 } 48 }puts("-1"); 49 }
T2：动态半平面交
大意：树，点权。多次询问$p$子树中距离不超过$u$的点的点权$lcm$。$n le 10^5,a_i le 10^7$
大数据结构，先鸽着。
T3：获取名额
大意：数列，求$1-prod limits_{i=l}^{r} (1-frac{a_i}{x})$。多次询问给出$l,r,x$。$n,q le 6 imes 10^5,eps=10^{-9}$
发现如果我们每次挑出$a_i$最大的，然后这样答案就会很快收敛。
那么对于$frac{a_i}{x}>0.5$的不断找最大值递归两边区间就好。$log$层就完事了。
对于$a_i$小的怎么办？
累乘不好处理，我们知道$prod a_i =exp( sum ln a_i)$
我们又知道$ln(1-x)=sumlimits_{j=1}^{+infty} frac{x^j}{j}$
这就是一个经典的泰勒展开，只要预处理$a_i^j$的前缀和，迭代个$20$轮就好了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 666666 4 long double a[S],pre[28][S],ST[28][S],ans,x;int STp[28][S],hb[S],A[S],n,mx,m; 5 void DaC(int l,int r){ 6 if(l>r)return; 7 if(ans<1e-7)return; 8 int B=hb[r-l+1],P;double m; 9 if(ST[B][l]>ST[B][r-(1<<B)+1])m=ST[B][l]/x,P=STp[B][l]; 10 else m=ST[B][r-(1<<B)+1]/x,P=STp[B][r-(1<<B)+1]; 11 if(m>0.4)ans*=1-m,DaC(l,P-1),DaC(P+1,r); 12 else{ 13 double sum=0,pw=x; 14 for(int i=1;i<27;++i)sum+=(pre[i][r]-pre[i][l-1])/pw/i,pw*=x; 15 ans*=exp(-sum); 16 } 17 } 18 int main(){ 19 scanf("%d%d",&n,&m); 20 for(int i=1;i<=n;++i)scanf("%d",&A[i]),mx=max(A[i],mx); 21 for(int i=200075;i<=200125;++i)cerr<<A[i]<<endl; 22 for(int i=1;i<=n;++i)a[i]=1.*A[i]/mx; 23 for(int i=1;i<=n;++i){ 24 long double pw=a[i]; 25 for(int j=1;j<27;++j)pre[j][i]=pre[j][i-1]+pw,pw*=a[i]; 26 } 27 for(int i=1;i<=n;++i)ST[0][i]=a[i],STp[0][i]=i; 28 for(int j=1;1<<j<n;++j)for(int i=1;i+(1<<j)-1<=n;++i) 29 if(ST[j-1][i]>ST[j-1][i+(1<<j-1)])ST[j][i]=ST[j-1][i],STp[j][i]=STp[j-1][i]; 30 else ST[j][i]=ST[j-1][i+(1<<j-1)],STp[j][i]=STp[j-1][i+(1<<j-1)]; 31 for(int j=0;1<<j<n;++j)for(int i=1<<j;i<1<<j+1&&i<=n;++i)hb[i]=j; 32 while(m--){ 33 int l,r,X;scanf("%d%d%d",&l,&r,&X);x=1.*X/mx; 34 ans=1;DaC(l,r);printf("%.10Lf ",1-ans); 35 } 36 }