当前位置: 首页 > news >正文

2023-2-11 刷题情况

最短路计数

题目描述

给出一个 NNN 个顶点 MMM 条边的无向无权图,顶点编号为 1∼N1\sim N1N。问从顶点 111 开始,到其他每个点的最短路有几条。

输入格式

第一行包含 222 个正整数 N,MN,MN,M,为图的顶点数与边数。

接下来 MMM 行,每行 222 个正整数 x,yx,yx,y,表示有一条由顶点 xxx 连向顶点 yyy 的边,请注意可能有自环与重边。

输出格式

NNN 行,每行一个非负整数,第 iii 行输出从顶点 111 到顶点 iii 有多少条不同的最短路,由于答案有可能会很大,你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 iii 则输出 000

样例

样例输入

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

样例输出

1
1
1
2
4

提示

111555 的最短路有 444 条,分别为 2221→2→4→51\to 2\to 4\to 512452221→3→4→51\to 3\to 4\to 51345(由于 4→54\to 545 的边有 222 条)。

  • 对于 20%20\%20% 的数据,1≤N≤1001\le N \le 1001N100
  • 对于 60%60\%60% 的数据,1≤N≤1031\le N \le 10^31N103
  • 对于 100%100\%100% 的数据,1≤N≤1061\le N\le10^61N1061≤M≤2×1061\le M\le 2\times 10^61M2×106

思路

无向无权图。可使用bfs遍历,因为路径的权重都为1。
当前图中存在自环,但自环并不影响bfs遍历的最短路。
然后就是重边会对结果造成影响,需要我们考虑。

代码实现

import java.util.*;public class Main{static int MOD = (int)1e5 + 3;public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt(), len = sc.nextInt();List<Integer> list[] = new ArrayList[n+1];// 去环,已经进入过队列的结点,将不再进入队列boolean[] vis = new boolean[n+1];int[] depth = new int[n+1];// 结果。int[] ans = new int[n+1];for(int i = 1; i <= n; i++) list[i] = new ArrayList<>();int x, y;for (int i = 0; i < len; i++) {x = sc.nextInt();y = sc.nextInt();list[x].add(y);list[y].add(x);}Queue<Integer> queue = new ArrayDeque<>();depth[1] = 0;vis[1] = true;ans[1] = 1;queue.offer(1);while(!queue.isEmpty()){int cur = queue.poll();for(int next : list[cur]){if(!vis[next]){vis[next] = true;depth[next] = depth[cur] + 1;queue.offer(next);}// next结点,只有深度为 depth[next]的时候才会更新。// 换句话说就是只有第一次与第一次相同时间到达next时,才会更新值。if(depth[next] == depth[cur] + 1) ans[next] = (ans[next] + ans[cur]) % MOD;}}for(int i = 1; i <= n; i++) System.out.println(ans[i]);sc.close();}
}

中位数

题目描述

给出 1,2,...,n1,2,...,n1,2,...,n 的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是 bbb。中位数是指把所有元素从小到大排列后,位于中间的数。

输入格式

第一行为两个正整数 nnnbbb,第二行为 1,2,...,n1,2,...,n1,2,...,n 的排列。

输出格式

输出一个整数,即中位数为 bbb 的连续子序列个数。

样例

样例输入

7 4
5 7 2 4 3 1 6

样例输出

4

提示

数据规模与约定

  • 对于 30%30\%30% 的数据中,满足 n≤100n \le 100n100

  • 对于 60%60\%60% 的数据中,满足 n≤1000n \le 1000n1000

  • 对于 100%100\%100% 的数据中,满足 n≤100000,1≤b≤nn \le 100000,1 \le b \le nn100000,1bn

思路

因为满足需要的区间一定包含b, 所以我们可以先把b在数组中的位置找到。再到基础上拓展区间。
需要b成为区间的中位数,即是需要区间内大于b的数的数量等于区间内小于b的数的数量,我们可以把大于b的数记作1, 小于b的数记为-1。然后只需要左边区间加+右边区间 = 0即为找到一个区间。(还需要特别注意区间长度为奇数也是条件之一)

代码实现

