2023杭电多校第一场部分题解

还有些没补的题以后回来补。

1001

感觉是大暴力题，数据范围给的很小所以每次可以暴力求出两人的路径。枚举路径的交集里的点然后看看两个人在这个点相遇需要的最短时间就可以了。确定了具体的点之后求 $4$ 次exgcd即可知道答案（分别看两个人是在 来/回 的路上相遇）。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define maxn 200010
#define inf 999999999#define cn getchar
template<class TY>void read(TY &x){x=0;int f1=1;char ch=cn();while(ch<'0'||ch>'9'){if(ch=='-')f1=-1;ch=cn();}while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=cn(); x*=f1;
}
template<class TY>void write2(TY x){if(x>9)write2(x/10);putchar(x%10+'0');
}
template<class TY>void write(TY x){if(x<0)putchar('-'),x=-x;write2(x);
}
int T,n,m;
struct edge{int y,next;}e[maxn<<1];
int first[maxn],et;
void buildroad(int x,int y){e[++et]=(edge){y,first[x]};first[x]=et;
}
int fa[maxn],dep[maxn];
void dfs(int x){for(int i=first[x];i;i=e[i].next){int y=e[i].y;if(y==fa[x])continue;fa[y]=x;dep[y]=dep[x]+1;dfs(y);}
}
vector<int> A,B;
int sta[maxn],t=0;
void get_path(int S,int T,vector<int> &d){int x=S,y=T;d.clear();while(dep[x]>dep[y])d.push_back(x),x=fa[x];while(dep[x]<dep[y])sta[++t]=y,y=fa[y];while(x!=y){d.push_back(x);x=fa[x];sta[++t]=y;y=fa[y];}d.push_back(x);while(t)d.push_back(sta[t--]);
}
int inA[maxn],inB[maxn];
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int g=exgcd(b,a%b,y,x);return y-=a/b*x,g;
}
int calc(int a,int l1,int b,int l2){int x,y;a<<=1;b<<=1;int g=exgcd(a,b,x,y);if(abs(l2-l1)%g)return inf;x*=(l2-l1)/g,y*=(l2-l1)/g;x-=x/(b/g)*(b/g);if(x<0)x+=b/g;return a*x+l1;
}int main()
{read(T);while(T--){read(n);read(m);for(int i=1;i<=n;i++)first[i]=0;et=0;for(int i=1;i<n;i++){int x,y;read(x);read(y);buildroad(x,y);buildroad(y,x);}dfs(1);for(int i=1;i<=m;i++){int Sa,Ta,Sb,Tb;read(Sa);read(Ta);read(Sb);read(Tb);get_path(Sa,Ta,A);get_path(Sb,Tb,B);for(int j=1;j<=n;j++)inA[j]=inB[j]=-1;for(int j=0;j<A.size();j++)inA[A[j]]=j;for(int j=0;j<B.size();j++)inB[B[j]]=j;int lenA=A.size()-1,lenB=B.size()-1;int ans=inf;for(int j=1;j<=n;j++)if(inA[j]!=-1&&inB[j]!=-1){ans=min(ans,calc(lenA,inA[j],lenB,inB[j]));if(inA[j]!=0&&inA[j]!=lenA)ans=min(ans,calc(lenA,2*lenA-inA[j],lenB,inB[j]));if(inB[j]!=0&&inB[j]!=lenB)ans=min(ans,calc(lenA,inA[j],lenB,2*lenB-inB[j]));if(inA[j]!=0&&inA[j]!=lenA && inB[j]!=0&&inB[j]!=lenB)ans=min(ans,calc(lenA,2*lenA-inA[j],lenB,2*lenB-inB[j]));}if(ans==inf)puts("-1");else{ans%=lenA*2;if(ans>lenA)write(A[2*lenA-ans]);else write(A[ans]);puts("");}}}
}

1002

很裸的树形dp，感觉应该有原题叭（

