自动搬运

查看原文

来自洛谷，原作者为

	sunkuangzheng **

搬运于2025-08-24 23:12:49，当前版本为作者最后更新于2025-04-10 18:38:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先记 $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();
}