[CF1369F] BareLee

Para · 2022-09-27 11:57:26 · 题解

思路

总共有 T 轮游戏，每一轮的先手为上一轮的失败者，非常明显的导向 dp。

定义 f_{i,0/1} 表示第 i 轮的先手在最后是否有必败/必胜方案。转移的时候考虑先手在本轮是否有必败/必胜态，推出第 i + 1 轮的先手是谁，逆序 dp 即可。

难点在于如何求解一轮中先手是否有必败/必胜态。设起始数字为 s，上届为 t。不妨先分情况考虑是否有必胜态。

对于先手是否有必败态，可以转换为求解是否有 (s, t / 2) 的必胜态，因为一旦一方跨过了 t/2，另一方进行 \times 2 操作必败。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define inf 1e9
#define pii pair <int, int>
const int mod = 1e9 + 7;
int read () {
    int x = 0, f = 1;
    char ch = getchar ();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar ();
    }
    return x * f;
}
void write (int x) {
    if (x < 0) x = -x, putchar ('-');
    if (x >= 10) write (x / 10);
    putchar (x % 10 + '0');
}
int ch(int s, int t) {
    if (s > t) return 1;
    if (s == t) return 0;
    if (t & 1) return !(s & 1);
    if (s * 2 > t) return s & 1;
    if (s * 4 > t) return 1;
    return ch(s, t >> 2);
}
pii get_ans(int s, int t) {
    return mp(ch(s, t), ch(s, t >> 1));
} 
pii a[100005];
int b[100005][2];
signed main () {
//  freopen (".in", "r", stdin);
//  freopen (".out", "w", stdout);
    int n = read();
    for (int i = 1; i <= n; i++) {
        int s = read(), t = read();
        a[i] = get_ans(s, t);
    }
    b[n][0] = a[n].second, b[n][1] = a[n].first;
    for (int i = n - 1; i >= 1; i--) {
        b[i][1] = ((a[i].second && b[i+1][1]) | (a[i].first && !b[i+1][1]));
        b[i][0] = ((a[i].second && b[i+1][0]) | (a[i].first && !b[i+1][0]));
    }
    write(b[1][1]), putchar(' '), write(b[1][0]), putchar('\n');
    return 0;
}
/*
*/