【大模拟】逻辑回环类

区块链

AcWing 3285. 区块链 - AcWing

区块链涉及密码学、哈希算法、拜占庭问题、共识算法、故障模型、网络模型等诸多知识,也在金融等领域有广泛的应用。

本题中,我们需要实现一个简单的区块链系统。

在一个分布式网络中,有 nn 个节点通过 mm 条边相连,节点编号从 11 至 nn。

每个节点初始化都有一个相同的“创世块”,链长都为 11。

每个节点在整个过程中都需要维护一条主链,任何操作都只在主链上进行。

在整个系统中产生的每个新块都有唯一的整数编号,创始块的编号为 00,其余块的编号都为正整数。

当某个节点的链更新时,会将它的主链发送给它相邻的节点(邻居);而当节点收到链时,决定是否更新自己的主链。

下列情况可能会导致某个节点的链更新:

  • 某个节点接收到邻居发送过来的链,与当前自己的主链进行比较:
    • 如果接收到的链更长,则将其作为自己的主链:
    • 如果收到的链长度与自身主链相同,且最后一块编号更小,则将其作为自己的主链
    • 如果接收到的链更短,则直接忽略该链。
  • 某个节点产生一个新块,将新块放在主链的尾部。

假设网络带宽足够大,每个节点状态更新后,会立刻将自己的主链同时发送给所有邻居。

每个节点在每个时刻总是先接收链,再产生新块(注意这与实际的区块链工作方式不相同)。

每个节点发送、接收、产生块不消耗时间,只有在网络中传输链会消耗时间。

不过因为一些故障,这个网络可能会出现“分区”的情况,即出现多个子网络,不同子网络的节点无法互相收发消息。

在计算机中常用逻辑时钟来定义“时刻”。

逻辑时钟初始时间为 00,以单位 11 递增。

任意节点传输一条链到其邻居所花费的时间相同,都为 tt。

现在已知整个网络的结构以及每个节点产生新块的时间,需要查询特定时刻某个节点的主链。

输入格式

第一行两个正整数分别为 n,mn,m,分别表示网络的 nn 个节点和 mm 条边。

接下来 mm 行,每行 22 个正整数 ui,vi(1≤i≤m)ui,vi(1≤i≤m),表示网络中节点 uiui 和节点 vivi 具有(双向)连接。

接下来一行两个正整数 t,kt,k,分别表示每次传输延时 tt 和操作(产生块或查询)的数量。

接下来 kk 行,每行 22 或 33 个正整数:

  • 如果是三个数 ai,bi,ciai,bi,ci,表示节点 aiai 在 bibi 时刻产生了一个编号为 cici 的块。保证 bi≤bi+1(1≤i<k)bi≤bi+1(1≤i<k)。
  • 如果是两个数 ai,biai,bi,表示查询节点 aiai 处理完 bibi 时刻及以前的所有操作后的主链。保证对于同一时刻,任何查询在输入文件中都出现在当前时刻所有的新块被产生之后。
输出格式

依次输出若干行,分别对应每一次查询。

每行第一个正整数 LL 表示主链的长度,接下来 LL 个数表示主链每个块的编号。从链头(一定为 00)到链尾依次输出。

数据范围

QQ截图20210224143635.png


保证题中所有输入均为整数,并且所有整数绝对值不大于 109109。
保证无重边,但可能存在自环。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <vector>
#include <queue>using namespace std;typedef vector<int> VI;
const int N = 510, M = 20010;int n, m, w, Q;
int h[N], e[M], ne[M], idx;
vector<VI> g;
int node[N];struct Op
{int t, id, pid, hid;bool operator< (const Op& r) const{return t > r.t;}
};
priority_queue<Op> heap;void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void eval()
{auto t = heap.top();heap.pop();auto &a = g[node[t.id]], &b = g[t.hid];if (b.size() > a.size() || b.size() == a.size() && b.back() < a.back()){node[t.id] = t.hid;for (int i = h[t.id]; ~i; i = ne[i])if (e[i] != t.pid && e[i] != t.id)heap.push({t.t + w, e[i], t.id, t.hid});}
}int main()
{scanf("%d%d", &n, &m);g.push_back({0});memset(h, -1, sizeof h);while (m -- ){int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a);}scanf("%d%d", &w, &Q);getchar();char str[100];while (Q -- ){fgets(str, 100, stdin);stringstream ssin(str);int a[3], cnt = 0;while (ssin >> a[cnt]) cnt ++ ;if (cnt == 3){while (heap.size() && heap.top().t <= a[1]) eval();g.push_back(g[node[a[0]]]);g.back().push_back(a[2]);node[a[0]] = g.size() - 1;for (int i = h[a[0]]; ~i; i = ne[i])if (e[i] != a[0])heap.push({a[1] + w, e[i], a[0], node[a[0]]});}else{while (heap.size() && heap.top().t <= a[1]) eval();printf("%d ", g[node[a[0]]].size());for (auto x: g[node[a[0]]])printf("%d ", x);puts("");}}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

