ecnuoj 5042 龟速飞行棋

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.cnblogs.com/bringlu/p/17282782.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:ecnuoj 5042 龟速飞行棋 - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • python数学建模之三大模型与十大常用算法详情

    下面是关于“Python数学建模之三大模型与十大常用算法”的完整攻略。 1. 三大模型 1.1 线性规划模型 线性规划模型是一种优化模型,它的目是在一组线性约束条件,最大化或最小化一个线性目标函数。在Python中,我们可以使用scipy.optimize.linprog函数来实现线性规划模型。 1.2 非线性规划模型 非线性规模型是一种优化模型它的目标是在…

    python 2023年5月13日
    00
  • C++数据结构之实现邻接表

    C++数据结构之实现邻接表 在图论中,为了表示节点及其之间的联系,我们需要使用数据结构。邻接表是图的一种常见表示方法,实现方便且高效。 什么是邻接表 邻接表是一种图形式的数据结构,由节点和边组成。它使用链式结构来存储相邻节点的信息。邻接表常用于表示有向图、无向图以及加权图。在邻接表中,每一个节点都存储了一个链表,其中包含了该节点与其他节点之间的连接情况。 实…

    数据结构 2023年5月17日
    00
  • 棋盘覆盖问题——分治法

    问题描述 有一个 x (k>0)的棋盘,恰好有一个方格与其他方格不同,称之为特殊方格。现在要用如下图所示的L形骨牌覆盖除了特殊方格以外的其他全部方格,骨牌可以任意旋转,并且任何两个骨牌不能重复。请给出一种覆盖方式。   样例: 输入: 输出:   思路——分治法: 将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。 递归…

    算法与数据结构 2023年4月27日
    00
  • C语言数据结构二叉树简单应用

    C语言数据结构二叉树简单应用攻略 1. 什么是二叉树? 二叉树(Binary Tree)是一种树形结构,它的每个节点最多包含两个子节点,它是非线性数据结构,可以用来表示许多问题,例如家族关系、计算机文件系统等等。 2. 二叉树的基本操作 二叉树的基本操作包括插入、删除、查找等等,本攻略主要讲解插入和查找的实现。 插入操作的代码如下: // 二叉树的插入操作 …

    数据结构 2023年5月17日
    00
  • Python强化练习之Tensorflow2 opp算法实现月球登陆器

    Python强化练习之Tensorflow2opp算法实现月球登陆器 本文将介绍如何使用Tensorflow 2.0实现opp算法来控制月球登陆器的着陆。我们将介绍opp算法的原理实现步骤,并提供两个示例,分别演示如何使用Python实现简单和复杂的月球着陆控制。 opp法原理 opp算法是一种基于模型预测控制(MPC)的控制法。该算法通过预测未来状态来计算…

    python 2023年5月14日
    00
  • C语言 超详细讲解算法的时间复杂度和空间复杂度

    C语言 超详细讲解算法的时间复杂度和空间复杂度 什么是时间复杂度和空间复杂度? 在进行算法分析时,我们需要考虑的两个重要因素是时间复杂度和空间复杂度。时间复杂度是指算法所需要的时间量,而空间复杂度是指算法所需要的空间量。在编写算法时,我们常常需要考虑如何在时间和空间两者之间做出平衡,以使算法既有足够高的效率,又不占用过多的资源。 如何计算时间复杂度? 计算时…

    数据结构 2023年5月17日
    00
  • python查找与排序算法详解(示图+代码)

    下面是关于“Python查找与排序算法详解”的完整攻略。 1. 查找算法 1.1 线性查找算法 线性查找算法是一种简单的查找算法,它的基本思想是从数据集合的第一个元素开始逐个比较,直到找到目标元素或遍完整个数据集合。在Python中,我们可以使用线性查找算法来查找任意数据类型的元素。 下面使用Python实现性查算法: def linear_search(a…

    python 2023年5月13日
    00
  • C语言线性表顺序表示及实现

    C语言线性表顺序表示及实现 线性表的概念 线性表是一种数据结构,它是由n(n≥0)个数据元素a1,a2,…,an 组成的有限序列(元素个数为0时,称为空表),并且这些数据元素遵循一定的线性关系。 线性表的存储结构 线性表的存储结构有两种:顺序存储和链式存储。顺序存储指的是用一段连续的存储单元依次存储线性表的数据元素,线性表中的元素在物理位置上也是相邻的;…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部