首页 > 其他分享 >「解题报告」CF936D World of Tank

「解题报告」CF936D World of Tank

时间:2023-06-03 19:33:07浏览次数:31  
标签:Tank 格子 int pos CF936D MAXN ans World dis

lxl。

模拟赛 T1。3000*。不过好像确实不是很难,考场上做出来的。

首先这玩意看起来就很 DP 了。格子很多,但是离散化一下之后就很少了,可以直接跑 DP。那么我们考虑如何 DP 这个过程。

首先很容易发现一点,就是我们攻击到的格子一定会经过。否则显然攻击这个格子是没有意义的。那么我们就可以根据这个来设计状态了。而我们到达一个格子的时候肯定要贪心的使得当前的等待时长越长越好,那么我们就设 \(f_{x, y}\) 表示到达 \((x, y)\) 这个格子的时候经过的等待时长最长是多少。

但是这样显然有一个问题,就是等待时长是有 \(t\) 的上限的,并且我们攻击的时候很可能在还没到第一个被攻击的格子时就已经攻击了很多个格子,所以直接算貌似是假的。那么我们直接把 \(t\) 的上限去掉,这样就不用管一堆限制了,只需要在经过某个障碍时判断一下当前的时长是否够上弹。

但是这样还有个问题啊,就是你不能提前把不在同一行里的格子炸掉啊。那其实也没关系,我们只需要在进行上下移动的时候再对步数取 \(\min\) 即可。这样就很正确了。而容易发现,我们在换行的时候,肯定是会走到某个格子后面的位置,这样我们只需要把每个格子的位置与这个格子后面的位置拿出来离散化,再跑这个 DP 就可以了。

构造方案也不难,只需要找到连续的一段同一行上的路线,然后每隔 \(t\) 格子就攻击一次就行了。需要注意一下最开始的时间。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000006;
int n, m, a, b, t;
int x[MAXN], y[MAXN];
int pos[MAXN];
int dis[MAXN][2];
int g[MAXN][2];
bool sxi[MAXN], syi[MAXN];
vector<pair<int, int>> ans;
void getAns(int x, int y) {
    if (x != 1 || y != 0) {
        if (g[x][y] == 0) getAns(x, y ^ 1);
        else getAns(x - 1, y);
    }
    ans.push_back({ x, y });
}
int main() {
    scanf("%d%d%d%d", &n, &a, &b, &t);
    pos[++m] = 0, pos[++m] = n + 1;
    for (int i = 1; i <= a; i++)
        scanf("%d", &x[i]), pos[++m] = x[i], pos[++m] = x[i] + 1;
    for (int i = 1; i <= b; i++)
        scanf("%d", &y[i]), pos[++m] = y[i], pos[++m] = y[i] + 1;
    sort(pos + 1, pos + 1 + m);
    m = unique(pos + 1, pos + 1 + m) - pos - 1;
    memset(dis, 0x80, sizeof dis);
    dis[1][0] = dis[1][1] = 0;
    for (int i = 1; i <= a; i++)
        sxi[lower_bound(pos + 1, pos + 1 + m, x[i]) - pos] = 1;
    for (int i = 1; i <= b; i++)
        syi[lower_bound(pos + 1, pos + 1 + m, y[i]) - pos] = 1;
    for (int i = 1; i <= m; i++) {
        if (!syi[i] && dis[i][1] < min(dis[i][0], t)) {
            dis[i][1] = min(dis[i][0], t), g[i][1] = 0;
        }
        if (!sxi[i] && dis[i][0] < min(dis[i][1], t)) {
            dis[i][0] = min(dis[i][1], t), g[i][0] = 0;
        }
        if (i != m) {
            if (!sxi[i + 1] && dis[i + 1][0] < dis[i][0] + pos[i + 1] - pos[i]) {
                dis[i + 1][0] = dis[i][0] + pos[i + 1] - pos[i], g[i + 1][0] = 1;
            }
            if (sxi[i + 1] && dis[i][0] + (pos[i + 1] - pos[i] - 1) >= t 
                && dis[i + 1][0] < dis[i][0] + (pos[i + 1] - pos[i]) - t) {
                dis[i + 1][0] = dis[i][0] + (pos[i + 1] - pos[i]) - t, g[i + 1][0] = 2;
            }
            if (!syi[i + 1] && dis[i + 1][1] < dis[i][1] + pos[i + 1] - pos[i]) {
                dis[i + 1][1] = dis[i][1] + pos[i + 1] - pos[i], g[i + 1][1] = 1;
            }
            if (syi[i + 1] && dis[i][1] + (pos[i + 1] - pos[i] - 1) >= t 
                && dis[i + 1][1] < dis[i][1] + (pos[i + 1] - pos[i]) - t) {
                dis[i + 1][1] = dis[i][1] + (pos[i + 1] - pos[i]) - t, g[i + 1][1] = 2;
            }
        }
    }
    if (dis[m][0] >= 0) {
        printf("Yes\n");
        if (g[m][0] == 0) getAns(m, 1);
        else getAns(m, 0);
        int curX = pos[ans[0].first], curY = ans[0].second, tim = 0;
        int begTim = 0;
        vector<int> ans1;
        vector<pair<int, int>> ans2;
        for (int i = 1; i < ans.size(); i++) {
            if (ans[i].second == ans[i - 1].second) {
                if (g[ans[i].first][ans[i].second] == 2) {
                    curX += (t - begTim);
                    ans2.push_back({ curX, curY });
                    begTim = 0;
                    tim -= t;
                }
                tim += pos[ans[i].first] - pos[ans[i - 1].first];
            } else {
                tim = min(tim, t);
                begTim = tim;
                ans1.push_back(pos[ans[i].first]);
                curX = pos[ans[i].first], curY = ans[i].second;
            }
        }
        printf("%lu\n", ans1.size());
        for (int i : ans1)
            printf("%d ", i);
        printf("\n%lu\n", ans2.size());
        for (auto p : ans2) {
            printf("%d %d\n", p.first, p.second + 1);
        }
    } else {
        printf("No\n");
    }
    return 0;
}

