2021.8.9 提高B组模拟赛

$2021.8.9$ 模拟赛
目录：

T1.最长公共回文子序列
T2.QYQ在艾泽拉斯
T3.平均数
T4.着色

$T1：$最长公共回文子序列

分析：

在$B$串里枚举回文子串 然后看这个子串在$A$串有没有即可

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+5;
char a[N],b[25],s[25];
int n,m,ans,vis[N],tot;
void dfs(int x)
{if(x>m){tot=0;for(int i=1;i<=m;i++)if(vis[i]) s[++tot]=b[i];for(int i=1;i<=(tot>>1);i++)if(s[i]!=s[tot-i+1]) return;int j=1;for(int i=1;i<=n;i++){if(a[i]==s[j]) j++;if(j>tot) break;}if(j<=tot) return;ans=max(ans,tot);return;}vis[x]=1; dfs(x+1);vis[x]=0; dfs(x+1);
}
int main(){freopen("lcps.in","r",stdin);freopen("lcps.out","w",stdout);scanf("%s%s",a+1,b+1);n=strlen(a+1);m=strlen(b+1);dfs(1);printf("%d",ans);return 0;
}

$T2：QYQ$在艾泽拉斯

分析：

$tarjan$把所有岛屿都先处理出
然后在拓扑序里 把每个连通块最大路径值求出 这个用并查集和拓扑序$dp$做
答案就是前$k$个之和

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m,k,tot,head[N],x[N],y[N];
int low[N],dfn[N],con[N],Index,size;
int fa[N],in[N],num,head2[N],tot2;
ll f[N],Ans,ans[N],w[N],val[N],sum[N];
queue<int> q; 
stack<int> st;
struct node{int to,next;
}a[N],a2[N];
void add(int x,int y)
{a[++tot]=(node){y,head[x]};head[x]=tot;
}
void add2(int x,int y)
{a2[++tot2]=(node){y,head2[x]};head2[x]=tot2;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void tarjan(int x)
{st.push(x);dfn[x]=low[x]=++Index;for(int i=head[x];i;i=a[i].next){int qwq=a[i].to;if(!dfn[qwq]){tarjan(qwq);low[x]=min(low[x],low[qwq]);}else if(!con[qwq])low[x]=min(low[x],dfn[qwq]);}if(dfn[x]==low[x]){con[x]=++size;sum[size]=w[x];while(st.top()^x){con[st.top()]=size;sum[size]+=w[st.top()];st.pop();}st.pop();}
}
void TpSort()
{while(!q.empty()){int x=q.front();q.pop();for(int i=head2[x];i;i=a2[i].next){int qwq=a2[i].to;if(val[x]+sum[qwq]>val[qwq]){val[qwq]=val[x]+sum[qwq];int now=find(qwq);f[now]=max(f[now],val[qwq]);}in[qwq]--;if(in[qwq]==0) q.push(qwq);}}
}
void merge(int x,int y){(x<y)?fa[y]=x:fa[x]=y;}
int main(){freopen("azeroth.in","r",stdin);freopen("azeroth.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x[i],&y[i]);add(x[i],y[i]);}for(int i=1;i<=n;i++)scanf("%lld",&w[i]);scanf("%d",&k);for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);for(int i=1;i<=size;i++)fa[i]=i;for(int i=1;i<=m;i++){int a=x[i],b=y[i];if(con[a]^con[b]){int fx=find(con[a]),fy=find(con[b]);merge(fx,fy);in[con[b]]++;add2(con[a],con[b]);}}for(int i=1;i<=size;i++)if(in[i]==0){q.push(i); val[i]=sum[i];int now=find(i);f[now]=max(f[now],val[i]);}TpSort();for(int i=1;i<=size;i++)if(f[i]) ans[++num]=f[i];sort(ans+1,ans+num+1);for(int i=num;i>=max(1,num-k);i--)Ans+=ans[i];printf("%lld",Ans);return 0;
}

$T3：$平均数

$Luogu$ $link$ $\&$ 双倍经验

分析：

二分
如果一个序列的平均值$>x$ 那每个数$-x>0$ 所以二分这个$x$
枚举前缀和 若当前前缀和 减 最小前缀和$>0$ $x$即合法

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=3e5+5; 
int n,k,a[N];
double ans,eps=1e-7,sum[N],l=0,r;
bool check(double x)
{for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(double)(a[i]-x);double tmp=0;for(int i=1;i<=n;i++)if(i-k>=0){tmp=min(tmp,sum[i-k]);if(sum[i]-tmp>=0) return 1;}return 0;
}
int main(){freopen("average.in","r",stdin);freopen("average.out","w",stdout);scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);r+=a[i];}while(r-l>eps){double mid=(l+r)/2.0;if(check(mid)) l=mid,ans=l;else r=mid;}printf("%.6lf",ans);return 0;
}

$T4：$着色

$Luogu$ $link$

分析：

$k=2$时 答案都为$2$
如果图能用两色或三色涂 $ans=$两色答案$\times C_k^2+($三色答案$-6)\times C_k^3$
如果只能用三色涂 $ans=($三色答案$-6)\times C_k^3$
$-6$是从三色中减去两色的方案数
三色时的答案可以手算 可以从样例里找 也可以$dfs$

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,k;
int main(){freopen("color.in","r",stdin);freopen("color.out","w",stdout);scanf("%lld%lld",&n,&k);long long C_2=k*(k-1)/2,C_3=k*(k-1)*(k-2)/6;if(n==1) printf("%lld",2*C_2+1572858*C_3); else if(n==2) printf("%lld",96*C_3);else if(n==3) printf("%lld",2*C_2+18*C_3);else if(n==4) printf("%lld",2*C_2+24570*C_3);else if(n==5) printf("%lld",12*C_3);else if(n==6) printf("%lld",6*C_3);else if(n==7) printf("%lld",96*C_3);else if(n==8) printf("%lld",2*C_2+((1<<30)+2ll-6ll)*C_3);return 0;
}