2023团队天梯模拟赛 L2-3 智能护理中心统计 and L3-1 塔防游戏(23分)

L2-3 智能护理中心统计

智能护理中心系统将辖下的护理点分属若干个大区,例如华东区、华北区等;每个大区又分若干个省来进行管理;省又分市,等等。我们将所有这些有管理或护理功能的单位称为“管理结点”。现在已知每位老人由唯一的一个管理结点负责,每个管理结点属于唯一的上级管理结点管辖。你需要实现一个功能,来统计任何一个管理结点所负责照看的老人的数量。

注意这是一个动态问题,即随时可能有老人加入某个管理结点,并且老人是有可能从一个管理结点换到另一个管理结点去的。

输入格式:

输入在第一行中给出 2 个正整数:N(104)是老人的总数量,即老人们从 1 到 N 编号;M(105)是归属关系的总数。

接下来是 M 行,每行给出一对归属关系,格式为:

A B

表示 A 归属于 BA 或 B 如果是某个管理结点,则用不超过 4 个大写英文字母表示其名称;如果是某位老人,则用老人的编号表示。这里每个 A 保证只有唯一的上级归属 B,且只有这个中心系统本身是没有上级归属的。此外,输入保证没有老人自己承担管理结点的角色,即 B 一定是一个管理结点,不可能是老人的编号。但一个管理结点既可以管辖下级结点,也可以直接护理一部分老人。

随后每行给出一个指令,格式为:

指令 内容

如果 指令 为 T,则表示有老人要入院或转院,内容 是某老人的编号和要去的管理结点的名称,以空格分隔;如果 指令 为 Q,则 内容 是一个管理结点的名称,意思是统计这个结点所负责照看的老人的数量;如果 指令 为 E,则表示输入结束。题目保证指令总数不会超过 100 个。

输出格式:

对每个 T 指令,将对应的老人转存到对应的管理结点名下;对每个 Q 指令,在一行中输出对应管理结点所负责照看的老人的数量。读到 E 指令就结束程序。

输入样例:

10 23
EAST CNTR
ZJ EAST
SD EAST
WEST CNTR
SX WEST
HZ ZJ
JN SD
2 JN
8 JTH
6 XAHP
4 ZDYH
5 ZDYH
ZDYH HZ
HUZ ZJ
JX ZJ
1 JX
3 JN
WZ ZJ
XAHP XIAN
XIAN SX
YL SX
JTH XIAN
7 XAHP
Q EAST
T 1 YL
Q EAST
Q SX
T 8 ZDYH
Q HZ
Q HUZ
T 10 XAHP
Q CNTR
E

输出样例:

5
4
4
3
0
9

题解:老人为叶子节点,考虑到每次只有叶子节点的变化,所以只需要贪心计算叶子节点对对应的这条链的贡献即可

2023团队天梯模拟赛 L2-3 智能护理中心统计 and L3-1 塔防游戏(23分)

