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\) 必敗，否則必勝，
#include<bits/stdc++.h>
using 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 << endl
template<typename Tp> 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<typename Tp> 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549051.html
標籤：其他
上一篇：一文搞定：前端如何選擇Angular、React和Vue三大主流框架
下一篇：全網最詳細中英文ChatGPT-GPT-4示例檔案-復雜函式快速轉單行函式從0到1快速入門——官網推薦的48種最佳應用場景（附python/node.js/curl命令源代碼，小白也能學）