草庐IT

ecnuoj 5042 龟速飞行棋

bringlu 2023-04-05 原文

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;
}
飞行棋ecnuojspaninlineclass算法与数据结构

有关ecnuoj 5042 龟速飞行棋的更多相关文章

  1. ruby - 配置思维 sphinx 和飞行 sphinx 时出错 - 2

    我在Heroku上运行了Rails3应用程序。我在我的应用程序中使用ThinkingSphinx搜索引擎。为了让它与Heroku一起工作，我按照Heroku文档中的建议向我的gemfile添加了一个flying-sphinxgem。这是我的gemfile中的内容gem'thinking-sphinx','2.0.11'gem'flying-sphinx','0.7.0'按照此处提到的步骤https://devcenter.heroku.com/articles/flying_sphinx,添加flying-sphinx插件后(Herokuaddons:addflying_sphinx:

  2. javascript - Angular JS 飞行购物车动画指令 - 2

    目前，我正在尝试创建一个Angular指令，为“飞行购物车”设置动画。我发现了很多使用jQuery的解决方案，但没有一个是在纯Angular指令中完成的。我想实现的jQuery飞行推车演示在这里...原始jQueryFlyingCartCodepen:http://codepen.io/ElmahdiMahmoud/pen/tEeDn我对Angular指令没有那么丰富的经验，无法确切地知道如何实现这一点。我已经开始了自己的Codepen，希望弄清楚它，但我无法理解需要发生什么以及如何发生。我目前的代码笔:http://codepen.io/anon/pen/emKoov?editors

  3. c# - WP7 如何在设备上调试飞行模式？ - 2

    有没有办法在设备上调试飞行模式？我尝试在设备设置中打开飞行模式并禁用计算机上的互联网连接，但NetworkInterface.GetIsNetworkAvailable()仍然返回true。我做错了什么吗？ 最佳答案 注意officialdoc底部的评论:ThisAPIwillalwaysreturntrueontheWindowsPhone7emulator.Testingthereforerequiresafacade,mockorconditionalchunkofcode.我刚刚在实际设备上对此进行了测试，确实，它返回了一个

  4. php - 从子目录飞行 PHP 路由 - 2

    所以我正在使用FlightPHP微框架(http://flightphp.com/)进行路由。我的问题是，如何从子目录中运行路由器？我的意思是，本质上，在一个文件夹中以“沙盒方式”运行它。就像，对“/”的请求只是拉取常规的index.php文件。但是对“/flight/file”的请求将使用Flight加载URL。我知道您不能只是将它转储到服务器上的文件夹中并期望它能正常工作，因为FlightPHP需要相对于根目录的URL。有没有办法在网站的其余部分运行常规PHP的目录中独立运行FlightPHP？编辑我试着简单地将.htaccess文件放入子目录。这具有导致路由仍然表现得好像它们来自

  5. 基于simulink的无人机姿态飞行控制仿真 - 2

    目录1.算法描述2.仿真效果预览3.MATLAB核心程序4.完整MATLAB1.算法描述    无人机是无人驾驶飞机的简称（UnmannedAerialVehicle），是利用无线电遥控设备和自备的程序控制装置的不载人飞机，包括无人直升机、固定翼机、多旋翼飞行器、无人飞艇、无人伞翼机。广义地看也包括临近空间飞行器（20-100公里空域），如平流层飞艇、高空气球、太阳能无人机等。从某种角度来看，无人机可以在无人驾驶的条件下完成复杂空中飞行任务和各种负载任务，可以被看做是“空中机器人”。    飞控子系统是无人机完成起飞、空中飞行、执行任务和返场回收等整个飞行过程的核心系统，飞控对于无人机相当于驾

  6. java - 两个时区之间的总飞行时间？ - 2

    如果我们在14:05离开法兰克福并在16:40到达洛杉矶。飞行多长时间？我尝试了以下:ZoneIdfrank=ZoneId.of("Europe/Berlin");ZoneIdlos=ZoneId.of("America/Los_Angeles");LocalDateTimedateTime=LocalDateTime.of(2015,02,20,14,05);LocalDateTimedateTime2=LocalDateTime.of(2015,02,20,16,40);ZonedDateTimeberlinDateTime=ZonedDateTime.of(dateTime,fr

  7. iOS - 在应用程序中跟踪飞行模式状态(我想在应用商店构建中使用它) - 2

    在我的应用程序中，我想知道飞行模式的当前状态。我浏览了很多链接，有些链接说我们可以使用可达性来了解飞行模式状态，但没有得到正确的结果。和使用PrivateFramework:ImportingRadioPreferences.h了解飞行模式状态的方法相同，但有人说使用此方法我们无法将应用程序提交到Appstore。但是我必须将应用提交到应用商店以下是我遵循的一些引用链接Reachabilityairplanemode(3G)vs.WifiUsingPrivateFramework:ImportingRadioPreferences.h 最佳答案

  8. javascript - React Native 检测飞行模式 - 2

    有没有办法检测ReactNative应用程序的飞行模式是否打开/关闭。我找到了npmmodule在Android上实现此目的，但找不到在iOS上实现相同目的的方法。如果无法通过ReactNative执行此操作，是否有一种解决方案可以在Swift中编写代码(这将获取飞行模式设置)并将其插入ReactNative应用程序？谢谢 最佳答案 react-native-system-settings是一个可以检测飞行模式条件的库:SystemSetting.isAirplaneEnabled().then((enable)=>{constst

  9. ios - 将应用程序提交到应用程序商店时的 iTunes 测试飞行问题 - 2

    我在将我的应用程序上传到应用程序商店时收到了来自AppleDeveloper的以下问题，最近已更新到Xcode7.0。更新到Xcode7.0后第一次上传。这是我从iTunes收到的邮件。Deardeveloper,Wehavediscoveredoneormoreissueswithyourrecentdeliveryfor"*********".Toprocessyourdelivery,thefollowingissuesmustbecorrected:InvalidBundle-Anestedbundledoesn'thavetherightplatformslistedinCF

  10. ios - 飞行模式切换时，CoreBluetooth 不会调用 didDisconnectPeripheral - 2

    我有一个CoreBluetooth应用程序。这会在前台启动连接并开始发送/接收数据，并在发送到后台时继续执行此操作，因为我已将bluetooth-central添加到app-Info中的UIBackgroundModes。plist。如果我切换飞行模式设置，我的应用会断开连接，但它不会获得didDisconnectPeripheral回调。为什么是这样？我的解决方法是清除centralManagerDidUpdateState中对我的CBPeriperal对象的所有引用，以便能够在应用程序再次进入前台时进行新的扫描和连接. 最佳答案

随机推荐