标签:Tank,格子,int,pos,CF936D,MAXN,ans,World,dis
From: https://www.cnblogs.com/apjifengc/p/17454443.html

相关文章

  • B2002 Hello,World!
    Hello,World!题目描述编写一个能够输出Hello,World!的程序。提示:使用英文标点符号;Hello,World!逗号后面没有空格。H和W为大写字母。输入格式输出格式样例#1样例输入#1无样例输出#1Hello,World!代码#include<bits/stdc++.h>usingnamespacestd;int......
  • mpi4py.MPI.COMM_WORLD.Get_size失败——mpiexec and python mpi4py gives rank 0 and
    参考:https://stackoverflow.com/questions/29264640/mpiexec-and-python-mpi4py-gives-rank-0-and-size-1  =========================================== 运行代码:importmpi4py.MPIasMPIcomm=MPI.COMM_WORLDcomm_rank=comm.Get_rank()comm_size=comm.G......
  • CUDA ---- Hello World From GPU
    本篇博文仅实现helloworld,先看到效果,具体细节将在后续博文解释。准备如果你是第一次使用CUDA,在Linux下可以使用下面的命令来检查CUDA编译器是否安装正确:$whichnvcc一般,该指令输出为:/usr/local/cuda/bin/nvcc另外,你可能还需要检查下你机器上的GPU型号,可以使用给下面的命令查询:$l......
  • go helloworld 部署到k8s
    打包容器shutdown_Dockerfile同级目录执行sudodockerbuild-thello:v0.01-fshutdown_Dockerfile. 导出docker容器AAA:8.2,8.2表示镜像版本号dockersave-otar名称.tarAAA:8.2BBB:5.6 推送到其它node节点[email protected]:/home/deployscp导......
  • 【虚幻引擎】UE4源码解析FWorldContent、UWorld、ULevel、UGameInstance、UEngine
    一、UEngineEngine,因为也是很基础的类,再加上开发过程中会经常访问到该类型,因此UE4引擎也在代码全局范围内定义了一个该类型的全局变量:UEngine*GEngine供开发者直接调用。该最基础的类型分化成了两个子类:UGameEngine和UEditorEngine。UGameEngine保存了唯一的一个UGameInstan......
  • C#输出helloworld以及定义变量输出变量
    手写第一个C#程序 usingSystem;namespacemyspace{    classxiaoxie    {        staticvoidMain()        {            Console.WriteLine("这是我的第一个程序");        }    }} 赋一个变量,同时输......
  • Revit二次开发系列教程01-如何在Revit中输出Hello World
    目录01项目环境准备02代码示例03输出示例04总结05源码地址01项目环境准备A.开发使用的软件:Revit2021、VisualStudio2022B.将源代码(BlogRevit\AddIns\)文件夹下的文件拷贝至C:\ProgramData\Autodesk\Revit\Addins\2021其中AddInManager插件作用是不重启Revit,即可加载自......
  • 003_HelloWorld
    003_HelloWorld写一个HelloWorld。代码publicclassHello{publicstaticvoidmain(String[]args){System.out.print("HelloWorld!");}}编译javac执行javaHello......
  • Hello World II - python垂直输出Hello World
    描述垂直输出"HelloWorld",全部代码不超过2行。 输入无输出Hello Worldstr="HelloWorld"fornameinstr[:]:print(name)修改:开始没看到要求不超过两行,正确代码为:fornamein"HelloWorld":print(name)题目来源:python123.io......
  • 踏入数字天地之中 | Metaworld SDK 2.0进化纵览
    ​ZEGO从未停止对技术边界的探索,我们力图让用户能够更高效、便捷地使用技术去创造价值。 去年8月,ZEGO打造的元宇宙智能互动引擎首次与大家见面,MetaworldSDK作为其中的核心能力组件,囊括了化身(Avatar)、空间打造和交互互动等关键能力。彼时的Metaworld虽然各项能力都已具备,但在......