import java.util.*;public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt(), b = sc.nextInt();int[] arr = new int[n+1];for(int i = 1; i <= n; i++) arr[i] = sc.nextInt();int index = query(arr, b);HashMap<Integer, Integer> one = new HashMap<>();HashMap<Integer, Integer> two = new HashMap<>();two.put(0, 1);int val = 0;for(int i = index - 1; i > 0; i--){val += (arr[i] > b ? 1 : -1);if((index - i) % 2 == 1) one.put(val, one.getOrDefault(val, 0) + 1);else two.put(val, two.getOrDefault(val, 0) + 1);}val = 0;long ans = 0;for(int i = index; i <= n; i++){val += (arr[i] == b ? 0 : (arr[i] > b ? 1 : -1));if((i-index) % 2 == 1) ans += one.getOrDefault(-val, 0);else ans += two.getOrDefault(-val, 0);}System.out.println(ans);sc.close();}static int query(int[] arr, int b){for(int i = 1; i < arr.length; i++){if(arr[i] == b) return i; }return -1;}
}

相关文章:

2023-2-11 刷题情况

最短路计数 题目描述 给出一个 NNN 个顶点 MMM 条边的无向无权图&#xff0c;顶点编号为 1∼N1\sim N1∼N。问从顶点 111 开始&#xff0c;到其他每个点的最短路有几条。 输入格式 第一行包含 222 个正整数 N,MN,MN,M&#xff0c;为图的顶点数与边数。 接下来 MMM 行&…...

2019_41 考研408

2019年(单链表)41.(13分)设线性表采用带头结点的单链表保存&#xff0c;链表中的结点定义如下:typedef struct node {int data;struct node* next;}NODE;请设计一个空间复杂度为O(1)且时间上尽可能高效的算法&#xff0c;重新排列L中的各结点&#xff0c;得到线性表L(q,a,,a,an…...

Linux账号与用户组

目录 用户标识符&#xff1a;UID与GID 用户账号 /etc/passwd文件结构 1、账号名称 2、密码 3、UID 4、GID 5、用户信息说明栏 6、家目录 7、shell /etc/shadow文件结构 1、账号名称 2、密码 3、最近修改密码的日期 4、密码不可被修改的天数&#xff08;与第三字…...

有趣的Hack-A-Sat黑掉卫星挑战赛——定位卫星Jackson

国家太空安全是国家安全在空间领域的表现。随着太空技术在政治、经济、军事、文化等各个领域的应用不断增加&#xff0c;太空已经成为国家赖以生存与发展的命脉之一&#xff0c;凝聚着巨大的国家利益&#xff0c;太空安全的重要性日益凸显[1]。而在信息化时代&#xff0c;太空安…...

JAVA集合专题3 —— vector + LinkedList + Set

目录vector的特点LinkedList底层结构模拟双向链表比较ArrayList和LinkedListSet接口基本介绍Set接口的遍历方式Set接口实现类对象的特点Set接口实现类HashSet模拟HashSet/HashMap的底层结构vector的特点 Vector底层是一个对象数组Vector是线程同步的&#xff0c;即线程安全的&…...

Scout:一款功能强大的轻量级URL模糊测试与爬取工具

关于Scout Scout是一款功能强大的轻量级URL模糊测试与爬取工具&#xff0c;可以帮助广大研究人员进行URL模糊测试&#xff0c;并爬取目标Web服务器中难以扫描发现的VHSOT、文件和目录等资源。 项目中包含了一个完整的字典文件&#xff0c;并尽可能地提供了更多的便携性&#…...

leaflet 解决marker呈现灰色边框的问题

第052个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet示例中处理marker外面有灰色边框的问题,请看未处理会后的图片。 处理后的结果非常满意,不再显示灰色边框。处理方法参考源代码。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果; 注意…...

MySQL JSON类型字段的查找与更新

MySQL 提供了丰富的函数用于 JSON 类型字段的查找与更新&#xff0c;详见官方文档。 创建一个表 t1&#xff0c;basic_info 字段为JSON类型: CREATE TABLE t1 (id int(11) NOT NULL AUTO_INCREMENT,basic_info json DEFAULT NULL,PRIMARY KEY (id) ) ENGINEInnoDB DEFAULT CH…...

element Ui树状图控件 spring boot Vue 实现角色授权功能

目录 前言&#xff1a; 二. element ui 2.1官网提供的核心代码 三.表结构 ​编辑 四.后端 4.1功能分析 4.2实体类 4.3 查询全部权限显示的结果 4.2修改角色权限的后台方法 五.vue 5.0代码总览 5.1树形图 5.2所需要的绑定数据 5.3所需方法 前言&#xff1a; 先上图…...

已解决sc delete MongoDB卸载MongoDB拒绝访问。

