P1 练习卷(C++4道题)

1.纷繁世界

内存限制:256MB 时间限制:1s

问题描述

  这是一个纷繁复杂的世界。 某一天清晨你起床很迟,没有吃上早饭。于是你骑着自行车去超市,但是你又发现商店的工作人员已经重新贴上了价格标签,零食价格都涨了50%。你一怒之下就这样饿了一个上午…… 当然,事情也许完全不会这样发展。 某一天清晨你起床比较迟,但还是没有吃上早饭。于是你骑着自行车去超市,恰好商店的工作人员还没有把涨价后的价格标签贴在零食上。于是你顺利的买了一些早餐然后逍遥而去…… 或许你会起得更早,也或许商店的工作人员会迟到。 有时候,人们只是按照预想的顺序去完成一些事情,不过可能有一些事件,它们发生时间的前后顺序会影响世界的发展。 比如,如果商店只有一个西瓜,你想买,我也想买,那么我们买西瓜的先后顺序就会直接影响到谁最后能够买到西瓜。 这样一个复杂的世界,分析它的运行规律是一件非常重要的工作,也是你所要研究的。

问题描述

  简单起见,假定总共有N个人以及M种不同类型事件。 定义事件之间的二元关系“相关”:
  . 相关关系是一个二元关系,就是说我们只能定义两种类型的事件间是否相关;
  . 同一种类型的事件之间一定是相关的;
  . 若事件x与事件y是相关的,那么事件y与事件x也一定是相关的;
  令表示第i个人计划完成的事件序列(称为计划序列),Ci表示Qi的长度。Qi中每个事件Qi,j都是M种事件中的某一种,且同一种类型的事件可以发生多次。 随着时间的推移每个计划序列中的事件都会发生一次且恰好一次;为了简单起见,不会有任何两个事件发生在同一时刻。
  为了描述事件的发生顺序,定义为世界的一条发展轨迹,P是满足如下条件的有序序列:
  1. 对于每个人,计划序列中的每个事件Qi,j都在P出现一次且恰好一次;
  2. 对于属于同一个计划序列的两个事件Qi,j1和Qi,j2(1 ≤ j1 < j2 ≤ Ci),Qi,j1一定发生在Qi,j2之前(也就是在P中位于更靠前的位置);
  两条轨迹P1和P2被定义为本质不同的,当且仅当存在两个相关的事件Qi,j和Qu,v,他们在P1和P2中发生的先后顺序不同,也就是说,如果在P1中Qi,j发生在Qu,v之前且在P2中Qi,j发生在Qu,v之后,那么P1和P2就是本质不同的;如果在P1中Qi,j发生在Qu,v之后且在P2中Qi,j发生在Qu,v之前,那么P1和P2也是本质不同的; 注意:本质相同具有传递性,即若P1与P2本质相同且P2与P3本质相同,那么P1与P3一定也本质相同。
  给定N, M、每个人计划序列以及事件之间的相关关系。你需要计算一共有多少种本质不同的世界运行轨迹。

输入格式

  输入文件world.in第一行包括一个整数,表示人数N。 输入文件第二行包括一个整数,表示事件种类数M,所有类型的事件按照0至M – 1编号。 接下来依次给出每个人的计划序列的描述,对于第i个人: 首先一行一个整数表示序列长度Ci。 第二行包含Ci个整数,依次给出Qi中的每个事件Qi,j。 最后M行输入一个M行M列的矩阵dep用来描述相关关系,每行包含M个整数,都是0或者1。dep(i,j)表示矩阵自上往下的第i行,自左往右的第j列所包含的整数。若dep(i, j)的值为1,那么第i类事件和第j类事件就是相关的,否则这两类事件不相关。

输出格式

  输出文件world.out只有一行,一个整数表示本质不同的世界轨迹数T。

样例输入   

2
3
2
0
1
2
2
1
1 1 0
1 1 1
0 1 1

样例输出   

4

