您现在的位置是:首页 > 正文

USACO翻译:USACO 2012 JAN三题(1)

2024-01-30 20:46:27阅读 0

USACO 2012 JAN(题目一)

一、题目概览

中文题目名称

礼物

配送路线

   游戏组合技

英文题目名称

gifts

delivery

combos

可执行文件名

gifts

delivery

combos

输入文件名

gifts.in

delivery.in

combos.in

输出文件名

gifts.out

delivery.out

combos.out

每个测试点时限

1秒

1秒

1秒

测试点数目

10

10

10

每个测试点分值

10

10

10

比较方式

全文比较

全文比较

全文比较

二、运行内存限制

运行内存上限

128 M

128 M

128 M

      注:感谢老胡鼎力翻译。【错误会有的,语句也不是那么流畅……】

 

1.礼物{Bronze1}

【问题描述】

    FJ计划用他的B(1 <= B <= 1,000,000,000)元预算给他的N(1 <= N <= 1000)头牛送礼物。

第i头牛的礼物的购买花费P(i)元,快递费用是S(i)元。FJ有一张可以半价购买一样礼物的优惠券,如果用于礼物i,则他花费在这个礼物上的总费用是P(i)/2+S(i),巧合的是,P(i)一定是一个偶数。

请计算FJ最多能给多少头牛送礼物。

【文件输入】

第一行,两个整数,分别是N和B。

第2..N+1行,每行两个整数,分别表示P(i)和 S(i). 

(0 <= P(i),S(i) <= 1,000,000,000)。

【文件输出】

一个整数,FJ最多能给多少头牛送礼物。

【输入样例】

5 24

4 2

2 0

8 1

6 3

12 5

【输出样例】

4

【样例说明】

购买1到4的礼物,优惠券给3使用,(4+2)+(2+0)+(4+1)+(6+3) = 22,他也可以将优惠券使用在1或者4.

 

2. 栅栏油漆{silver1}

【问题描述】

    FJ有N (1 <= N <= 100)个农场,每个农场具有独立的整数坐标(x_i, y_i)。他需要一个物资配送路线,从第1个农场出发,依次经过农场1,农场2,农场3…,最后从农场N回到农场1.

FJ每次只能朝东南西北四个方向行走,没行走一个单位长度需要1分钟,除了农场1,其他农场能且仅能到达一次。

请计算FJ的最小时间花费。

【文件输入】

   第一行,一个整数N。

   第2..N+1行,每行两个整数x_i和y_i  (1 <= x_i, y_i <= 1,000,000).

【文件输出】

   一行,一个整数,表示最小时间花费。无解则输出-1。

【输入样例】

4

2 2

2 4

2 1

1 3

【输出样例】

12

【样例说明】

FJ可以在12分钟内完成,他的传递路线:2分钟,从农场去1至2农场;5分钟从农场2到3农庄(绕过农场1);3分钟以去从农场3到农场4; 2分钟,从农场4回到农场1。

3. 游戏组合技{ Gold1}

【问题描述】

    贝西在玩一款游戏,该游戏只有三个技能键 “A”“B”“C”可用,但这些键可用形成N种(1 <= N<= 20)特定的组合技。第i个组合技用一个长度为1到15的字符串S_i表示。

    当贝西输入的一个字符序列和一个组合技匹配的时候,他将获得1分。特殊的,他输入的一个字符序列有可能同时和若干个组合技匹配,比如N=3时,3种组合技分别为"ABA", "CB", 和"ABACB",若贝西输入"ABACB",他将获得3分。

    若贝西输入恰好K (1 <= K <= 1,000)个字符,他最多能获得多少分?

【文件输入】

第一行,两个整数N和K。

第2..N+1行,每行一个字符串,表示一种组合技。

【文件输出】

一行,一个整数,表示最大得分。

【输入样例】

3 7

ABA

CB

ABACB

【输出样例】

4

【样例说明】

输入ABACBCB,ABA得1分,ABACB得1分,CB得2分。

转载于:https://www.cnblogs.com/jznoi/p/4149742.html

