2023 - 04 - 03 2016天梯赛初赛(L2)练习

7-12 关于堆的判断

分数 25

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：

  • x is the root：x是根结点；
  • x and y are siblings：x和y是兄弟结点；
  • x is the parent of y：x是y的父结点；
  • x is a child of y：x是y的一个子结点。

输入格式：

每组测试第1行包含2个正整数N（≤ 1000）和M（≤ 20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。

输出格式：

对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。

输入样例：

5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10

输出样例：

F
T
F
T
#include<bits/stdc++.h>

using namespace std;
const int MAX = 10001;
int N, M, num;
string str;
int Heapmin[MAX];

int find(int x)
{
    for (int i = 1; i <= N; i++)
        if (Heapmin[i] == x)return i;
    return 0;
}

int nums(string s)
{
    bool fs = 0;//区间[−10000,10000]
    int sum = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if(s[i] == '-')fs = 1;
        if (isdigit(s[i]))
        {
            if (!sum)sum = s[i] - '0';
            else
            {
                if (s[i] - '0' == 0)
                    sum *= 10;
                else
                {
                    sum *= 10;
                    sum += s[i] - '0';
                }
            }
        }
    }
    if(fs)return -sum;
    return sum;
}

int main()
{
    //建堆
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> Heapmin[i];
        int k = i;
        while (k > 1 && Heapmin[k] < Heapmin[k / 2])
        {
            swap(Heapmin[k], Heapmin[k / 2]);
            k /= 2;
        }
    }
    while (M--)
    {
        cin >> num;
        getline(cin, str);
        if (str.find("root") != str.npos)
        {
            if (Heapmin[1] == num)cout << "T" << endl;
            else cout << "F" << endl;
        }
        else if (str.find("and") != str.npos)
        {
            int T = nums(str);
            if (find(num) / 2 == find(T) / 2)cout << "T" << endl;
            else cout << "F" << endl;
        }
        else if (str.find("parent") != str.npos)
        {
            int T = nums(str);
            if (find(num) == find(T) / 2)cout << "T" << endl;
            else cout << "F" << endl;
        }
        else if (str.find("child") != str.npos)
        {
            int T = nums(str);
            if (find(num) / 2  == find(T))cout << "T" << endl;
            else cout << "F" << endl;
        }
        str.clear();
    }
    return 0;
}

 优化

#include<bits/stdc++.h>
using namespace std;

//优化 使用map容器进行查找操作
const int MAX = 10001;
int N, M, num;
string str;
int Heapmin[MAX];
map<int, int>root;
int nums(string s)
{
    bool fs = 0;//区间[−10000,10000]
    int sum = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '-')fs = 1;
        if (isdigit(s[i]))
        {
            if (!sum)sum = s[i] - '0';
            else
            {
                if (s[i] - '0' == 0)
                    sum *= 10;
                else
                {
                    sum *= 10;
                    sum += s[i] - '0';
                }
            }
        }
    }
    if (fs)return -sum;
    return sum;
}

int main()
{
    //建堆
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> Heapmin[i];
        int k = i;
        while (k > 1 && Heapmin[k] < Heapmin[k / 2])
        {
            swap(Heapmin[k], Heapmin[k / 2]);
            k /= 2;
        }
    }
    for (int i = 1; i <= N; i++)root[Heapmin[i]] = i;
    while (M--)
    {
        cin >> num;
        getline(cin, str);
        if (str.find("root") != str.npos)
        {
            if (Heapmin[1] == num)cout << "T" << endl;
            else cout << "F" << endl;
        }
        else if (str.find("and") != str.npos)
        {
            int T = nums(str);
            if (root[num] / 2 == root[T] / 2)cout << "T" << endl;
            else cout << "F" << endl;
        }
        else if (str.find("parent") != str.npos)
        {
            int T = nums(str);
            if (root[num] == root[T] / 2)cout << "T" << endl;
            else cout << "F" << endl;
        }
        else if (str.find("child") != str.npos)
        {
            int T = nums(str);
            if (root[num] / 2 == root[T])cout << "T" << endl;
            else cout << "F" << endl;
        }
        str.clear();
    }
    return 0;
}

7-10 排座位(并查集操作)

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：

输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。

输入样例：

7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2

输出样例：

No problem
OK
OK but...
No way

