1. Python技术站首页
  2. 其他
  3. C++

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

• C++

L2-3 智能护理中心统计

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

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

输入格式：

输入在第一行中给出 2 个正整数：N（≤104）是老人的总数量，即老人们从 1 到 N 编号；M（≤105）是归属关系的总数。

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

A B

表示 A 归属于 B。A 或 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)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年4月18日
下一篇 2023年4月19日

相关文章

  • C++深拷贝与浅拷贝

    浅拷贝的问题 默认提供的拷贝构造就是浅拷贝，如果拷贝的对象中含有成员指针变量指向堆区中的内存空间，那么就会出现两个对象中的成员指针变量指向同一块堆区空间，当方法执行结束后，对象就会被释放，调用析构函数(析构函数中存在释放在堆区开辟的内存空间)，就会存在一块内存空间被多次释放的问题。 解决办法 自己写拷贝构造，让拷贝构造后的对象中的成员指针变量指向一块新的内存…

    C++ 2023年4月25日
    00

  • MordernC++之左值（引用）与右值（引用）

    左值与右值 C++中左值与右值的概念是从C中继承而来，一种简单的定义是左值能够出现再表达式的左边或者右边，而右值只能出现在表达式的右边。 int a = 5; // a是左值，5是右值 int b = a; // b是左值，a也是左值 int c = a + b; // c是左值，a + b是右值 另一种区分左值和右值的方法是：有名字、能取地址的值是左值，没…

    C++ 2023年4月17日
    00

  • Qt源码阅读(四) 事件循环

    事件系统 文章为本人理解，如有理解不到位之处，烦请各位指正。 @ 目录 事件系统 什么是事件循环？ 事件是如何产生的？ sendEvent postEvent 事件是如何处理的？ 事件循环是怎么遍历的？ 事件过滤器 event 夹带私货时间 Qt的事件循环，应该是所有Qter都避不开的一个点，所以，这篇博客，咱们来了解源码中一些关于Qt中事件循环的部分。先抛…

    C++ 2023年4月18日
    00

  • C++：explicit关键字

    C++中的explicit关键字只能用于修饰只有一个参数的类构造函数，它的作用是表明该构造函数是显示的，而非隐式的，跟它相对应的另一个关键字是implicit，意思是隐藏的，类构造函数默认情况下即声明为implicit(隐式)。 那么显示声明的构造函数和隐式声明的有什么区别呢? 来看下面的例子： class CxString // 没有使用explicit关…

    C++ 2023年4月18日
    00

  • 第一部分：介绍 Spdlog 日志库

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

    C++ 2023年4月18日
    00

  • 内存淘汰策略|页面置换算法对比总结

    在学习【操作系统】 【MySQL】【Redis】后，发现其都有一些缓存淘汰的策略，因此一篇小文章总结一下。 目前还没着笔，初略一想MySQL和操作系统应该都是使用的年轻代和老生代的改进策略，而Redis使用的是随机抽的策略。 MySQL MySQL中存在一个内存缓存池，Buffer Pool。里面存在着控制块和缓存的数据页（当然还有些其他缓存，比如：锁信息、…

    C++ 2023年4月18日
    00

  • 【Visual Leak Detector】配置项 SkipCrtStartupLeaks

    说明 使用 VLD 内存泄漏检测工具辅助开发时整理的学习笔记。本篇介绍 VLD 配置文件中配置项 SkipCrtStartupLeaks 的使用方法。同系列文章目录可见 《内存泄漏检测工具》目录 目录 说明 1. 配置文件使用说明 2. 设置是否忽略启动代码引起的内存泄漏 1. 配置文件使用说明 在程序中通过 #include “vld.h” 的方式检测内存…

    C++ 2023年4月18日
    00

  • 最少步数

    在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100*100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一…

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