题解：P12111 [NWRRC2024] Game of Annihilation

· · 题解

首先记 s_a,s_b 是先后手的棋子总数，那么如果 s_a = s_b 则一定平局，否则 s_a > s_b 则先手不败，s_a < s_b 则先手不胜，因此我们要判定的其实只是先手能否胜/平。

先考虑第一种情况，我们希望先手获胜，这时候后手想要平局的唯一策略是一个棋子一直右移，让先手永远也追不上。这时候如果最右边的棋子是后手就直接结束了，否则先手需要在后手的棋子冲过最右边先手的棋子之前吃掉后手棋子。

注意到双方任意时刻都不会左移棋子，左移一定是不优秀的。考虑这么一个贪心：双方任意时刻都会选择自己最靠右侧的棋子向右移动。对于后手这个策略显然正确，因为这样移动就有更大概率可以冲出去。对于先手这个策略也比较对，因为移动右边的棋子有更大概率可以追上后手的棋子。

那么后手的棋子可以分为两部分：左半部分是放弃的，右半部分是向右移动并希望冲出去的，我们不妨枚举这个分界点在哪里，设分界点右侧有 x 个后手的棋子，那么根据上面的分析先手也只会动用前 x 个棋子去吃后手的棋。如何判断后手能不能冲出去？如果当前最右侧的棋子位置是 r，那你其实只需要比较 \sum r - pos_a 和 \sum r - pos_b 的大小。这是因为一次吃棋后，我们仍然可以认为将两个棋子可以一起右移；也不需要考虑后手棋子向右遇到了先手放弃的棋子，这样的 x 一定不是后手的最优解。

判断第二种情况先手能否平局是类似的；判定条件可能有一些 +1 或 -1 的小细节需要考虑清楚。

由于 \sum m_i 比较大，复杂度只能和 n 有关。当然这是简单的，直接双指针一下就是线性。

/**
 *    author: sunkuangzheng
 *    created: 19.11.2024 10:42:23
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,a[N],b[N],c[N]; char d;
void los(){
    cin >> n; ll sa = 0,sb = 0;
    for(int i = 1;i <= n;i ++)
        if(cin >> a[i] >> b[i] >> d,c[i] = (d == 'R'))
            sa += b[i] ; else sb += b[i];
    if(sa == sb) return cout << "Draw 0 0\n",void();
    int i = n,j = n;
    int mxp = 0;
    for(int i = 1;i <= n;i ++) if(c[i]) mxp = a[i];
    if(sa < sb){
        ll sa = 0,sb = 0; 
        while(i && j){
            while(i && (!c[i] || !b[i])) i --;
            while(j && (c[j] || !b[j])) j --;
            if(!i || !j) break;
            ll now = min(b[i],b[j]);
            b[i] -= now,b[j] -= now;
            sa += a[i] * now,sb += a[j] * now;
            if(sa > sb) return cout << "Draw " << mxp << " +\n",void();
        }
        cout << "Second\n";
    }else{
        ll sa = 0,sb = 0;
        while(i && j){
            while(i && (!c[i] || !b[i])) i --;
            while(j && (c[j] || !b[j])) j --;
            if(!i || !j) break;
            ll now = min(b[i],b[j]);
            b[i] -= now,b[j] -= now;
            sa += a[i] * now,sb += a[j] * now;
            if(sb > sa + 1) return cout << "Draw 0 0\n",void();
        }cout << "First " << mxp << " +\n";
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}