5G毫米波测试助力突破高频段设备局限,实现高效外场测试

作者介绍 一、方案背景 随着业务对带宽需求的不断增加&#xff0c;通信频谱不断向更高频谱延伸&#xff0c;5G毫米波具有丰富的频率资源&#xff0c;是移动通信技术演进的必然方向。下图是ITU的WRC-19会议发布的目前5G所占用频段。 从图中可以看出&#xff0c;在5G毫米波测试中…

Java基础核心知识学习笔记

方法重载 请记住下面重载的条件 方法名称必须相同。参数列表必须不同&#xff08;个数不同、或类型不同、参数类型排列顺序不同等&#xff09;。方法的返回类型可以相同也可以不相同。仅仅返回类型不同不足以成为方法的重载。重载是发生在编译时的&#xff0c;因为编译器可以根…

【计算机网络】网络版本计算器

此前我们关于TCP协议一直写的都是直接recv或者read&#xff0c;有了字节流的概念后&#xff0c;我们知道这样直接读可能会出错&#xff0c;所以我们如何进行分割完整报文&#xff1f;这就需要报头来解决了&#xff01; 但当前我们先不谈这个话题&#xff0c;先从头开始。 将会…

第二十三节、血量更新逻辑的实现

一、创建代码 引入命名空间 using UnityEngine.UI; 调用UI必须有这个代码 二、ScriptObject类 1、是一个持久化存储文件的类型 接收所有的事件方法 先继承SO类&#xff0c;然后创建项目菜单 2、进行订阅 放入事件类&#xff0c;关联代码&#xff0c;即可进行广播 传递给这…

蓝桥杯2021第十二届蓝桥杯青少年组省赛试题真题

带我去看题解&#xff01;&#xff01;&#xff01; 带我去看题单&#xff01;&#xff01;&#xff01; 目录 第一题&#xff1a;[2021第十二届蓝桥杯青少年组省赛] 字符串 题目背景 题目描述 输入格式 输出格式 输入输出样例 第二题&#xff1a;[2021第十二届蓝桥杯…

AI + 3D 机器人视觉领域综合资源库

随着人工智能技术的不断发展,3D 机器人视觉领域已经成为了一个备受关注的研究方向。在这个领域中,研究者们致力于探索如何让机器人更好地理解三维空间,从而实现更加智能和灵活的操作。为了方便大家学习和研究,这里介绍一个全面的资源库——Awesome Robotics 3D,它汇集了最…

Ajax技术详解

Ajax简介 Ajax 即 "Asynchronous Javascript And XML"&#xff08;异步 JavaScript 和 XML&#xff09;&#xff0c;是指一种创建交互式、快速动态应用的网页开发技术&#xff0c;无需重新加载整个网页的情况下&#xff0c;能够更新页面局部数据的技术。 为什么要使…

Markdown中使用 LaTeX 绘图 -- TikZ

