赛后——2.14 寒假模拟10
\(\text{T1}\) 正方形
题意
小 \(S\) 有一个二维平面，上面有 \(n\) 个点。
现在，小 \(S\) 想用一个长和宽都平行于坐标轴的正方形去覆盖所有点，求正方形的最小面积。
思路
\(S=(\max(x_{\max}-x_{\min},y_{\max}-y_{\min}))^2\)
代码
点击查看代码
int main(){
n=read();
maxx=maxy=-1,minx=miny=2000;
for(int i=1;i<=n;i++){
int x=read(),y=read();
maxx=max(maxx,x),minx=min(minx,x);
maxy=max(maxy,y),miny=min(miny,y);
}
int ans=max(maxx-minx,maxy-miny);
printf("%d\n",ans*ans);
return 0;
}
\(\text{T2}\) 玩蛇
题意
小 \(S\) 画了一个高度为 \(n\) 的三角形，从上到下第 \(i\) 层的宽度为 \(i\)。
接着小 \(S\) 将一个字符串 \(T\) 蛇形的循环填入三角形，例如 \(n=6,T=\text{JANJETINA}\) 时，三角形为：
\(\text{J}\)
\(\text{NA}\)
\(\text{JET}\)
\(\text{JANI}\)
\(\text{ANJET}\)
\(\text{NAJANI}\)
现在有 \(Q\) 次询问，每次询问要去第 \(k\) 行字符 \(c\) 出现了多少次？
思路
赛时瞎搞用分块优化疯狂挂分。
首先我们发现这东西可以取模然后把左右的零散串暴力算出来，发现 \(|S|\le 10^6\)，因此需要前缀和。
做完了，赛时真是智障。
代码
点击查看代码
int main(){
n=read();
scanf("%s",s+1);
len=strlen(s+1);
for(int i=1;i<=len;i++){
for(int j=1;j<=26;j++){
sum[i][j]=sum[i-1][j];
}
sum[i][s[i]-'A'+1]++;
}
q=read();
while(q--){
ll k=read(),ans=0;
char c;
cin>>c;
ll l,r;
if(k&1) l=(((k-1)/2%len)*(k%len)+1)%len;
else l=(((k/2)%len)*((k-1)%len)+1)%len;
r=(l+k-1)%len;
if(!l) l=len;
if(!r) r=len;
if(l\(\text{T3}\) 嗷呜
题意
现在有一个仅包含前 \(m\) 个小写字母且长度为 \(n\) 的串 \(A\)，现在要找到一个也仅包含前 \(m\) 个小写字母且长度为 \(n\) 的串 \(B\)，使 \(A\) 与 \(B\) 的最长公共子序列长为 \(n-1\)。
思路
首先考虑对子序列去重，就是每个与前一个字符不相等的字符个数和，记为 \(cnt\)，一个长 \(n-1\) 的公共子序列可以在 \(n\) 个位置插入 \(m-1\) 种与之不同的字符，于是第一步答案为：\(cnt\times n\times (m-1)\)。
然后发现还有一种重复情况，形如 \(\text{ababab}\) 的循环节，重复情况是等差数列求和，值为 \(t(t+1)/2\)，于是枚举循环节暴算。
代码
点击查看代码
int main(){
n=read(),m=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++){
if(s[i]!=s[i-1]) cnt++;
}
ans=cnt*n*(m-1);
int pos=1;
while(pos+1<=n){
if(s[pos]==s[pos+1]){
pos++;
continue;
}
int len=1;
while(pos+len+1<=n&&s[pos+len+1]==s[pos+(len+1)%2]){
len++;
}
pos+=len;
ans-=1ll*len*(len+1)/2;
}
printf("%lld\n",ans);
return 0;
}
\(\text{T4}\) 开车
题意
小 \(S\) 所在的城镇是一棵树，有 \(n-1\) 条道路连接 \(n\) 个节点，经过每条路需要花一定时间。
现在，小 \(S\) 要送 \(K\) 个乘客去到他们的目的地 \(a_i\)，保证 \(a_i\) 互不相同。
求从每个点出发将每个人送到各自的目的地，求最小时间。（不必再回到起点）
思路
发现答案实际为从根节点出发，完全走完其他子树，最后一棵子树停留在目的地的最小代价，设其为 \(g_u\)，发现其他子树需要完全走完（指去到每个需要去到的节点并回到子树的根），设其为 \(f_u\)，于是有转移方程：
\[f_u=\sum_{v\in G} w(u,v)\times 2+f_v \]对于 \(g\) 而言，实质是若干个 \(f\) 与一个 \(g\) 之和的最小值，这若干个可以直接用 \(f_u\) 去掉一棵子树来求，也就是：
\[\begin{aligned} g_u&=\min_{v\in G}\{f_u-2\times w(u,v)-f_v+g_v\}\\ &=f_u-\max_{v\in G}\{2\times (u,v)+f_v-g_v\} \end{aligned}\]这样部分分就拿到了。
点击查看代码
inline void dfs1(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs1(v,u);
if(vis[v]){
vis[u]=1;
f[u]+=f[v]+e[i].w*2;
}
}
}
inline void dfs2(int u,int fa){
g[u]=f[u];
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs2(v,u);
if(vis[v]){
g[u]=min(g[u],f[u]-e[i].w-f[v]+g[v]);
}
}
}
int main(){
n=read(),q=read();
for(int i=1;i考虑换根，发现维护 \(f\) 的一半，即单次路程的长更好转移，每次维护处一个除去该子树的代价和与最大代价，二次扫描即可。（关键是转移方程要写好）
代码
点击查看代码
inline void dfs(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
if(vis[v]){
vis[u]=1;
sumdis[u]+=e[i].w+sumdis[v];
maxdis[u]=max(maxdis[u],maxdis[v]+e[i].w);
}
}
}
inline void secdfs(int u,int fa,ll Sum,ll Max,int siz){
ans[u]=(sumdis[u]+Sum)*2-max(maxdis[u],Max);
ll lftmax=-0x3f3f3f3f3f3f3f3f;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa||!vis[v]) continue;
siz++;
Sum+=e[i].w+sumdis[v];
lftmax=max(lftmax,e[i].w+maxdis[v]);
if(lftmax>Max) swap(Max,lftmax);
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
if(vis[v]){
ll lftsum=Sum-sumdis[v];
if(siz==1) lftsum=0;
if(e[i].w+maxdis[v]==Max){
secdfs(v,u,lftsum,lftmax+e[i].w,min(1,siz));
}
else{
secdfs(v,u,lftsum,Max+e[i].w,min(1,siz));
}
}
else{
secdfs(v,u,Sum+e[i].w,Max+e[i].w,min(1,siz));
}
}
}
int main(){
n=read(),q=read();
for(int i=1;i