样例说明

  样例中有2个人与3类事件,C1 = C2 = 2。Q1,0 = 0, Q1,1 = 1, Q2,0 = 2, Q2,1 = 1。
  一共有4种不同的发生轨迹:
  P1 = (Q1,0, Q1,1, Q2,0, Q2,1)
  P2 = (Q1,0, Q2,0, Q1,1, Q2,1)
  P3 = (Q1,0, Q2,0, Q2,1, Q1,1)
  P4 = (Q2,0, Q2,1, Q1,0, Q1,1)
  对于其他任何合法的发展轨迹,都一定和这四条轨迹中的某一条本质相同。例如P = (Q2,0, Q1,0, Q2,1, Q1,1)与P3是本质相同的,因为两条轨迹只交换了Q1,0 = 0和Q2,0 = 2的顺序,但是这两类事件是不相关的。

数据规模和约定

  总人数N ≤ 10;
  事件种类数 M ≤ 15;
  计划序列长度Ci ≤ 20;
  世界轨迹数T ≤ 106。

2.道路游戏

时间限制:1s 内存限制:128MB

小新正在玩一个简单的电脑游戏。

游戏中有一条环形马路,马路上有 n 个机器人工厂,两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 n个机器人工厂编号为 1∼n,因为马路是环形的,所以第 n个机器人工厂和第 1个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为 1∼n,并规定第 i 段马路连接第 i 个机器人工厂和第 i+1个机器人工厂(1≤i≤n−1),第 n 段马路连接第 n 个机器人工厂和第 1 个机器人工厂。

游戏过程中,每个单位时间内,每段马路上都会出现一些金币,金币的数量会随着时间发生变化,即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买,机器人一旦被购买,便会沿着环形马路按顺时针方向一直行走,在每个单位时间内行走一次,即从当前所在的机器人工厂到达相邻的下一个机器人工厂,并将经过的马路上的所有金币收集给小新,例如,小新在 ii(1≤i≤n)号机器人工厂购买了一个机器人,这个机器人会从 ii 号机器人工厂开始,顺时针在马路上行走,第一次行走会经过 i 号马路,到达 i+1 号机器人工厂(如果 i=n,机器人会到达第 1 个机器人工厂),并将 i 号马路上的所有金币收集给小新。游戏中,环形马路上不能同时存在 2 个或者 2 个以上的机器人,并且每个机器人最多能够在环形马路上行走 p 次。小新购买机器人的同时,需要给这个机器人设定行走次数,行走次数可以为 1∼p 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失,小新必须立刻在任意一个机器人工厂中购买一个新的机器人,并给新的机器人设定新的行走次数。

以下是游戏的一些补充说明:

  1. 游戏从小新第一次购买机器人开始计时。
  2. 购买机器人和设定机器人的行走次数是瞬间完成的,不需要花费时间。
  3. 购买机器人和机器人行走是两个独立的过程,机器人行走时不能购买机器人,购买完机器人并且设定机器人行走次数之后机器人才能行走。
  4. 在同一个机器人工厂购买机器人的花费是相同的,但是在不同机器人工厂购买机器人的花费不一定相同。
  5. 购买机器人花费的金币,在游戏结束时再从小新收集的金币中扣除,所以在游戏过程中小新不用担心因金币不足,无法购买机器人而导致游戏无法进行。也因为如此,游戏结束后,收集的金币数量可能为负。

现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费,请你告诉小新,经过 m 个单位时间后,扣除购买机器人的花费,小新最多能收集到多少金币。

输入格式

第一行 3 个正整数 n,m,p,意义如题目所述。

接下来的 nn 行,每行有 mm 个正整数,每两个整数之间用一个空格隔开,其中第 ii 行描述了 ii 号马路上每个单位时间内出现的金币数量(1≤金币数量 ≤100),即第 i 行的第 j(1≤j≤m)个数表示第 j 个单位时间内 i 号马路上出现的金币数量。

最后一行,有 n 个整数,每两个整数之间用一个空格隔开,其中第 i 个数表示在 i号机器人工厂购买机器人需要花费的金币数量(1≤金币数量 ≤100)。

输出格式

共一行,包含 11 个整数,表示在 mm 个单位时间内,扣除购买机器人花费的金币之后,小新最多能收集到多少金币。

输入输出样例

输入 #1

2 3 2 
1 2 3 
2 3 4 
1 2