已解决sc delete MongoDB卸载MongoDB拒绝访问。 文章目录报错问题报错翻译报错原因解决方法联系博主免费帮忙解决报错报错问题 粉丝群里面的一个小伙伴遇到问题跑来私信我&#xff0c;想卸载MongoDB数据库&#xff0c;但是发生了报错&#xff08;当时他心里瞬间凉了一大截&…...

python的opencv操作记录11——阈值分割

文章目录传统图像处理分割阈值分割一个应用场景opencv库中的阈值分割固定阈值THRESH_OTSU 大津法阈值自适应阈值传统图像处理分割 现在提到图像分割&#xff0c;很多人会直接想到当前火爆的深度学习的各种分割网络&#xff0c;比如实例分割&#xff0c;语义分割等。其实在传统…...

Python-项目实战--飞机大战-英雄登场(7)

目标设计英雄和子弹类使用pygame.key.get_pressed()移动英雄发射子弹1.设计英雄和子弹类1.1英雄需求游戏启动后&#xff0c;英雄出现在屏幕的水平中间位置&#xff0c;距离屏幕底部120像素英雄每隔0.5秒发射一次子弹&#xff0c;每次连发三枚子弹英雄默认不会移动&#xff0c;需…...

寒假安全作业nginx-host绕过实例复现

1.测试环境搭建 LNMP架构的话&#xff0c;肯定就是linux、nginx、mysql、php四大组件。在后面的复现中我们还会用到https的一部分知识&#xff0c;故这里的nginx就需要使用虚拟主机并且配置https证书&#xff0c;且具有php解析功能。 1.1 基础nginx配置 #1.创建web目录 mkdir …...

RocketMQ-消息消费模式 顺序消费

RocketMQ-消息消费模式 顺序消费RocketMQ-消息消费模式集群模式集群模式的演示(本身就默认)Rocketmq存储队列广播模式顺序消费如何改实现顺序消费RocketMQ-消息消费模式 集群模式 在消费模式为集群的情况下,如果机器是集群的,消息只会给集群中的其中一台机器消费到 集群模…...

一、Java并发编程之线程、synchronized

黑马课程 文章目录1. Java线程1.1 创建和运行线程方法一&#xff1a;Thread方法二&#xff1a;Runnable&#xff08;推荐&#xff09;lambda精简Thread和runnable原理方法三&#xff1a;FutureTask配合Thread1.2 查看进程和线程的方法1.3 线程运行原理栈与栈帧线程上下文切换1.…...

12.hadoop系列之MapReduce分区实践

本文我们学习MapReduce默认分区以及自定义分区实践 当我们要求将统计结果按照条件输出到不同文件(分区)&#xff0c;比如按照统计结果将手机归属地不同省份输出到不同文件中(分区) 1.默认Partitioner分区 public class HashPartitioner<K, V> extends Partitioner<…...

有了独自开,一个人就是一个团队

文章目录 简单介绍优点 优秀案例平台福利总结 简单介绍 独自开是一个基于商品与服务交易全流程的PaaS开发平台。对于开发者&#xff0c;独自开可以协助开发者一个人独自开发一套系统。 优点 独自开有独创的分层标准化平台架构&#xff0c;可以满足系统的任何个性化需求。 …...

web期末复习 2023.02.11

文章目录Web 的概念Web 组成用户通过浏览器请求资源的过程:HTML 超文本标记语言CSS插入样式表的方法有三种:对象&#xff0c;类&#xff0c;实例一个完整的 JavaScript 实现是由以下 3 个不同部分组成的&#xff1a;JavaScript 用法什么是 Java Server Pages?JSP 注释JSP 的 J…...

第44章 用户密码实体及其约束规则的定义实现

1 说明&#xff1a; 由当前程序需要兼容实现多种用户密码的加密操作&#xff0c;所以必须把“CustomerPassword”定义为实体类&#xff0c;该类用于用于把加密方式、密钥及其加密后的密码持久化到“CustomerPassword”表中&#xff0c;以便用为用户登录操作提供验证支撑。 如果…...

聊聊并发与锁

持续坚持原创输出&#xff0c;点击蓝字关注我吧1.并发与并行并发可以充分地利用 CPU 资源&#xff0c;一般都会使用多线程实现。多线程的作用是提高任务的平均执行速度&#xff0c;但是会导致程序可理解性变差&#xff0c;编程难度加大。关于对并发与并行的概念&#xff0c;大家…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...

高分辨率图像合成归一化流扩展

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 1 摘要 我们提出了STARFlow&#xff0c;一种基于归一化流的可扩展生成模型&#xff0c;它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流&#xff08;TARFlow&am…...

react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架

1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...