5042. 龟速飞行棋
题目链接：5042. 龟速飞行棋
赛中没过，赛后补题时由于题解有些抽象，自己写个题解。
可以发现每次转移的结果只跟后面两个点的胜负状态有关。
不妨设 \(f_{u,a,b}\) 表示，\(u+1\) 号点的胜负态为 \(a\)，\(u+2\) 号点的胜负态为 \(b\)，此时从 \(1\) 号点出发的胜负态是什么。那么可以发现，利用 \(a, b\) 的数值，可以求出 \(u\) 号点的胜负态 \(uwin\)。这样就可以从 \(n\) 号点的胜负态一路推到 \(1\) 号点的胜负态，然后在推的过程中用记忆化搜索的方式记录一下，就可以简单做了。
当 \(u=n\) 时，不妨令 \(a=1, b=1\)，这样 \(u\) 号点必败。\(u-1\) 号点若 \(t_u = 2\) 必败，否则必胜。
#includeusing namespace std;typedef long long ll;typedef double db;typedef long double ld;#define IL inline#define fi first#define se second#define mk make_pair#define pb push_back#define SZ(x) (int)(x).size()#define ALL(x) (x).begin(), (x).end()#define dbg1(x) cout << #x << " = " << x << ", "#define dbg2(x) cout << #x << " = " << x << endltemplate IL void read(Tp &x) { x=0; int f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch == '-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} x *= f;}int buf[42];template IL void write(Tp x) { int p = 0; if(x < 0) { putchar('-'); x=-x;} if(x == 0) { putchar('0'); return;} while(x) { buf[++p] = x % 10; x /= 10; } for(int i=p;i;i--) putchar('0' + buf[i]);}const int N = 200000 + 5;int n, q;int t[N];int f[N][2][2];int dfs(int u, int a, int b) { if(f[u][a][b] != -1) return f[u][a][b]; int uwin; if(t[u] == 1) uwin = 1 - a; else if(t[u] == 2) uwin = 1 - b; else if(t[u] == 3) uwin = !(a & b); if(u == 1) return uwin; return f[u][a][b] = dfs(u - 1, uwin, a);}void solve() { read(n); for(int i=1;i<=n;i++) read(t[i]); memset(f, -1, sizeof(f)); read(q); while(q--) { int k; read(k); write(dfs(k, 1, 1)); putchar(10); }}int main() {#ifdef LOCAL freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout);#endif int T = 1; // read(T); while(T--) solve(); return 0;}