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
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 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
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net