设 $f_{i,0/1/2}$ 表示 $i$ 点没有被cover，$i$ 自己这里放了路由器，$i$ 被某个儿子cover了的情况，转移可以看代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 200010int n,a[maxn];
vector<int> to[maxn];
long long f[maxn][3];
void dfs(int x,int fa){f[x][0]=f[x][2]=0;f[x][1]=a[x];long long mi=1e10;//注意这个inf值别给太大了，之前给1e18还WA了一发，因为假如有一个点下面挂了很多个叶子那他的f[x][0]就会爆炸了for(int y:to[x])if(y!=fa){dfs(y,x);f[x][0]+=f[y][2];f[x][1]+=min(min(f[y][0],f[y][1]),f[y][2]);if(f[y][1]<=f[y][2])f[x][2]+=f[y][1],mi=0;else f[x][2]+=f[y][2],mi=min(mi,f[y][1]-f[y][2]);}f[x][2]+=mi;
}int main()
{int T;cin>>T;while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),to[i].clear();for(int i=1;i<n;i++){int x,y;scanf("%d %d",&x,&y);to[x].push_back(y);to[y].push_back(x);}dfs(1,0);printf("%lld\n",min(f[1][1],f[1][2]));}
}

1003

这题其实不是很难，但赛时看过的人少就没怎么看，最后一点时间看的时候就感觉应该可以做，但是dp方向想错了一点，时间不够接着思考了。

实际上就是考虑dp，$f_{l,r,k,r}$ 表示 $[l,r]$ 区间内消得只剩一张 $k$ 类 $r$ 级牌的最优贡献，另外多一种状态是 $f_{l,r,0,0}$ 表示 $[l,r]$ 区间内啥也不剩的最优贡献，很容易就能得到转移，复杂度是 $P(n^{3}mR)$，无压力过。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ll long longint n,m,R,P;
int a[110],V[110];
ll f[110][110][21][8];
int pw[9];int main()
{int T;cin>>T;while(T--){cin>>n>>m>>R>>P;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>V[i];R=min(R,6);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=0;k<=m;k++)//注意初始化别忘记 f[i][j][0][0] 的情况for(int r=0;r<=R;r++)f[i][j][k][r]=-1e13;for(int i=1;i<=n;i++)f[i][i][a[i]][1]=0,f[i][i][0][0]=V[a[i]];pw[0]=1;for(int i=1;i<=R;i++)pw[i]=pw[i-1]*P;for(int len=2;len<=n;len++){for(int i=1;i+len-1<=n;i++){int j=i+len-1;for(int k=1;k<=m;k++)for(int r=1;r<=R&&(1<<r-1)<=len;r++){for(int p=i;p<j;p++){f[i][j][k][r]=max(f[i][j][k][r],f[i][p][k][r]+f[p+1][j][0][0]);f[i][j][k][r]=max(f[i][j][k][r],f[i][p][0][0]+f[p+1][j][k][r]);f[i][j][k][r]=max(f[i][j][k][r],f[i][p][k][r-1]+f[p+1][j][k][r-1]);}if(f[i][j][k][r]>=0)f[i][j][0][0]=max(f[i][j][0][0],f[i][j][k][r]+1ll*V[k]*pw[r-1]);}}}cout<<f[1][n][0][0]<<'\n';}
}

1005

将每个已知串哈希一下放到map里，每次O(1)查询即可。

但是似乎没有什么很好的环哈希技术，只能先求个最小表示法再用串哈希了。

代码很简单就不贴了。

1009

用鸽巢原理判断一下即可，

1010

$x_j\ge x_{j+1}$可以得到一个很经典的性质：$[a_i\ge x_j]$ 的值，只可能形如 $1,1,1,0,0,0,0,...$，也就是至多发生一次转换。

那么也很经典的用线段树来维护就行，$a_i\ge x_j$ 时每次操作相当于区间减，每次看看区间内最小值是否 $<x_j$，是的话暴力进去修改成 $a_i<x_j$ 类的点，这一类点每次操作相当于区间取反并且 $+x_j$。

队友写的代码，有空再补。

1012

是一类很经典的博弈的几乎板子题，但我居然没见过啊可恶，

一棵树每次删掉一条边 以及去掉所有不和根节点相连的点，不能操作者败。

考虑SG函数，假如子树是一条链，那么SG值显然是总边数，这个相当于 Nim 游戏只有一堆石子的情况。

对于一个点，如果有多个儿子，先递归进去求他们的SG值，假如一个儿子SG值为 $p$，那么其实可以直接将子树看做一条长度为 $p$ 的链，那么这个点的SG值就是 $S{G}_x={\oplus }_{y\in son}(S{G}_y+1)$，因为每个儿子的链相当于多了一条边，那么SG值自然就+1，然后根据经典的博弈结论，直接将他们的新SG值异或起来就得到这个点的SG值了。

---

看回这个题，每次删掉一棵子树+不可操作者获胜其实等价于上面的每次删掉一条边以及对应的子树+不可操作者失败。

所以用一个换根dp求一下每个点的SG值即可求出答案。

代码很简单就不贴了。