输出 #1

5

说明/提示

对于 40% 的数据,2≤n≤40,1≤m≤40。

对于 90% 的数据,2≤n≤200,1≤m≤200。

对于 100% 的数据,2≤n≤1000,1≤m≤1000,1≤p≤m。

NOIP 2009 普及组 第四题

3.查词典

时间限制:1s 内存限制:128MB

题目描述:

小A有一本词典,一天他在写英语老师留的阅读理解题中,遇到了n不会的词。

小A很贪玩,想要在t分钟后写完阅读理解的作业,然后就可以去玩手机去了。

但是他查词典的速度很慢,如果把他不会的单词全都查一遍,那肯定会超过t分钟

所以他快速浏览了一遍单词,发现他不会的单词中,有一部分很重要,还有一部分即使不会也不影响文章整体阅读,所以他列了一个清单,给每个单词做了一个重要度和查该单词所需的时间

现在小A想知道,在t分钟之内(不一定非要花光t分钟,可以提前结束 ),自己能查到的所有单词的重要度总和最大是多少。

输入格式

第一行两个整数 n,t

接下来n行,每行两个整数:time[i],important[i]

输出格式

一个整数,表示小A能查到的单词的重要度总和的最大值

输入样例

5 10

1 1

2 2

3 3

4 4

5 10

输出样例

15

数据规模

0<n,t<=10^12

提示

本题数据很大,需要开long long

4. 朋友圈(强化版)

时间限制 0.5s 内存限制 100MB

题目描述

在很久很久以前,曾经有两个国家和睦相处,无忧无虑的生活着.

一年一度的评比大会开始了,作为和平的两国,一个朋友圈数量最多的永远都是最值得他人的尊敬,所以现在就是需要你求朋友圈的最大数目.两个国家看成是 AB 两国,现在是两个国家的描述:

  • A 国:每个人都有一个友善值,当两个 A 国人的友善值 a,ba,b,如果 (axorb) mod 2=1(axorb)mod2=1,那么这两个人都是朋友,否则不是;
  • B 国:每个人都有一个友善值,当两个 B 国人的友善值 a,ba,b,如果 (axorb) mod 2=0(axorb)mod2=0 或者 (aorb)(aorb) 化成二进制有奇数个 11,那么两个人是朋友,否则不是朋友.

A、B 两国之间的人也有可能是朋友,数据中将会给出 A、B 之间「朋友」的情况.

对于朋友的定义,关系是是双向的.

在 AB 两国,朋友圈的定义:一个朋友圈集合 SS,满足 S⊂A∪BS⊂A∪B,对于所有的 i,j∈Si,j∈S,ii 和 jj 是朋友.

输入格式

本题包含多组数据.

  • 第一行一个整数 TT,表示输入数据总数.
  • 对于每组数据:
    • 第 11 行 33 个整数 A,B,MA,B,M,分别表示 A 国人数,B 国人数,AB 两国之间是朋友的对数.
    • 第 22 行 AA 个整数 aiai​,表示 A 国第 ii 个人的友善值.
    • 第 33 行 BB 个整数 bibi​,表示 B 国第 ii 个人的友善值.
    • 第 44 到第 3+M3+M 行,每行两个整数 x,yx,y 表示 A 国的第 xx 个人和 B 国第 yy 个人是朋友.

输出格式

  • 输出 TT 行,每行输出一个整数,表示最大朋友圈的数目.

输入输出样例

输入 #1

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

输出 #1

5

说明/提示

样例解释

最大朋友圈包含 A 国第 1,2人和 B 国第 1,2,3人.

数据范围

对于 100% 的数据,1≤T≤6,1≤ai,bi<231

本题共有两类数据,保证所有测试点均满足其中至少一类的限制:

  • 第一类:1≤A≤20000,1≤B≤20000
  • 第二类:1≤A≤15,1≤B≤30000

评分:

0-20:

编程水平较弱,CSP-J复赛大约可得50-120分, 不建议报考CSP-S

20-100:

编程水平一般,CSP-J复赛大约可得三等奖-二等奖,建议尝试报考CSP-S

100-200:

