当前位置: 首页 > 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…...

hot100——二分查找

4.寻找两个正序数组的中位数解题思路首先&#xff0c;题目中已经说明&#xff0c;是正序&#xff0c;那么nums1以及nums2中都是从小到大进行排列的&#xff1b;又因为题目中要求时间复杂度为O(log(mn))&#xff0c;一般看到这种时间复杂度是O(log……)形式的&#xff0c;基本上…...

ViGEmBus如何解决Windows游戏控制器兼容性难题?

ViGEmBus如何解决Windows游戏控制器兼容性难题&#xff1f; 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus ViGEmBus是一款专业的Windows内核模式驱动程序&a…...

6种压缩黑科技如何彻底解决文件处理的效率难题

6种压缩黑科技如何彻底解决文件处理的效率难题 【免费下载链接】7-Zip-zstd 7-Zip with support for Brotli, Fast-LZMA2, Lizard, LZ4, LZ5 and Zstandard 项目地址: https://gitcode.com/gh_mirrors/7z/7-Zip-zstd 为何压缩工具总是陷入"速度与压缩率"的两难…...

手把手教你用PHPStudy部署彩虹云商城二开版(2025修复完整版,含自动对接与漏洞修复)

零基础实战&#xff1a;PHPStudy环境下的彩虹云商城完整部署指南&#xff08;2025安全强化版&#xff09; 在个人站长和电商创业者的圈子里&#xff0c;彩虹云商城系统一直以其轻量化和易用性备受青睐。最近接触到的这个2025修复版&#xff0c;不仅保留了原系统的核心优势&…...

零基础手写大模型

从零搭建大模型&#xff1a;零基础学习实现职业经济跃迁指南 引言 在人工智能重塑全球产业格局的今天&#xff0c;“大模型”已不再仅仅是科技巨头的专利&#xff0c;而是成为了数字经济时代新的“电力”与“石油”。对于广大职场人士、创业者及寻求转型的个体而言&#xff0…...

STS4x温度传感器I²C驱动库深度解析与跨平台移植

1. STS4x温湿度传感器驱动库技术解析1.1 项目定位与工程价值Sensirion STS4x系列是瑞士Sensirion公司推出的高精度数字温度传感器&#xff0c;采用CMOSens技术&#xff0c;具备0.1C典型精度、0.01C分辨率、低功耗&#xff08;典型待机电流仅0.5μA&#xff09;及快速响应&#…...

基于2026校招数据分析:拥有这几张AI证书的学生,起薪普遍高30%

2026年校招季已近尾声&#xff0c;随着DeepSeek等大模型技术的持续突破与“人工智能”向千行百业的深度渗透&#xff0c;AI人才市场的竞争呈现白热化态势。前程无忧51job发布的《2026届校招市场AI人才需求报告》显示&#xff0c;AI相关岗位校招薪酬中位数已突破2万元/月&#x…...

终极指南:Autoenv如何彻底解决团队开发环境配置难题

终极指南&#xff1a;Autoenv如何彻底解决团队开发环境配置难题 【免费下载链接】autoenv 项目地址: https://gitcode.com/gh_mirrors/aut/autoenv Autoenv是一款强大的目录环境管理工具&#xff0c;能够在您进入包含.env文件的目录时自动执行其中的环境配置&#xff0…...

OpenClaw长期运行:Qwen3.5-9B自动化系统的维护与更新

OpenClaw长期运行&#xff1a;Qwen3.5-9B自动化系统的维护与更新 1. 为什么需要长期维护&#xff1f; 去年冬天&#xff0c;我部署了一个基于OpenClaw和Qwen3.5-9B的自动化系统来处理日常的文档整理工作。最初几周运行得很顺利&#xff0c;直到某个凌晨&#xff0c;系统突然停…...

MATLAB中扩展卡尔曼滤波与无迹卡尔曼滤波源代码:一键运行,误差对比及显示最大误差数字图像程...

MATLAB编写的EKF和UKF滤波程序源代码 扩展卡尔曼滤波、无迹卡尔曼滤波的MATLAB程序&#xff0c;有误差对比图像和最大误差数字的显示。 只有一个m文件&#xff0c;打开就能运行。 带中文注释。直接双击EKFUKFComparison.m就能看到两个滤波器在非线性系统里的较量。这个文件里塞…...