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

NOIP真题答案 过河 数的划分

过河

题目描述

在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,⋯ ,L0,1,\cdots,L0,1,,L(其中 LLL 是桥的长度)。坐标为 000 的点表示桥的起点,坐标为 LLL 的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是 SSSTTT 之间的任意正整数(包括 S,TS,TS,T)。当青蛙跳到或跳过坐标为 LLL 的点时,就算青蛙已经跳出了独木桥。
题目给出独木桥的长度 LLL,青蛙跳跃的距离范围 S,TS,TS,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

输入输出格式

第一行有 111 个正整数 L(1≤L≤109)L(1\le L\le 10^9)L(1L109),表示独木桥的长度。
第二行有 333 个正整数 S,T,MS,T,MS,T,M,分别表示青蛙一次跳跃的最小距离,最大距离及桥上石子的个数,其中 1≤S≤T≤101\le S\le T\le101ST10,1≤M≤1001\le M\le1001M100
第三行有 MMM 个不同的正整数分别表示这 MMM 个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。

输出格式

一个整数,表示青蛙过河最少需要踩到的石子数。

输入输出样例

10
2 3 5
2 3 5 6 7
Copy
2
Copy

说明

对于30%的数据,L≤104L \le 10^4L104
对于全部的数据,L≤109L \le 10^9L109
**【题目来源】**
NOIP 2005 提高组第二题

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200 + 10;
int n, na, nb, a[MAXN], b[MAXN], cnta, cntb;
int vs[5][5] = {{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}}; //得分表的处理 
int main()
{cin >> n >> na >> nb;for(int i = 0; i < na; i++) cin >> a[i];for(int i = 0; i < nb; i++) cin >> b[i];for(int i = 0; i < n; i++){cnta += vs[a[i % na]][b[i % nb]]; //周期循环 cntb += vs[b[i % nb]][a[i % na]];}cout << cnta << " " << cntb << endl;return 0;
}

数的划分

Description

将整数 nnn 分成 kkk 份,且每份不能为空,任意两个方案不相同(不考虑顺序)。

例如:n=7n=7n=7k=3k=3k=3,下面三种分法被认为是相同的。

1,1,51,1,51,1,5;
1,5,11,5,11,5,1;
5,1,15,1,15,1,1.

问有多少种不同的分法。

Input

n,kn,kn,k6≤n≤2006 \le n \le 2006n2002≤k≤62 \le k \le 62k6

Output

111 个整数,即不同的分法。

Samples

输入数据 1

7 3
Copy

输出数据 1

4
Copy
    </div></div></div>
</div>
#include<bits/stdc++.h>
using namespace std;
long long q,w,e,r,t,y,u,o,p,s,d,f,g,h,j,l,z,x,c,v,n,m,i;
long long k;
long long a[10000][10000],b[10000];
int main()
{cin>>n>>k;for(i=1;i<=n;i++){a[1][i]=1;}for(l=1;l<=n;l++){for(i=2;i<=n;i++){     for(j=i;j<=n;j++){     a[i][j]=a[i-1][j-1]+a[i][j-i];}}}cout<<a[k][n];return 0;
}

相关文章:

NOIP真题答案 过河 数的划分

过河 题目描述 在河上有一座独木桥&#xff0c;一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子&#xff0c;青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数&#xff0c;我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点&#xf…...

图为科技-边缘计算在智慧医疗领域的作用

边缘计算在智慧医疗领域的作用 随着科技的进步&#xff0c;智慧医疗已成为医疗行业的重要发展趋势。边缘计算作为新兴技术&#xff0c;在智慧医疗领域发挥着越来越重要的作用。本文将介绍边缘计算在智慧医疗领域的应用及其优势&#xff0c;并探讨未来发展方向。 一、边缘计算…...

Linux配置nginx反向代理

在云服务器上部署高并发的服务&#xff0c;使用Nginx作为反向代理是一种常见的做法&#xff0c;可以实现流量分发、负载均衡&#xff0c;同时提升系统的可靠性和性能。 步骤概览&#xff1a; 安装Nginx&#xff1a; 确保服务器已安装Nginx。若未安装&#xff0c;可使用适用于你…...

随便记录记录

统一整理一下各种 pandas读csv import pandas as pd ## 默认会将第一行作为列 df pd.read_csv(path_to_your_file.csv) ## 传递 headerNone 参数来告诉 Pandas 不要将第一行 df pd.read_csv(path_to_your_file.csv, headerNone) ## 使用多种选项来处理数据&#xff0c;如指…...

UbuntuDDE 23.04发布,体验DeepinV23的一个新选择

UbuntuDDE 23.04发布&#xff0c;体验DeepinV23的一个新选择 昨晚网上搜索了一圈&#xff0c;无意看到邮箱一条新闻&#xff0c;UbuntuDDE 23.04发布了 因为前几天刚用虚拟机安装过&#xff0c;所以麻溜的从网站下载了ISO文件&#xff0c;安装上看看。本来没多想&#xff0c;…...

RabbitMQ 消费者

RabbitMQ的消费模式分两种&#xff1a;推模式和拉模式&#xff0c;推模式采用Basic.Consume进行消费&#xff0c;拉模式则是调用Basic.Get进行消费。   消费者通过订阅队列从RabbitMQ中获取消息进行消费&#xff0c;为避免消息丢失可采用消费确认机制 消费者 拉模式拉模式的实…...

软件测试面试真题 | 什么是PO设计模式?

面试官问&#xff1a;UI自动化测试中有使用过设计模式吗&#xff1f;了解什么是PO设计模式吗&#xff1f; 考察点 《page object 设计模式》&#xff1a;PageObject设计模式的设计思想、设计原则 《web自动化测试实战》&#xff1a;结合PageObject在真实项目中的实践与应用情…...

GB2312转UTF-8部分中文乱码

现象 最近写了个txt导入&#xff0c;客户反馈有时候导入的数据&#xff0c;会出现个别中文乱码的现象&#xff0c;但是我之前已经做过编码转换处理了&#xff0c;统一转成了UTF-8。 比如“鞠婧祎”,导入进来是这样&#xff1a; 排查思路 首先看了一下这个文本的编码格式&am…...

项目——电子词典(客户端、服务器交互,字典导入,单词查询)

一、项目要求 登录注册功能&#xff0c;不能重复登录&#xff0c;重复注册单词查询功能历史记录功能&#xff0c;存储单词&#xff0c;意思&#xff0c;以及查询时间基于TCP&#xff0c;支持多客户端连接采用数据库保存用户信息与历史记录将dict.txt的数据导入到数据库中保存。…...

jenkins 是什么?

一、jenkins 是什么&#xff1f; Jenkins是一个开源的、提供友好操作界面的持续集成(CI)工具&#xff0c;起源于Hudson&#xff0c;主要用于持续、自动的构建/测试软件项目、监控外部任务的运行。Jenkins用Java语言编写&#xff0c;可在Tomcat等流行的servlet容器中运行&#…...

无涯教程-PHP - sql_regcase()函数

sql_regcase() - 语法 string sql_regcase (string string) 可以将sql_regcase()函数视为实用程序函数&#xff0c;它将输入参数字符串中的每个字符转换为包含两个字符的带括号的表达式。 sql_regcase() - 返回值 返回带括号的表达式字符串以及转换后的字符。 sql_regcase…...

cesium 实现鼠标中键拖动地图

cesium默认左键拖动地图&#xff0c;中键旋转&#xff0c;再绘图时带来诸多不便。所以改成鼠标中键按下拖动地图&#xff0c;鼠标左键选点。代码如下&#xff1a;【感谢chatGPT】 //改为中建拖动// 假设 viewer 是你的 Cesium Viewer 实例const cameraController viewer.scene…...

低压风机单片机方案

低压风机通常由电机、转子、机壳、进气管、出气管、齿轮和减速机等组成。电机带动转子旋转&#xff0c;旋转的转子带动齿轮和减速机转动&#xff0c;进而形成空气被吸入转子内部&#xff0c;通过旋转而产生的离心力把气体压缩&#xff0c;并将气体排出。 低压风机方案的主控型…...

R语言06-R语言的基本运算

概念 R语言支持多种基本运算&#xff0c;包括算术运算、逻辑运算、比较运算和向量化运算等。 代码示意 逻辑运算 a <- TRUE b <- FALSElogical_and <- a & b # 逻辑与 logical_or <- a | b # 逻辑或 logical_not <- !a # 逻辑非比较运算 x <…...

Docker容器:docker-compose管理创建LNMP服务并运行Wordpress网站平台

文章目录 一&#xff0e;项目环境1. 环境描述2.项目需求 二&#xff0e;部署过程1.安装Docker2.安装Docker加速器3.Docker-Compose安装部署4.准备依赖文件、配置nginx5.配置mysql6.配置php7.编写docker-compose.yml8.验证 三.容器快照&#xff0c;然后将Docker镜像打包成tar包备…...

实业兴国 守护种源 —— 白露木實®农业的活力之风

高科技领域&#xff0c;芯片是生命线&#xff1b;而在农业领域&#xff0c;种源与芯片在高科技领域的重要性是相同的。保护、发展、培育我国的种质资源&#xff0c;是中国农业发展至为关键的一环。但是&#xff0c;因为思想、观念、认识、技术等方面的原因&#xff0c;让我们错…...

Web3.0

一、Web3.0是什么 Web3.0&#xff08;有时称为“分布式Web”或“去中心化Web”&#xff09;是对互联网的下一代演进的概念。它代表了一种更加分散、去中心化和用户掌控的互联网模式&#xff0c;与传统的Web2.0模型有很大不同。 以下是Web3.0的一些关键特征和概念&#xff1a;…...

精密图纸被窃,知名手表品牌Seiko遭BlackCat勒索软件攻击

据BleepingComputer消息&#xff0c;日本著名手表制造商Seiko在7月末遭到了网络攻击&#xff0c;8月21日&#xff0c;BlackCat&#xff08;又名ALPHV&#xff09;勒索软件组织在其网站上宣布对这起攻击事件负责。 8 月 10 日&#xff0c;Seiko发布了一份数据泄露通知&#xff0…...

K8S如何部署Redis(单机、集群)

在今天的讨论中&#xff0c;我们将深入研究如何将Redis数据库迁移到云端&#xff0c;以便更好地利用云计算的优势提高数据管理的灵活性。 Redis(Remote Dictionary Server)是一个开源的、基于内存的数据结构存储系统&#xff0c;它可以用作数据库、缓存和消息代理。Redis支持多…...

Flask狼书笔记 | 03_模板

文章目录 3 模板3.1 模板基本使用3.2 模板结构组织3.3 模板进阶 3 模板 模板&#xff08;template&#xff09;&#xff1a;包含固定内容和动态部分的可重用文件。Jinja2模板引擎可用于任何纯文本文件。 3.1 模板基本使用 HTML实体&#xff1a;https://dev.w3.org/html5/htm…...

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, …...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...