是没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 }
View Code
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 \times 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)=\sum\limits_{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\n",1-ans);
35 }
36 }
View Code