//
#include<bits/stdc++.h>
using namespace std;
#define maxn 610938
int n,m;
int cnt1=0,cnt2=0,cnt=200000;
unordered_map<string,int>mapp;
int cot[maxn];
int yezi[maxn];
int pre[maxn];
int main()
{
    cin>>n>>m;
    string s1,s2;
    for(int i=1;i<=m;i++)
    {
        cin>>s1>>s2;
        if(s1[0]>='0'&&s1[0]<='9')
        {
            if(!mapp[s2])
            {
                ++cnt;
                mapp[s2]=cnt;
            }
            pre[stoi(s1)]=mapp[s2];
        }
        else
        {
            if(!mapp[s1])
            {
                ++cnt;
                mapp[s1]=cnt;
            }
            if(!mapp[s2])
            {
                ++cnt;
                mapp[s2]=cnt;
            }
            pre[mapp[s1]]=mapp[s2];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(pre[i]!=0)
        {
            int x=pre[i];
            cot[i]=1;
            while(pre[x]!=x)
            {
                cot[x]++;
                x=pre[x];
            }
            cot[x]++;
        }
    }
    while(1)
    {
        char c;
        cin>>c;
        if(c=='E')
        {
            break;
        }
        if(c=='T')
        {
            int a;
            string b;
            cin>>a>>b;
            int x=pre[a];
            cot[a]=1;
            while(pre[x]!=x)
            {
                cot[x]--;
                x=pre[x];
            }
            cot[x]--;
            pre[a]=mapp[b];
            int y=pre[a];
            cot[a]=1;
            while(pre[y]!=y)
            {
                cot[y]++;
                y=pre[y];
            }
            cot[y]++;
        }
        if(c=='Q')
        {
            string x;
            cin>>x;
            cout<<cot[mapp[x]]<<endl;
        }
    }
}

View Code

 

 
--------------------
L3-1 塔防游戏

有一种简单的塔防游戏是这样的:给定一张由 n 行 m 列个方格子构成的地图,玩家可以任选一个格子放置自己的大本营,还可以在任意一个格子里放置自己的防御堡垒。大本营和每个防御堡垒都有自己的防御能力值 d,表示可以抵御 d 个僵尸的攻击。每一轮游戏开始时,玩家在规定时间内将本级别可以用的防御堡垒布置在地图中,然后僵尸们就从地图边界涌入地图中,向着大本营发起攻击。每轮进攻持续一个固定的时长,结束后剩余的僵尸就原地蒸发。

每队僵尸可以向一个方格的上下左右四个方向移动。如果相邻的目标方格没有堡垒,它们就可以用 1 秒的时间移动过去,否则会被堡垒阻挡或者消灭。对每一队僵尸(从同一地点出发的所有僵尸)而言,每秒会被堡垒消灭 1 个队友,同时消耗掉该堡垒 1 个单位的防御能力。当防御能力降为 0,则该堡垒消失,剩下的僵尸则用 1 秒移动到这个方格继续行进。注意:如果有多支僵尸队都进入了同一个方格,它们并不会合并成一支队伍。

所有的僵尸队都会根据进攻开始时的地图选择被歼灭最少的到达大本营的路线,并且一直按照这个路线行进,中途不因为地图状态的改变而改变。当这样的进攻路径不唯一时,选择能最快到达大本营的路径。题目保证这样的路径所打掉的堡垒的布局是唯一的。

本题就要求你计算出一轮攻击结束时,地图上的布局情况。

输入格式:

输入首先在第一行中给出三个正整数:不超过 100 的 n 和 m,为地图的尺寸;不超过 1000 的 T,为一轮攻击持续的时长。

随后给出 n+2 行,每行给出 m+2 个数字,每行中的数字都用空格分隔,表示攻击开始前地图上的布局。其中第 1 行、第 1 列、第 n+2 行、第 m+2 列是地图边界外僵尸们出发的位置,这些位置上,0 表示没有僵尸,其他正整数表示从该位置出发的僵尸们的数量。而地图中的每个位置上,0 表示没有堡垒,其它正整数表示该位置上堡垒的防御能力值。大本营是一个特殊的建筑,我们用一个负数 D 表示这里是大本营,其防御能力值为 D。这里的防御值和任一队僵尸的数量都不超过 100。

注意:僵尸不可在地图边界外移动,它们的第一个移动目标必须在地图中,所以四个角落里出现的僵尸可以被忽略,因为它们没有进入地图的途径。

输出格式:

输出 n 行,每行 m 个数字,对应攻击结束后地图上每个方格的状态。状态的表示与输入相同:没有堡垒的地方输出 0,有堡垒的地方输出其剩余防御值,大本营的位置上输出其剩余防御值的负值。

注意每行数字间以 1 个空格分隔,行首尾不得有多余空格。

当大本营被攻陷时,游戏即刻结束。此时应输出结束时的地图状态,并且在最后一行输出一句 Game Over

输入样例 1:

7 5 17
0 0 0 0 13 0 0
0 0 0 0 0 0 0
0 0 0 8 0 0 0
0 0 0 0 2 1 0
0 0 0 7 5 3 0
8 0 1 4 -10 1 0
0 0 0 3 3 0 0
0 0 8 0 9 0 0
0 0 0 4 0 0 0
 

输出样例 1:

0 0 0 0 0
0 0 8 0 0
0 0 0 2 0
0 0 7 5 0
0 0 0 -1 0
0 0 0 2 0
0 8 0 9 0
 

样例说明:

地图布局如下图所示。

map.JPG

规模为 13 和 8 的两队僵尸都有两种选择,攻打蓝色或者紫色堡垒都是消耗最少的。在这种情况下,规模为 13 的僵尸队走蓝色比较快,需要 1+1+1+2+4+2=11 秒到达大本营边上;规模为 8 的僵尸队走紫色比较快,需要 1+2+5=8 秒到达大本营边上。

规模为 4 的僵尸队比较惨,只能选择绿色堡垒,最后被大本营边上的绿色堡垒消灭。注意到在攻击过程中,其实它们可以等到紫色堡垒被攻陷之后走紫色原始值为 4 的方格,但是因为路径是在初始状态下选定就不能改的,所以它们不能这样选择。

攻打大本营时,规模为 8 的僵尸队剩下了 3 只先到达,在第 11 秒被大本营消灭。此时大本营还剩 7 个单位的防御值,同时规模为 13 的僵尸队剩下的 8 只进入了大本营相邻的方格,开始攻击。但此时距离本轮结束只剩 6 秒,结果大本营在结束时还剩 1 个单位的防御值,玩家胜。

输入样例 2:

7 5 20
0 0 0 0 13 0 0
0 0 0 0 0 0 0
0 0 0 8 0 0 0
0 0 0 0 2 1 0
0 0 0 7 5 3 0
8 0 1 4 -10 1 0
0 0 0 3 3 0 0
0 0 8 0 9 0 0
0 0 0 4 0 0 0
 

输出样例 2:

0 0 0 0 0
0 0 8 0 0
0 0 0 2 0
0 0 7 5 0
0 0 0 0 0
0 0 0 2 0
0 8 0 9 0
Game Over
题解:
最开始以为是简单的bfs,然后发现题目中有个很关键的点,所有的僵尸队都会根据进攻开始时的地图选择被歼灭最少的到达大本营的路线,并且一直按照这个路线行进,
中途不因为地图状态的改变而改变。当这样的进攻路径不唯一时,选择能最快到达大本营的路径。题目保证这样的路径所打掉的堡垒的布局是唯一的。

也就是说行经路线是一开始就定好的,所以不用宽搜。所以考虑spfa和dij的做法,由于这俩都是单源最短路,所以考虑反向从大本营开始跑spfa。 dis[i][0]代表破坏堡垒和移动的总消耗的最短路径,
dis[i][1]代表仅破坏堡垒的总消耗的最短路径。然后我们对于每个网格点,记录是哪一个最小损失僵尸的点更新的他就行了。
最后按照这个路径进行模拟就行。
大致思路就是这样,但是天梯赛的数据真的好多坑。。。不想改了。。。
下面附上一个23分的代码
2023团队天梯模拟赛 L2-3 智能护理中心统计 and L3-1 塔防游戏(23分)

//
#include<bits/stdc++.h>
using namespace std;
#define maxn 610938
#define inf 1290311
int n,m,t;
struct no
{
    int x,y,nowtime,shu;
};
map<pair<int,int> ,pair<int,int>>mp;
int mapp[200][200];
queue<no>Q;
int dx[6]={1,-1,0,0};
int pre1[200];
int pre2[200];
int dy[6]={0,0,1,-1};
int mark[200][200];
int tx,ty;
int dis[200][200][2];
void bfs()
{
    dis[tx][ty][0]=0;
    dis[tx][ty][1]=0;
    memset(mark,0,sizeof(mark));
    queue<pair<int,int> >K;
    K.push(make_pair(tx,ty));
    while(K.size())
    {
        pair<int ,int> p1=K.front();
        K.pop();
        int x=p1.first;
        int y=p1.second;
        mark[x][y]=0;
        for(int i=0;i<4;i++)
        {
            if(x+dx[i]>=2&&y+dy[i]>=2&&x+dx[i]<=n+1&&y+dy[i]<=m+1)
            {
                
                if(x+dx[i]==tx&&y+dy[i]==ty)continue;
                if(dis[x+dx[i]][y+dy[i]][0]>dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]])
                {
                    dis[x+dx[i]][y+dy[i]][0]=dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]];
                    if(!mark[x+dx[i]][y+dy[i]])
                    {
                        mark[x+dx[i]][y+dy[i]]=1;
                        K.push(make_pair(x+dx[i],y+dy[i]));
                    }
                }
            }
        }
    }
    memset(mark,0,sizeof(mark));
    K.push(make_pair(tx,ty));
    while(K.size())
    {
        pair<int ,int> p1=K.front();
        K.pop();
        int x=p1.first;
        int y=p1.second;
        mark[x][y]=0;
        for(int i=0;i<4;i++)
        {
            if(x+dx[i]>=2&&y+dy[i]>=2&&x+dx[i]<=n+1&&y+dy[i]<=m+1)
            {
                if(x+dx[i]==tx&&y+dy[i]==ty)continue;
                if(dis[x+dx[i]][y+dy[i]][1]>dis[x][y][1]+mapp[x+dx[i]][y+dy[i]])
                {
                    dis[x+dx[i]][y+dy[i]][1]=dis[x][y][1]+mapp[x+dx[i]][y+dy[i]];
                    
                    mp[make_pair(x+dx[i],y+dy[i])]=make_pair(x,y);
                
                    if(!mark[x+dx[i]][y+dy[i]])
                    {
                        mark[x+dx[i]][y+dy[i]]=1;
                        K.push(make_pair(x+dx[i],y+dy[i]));
                    }
                }
                else
                {
                    if(dis[x+dx[i]][y+dy[i]][1]==dis[x][y][1]+mapp[x+dx[i]][y+dy[i]])
                    {
                        if(dis[x+dx[i]][y+dy[i]][0]<=dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]])continue;
                        
                        mp[make_pair(x+dx[i],y+dy[i])]=make_pair(x,y);
                        if(!mark[x+dx[i]][y+dy[i]])
                        {
                            mark[x+dx[i]][y+dy[i]]=1;
                            K.push(make_pair(x+dx[i],y+dy[i]));
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>t;
    for(int i=1;i<=n+2;i++)
    for(int j=1;j<=m+2;j++)
    {
        {
            dis[i][j][0]=inf;
            dis[i][j][1]=inf;
        }
    
        cin>>mapp[i][j];
        if(i==1||i==n+2||j==1||j==m+2)
        {
            if(!mapp[i][j]) continue;
            if(i==1&&(j==1||j==m+2))continue;
            if(i==n+2&&(j==1||j==m+2))continue;
                for(int k=0;k<4;k++)
            {
                if(i+dx[k]>=2&&j+dy[k]>=2&&i+dx[k]<=n+1&&j+dy[k]<=m+1)
                {
                    Q.push(no{i+dx[k],j+dy[k],0,mapp[i][j]});
                }
            }
        }
        if(mapp[i][j]<0)
        {
            tx=i;
            ty=j;
        }
    }
    int fla=0;
    bfs();
    while(Q.size())
    {
        no tmp=Q.front();
        Q.pop();
        int x=tmp.x;
        int y=tmp.y;
        int pret=1+mapp[x][y];
        int num=tmp.shu;
        if(num>mapp[x][y])
        {
            num-=mapp[x][y];
            mapp[x][y]=0;
        }
        else
        {
            mapp[x][y]-=num;
            continue;
        }
    
        while(!(x==tx&&y==ty))
        {
            pair<int,int>R;
            R=mp[make_pair(x,y)];
            x=R.first;
            y=R.second;
            
             if(mapp[x][y])
            {
                if(x==tx&&y==ty)continue;
                pret=pret+1+mapp[x][y];
                if(num>mapp[x][y])
                {
                    num-=mapp[x][y];
                    mapp[x][y]=0;
                }
                else
                {
                    mapp[x][y]-=num;
                    break;
                }
            }
            else
            {
                if(x==tx&&y==ty)continue;
                pret++;
            }
        }
        if(x==tx&&y==ty)
        {
            int w=max(0,min(t-pret,num));
            mapp[tx][ty]+=w;
            mapp[tx][ty]=min(mapp[tx][ty],0);
            if(mapp[tx][ty]==0)
            {
                fla=1;
            }
        }
    }
    for(int i=2;i<=n+1;i++)
    for(int j=2;j<=m+1;j++)
    {
        if(j==2)
        cout<<mapp[i][j];
        else
        {
            cout<<" "<<mapp[i][j];
            if(j==m+1&&i!=n+1)
            cout<<endl;
        }
    }
    if(fla==1)
    {
        cout<<endl;
        cout<<"Game Over";
    }
}

View Code

 

 

原文链接:https://www.cnblogs.com/zdxxdz/p/17331874.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:2023团队天梯模拟赛 L2-3 智能护理中心统计 and L3-1 塔防游戏(23分) - Python技术站

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

相关文章

  • 创建一个简单的Qt工程

    1.打开QtCreator进行如下选择。(开软去官网下载即可,注册邮箱可以断网跳过) 第一步: 选择Application     第二步:这里文件名称和路径都不要有中文 第三步:选择编译模式 点击下一步 第四步:选择 Widget点击下一步   第五步:运行工程,判断是否创建成功 课堂小记: 1.析构函数不能被重载 2.被protect关键字修饰的成员变量…

    C++ 2023年5月7日
    00
  • 【Visual Leak Detector】核心源码剖析(VLD 2.5.1)

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇对 VLD 2.5.1 源码做内存泄漏检测的思路进行剖析。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 源码获取 2. 源码文件概览 3. 源码剖析 3.1 通过 inline hook 修补 LdrpCallInitRoutine 3.2 通过 IAT hook 替换内存操…

    C++ 2023年5月11日
    00
  • 第一部分:介绍 Spdlog 日志库

    什么是 Spdlog 日志库 Spdlog 是一个 C++ 的日志库,它具有高效、易用、跨平台等特点。它可以写入到控制台、文件等输出目标,支持多种日志级别、多线程安全等功能,非常适合在 C++ 项目中使用。 Spdlog 日志库的历史和背景 Spdlog 日志库最初由 Gabi Melman 开发,它最初是为了解决 C++ 中的日志记录问题而创建的。在很长一…

    C++ 2023年4月18日
    00
  • NX二次开发:Checkmate例子根据dfa文件检查模型数据

    NX中的checkmate功能是用于检查模型、图纸数据的工具,在UGOPEN中有例子。手动操作可以检查已加载的装配下所有零部件,可以设置通过后保存模型,检查结果保存到Teamcenter中,默认保存在零组件版本下。 代码中可以设置多个检查规则。相关设置可以在用户默认设置中进行设置。 1 //============================= 2 //…

    C++ 2023年4月18日
    00
  • 第四部分:Spdlog日志库的核心组件分析-logger

    Spdlog是一个快速且可扩展的C++日志库,它支持多线程和异步日志记录。在本文中,我们将分析Spdlog日志库的核心代码,探究其实现原理和代码结构。 Spdlog的基本架构 上一篇文章介绍了spdlog的五个主要组件,其中最重要是Logger、Sink和Formatter其中,Logger负责日志的记录和管理,Sink负责将日志输出到不同的目标(比如控制台…

    C++ 2023年4月18日
    00
  • 【Visual Leak Detector】配置项 ReportEncoding

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇介绍 VLD 配置文件中配置项 ReportEncoding 的使用方法。 同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 配置文件使用说明 2. 设置输出报告的编码格式 2.1 测试代码 2.2 ReportEncoding = ascii 时的输出 2.3 ReportEn…

    C++ 2023年4月18日
    00
  • 驱动开发:探索DRIVER_OBJECT驱动对象

    本章将探索驱动程序开发的基础部分,了解驱动对象DRIVER_OBJECT结构体的定义,一般来说驱动程序DriverEntry入口处都会存在这样一个驱动对象,该对象内所包含的就是当前所加载驱动自身的一些详细参数,例如驱动大小,驱动标志,驱动名,驱动节等等,每一个驱动程序都会存在这样的一个结构。 首先来看一下微软对其的定义,此处我已将重要字段进行了备注。 typ…

    C++ 2023年4月18日
    00
  • 关于自定义Base64编解码的实现

    什么是Base64 Base64编码是将字符串以每3个8比特(bit)的字节子序列拆分成4个6比特(bit)的字节(6比特有效字节,最左边两个永远为0,其实也是8比特的字节)子序列,再将得到的子序列查找Base64的编码索引表,得到对应的字符拼接成新的字符串的一种编码方式。 每个3位8比特数据拆分成4个6比特数据过程如下图所示:      注意事项 Base…

    C++ 2023年4月18日
    00
合作推广
合作推广
分享本页
返回顶部