网站文章

  • 详解pandas的read_csv方法

    详解pandas的read_csv方法

    而为了保证正常读取,就会把类型像大的方向兼容,比如第一块的user_id被解析成整型,但是在解析第二个块发现user_id有的值无法解析成整型,那么类型整体就会变成字符串,于是pandas提示该列存在...

    2024-01-30 20:45:50
  • QTextLine、QGlyphRun、QTextLayout

    QTextLine、QGlyphRun、QTextLayout

    QTextLine、QGlyphRun、QTextLayout

    2024-01-30 20:45:43
  • npm 启动报错 ERROR in [eslint] Failed to load plugin ‘vue‘ declared in ‘.eslintrc.js‘:

    npm 启动报错 ERROR in [eslint] Failed to load plugin ‘vue‘ declared in ‘.eslintrc.js‘:

    1.清缓存,删除node_modules 文件夹,删除package-lock.json ,然后执行npm install ---试了不好用。版本 由 node-v12.2.0-x64.msi 更新至 最新版本node-v20.3.1-x64.msi。2. 更新 node.js 版本 ---这个好用问题解决,下载 | Node.js 中文网。node 中文官网下载地址。

    2024-01-30 20:45:37
  • realuid、saveduid和effectiveuid

    Maurice J.Bach 的《The Design of The UNIX Operating System》一书中对这个问题的论述。。。p2277.6 THE USER ID OF A PROCESS内核会给每个进程关联两个和进程ID无关的用户ID,一个是真实用户ID,还有一个是有效用户ID或者称为setuid(set user ID)。真实用户ID用于标识由谁为正在运行的进程负责。有效用户

    2024-01-30 20:45:07
  • 离散傅里叶变换(DFT)/快速傅里叶变换(FFT)matlab

    matlab计算卷积例1x1(n)={2,1,1,2} x2(n)={1,-1,-1,1}两种方法1)直接用时域计算卷积2)x1(n)={2,1,1,2} x2(n)={1,-1,-1,1}分别dft...

    2024-01-30 20:45:02
  • asp.net MVC3之AJAX实现(json)

    1.建一个mvc3的项目,取名叫MVC3Test 2.修改About.cshtml,如下代码 About.cshtml About.cshtml@{ ViewBag.Title = &quot;About Us&quot;; } script type=&quot;text/javascr

    2024-01-30 20:44:56
  • STM32cubeIDE安装教程

    STM32cubeIDE安装教程

    STM32CubeIDE集成了STM32CubeMX的STM32配置与项目创建功能,以便提供一体化工具体验,并节省安装与开发时间。在通过所选板卡或示例选择一个空的STM32 MCU或MPU,或者预配置微控制器或微处理器之后,将创建项目并生成初始化代码。在开发过程的任何时间,用户均可返回外设或中间件的初始化和配置阶段,并重新生成初始化代码,期间不会影响用户代码。

    2024-01-30 20:44:28
  • 如何解决Form表单的重复提交

    以前在做居民信息管理系统时出现过一个非常严重的问题,在添加居民信息,每刷新一次就会数据库中就会重复提交一次。这个问题很让人头疼,正好最近有一次面试,也被提问到此问题了,故在网上搜了一些这方面的文章。供交流学习之用。  三种方案javascript ,设置一个变量,只允许提交一次。   var checkSubmitFlg = false;  funct

    2024-01-30 20:44:20
  • 往c盘复制文件时,总是拒绝访问

    往c盘复制文件时,总是拒绝访问

    win10如何获取管理员权限?在往c盘复制文件时,总是拒绝访问,请问该怎么办?20 分享 举报 6个回答 #热议#3分钟看懂!2019年个税年度汇算怎么算? 华硕服务 百度认证:华硕电脑(上海)官方帐号推荐于2017-12-11 关注 Windows 10操作系统中开启Administrator超级管理员账户方法步骤如下百: 1、在Win10左下角的开始图标上点击...

    2024-01-30 20:44:12
  • 基本排序(二)插入排序(直接插入、Shell、折半)

      插入排序是常见的内部排序之一。常见的插入排序包括直接插入排序、Shell排序、折半排序。本篇主要介绍这三个排序。  转载请注明出处——http://www.cnblogs.com/zrtqsk/p/3807611.html,谢谢!一、直接插入排序  直接插入排序大概是我们最容易理解的一类排序了。  1、原理  对于n个元素的记录。  第一趟  :  把第2个元素拿...

    2024-01-30 20:44:05