编程水平较强,建议报考CSP-S,S组复赛大约可得80分

200-300:

编程水平强,建议报考NOI

300-350:

编程水平很强,和开挂一样,建议报考NOI

350-400

666,这个入是挂

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

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

相关文章

私有化部署视频平台EasyCVR宇视设备视频平台如何构建视频联网平台及升级视频转码业务?

在当今数字化、网络化的时代背景下&#xff0c;视频监控技术已广泛应用于各行各业&#xff0c;成为保障安全、提升效率的重要工具。然而&#xff0c;面对复杂多变的监控需求和跨区域、网络化的管理挑战&#xff0c;传统的视频监控解决方案往往显得力不从心。 EasyCVR视频融合云…

物体网格弹性变形---Unity中实现

在游戏引擎场景中的3D物体是由一定数量的点、面组成的&#xff0c;如下图&#xff1a; 要使这些物体变形就是改变3D物体每个顶点状态。 1.首先在Unity场景中增加一个球体&#xff0c;如下图 3D组件默认拥有MeshFilter、meshRenderer、Collider组件&#xff0c;分别用来获取Mes…

Java爬虫:获取商品详情的实践之旅

在当今这个信息爆炸的时代&#xff0c;数据的价值日益凸显。对于电商行业来说&#xff0c;商品详情的获取尤为重要&#xff0c;它不仅关系到产品的销售&#xff0c;还直接影响到用户体验。传统的人工获取方式耗时耗力&#xff0c;而自动化的爬虫技术则提供了一种高效解决方案。…

【LLM】一文学会SPPO

博客昵称&#xff1a;沈小农学编程 作者简介&#xff1a;一名在读硕士&#xff0c;定期更新相关算法面试题&#xff0c;欢迎关注小弟&#xff01; PS&#xff1a;哈喽&#xff01;各位CSDN的uu们&#xff0c;我是你的小弟沈小农&#xff0c;希望我的文章能帮助到你。欢迎大家在…

腾讯云 AI 代码助手:产品研发过程的思考和方法论

一、文章摘要 本文将详细阐述 腾讯云 AI 代码助手的历史发展形态与产品整体架构&#xff0c;并从技术、研发方法论的角度分别阐述了产品的研发过程。 全文阅读约 5&#xff5e;8 分钟。 二、产品布局 AI 代码助手产品经历了三个时代的发展 第一代诸如 Eclipse、Jetbrains、V…

RabbitMQ实现异步下单与退单

前言&#xff1a; 在电商项目中的支付模块也是一个很重要的模块&#xff0c;其中下订操作以及退订操作就是主要的操作。其次的下单是同步下单&#xff0c;也就是第三方支付、数据库扣减、积分增加、等等其他业务操作&#xff0c;等待全部执行完毕后向用户返回成功响应请求。对…

SQL99版全外连接和交叉连接和总结

全外连接MySQL不支持 elect 查询列表 from 表名1 表别名1 cross join 表名2 表别名2 on 连接条件 ...... ; 交叉连接 就两个记录做笛卡尔积&#xff01;没什么好说的&#xff0c;基本也没用过&#xff01; 总结

从〇开始深度学习(0)——背景知识与环境配置

从〇开始深度学习(0)——背景知识与环境配置 文章目录 从〇开始深度学习(0)——背景知识与环境配置写在前面1.背景知识1.1.Pytorch1.2.Anaconda1.3.Pycharm1.4.CPU与GPU1.5.整体关系 2.环境配置2.1.准备工作2.1.1.判断有无英伟达显卡2.1.2.清理电脑里的旧环境 2.1.安装Anaconda…

PHP屏蔽海外IP的访问页面(源代码实例)

PHP屏蔽海外IP的访问页面&#xff08;源代码实例&#xff09;&#xff0c;页面禁用境外IP地址访问 <?php/*** 屏蔽海外ip访问* 使用ip2long函数得到ip转为整数的值&#xff0c;判断值是否在任一一个区间中* 以下是所有国内ip段* 调用方法&#xff1a;IschinaIp($ALLIPS)* …

“iOS profile文件与私钥证书文件不匹配”总结打ipa包出现的问题