Markdown中使用 LaTeX 绘图 -- TikZ 1 介绍1.1 概述1.2 与其他图包对比 2 示例 & 学习[The TikZ and PGF Packages](https://tikz.dev/)[Graphics with TikZ in LaTeX](https://tikz.net/)[TikZ PGF Manual](https://www.bu.edu/math/files/2013/08/tikzpgfmanual.pdf)[在 …

【从Qwen2,Apple Intelligence Foundation,Gemma 2,Llama 3.1看大模型的性能提升之路】

从早期的 GPT 模型到如今复杂的开放式 LLM&#xff0c;大型语言模型 (LLM) 的发展已经取得了长足的进步。最初&#xff0c;LLM 训练过程仅侧重于预训练&#xff0c;但后来扩展到包括预训练和后训练。后训练通常包括监督指令微调和校准&#xff0c;这是由 ChatGPT 推广的。 自 …

机器学习:逻辑回归处理手写数字的识别

1、获取数据, 图像分割该数据有50行100列&#xff0c;每个数字占据20*20个像素点&#xff0c;可以进行切分,划分出训练集和测试集。 import numpy as np import pandas as pd import cv2 imgcv2.imread("digits.png")#读取文件 graycv2.cvtColor(img,cv2.COLOR_BGR2G…

LVS负载均衡群集-DR模式

一、负载均衡群集 1.数据包流向分析 客户端发送请求到 Director Server&#xff08;负载均衡器&#xff09;&#xff0c;请求的数据报文&#xff08;源 IP 是 CIP,目标 IP 是 VIP&#xff09;到达内核空间。Director Server 和 Real Server 在同一个网络中&#xff0c;数据通过…

深度学习基础—Softmax回归

通常对于二分类问题&#xff0c;大家熟知的模型就是logistic回归。那么对于多分类问题呢&#xff1f;如果要多分类&#xff0c;我们可以在网络的最后一层建立多个神经元&#xff0c;每个神经元对应一个分类的输出&#xff0c;输出的是某一个分类的概率&#xff0c;这些概率之和…

写给大数据开发:如何优化临时数据查询流程

你是否曾因为频繁的临时数据查询请求而感到烦恼&#xff1f;这些看似简单的任务是否正在蚕食你的宝贵时间&#xff0c;影响你的主要工作&#xff1f;如果是&#xff0c;那么这篇文章正是为你而写。 目录 引言&#xff1a;数据开发者的困境问题剖析&#xff1a;临时数据查询的…

小程序开发与发布指南:API、协同工作、版本管理与运营数据

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

乡村养老服务管理系统

TOC springboot549乡村养老服务管理系统pf 绪论 1.1 研究背景 现在大家正处于互联网加的时代&#xff0c;这个时代它就是一个信息内容无比丰富&#xff0c;信息处理与管理变得越加高效的网络化的时代&#xff0c;这个时代让大家的生活不仅变得更加地便利化&#xff0c;也让…

【论文阅读33】Deep learning optoacoustic tomography with sparse data

Deep learning optoacoustic tomography with sparse data 论文题目:基于稀疏数据的深度学习光声断层扫描 论文链接:Deep learning optoacoustic tomography with sparse data | Nature Machine Intelligence 代码链接:GitHub - ndavoudi/sparse_artefact_unet 数据链接…

「C++系列」vector 容器

文章目录 一、vector 容器1. 基本特性2. 基本操作3. 注意事项 二、应用场景1. 应用场景2. 案例案例一&#xff1a;存储动态大小的数据集合案例二&#xff1a;实现栈 三、相关链接 一、vector 容器 C 中的 vector 是一个非常常用的容器&#xff08;container&#xff09;&#…

comfyUI工作流-Flux大模型应用/黑神话悟空角色生成(附lora)

​ 是什么让悟空开始搬砖&#xff0c;这莫不是新的副本 其实我们用AI就能生成这种黑神话悟空的衍生图片 让悟空做ceo&#xff0c;做老师&#xff0c;上工地搬砖 七十二变&#xff0c;体验人生百态 操作很简单&#xff0c;只需要一个comfyUI工作流&#xff0c;你就能任意生成…

嵌入式day31

mplayer项目问题分析&#xff1a; 知识短时间内可以获取到 能力的提升一定需要练习 IPC 进程间通信方式 共享内存 //最高效的进程间通信方式 共享内存&#xff1a; 1.是一块 内核预留的空间 2.最高效的通信方式 //避免了用户空间到内核空间的数据拷贝 操作&#xff1a; …

<数据集>航拍牧场牛羊识别数据集<目标检测>

数据集格式&#xff1a;VOCYOLO格式 图片数量&#xff1a;1021张 标注数量(xml文件个数)&#xff1a;1021 标注数量(txt文件个数)&#xff1a;1021 标注类别数&#xff1a;3 标注类别名称&#xff1a;[cattle, cow, sheep] 序号类别名称图片数框数1cattle29741282cow6740…