#include<bits/stdc++.h>
using namespace std;
const int MAX = 110;
//首先对于关系分为朋友 敌对 无交集
//其中 敌对只有一对一的情况 但是朋友关系存在相交集 即有共同朋友的情况 但不用考虑共同敌对关系
bool enemy[MAX][MAX];
int frend[MAX];
int N,M,K;
//对于朋友网,可以通过查集合的根,若存在公共根说明在一个朋友圈中间
int find_frend(int x)
{
    if(frend[x] == x)
    {//如果自己就是根
        return x;
    }
    return frend[x] = find_frend(frend[x]);
}
void Union(int A,int B)
{
    int x = find_frend(frend[A]);//将A的朋友圈进行压缩
    int y = find_frend(frend[B]);//将B的朋友圈进行压缩
    if(x != y)//俩人不在一个朋友圈中间
        frend[x] = y;//将A拉入B的朋友圈里
}
int main()
{
    cin>>N>>M>>K;
    //初始关系网
    for(int i = 1; i<=N;i++)frend[i] = i;
    int A,B,C;
    while(M--)
    {
        cin>>A>>B>>C;
        if(C == 1)
        {
            Union(A,B);
        }
        else
        {
            enemy[A][B] = enemy[B][A] = 1;
        }
    }
    while(K--)
    {
        cin>>A>>B;
        if(find_frend(A) == find_frend(B) && !enemy[A][B])
            cout<<"No problem"<<endl;
        else if(find_frend(A) == find_frend(B) && enemy[A][B])
            cout<<"OK but..."<<endl;
        else if(enemy[A][B])
             cout<<"No way"<<endl;
        else 
            cout<<"OK"<<endl;
    }
    return 0;
}

7-9 抢红包

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：

输入第一行给出一个正整数N（≤104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

KN1​P1​⋯NK​PK​

其中K（0≤K≤20）是发出去的红包个数，Ni​是抢到红包的人的编号，Pi​（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：

10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10

输出样例：

1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32
#include<bits/stdc++.h>
using namespace std;
const int MAX = 10001;
int N, K;
//结构体(类)写法
class people
{
public:
    int name;
    int num = 0;//抢到红包个数
    double Money = 0;//
}p[MAX];

bool mysort(people A, people B)
{
    if (A.Money != B.Money)return A.Money > B.Money;
    else
    {
        if (A.num != B.num)return A.num > B.num;
        else return A.name < B.name;
    }
}

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        p[i].name = i;
        double sum = 0;
        cin >> K;
        int n;
        double m;
        while (K--)
        {
            cin >> n >> m;
            p[n].Money += m;
            p[n].num++;
            sum += m;
        }
        p[i].Money -= sum;
    }
    sort(p + 1, p + N + 1, mysort);
    for (int i = 1; i <= N; i++)
    {
        cout << p[i].name << " ";
                p[i].Money /= 100;
        printf("%.2lf\n", p[i].Money);
    }
    return 0;
}

 7-11 玩转二叉树

#include<bits/stdc++.h>
using namespace std;
int N;
vector<int> in;
vector<int> pre;
class Tree
{
public:
    int val;
    Tree* L;
    Tree* R;
    vector<int> ans;
    Tree(int N)
    {
        val = N;
        L = R = NULL;
    }
    void CX(Tree* root)
    {
        queue<Tree*> Q;
        Q.push(root);
        while (!Q.empty())
        {
            ans.emplace_back(Q.front()->val);
            if (Q.front()->L)Q.push(Q.front()->L);
            if (Q.front()->R)Q.push(Q.front()->R);
            Q.pop();
        }
        for (int i = 0; i < ans.size(); i++)
        {
            cout << ans[i];
            if (i != ans.size() - 1)cout << " ";
        }
    }
};

Tree* Re(Tree* root)
{
    if (!root) return NULL;
    Tree* LL = Re(root->L);
    Tree* RR = Re(root->R);
    root->L = RR;
    root->R = LL;
    return root;
}

Tree* Built(int prel, int prer, int inl, int inr)
{
    if (prel > prer)return NULL;
    Tree* root = new Tree(pre[prel]);
    int i;
    for (i = inl; i < inr; i++)
        if (pre[prel] == in[i])break;
    int j = i - inl;
    root -> L= Built(prel + 1, prel + j, inl, i - 1);
    root -> R= Built(prel + j + 1, prer, i + 1, inr);
    return root;
}