目录 文件和证书未加载或特殊字符问题 证书过期或Profile文件错误 确认开发者证书和私钥是否匹配 创建证书选择错误问题 申请苹果 AppId时勾选服务不全问题 ​总结 在上线ios平台的时候&#xff0c;在Hbuilder中打包遇见了问题&#xff0c;生成ipa文件时候&#xff0c;一…

VUE 的前置知识

一、JavaScript----导图导出 1. JS 提供的导入导出机制&#xff0c;可以实现按需导入 1.1 在html页面中可以把JS文件通过 <script src"showMessage.js"></script> 全部导入 1.2 通过在JS文件中写export关键字导出通过 <script src"showMessage…

量子卷积神经网络

量子神经网络由量子卷积层、量子池化层和量子全连接层组成 量子卷积层和量子池化层交替放置&#xff0c;分别实现特征提取和特征降维&#xff0c;之后通过量子全连接层进行特征综合 量子卷积层、量子池化层和量子全连接层分别由量子卷积单元、量子池化单元和量子全连接单元组…

学习编程,学习中间件,学习源码的思路

01 看的多&#xff0c;内化不足 最近想复习一下编程相关的知识&#xff0c;在复习前我翻开了之前的一些笔记&#xff0c;这些笔记基本都是从书本、视频、博客等摘取记录的&#xff0c;看着这些笔记心里总结&#xff1a;看的多&#xff0c;内化不足。 02 整理大纲 为了解决这个…

MyBatis框架

1. 什么是MyBatis框架 MyBatis框架是一个优秀的持久层框架&#xff0c;为了简化JDBC开发。传统的JDBC编程编写起来很麻烦。 MyBatis框架使用了数据库连接池技术&#xff0c;避免了频繁的创建和销毁操作。 初始情况下&#xff0c;数据库连接池会默认创建一定数量的connection对…

IDEA配置本地maven

因为idea和maven是没有直接关系的。所以使用idea创建maven工程之前需要将本地的maven配置到idea环境中&#xff0c;这样才可以在idea中创建maven工程。配置方法如下&#xff1a; 1.1 配置本地maven 第一步&#xff1a;关闭当前工程&#xff0c;回到idea主界面找到customize--…

论文阅读——Intrusion detection systems using longshort‑term memory (LSTM)

一.基本信息 论文名称&#xff1a;Intrusion detection systems using longshort‑term memory (LSTM) 中文翻译&#xff1a;基于长短期记忆(LSTM)的入侵检测系统 DOI&#xff1a;10.1186/s40537-021-00448-4 作者&#xff1a;FatimaEzzahra Laghrissi1* , Samira Douzi2*, Kha…

企业OA管理系统:Spring Boot技术实现与案例研究

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了企业OA管理系统的开发全过程。通过分析企业OA管理系统管理的不足&#xff0c;创建了一个计算机管理企业OA管理系统的方案。文章介绍了企业OA管理系统的系统分析部…

递归算法专题一>Pow(x, n)

题目&#xff1a; 解析&#xff1a; 代码&#xff1a; public double myPow(double x, int n) {return n < 0 ? 1.0 / pow(x,-n) : pow(x,n); }private double pow(double x, int n){if(n 0) return 1.0;double tmp pow(x,n / 2);return n % 2 0 ? tmp * tmp : tmp …

阿里云私服地址

1.解压apache-maven-3.6.1-bin 2.配置本地仓库&#xff1a;修改conf/dettings.xml中的<localReoisitory>为一个指定目录。56行 <localRepository>D:\apache-maven-3.6.1-bin\apache-maven-3.6.1\mvn_repo</localRepository> 3.配置阿里云私服&#xff1a;…

基于之前的秒杀功能的优化(包括Sentinel在SpringBoot中的简单应用)

这篇博客主要是对自己之前写的博客的一次优化&#xff0c;可以结合下面两篇博客进行这篇博客的阅读&#xff1a; 对自己关于秒杀功能的一次访谈与实战-CSDN博客 SpringBoot中使用Sharding-JDBC实战&#xff08;实战版本兼容Bug解决&#xff09;-CSDN博客 开始正题&#xff1a…