Codeforces_943_D_Permutation Game

Gusare / 2024-11-08 / 原文

题目指路: 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)不能超过最大操作次数lmt
        ans=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;
}