题目指路: https://codeforces.com/contest/1968/problem/D
题目大意
Bodya, Sasha 两人博弈
输入为
- 一个n的排列p
- 一个长为n的数组a(a[i]代表在i位置的分数)
- 可操作次数k
- 和各自的起点
每次操作,若玩家的位置为pos
- 玩家先加上当前位置下标对应的分数a[pos]
- 然后可以选择:
- 留在当前位置pos
- 或者前往该位置在排列的对应元素p[pos]
若双方都以最优策略游戏,求最后获胜的人,输出姓名,若平局则输出Draw
思路
由排列的性质可以知道,如果以i->p[i]的规则建图e的话,会形成一个或多个有向环
所以题目等价于:求B和S在各自出发点所在的环上操作k次的最大得分
每次操作:要么留在原地,要么沿着有向边往下走一步
比较妙的地方,同时也是我tle的地方在于:对这个最大值的求法
如果k足够大,那么得分最大化的策略很显然:
走到环上得分最大的点上,然后一直不动。
但是k有限制,那么在点pos:
- 如果a[e[pos]]>a[pos],也就是下一个点的得分大于当前点,那么必然移动。
- 反之,那么可能移动/不移动。状态无法确定。
求得分最大值
首先得注意到:最大操作次数是: min(n,k)
k是题目给的步数限制,这个容易理解
但是也要注意到,一个环的阶(就是组成环的点的数量)最大为n,此时所有的排列只组成一个环。
有了前面对k有限制下的分析,可以知道:
一个点如果在环上一直往下走,在回到本身之前,必然在某点停下。
注意到这点很重要,因为知道了这点我们可以枚举停下的位置,然后在所有这些位置里求得分最大值,这个最大值就是该玩家的得分最大值。
在点u停下的得分=得分前缀和+(k-已操作次数)*a[u]
每个点的得分可以由前面的点递推得到
更细节的讲解可以见代码 > <
AC代码
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;ll e[200005],a[200005]; //e存图,a保存得分
ll n,k,pb,ps,p[200005]; //p保存n的排序,pb和ps是B和S两位玩家的出发点ll score(ll pp,ll lmt);
void solve();ll score(ll pp,ll lmt){vector<bool> vis(n+1,false); //vis数组记录点是否走过(由分析可知环上每个点最多走一次)ll ans=0; //ans维护得分最大值ll sum=0; //sum记录得分前缀和ll cnt=0; //cnt记录已操作次数while(!vis[pp] && cnt<=lmt){ //两层限制:(1) 回到自身停下 (2)不能超过最大操作次数lmtans=max(ans,sum+a[pp]*(k-cnt)); //得分=前缀和+剩余操作次数*该点得分sum+=a[pp]; //前缀和更新vis[pp]=true; //该点标记为走过pp=e[pp]; //往下走cnt++; //操作次数自增}return ans; //返回最大值
}void solve(){cin>>n>>k>>pb>>ps;for(ll i=1;i<=n;i++){ //存序列,建图cin>>p[i];e[i]=p[i];}for(ll i=1;i<=n;i++){ //存得分cin>>a[i];}ll lmt=min(n,k); //操作的最大次数限制ll bb=score(pb,lmt);ll ss=score(ps,lmt);// cerr<<bb<<' '<<ss<<'\n';if(bb==ss){cout<<"Draw\n";} else if(bb>ss){cout<<"Bodya\n";} else {cout<<"Sasha\n";}
}
int main(){ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);ll t=1;cin>>t;while(t--){solve();}return 0;
}
收获
对我来说,这题的突破点在于意识到“回到自身前必然在某点停下”这条信息,并且利用这点枚举终点求最大值。