int main()
{
    cin >> N;
    int num;
    for (int i = 0; i < N; i++)
    {
        cin >> num;
        in.emplace_back(num);
    }
    for (int i = 0; i < N; i++)
    {
        cin >> num;
        pre.emplace_back(num);
    }
    Tree* root;
    root = Built(0, N - 1, 0, N - 1);
    root = Re(root);
    root->CX(root);
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/6504.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

对拍程序 并查集专题 （C++ | 洛谷 | acwing | 蓝桥）

对拍程序 并查集专题 （C++ | 洛谷 | acwing | 蓝桥）

文章目录【蓝桥杯专题】 &#xff08;C | 洛谷 | acwing | 蓝桥&#xff09;1249. 亲戚836. 合并集合837. 连通块中点的数量238. 银河英雄传说 【带权并查集】145. 超市 【并查集 贪心】4793. 危险程度 (连通块并查集 &#xff09;普通oi 读文件对拍程序【蓝桥杯专题】 &#…
阅读更多...
树和二叉树相关的练习（选择题）

树和二叉树相关的练习（选择题）

目录 一、二叉树 二、堆 三、遍历二叉树 一、二叉树 某二叉树共有 399 个结点&#xff0c;其中有 199 个度为 2 的结点&#xff0c;则该二叉树中的叶子结点数为&#xff08; &#xff09;。 A. 不存在这样的二叉树 B. 200 C. 198 D. 199 下列数据结构中&#xff0c;不适合…
阅读更多...
C++ Primer Plus 学习笔记（八）——输入、输出和文件

C++ Primer Plus 学习笔记（八）——输入、输出和文件

1 流和缓冲区 C程序把输入和输出看作字节流。输入时&#xff0c;程序从输入流中抽取字节&#xff1b;输出时&#xff0c;程序将字节插入到输出流中。 缓冲区是用作中介的内存块&#xff0c;它是将信息从设备传输到程序或从程序传输给设备的临时存储工具&#xff0c;通过使用缓…
阅读更多...
HTTP协议：当下最主流的应用层协议之一，你确定不了解一下吗？

HTTP协议：当下最主流的应用层协议之一，你确定不了解一下吗？

一.HTTP协议的含义http是什么&#xff1f;超文本传输协议&#xff08;Hyper Text Transfer Protocol&#xff0c;HTTP&#xff09;是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。‘超’可以理解为除了文本之外的图片&#xff0c;音频和视频&#xff0c;和一些其他…
阅读更多...
STM32基于HAL工程FREERTOS读取DS18B20数据+串口输出

STM32基于HAL工程FREERTOS读取DS18B20数据+串口输出

STM32基于HAL工程FREERTOS读取DS18B20数据串口输出✨申明&#xff1a;本文章仅发表在CSDN网站&#xff0c;任何其他网站&#xff0c;未注明来源&#xff0c;见此内容均为盗链和爬取&#xff0c;请多多尊重和支持原创!&#x1f341;对于文中所提供的相关资源链接将作不定期更换。…
阅读更多...
无需公网IP，远程连接SQL Server数据库【内网穿透】

无需公网IP，远程连接SQL Server数据库【内网穿透】

文章目录1.前言2.本地安装和设置SQL Server2.1 SQL Server下载2.2 SQL Server本地连接测试2.3 Cpolar内网穿透的下载和安装2.3 Cpolar内网穿透的注册3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置4.公网访问测试5.结语1.前言 数据库的重要性相信大家都有所了解&#xf…
阅读更多...
现代前端开发者的自我迷失，你还会前端基础知识吗？

现代前端开发者的自我迷失，你还会前端基础知识吗？

通常来说&#xff0c;我认为情况并不算糟糕&#xff0c;熟练的手可以几乎做到一切。然而&#xff0c;最近我注意到一些事情改变了我对这个行业的看法。似乎在这些无尽的趋势、范式和新奇玩意中&#xff0c;我们忘记了前端开发的支柱&#xff08;意思是忘记了基础知识&#xff0…
阅读更多...
【python】GIL全局锁

【python】GIL全局锁

一、原理&#xff1a; 全局解释器锁&#xff08;Global Interpreter Lock&#xff0c;GIL&#xff09;规定全局范围内任意时候一个进程里只能同时执行一个线程。每一个线程在执行时&#xff0c;都会锁住GIL&#xff0c;以阻止别的线程执行&#xff1b;执行一段时间后&#xff…
阅读更多...
OBCP第四章 SQL调优-SQL执行性能监控

OBCP第四章 SQL调优-SQL执行性能监控

(g)v$sql_audit 全局 SQL 审计表 基于虚拟表__all_virtual_sql_audit的视图&#xff0c; 该虚拟表对应的数据存放在一个可配置的内存空间中 由于存放这些记录的内存是有限的&#xff0c;因此到达一定内存使用量&#xff0c;会触发淘汰 可以用来查看每次请求客户端来源&…
阅读更多...
【操作系统复习】第3章 处理机调度与死锁 3

【操作系统复习】第3章 处理机调度与死锁 3

死锁&#xff08;Deadlock&#xff09;&#xff1a;指多个进程在运行过程中因争夺资源而造成的一种僵局&#xff0c;当进程处于这种僵持状态时&#xff0c;若无外力作用&#xff0c;这些进程都将永远不能再向前推进。 对资源不加限制地分配可能导致进程间由于竞争资源而相互制约…
阅读更多...
JavaSE学习总结（十三）Set集合HashSet集合LinkedHashSet集合TreeSet集合比较器的使用利用Set集合实现去重

JavaSE学习总结（十三）Set集合HashSet集合LinkedHashSet集合TreeSet集合比较器的使用利用Set集合实现去重

JavaSE学习总结&#xff08;十三&#xff09;Set集合/HashSet集合/LinkedHashSet集合/TreeSet集合/比较器的使用/利用Set集合实现去重 一、Set集合 Set集合是Collection集合的一个子接口&#xff0c;实际上Set就是Collection&#xff0c;只是行为略有不同&#xff1a; Set集…
阅读更多...
VUE3项目实现动态路由demo

VUE3项目实现动态路由demo

文章目录1、创建vue项目2、安装常用的依赖2.1 安装elementUI2.2 安装axios2.3 安装router2.4 安装vuex2.5 安装store2.6 安装mockjs3、编写登录页面以及逻辑4、编写首页以及逻辑5、配置router.js6、配置store.js7、配置menuUtils.js&#xff08;动态路由重点&#xff09;8、配置…
阅读更多...
树的前序遍历与中序遍历构造二叉树和树的中序遍历与后序遍历构造二叉树

树的前序遍历与中序遍历构造二叉树和树的中序遍历与后序遍历构造二叉树

目录 一.树的前序遍历与中序遍历构造二叉树 1.题目描述 2.问题分析 3.代码实现 二.树的中序遍历与后序遍历构造二叉树 1.题目描述 2.问题分析 3.代码实现 三.问题思考 一.树的前序遍历与中序遍历构造二叉树 1.题目描述 给定两个整数数组 preorder 和 inorder &#xf…
阅读更多...
【机器学习】Logistic回归---学习笔记

【机器学习】Logistic回归---学习笔记

Logistic回归学习笔记Logistic回归学习线路预备知识&#xff1a;建议先去B站学习一下信息量&#xff0c;熵&#xff0c;BL散度&#xff0c;交叉熵的概念。Logistic回归的函数模型损失最小化架构分类函数最大概率分类函数阈值分类函数Logistic回归的优化算法梯度下降随机梯度下降…
阅读更多...
4.5--计算机网络之基础篇--2.网址到网页解析--（复习＋深入）---好好沉淀，加油呀

4.5--计算机网络之基础篇--2.网址到网页解析--（复习＋深入）---好好沉淀，加油呀

1.浏览器做的第一步工作是解析 URL 对 URL 进行解析&#xff0c;从而生成发送给 Web 服务器的请求信息 URL? URL 实际上是请求服务器里的文件资源 当没有路径名时&#xff0c;就代表访问根目录下事先设置的默认文件&#xff0c;也就是 /index.html 或者 /default.html 这些文件…
阅读更多...
计算机网络复习笔记（三）物理层

计算机网络复习笔记（三）物理层

文章目录一物理层的基本概念四大特性&#xff1a;两种信号&#xff1a;调制和编码传输介质三大部分二物理层的基本通信技术四种信道复用技术数据的传输方式三OSI模型一物理层的基本概念 四大特性&#xff1a; 机械特性 接口是怎么样的 电气特性 用多少伏的电 功能特性 线路上…
阅读更多...
linux基础之计算机基础

linux基础之计算机基础

一、计算机基础 &#xff08;1) 计算机发展&#xff1a;电子管、晶体管、集成电路、大规模集成电路 &#xff08;2) 冯诺依曼体系&#xff1a;用二进制表示数据和指令&#xff1b; 存储程序控制&#xff0c;程序和数据预先存入存储器&#xff1b; 计算机系统5大部分&#xf…
阅读更多...
Python 高级编程（文件操作）

Python 高级编程（文件操作）

文件&#xff1a;存储在某种长期存储设备上的数据&#xff01;&#xff01;包括&#xff08;硬板 u 盘 移动硬盘 光盘&#xff09; 计算机中临时的数据&#xff1a; 存储在内存中&#xff0c;一旦操作结束&#xff0c;内存中的空间就会被释放 文件&#xff08;特指普通文本&am…
阅读更多...
R语言 4.2.2安装包下载及安装教程

R语言 4.2.2安装包下载及安装教程

[软件名称]:R语言 4.2.2 [软件大小]: 75.6 MB [安装环境]: Win11/Win10/Win7 [软件安装包下载]: https://pan.quark.cn/s/b6f604930d04 R语言软件的GUI界面比较的简陋,只有一个命令行窗口,且每次创建图片都会跳出一个新的窗口,比较的繁琐,我们可以安装RStudio,来更方便的操作R(…
阅读更多...
ChatGPT +工业机器人/自动驾驶控制器的一些尝试

ChatGPT +工业机器人/自动驾驶控制器的一些尝试

ChatGPT 的功能目前已扩展到机器人领域&#xff0c;可以用语言直观控制如机械臂、无人机、家庭辅助机器人等的多个平台。这会改变人机交互的未来形式吗&#xff1f; 你可曾想过用自己的话告诉机器人该做什么&#xff0c;就像对人说话那样&#xff1f; 比如说&#xff0c;只要告…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站