中国地质大学（武汉）2025年冬新生赛 个人题解
A+B-Problem
https://ac.nowcoder.com/acm/contest/122886/A
前情提要
本来是想写一份非常非常详细的题解的，但是毕竟不是假期而且也想赶紧写出来，于是只能尽量精炼一点了。又因为有官方题解了，所以还是尽量写点实现细节吧。按个人过题顺序来写：ALCEIDBJHGMFK。
新人第一次牛客题解，如有错误不妥多多见谅，恳求指导，谢谢！
A. A+B-Problem
输入两个整数
，输出
的个位数。
以字符串形式输入，只考虑最后的字符即可。
string s,t;
int main(){
cin>>s>>t;
int x=s[s.length()-1]-'0';
int y=t[t.length()-1]-'0';
cout<<(x+y)%10ll<<endl;
return 0;
}
直接 a+b 错了一发 qwq
L. Ep13.没有爱就看不见
输出一行字符串："It is magic."
纯签到
int main(){
puts("It is magic.");
return 0;
}
C. 七千四百号的回响
给一个长为
的序列
，
个操作每次将
间的数取相反数，求最后序列所有数的和。
对于最后每个位置，要么为相反数（定义为状态 ），要么为本身（定义为状态
）。
那么每次相当于对 内的位置的状态取反，相当于
。维护一个标记数组，故对
位置标记
，
位置标记
，则对标记数组求前缀异或和，前缀异或和对应改位置的翻转状态。
int n;
ll a[N];
int tag[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
int T;scanf("%d",&T);
while(T--){
int l,r;scanf("%d%d",&l,&r);
tag[l]^=1,tag[r+1]^=1;
}
ll sum=0;
for(int i=1;i<=n;++i){
tag[i]^=tag[i-1];
if(tag[i]==0)sum+=a[i];
else sum-=a[i];
}
printf("%lld\n",sum);
return 0;
}
E. 不畏苦暗
解骑士临光为了驱散整片卡西米尔的黑暗，将
根光枪插成一排。每个光枪有一个位置
和亮度
，对任一整数位置
，第
个光枪对该位置的影响遵循以下规则：
- 记该位置与光枪的距离为
(即从
- 当
时，光枪在该位置提供的亮度分别为
，也就是说，每远离光枪一个位置，亮度减少 1。
- 当
时，该光枪不照亮该位置，即提供的亮度为 0。
某个位置的实际亮度取所有光枪对该位置提供亮度中的最大值。
临光想知道，她到底给卡西米尔提供了多少光芒，请你计算所有整数位置实际亮度的总和。
个光枪将数轴分成了
个区间。对于每个区间
，我们如果能知道其从左端点向右照的最大亮度
和从右端点向左照的最大亮度
，就可以通过数学方法
求区间求亮度之和。具体而言，区间答案
：
中左边的式子看作斜率为负直线（自变量
），右边式子看作斜率为正直线，求交点
（当然你可以认为下取整了），则答案变成
这两个求和都可以使用等差数列求和公式计算。对于 不在
的情况，取两个求和区间在
的部分即可。
现在我们要知道每个位置 从左向右照的最大亮度
和从右向左照的最大亮度
，分别从左往右扫一遍和从右往左扫一遍，根据上一个位置的最大亮度和位置及这个位置的亮度，计算位置的最大亮度即可。
对于最左和最右的区间，只需考虑一个方向亮度即可。
注意一下亮度不能为负数的情况和边界情况，具体实现见代码。
int n;
array<ll,2>a[N];
ll lv[N],rv[N];
inline ll calc(ll x,ll y){
if(x>y)swap(x,y);
return (x+y)*(y-x+1)/2ll;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld%lld",&a[i][0],&a[i][1]);
}
sort(a+1,a+1+n);
ll maxv=-INF;
for(int i=1;i<=n;++i){
maxv=maxv-(a[i][0]-a[i-1][0]);
maxv=max(maxv,a[i][1]);
lv[i]=maxv;
}
maxv=-INF;
for(int i=n;i>=1;--i){
maxv=maxv-(a[i+1][0]-a[i][0]);
maxv=max(maxv,a[i][1]);
rv[i-1]=maxv-1;
}
ll ans=0;
for(ll i=1;i<n;++i){
ll l=a[i][0],r=a[i+1][0]-1;//lv+l-x, rv-r+x
ll sm=(lv[i]+l-rv[i]+r)/2;
if(lv[i]+l-sm>=0){
if(sm>=l)ans+=calc(lv[i],lv[i]+l-min(r,sm));
if(sm+1<=r)ans+=calc(rv[i],rv[i]-r+max(l,sm+1));
continue;
}
ans+=calc(lv[i],max(0ll,lv[i]+l-r));
ans+=calc(rv[i],max(0ll,rv[i]-r+l));
}
ans+=calc(lv[n],0);
ans+=calc(rv[0],0);
printf("%lld\n",ans);
return 0;
}
也是拿下牛客 1a 了，这个题的确是实现大于思维。
I. 隔墙花影旧相知
给一个正整数
。
显然只有小于等于 的因子
才会参与到答案中，否则
。
故我们枚举每一个小于 的因子并判断是否合法即可。
int main(){
ll x,ans=0;scanf("%lld",&x);
for(ll i=2;i<=1000005;++i){
if(x%i==0&&(x%(i-1)==0))++ans;
}
printf("%lld\n",ans);
return 0;
}
D. 寻找哈基米
现在立希有一张导航地图，上面显示着她(S)和哈基米(T)的方位、空地(.)、建筑(#)和街道(M)。
立希可以在四个方向上移动，规则如下：
- 普通移动：从当前格子移动到相邻的上/下/左/右格子，前提是该格子为
.、S或T，代价为 1 步。- 穿过街道：不能踩在
M上，但允许跨过恰好一个相邻的M到它后面的格子（同一方向直线跳 2 格）。
落点必须在网格内，且为.、S或T，代价也为 1 步。#为不可通过的建筑，M为街道，不可停留，只能被穿过；.为可走空地。起点S和终点T视为可走格。现在立希想知道她是否能到达哈基米的位置；若能到达，那么她走到哈基米位置的最少步数是多少。
广度优先搜索即可，具体实现见代码
const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};
int n,m,Sx,Sy,Tx,Ty;
int dis[N][N];bool vis[N][N];
char s[N][N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
for(int j=1;j<=m;++j){
if(s[i][j]=='S'){Sx=i,Sy=j;s[i][j]='.';}
if(s[i][j]=='T'){Tx=i,Ty=j;s[i][j]='.';}
}
}
memset(dis,0x3f,sizeof(dis));
dis[Sx][Sy]=0;vis[Sx][Sy]=1;
queue<ttfa>q;q.push({Sx,Sy});
while(!q.empty()){
auto [x,y]=q.front();q.pop();
for(int i=0;i<4;++i){
int tx=x+dx[i],ty=y+dy[i];
if(tx<1||tx>n||ty<1||ty>m||s[tx][ty]=='#')continue;
if(s[tx][ty]=='.'){
if(!vis[tx][ty]){
vis[tx][ty]=1;
dis[tx][ty]=dis[x][y]+1;
q.push({tx,ty});
}
continue;
}
assert(s[tx][ty]=='M');
tx+=dx[i],ty+=dy[i];
if(tx<1||tx>n||ty<1||ty>m||s[tx][ty]=='#')continue;
if(s[tx][ty]=='.'){
if(!vis[tx][ty]){
vis[tx][ty]=1;
dis[tx][ty]=dis[x][y]+1;
q.push({tx,ty});
}
continue;
}
}
}
if(vis[Tx][Ty])printf("%d\n",dis[Tx][Ty]);
else puts("-1");
return 0;
}
B. 共鸣护符
给定两个整数
与
（
），设
。
请构造一个长度为，使其为区间
上所有整数的一个排列（即序列
中
每个数均出现且恰好出现一次），并满足如下条件：
对任意下标
：
- 若
，则必须有
；
- 若
，则必须有
。
如果无法构造满足条件的序列，请输出
"NO"；否则输出"YES"以及任意一个满足条件的序列。
-
，序列
合法
-
，由于相邻的两个数
必为
，序列
合法。
-
，分为两种情况。
（即
为奇数），则序列
合法。
（即
前面，而根据相邻两数前后的结论，
后面，
-
，可以发现序列一定同时包含
int main(){
int Test;scanf("%d",&Test);
while(Test--){
ll l,r;scanf("%lld%lld",&l,&r);
if(r-l+1>=4){
puts("NO");
}
else if(r-l+1>=3){
if(__gcd(l,r)==1){
puts("YES");
printf("%lld %lld %lld\n",r,r-1,r-2);
}else puts("NO");
}
else if(r-l+1>=2){
puts("YES");
printf("%lld %lld\n",r,l);
}
else{
puts("YES");
printf("%lld\n",l);
}
}
return 0;
}
J. 伊波恩·弗塔根的抄本
阿卡姆城有
假设
为阿卡姆城的两位祭品，
为伊格城的两位祭品，如果纽带已经连接
、
与
，则允许产生
的连接。
在你来之前，两座城邦已经产生了
条纽带的连接。为表公平，两座城邦的大祭司将轮流执行献祭，阿卡姆城先手献祭。每次献祭可以选择一条允许连接的纽带进行连接。
如果最终某位大祭司已经没有允许的连接可供选择，那他便失去了觐见古神的机会。问谁能获胜。
这张图最后的边数是有限的，因此只需要判断连边次数的奇偶性即可，奇数次先手赢，偶数次后手赢。
这是一张二分图，记左边的点为 ，记右边的点为
。
如果存在边 和
，则我称这个点对
被“激活”了，并加入到一个激活的集合中，如果有
和这个激活的集合中的任意一个点
有边，则
可以跟这个集合中的所有点
连边。
这个被激活的集合不止可以包含两个点，如果点对 ，
被激活，他们会进入同一个集合中，所有与这一个集合中任意一个点有边的
，都能和这个集合中所有的点连边。这样这个集合就是一个完全二分图中右侧的所有点。
我们枚举左端点，把所有能激活的右端点都激活，并把他们分配在若干个集合中（可以使用并查集维护）。对于一个大小为 集合，找出与之相连的左端点个数
，则这张子图最后的边个数为
，又可以知道原来的边数，则能计算出新加的边数。
具体实现见代码。
int n,m,k,fa[N];
inline int fidf(int x){
return x==fa[x]?x:fa[x]=fidf(fa[x]);
}
inline void merge(int x,int y){
x=fidf(x),y=fidf(y);
if(x==y)return;
fa[y]=x;
}
vector<int>tar[N],bak[N];
vector<int>lis[N];int tot=0,num[N],idx[N];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;++i)fa[i]=i;
for(int i=1;i<=k;++i){
int u,v;scanf("%d%d",&u,&v);
tar[u].push_back(v);
bak[v].push_back(u);
}
for(int i=1;i<=n;++i){
if(tar[i].size()>1){
for(int j=1;j<(int)tar[i].size();++j){
merge(tar[i][j],tar[i][j-1]);
}
}
}
for(int i=1;i<=m;++i){
int x=fidf(i);
++num[x];
for(auto u:bak[i]){
lis[x].push_back(u);
}
}
ll ans=0;
for(int i=1;i<=m;++i){
if(num[i]<=1)continue;
ll val=lis[i].size();
sort(lis[i].begin(),lis[i].end());
lis[i].erase(unique(lis[i].begin(),lis[i].end()),lis[i].end());
ll cnt=lis[i].size();
ans+=cnt*num[i]-val;
}
//printf("%lld\n",ans);
if(ans&1ll)puts("Arkham");
else puts("Yightek");
return 0;
}
H. 魔女之旅
给一个序列长为
范围的连续区间的最大平均值。
二分答案，判断当前二分出来的 能否小于等于某一个区间的平均值，如果可以，则看答案能否更大，否则答案一定更小。现在考虑如何判断
是否合法，考虑求前缀和
，则如果
合法，存在一个区间
满足
现在定义 ，问题转化为是否存在两个位置
，
，与此同时有限制
。假设当前考虑
，实际上是找
范围内的
最小值看看能否小于等于
。
一个连续平移范围内的最小值，可以使用单调队列，还有很多别的做法。具体见时间。
int n,L,R;
ll a[N],s[N],v[N];
int q[N*2];
inline bool check(ll x){
ll minv=0;int l=1,r=0;
for(ll i=1;i<=n;++i){
int j=i-L;
if(j>=0){
while(l<=r&&i-q[l]>R)++l;
while(l<=r&&v[q[r]]>v[j])--r;
q[++r]=j;
}
ll val=s[i]-x*i;v[i]=val;
//printf("%lld %lld\n",val,minv);
if(l<=r&&val-v[q[l]]>=0)return 1;
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&L,&R);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
ll l=0,r=1e10,ans=-1;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid))l=mid+1,ans=mid;
else r=mid-1;
}
printf("%lld\n",ans);
return 0;
}
G. 猫猫虫困境III
在二维整数网格
上，有
。
平面上固定有一个黑洞，坐标为。
此外，平面上给定。
时间离散为
，所有未离开的猫猫虫在每个整数时刻顺序进行如下三个阶段：
主动移动阶段：每只猫猫虫可以选择不动，或沿轴向主动移动一个单位（将
增减 1，两者不可同时进行）。假设猫猫虫此刻坐标为
，那么其在该阶段可以移动到
中的一个位置。
吸引阶段：对于仍未离开的猫猫虫，黑洞会将其同时在两个坐标方向上各向黑洞靠近一个单位。若其此时位置为
其中为符号函数。具体地，当
时，
; 当
时，
; 当
时，
。
判定阶段：判定此时所有还未离开的猫猫虫的位置，所有与出口位置重合的猫猫虫立即离开。一旦猫猫虫离开，便不再参与任何阶段。
多只猫猫虫互不影响；出口可以被多只猫猫虫在不同或相同时间使用。不要求出口两两不同；多只猫猫虫可以有相同的初始位置；猫猫虫的初始位置可以与出口重合，但不代表其可以直接离开。
你的任务是判断对每一只猫猫虫，是否存在一种策略，使其在有限时间内离开。
首先明确，由于坐标为负的地方没有出口，则将一个猫猫虫移动到坐标为负的地方是无意义且浪费步数的。
对于 的猫猫虫，如果主动移动阶段执行
，则黑洞阶段会执行
，最终的效果为
；如果主动阶段执行
，则最终的效果
。也就是说，我们每次至少将横坐标或纵坐标减小
（故主动将横纵坐标减小是不优的）。这样它可以走到所有横纵坐标均小于等于它的出口（除开这个位置本身）。
对于位于坐标轴上的猫猫虫，我们进行类似的分析，发现它只能原地不动，或者向原点移动一个单位。这样它可以走到所有横纵坐标均小于等于它的出口（包括这个位置本身）。
现在问题转化为，有若干个出口位置为 ，对于一个查询
，要找是否有一个出口满足
。
那么我们对所有横坐标排序（并将其离散化），求出口纵坐标的前缀最小值，对一个查询 ，看看前缀最小值是否小于
即可。
注意我们说对于不在坐标轴上的猫猫虫，由于与猫猫虫初始位置重合的出口无法走到，因此需要同时查询 和
，其中有一个合法就合法。
int n,m;
array<ll,2>a[N],b[N];
ll lis[N*2],minv[N*2];int tot;
int main(){
memset(minv,0x3f,sizeof(minv));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld%lld",&a[i][0],&a[i][1]);
lis[++tot]=a[i][0];
}
for(int i=1;i<=m;++i){
scanf("%lld%lld",&b[i][0],&b[i][1]);
lis[++tot]=b[i][0];
}
sort(lis+1,lis+1+tot);
tot=unique(lis+1,lis+1+tot)-lis-1;
for(int i=1;i<=m;++i){
int loc=lower_bound(lis+1,lis+1+tot,b[i][0])-lis;
minv[loc]=min(minv[loc],b[i][1]);
}
//minv[0]=INF;
for(int i=1;i<=tot;++i){
minv[i]=min(minv[i],minv[i-1]);
}
for(int i=1;i<=n;++i){
int loc=lower_bound(lis+1,lis+1+tot,a[i][0])-lis;
if(a[i][0]==0){
if(minv[loc]<=a[i][1])puts("YES");
else puts("NO");
continue;
}
if(a[i][1]==0){
if(minv[loc]==0)puts("YES");
else puts("NO");
continue;
}
if(minv[loc-1]<=a[i][1]||minv[loc]<a[i][1])puts("YES");
else puts("NO");
}
return 0;
}
M. 如果是勇者辛美尔的话
感觉官方题解写得真没毛病，这里直接复制粘贴，然后我说点细节即可。
问题等价转化为所有的激活点都落在某个半圆内，即激活节点集合的极角最大相邻间隔小于等于
的概率是多少。
考虑如何计算公式：为了不重复计算，我们令每个枚举的点为逆时针顺序最后激活的点。那么以该点逆时针旋转
连乘用前缀积维护即可。注意前缀积存在
时的处理。总复杂度为
实现时，将角度排序并把原序列角度 后复制一次，那么我们假设逆时针区域最后激活的点为
，计算时只需考虑下标大于
的点。
实际上题解中公式也并不完全严谨：
-
要考虑所有点均不被激活的情况，概率为
。
-
不同点的角度可能相同，为了不重复计算答案，因此还要对点排序后编号，即要加上限制条件
，最后变成
由于输入角度只有三位小数，故不用考虑 的精度问题。其余具体见代码
好的我又来多写几句了，因为我发现真的有人不会处理前缀积存在 的情况。对于
的位置，如果它在要求的区间中，则答案为
，否则应该不影响答案，将他设成
即可；然后再额外开一个数组记录前缀中
的位置的个数，就可以判断区间中是否存在
了。当然如果有更好的写法也欢迎分享。
int n;
struct node{
double ag;
ll p;
}a[N];
inline bool cmp(node x,node y){
return x.ag<y.ag;
}
double b[N];
ll p[N],mul[N],cnt[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
ll x=0,y=0;
scanf("%lf%lld%lld",&a[i].ag,&x,&y);
a[i].p=(x%P)*fpr(y%P)%P;
}
sort(a+1,a+1+n,cmp);
mul[0]=1;
for(int i=1;i<=2*n;++i){
if(i<=n)b[i]=a[i].ag,p[i]=a[i].p;
else b[i]=b[i-n]+2*pi,p[i]=p[i-n];
if(p[i]==1){
cnt[i]=cnt[i-1]+1;
mul[i]=mul[i-1];
}else{
cnt[i]=cnt[i-1];
mul[i]=mul[i-1]*(1-p[i]+P)%P;
}
}
ll ans=(cnt[n]>=1?0:mul[n]);
for(int i=1;i<=n;++i){
int l=i+1,r=upper_bound(b+1,b+1+2*n,b[i]+pi)-b-1;
if(b[l]-b[i]>pi||l>r){ans=(ans+p[i])%P;continue;}
if(cnt[r]-cnt[l-1]>=1){ans+=0;continue;}
ans=(ans+p[i]*mul[r]%P*fpr(mul[l-1])%P)%P;
}
printf("%lld\n",ans);
return 0;
}
感觉是全场出得最好的一题，尽管这个前缀积为 有点烦。然后赛时读错题了写了个原点被三角形覆盖的期望次数，直接导致想复杂了。
F.邵接待之战
大模拟，题面太长了
如果出错了的话，可以再读一边题面，感觉把坑点都提到了。
直接被大模拟吓退了，其实看了下也不是很复杂，但还是懒得写，最后为了写题解也还是写了一下，很丑而且没封装。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>ttfa;
struct node{
ll mx,x,my,y;
int skip,cnt;
}a[2];
queue<ttfa>q[2];
inline void addy(int i,ll v){
a[i].y=min(a[i].my,a[i].y+v);
}
inline void dely(int i,ll v){
a[i].y=max(0ll,a[i].y-v);
}
inline void del(int i,ll v){
a[i].x=max(0ll,a[i].x-v);
a[i].y=max(0ll,a[i].y-v);
}
char instr[10];
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
for(int i=0;i<2;++i){
scanf("%lld%lld",&a[i].mx,&a[i].my);
a[i].x=a[i].mx,a[i].y=a[i].my;
}
int R;scanf("%d",&R);
for(int r=1;r<=R;++r){
int c1,c2;scanf("%d%d",&c1,&c2);
for(int i=1;i<=c1;++i){
ll val;scanf("%s%lld",instr,&val);
if(a[0].skip)continue;
if(instr[0]=='A')q[0].push({1,val}),++a[0].cnt;
if(instr[0]=='D')q[0].push({2,val});
if(instr[0]=='H')q[0].push({3,val});
}
for(int i=1;i<=c2;++i){
ll val;scanf("%s%lld",instr,&val);
if(a[1].skip)continue;
if(instr[0]=='A')q[1].push({1,val}),++a[1].cnt;
if(instr[0]=='D')q[1].push({2,val});
if(instr[0]=='H')q[1].push({3,val});
}
while(1){
if(q[0].empty()&&q[1].empty())break;
if(q[0].empty()&&a[1].cnt==0)break;
if(q[1].empty()&&a[0].cnt==0)break;
ll o0=0,c0=0,o1=0,c1=0;
if(!q[0].empty())o0=q[0].front().first,c0=q[0].front().second;
if(!q[1].empty())o1=q[1].front().first,c1=q[1].front().second;
{
if(o0==1||o0==2)q[0].pop();
if(o1==1||o1==2)q[1].pop();
//printf("action %d %d %d %d\n",o0,c0,o1,c1);
a[0].cnt-=(o0==1);
a[1].cnt-=(o1==1);
if(o0==0){
if(o1==1)del(0,c1);
if(o1==3)q[1].pop();
}
if(o0==1){
if(o1==1||o1==0){
if(c0>c1)del(1,c0);
if(c0<c1)del(0,c1);
}
if(o1==2){
if(c0>c1)del(1,c0-c1);
if(c0<c1)dely(0,c1-c0);
}
if(o1==3){
if(c0>c1){del(1,c0);q[1].pop();}
else addy(1,c1);
}
}
if(o0==2){
if(o1==1){
if(c0>c1)dely(1,c0-c1);
if(c0<c1)del(0,c1-c0);
}
if(o1==2){
if(c0>c1)dely(1,c0);
if(c0<c1)dely(0,c1);
}
if(o1==3){
if(c0>c1){dely(1,c0);q[1].pop();}
else addy(1,c1);
}
}
if(o0==3){
if(o1==0)q[0].pop();
if(o1==1){
if(c1>c0){del(0,c1);q[0].pop();}
else addy(0,c0);
}
if(o1==2){
if(c1>c0){dely(0,c1);q[0].pop();}
else addy(0,c0);
}
if(o1==3){
if(c0>c1){addy(0,c0);q[1].pop();}
if(c0<c1){addy(1,c1);q[0].pop();}
if(c0==c1){q[0].pop(),q[1].pop();}
}
}
}
if(a[0].x==0||a[1].x==0)goto finish;
if(a[0].y==0){
if(!a[0].skip)a[0].skip=r;
a[0].cnt=0;
while(!q[0].empty())q[0].pop();
}
if(a[1].y==0){
if(!a[1].skip)a[1].skip=r;
a[1].cnt=0;
while(!q[1].empty())q[1].pop();
}
}
if(a[0].skip&&r>a[0].skip){a[0].skip=0;a[0].y=a[0].my;}
if(a[1].skip&&r>a[1].skip){a[1].skip=0;a[1].y=a[1].my;}
}
finish:
printf("%lld %lld\n",a[0].x,a[1].x);
return 0;
}
K. 黄金魔女的谜题
给定一棵以节点
, Bob 位于节点
（保证
），两人轮流行动，Alice 先手。
- 祖先 / 后代：均相对根 1 定义某节点的子树包含其自身及所有后代；某节点的祖先指从该节点沿父指针向上所能到达的所有节点（不含自身），其中与其距离为 1 的祖先称为父节点。
- 标记：Alice 维护自己的标记集合
, Bob 维护自己的标记集合
, 两者相互独立, 初始两集合为空。一名选手若将某节点加入自己的集合，并不影响对方是否可以在其回合将同一节点加入其集合。
- 代价：当某位选手在其行动中标记了若干节点时，需要支付这些被其标记节点权值之和，记为该选手在本局的总代价。移动到祖先的操作不需要支付代价。
行动规则：
在自己的回合中，当前选手（位于节点
）必须选择并执行以下两种操作之一：
向上跳：任选一个祖先节点
（可为直接父节点，也可为更高层祖先），将自己的位置从
），则该操作不可选。
向下标记并跳：任选一个未被该选手标记的节点
将节点
注：操作 2 中的"未被标记"仅指该名选手自己的标记集合中不包含该节点；对手是否标记过该节点不作限制。
胜负判定：
- 当执行完某名选手的一次行动后，若两名选手的位置处于同一节点，则执行这次行动的选手立即获胜，对局结束。
- 如果轮到某名选手行动时，他没有任何合法行动（既不能向上跳，也无可标记的子树节点），则其对手立即获胜，对局结束。
可以证明，对局一定在有限步内结束。
在双方都以"使自己获胜"为目标且都采取最优策略的前提下：
- 判断谁能保证获胜（Alice 或 Bob）。
- 输出获胜者为确保胜利所需支付的最小总代价, 若获胜者在最优策略下无需进行任何标记操作，则代价为 0。这里只统计最终获胜者在其最优取胜策略下需要支付的总代价；对手的代价不计入。
首先，如果 ，则 Bob 是 Alice 的祖先，Alice 可以执行操作 1 无代价地一步干掉 Bob。
如果 ，则 Bob 是 Alice 子树中的一个点，Alice 是必胜的，并且一种获胜方法的代价是
，但不一定是最优的，我们暂且按下不表。
对于其他的情况，记 。可以发现，一旦有一名玩家率先走到了
或
的祖先，另一名玩家还在
的某棵子树中，则这名玩家可以直接向上跳直接获胜。也就是说，对于任意一名玩家，他们都希望在自身所处的
的某棵子树（不含
）中尽量多走，直到对手走到
及其祖先。那么我们就要计算两名玩家在所属的
的子树中最多能走的步数
和
。（注意是
的某棵子树，而不是以
或以
为根的子树，因为两名玩家只要不走到
或更上都行。）如果
则 Alice 获胜，若
，则 Bob 获胜。
记 能向上走到的最浅节点为
（
为
的儿子），
能向上走到的最浅节点为
，则 Alice 只能在以
为根的子树内走，Bob 只能在
为根的子树内走，直到一方走不了然后失败。
我们要尽量增加向上走的步数，因为他是无代价的，显然对于连续上多步，不如一步一步上。对于玩家 Alice，先让 走
步无代价且最多步上到
节点，然后之后每次都可以选择
子树内的某个点
向下跳
步，花费代价
，接着无代价地走
步回到
节点，直到所有
子树内的点都被标记。这样进行总地操作次数最多，为
。对 Bob 也进行同样的操作。
可以粗略地这样理解：可以一开始花费 代价走
步，之后选择每次花费
代价
步，选择共有
种。假设 Alice 能够获胜，那么她则要最小化走一定步数时的代价，这就变成了一个背包的问题。背包的大小是
级别的，而加入的物品个数也为
个为
级别，直接背包是
无法接受。发现
，我们将问题转化为求花费代价为
时，最多能走多少步
（原先为求走
步时，最小的花费
），则背包空间优化为
，时间复杂度为
，可以通过本题。
现在我们需要继续考虑 的情况了，如果 Alice 走到一个新位置
，满足
不为
或
，我们可以根据刚刚的策略来计算代价。显然 Alice 只能向下走，但我们仍然不能枚举每一个
，跑上面的方法，这样复杂度达到了
。
可以发现走到 的代价为
，步数为
，然后这个时候我们走到
能向上走到的最浅节点
，无代价走步数
。相当于走
步，花费代价
，并且现在对于
子树中的选择，不能再选择走到
点。那么对于子树
而言，无论一开始选择走到哪一个
，始终可以看作每次选择花费
代价
步，
为子树
中的所有点。
则我们只需考虑 的这条链上所有与链相连的子树即可。对于一颗子树
，Alice 最多可以在其中走
次；而 Bob 能走上的最浅节点即为
，
仍是链上的点，然后
与
的父亲相同，为
，需要计算 Bob 能走的最多次数，才能判断输赢并计算最小代价。
现在来考虑一下实现，一个经典结论就是
记录 ，一个子树
内能走的最大步数（不考虑一开始往上无代价走的步数）就为
，一开始遍历树时就可以计算出来，然后后续查步数就可以
计算。
然后我们设计一个函数计算一个子树内走 步时最小的花费
（不考虑一开始往上无代价走）。就是一个刚才我们所说的
背包。对于额外的无代价走步数，对这个背包答案进行下标的变化即可。具体实现见代码。
typedef long long ll;
typedef pair<int,int>ttfa;
const int N=2003,W=100;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
int siz[N],dep[N],sum[N],n,A,B,a[N],fa[N];
vector<int>tar[N];
void dfs(int u,int f){
siz[u]=1;fa[u]=f;
dep[u]=dep[f]+1;
for(auto v:tar[u]){
if(v==f)continue;
dfs(v,u);
sum[u]+=sum[v];
siz[u]+=siz[v];
}
sum[u]+=siz[u];
}
inline int __lca(int x,int y){
if(dep[x]>dep[y])swap(x,y);
while(dep[y]>dep[x])y=fa[y];
while(x!=y)x=fa[x],y=fa[y];
return x;
}
int dp[N*N],lis[N],tot,f[N*W];
void getlis(int u,int f){
lis[++tot]=u;
for(auto v:tar[u]){
if(v==f)continue;
getlis(v,u);
}
}
inline void calc(int rt){
tot=0;getlis(rt,fa[rt]);
for(int i=0;i<=sum[rt];++i)dp[i]=INF;
/* n^3 做法
dp[0]=0;
for(int i=1,m=0;i<=tot;++i){
int c=dep[lis[i]]-dep[rt]+1,v=a[lis[i]];
m+=c;
for(int j=m;j>=1;--j){
dp[j]=min(dp[j],dp[max(0,j-c)]+v);
}
}
*/
// 正解 n^2w 做法
for(int i=0;i<=W*tot;++i)f[i]=0;
f[0]=0;
for(int i=1,m=0;i<=tot;++i){
int w=a[lis[i]],v=dep[lis[i]]-dep[rt]+1;
m+=w;
for(int j=m;j>=w;--j){
f[j]=max(f[j],f[j-w]+v);
}
}
for(int i=0;i<=W*tot;++i)dp[f[i]]=min(dp[f[i]],i);
for(int i=sum[rt]-1;i>=0;--i)dp[i]=min(dp[i+1],dp[i]);
}
int main(){
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i<n;++i){
int u,v;scanf("%d%d",&u,&v);
tar[u].push_back(v);
tar[v].push_back(u);
}
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
dfs(1,0);
int lca=__lca(A,B),xx=0,yy=0,mov_A=0,mov_B=0;
//printf("%d\n",lca);
if(lca==B){
puts("Alice");
puts("0");
return 0;
}
if(lca==A){
int ans=a[B];
xx=B;
while(xx!=A){
mov_B=sum[xx];
for(auto u:tar[fa[xx]]){
if(u==fa[fa[xx]]||u==xx)continue;
calc(u);mov_A=sum[u];
if(mov_A>mov_B)ans=min(ans,dp[mov_B+1]);
}
xx=fa[xx];
}
puts("Alice");
printf("%d\n",ans);
return 0;
}
xx=A,yy=B;
while(fa[xx]!=lca)xx=fa[xx];
while(fa[yy]!=lca)yy=fa[yy];
mov_A=sum[xx]+dep[A]-dep[xx];
mov_B=sum[yy]+dep[B]-dep[yy];
if(mov_A>mov_B){
puts("Alice");
calc(xx);
printf("%d\n",dp[max(0,mov_B+1-(dep[A]-dep[xx]))]);
}else{
puts("Bob");
calc(yy);
printf("%d\n",dp[max(0,mov_A-(dep[B]-dep[yy]))]);
}
return 0;
}
为什么我要提一嘴 的做法，因为这个入一开始没想到要
，结果优化了一下还真过了，在代码中也有体现。
最后欢迎关注本菜鸡某客园，最近应该会积极更新 CF 场次和各类题解。（如果不符合平台规定抱歉了）
