【AGC026】Manju Game

这个题我想了一晚上才民白。
设编号为奇数的盒子为黑色,偶数为白色
我们首先要按照奇偶性讨论,n为偶数的时候,这个时候,先手能去到的一定不会低于max(w, b)w是白色的和,b是黑色,后手一定不会低于min(a,b),因此两个人互相牵制,答案就是这两个数。
考虑奇数的情况,首先先手的答案不会低于b,考虑每次我取黑色点的时候,将问题拆分成两半,一半直接选了,留下另一半递归处理,把这个递归树画出来,你会发现所有的节点都是黑色的,也就说这些段落都是先手拿黑后手拿白,只有一个段落是先手拿白后手拿黑的。二分答案=w+x,二分这个x=w_{l,r}-b_{l,r}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, bla, whi, a[300030];

inline bool check(int v)
{
    int su = 0;
    for(ri i = 1; i <= n; i += 2)
        if(su >= v)
            su = max(su + a[i] - a[i - 1], a[i]);
        else
            su += a[i] - a[i - 1];
    return su >= v;
}

int main()
{
    re(n);
    for(ri i = 1; i <= n; re(a[i]), bla += (i & 1) ? a[i] : 0, whi += (!(i & 1)) ? a[i] : 0, i ++);
    if(!(n & 1))
        printf("%d %d", max(bla, whi), min(bla, whi));
    else
    {
        int l = 0, r = bla, ans = 0;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(mid))
                ans = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d %d", max(bla, whi + ans), min(whi, bla - ans));
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注