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

牛客刷题-Day7

牛客刷题-Day7

今日刷题:\(1031-1035\)

1032 迁徙过程中的河流

题目描述

牛市的幸存的先民在流星雨之后就忍痛离开了这片土地,选择迁徙,在迁徙的途中,他们需要渡过一条河。因为牛市的树木在流星雨中被严重破坏,所以他们只造出了一艘小船,船太小了,一次只能乘坐两人。
牛市的先民们每个人划船的速度都不尽相同,所以每个人都有一个渡河时间T,为了保证船的平衡,当穿上有两个人的时候,需要他们按照慢的那个人的速度划船,也就是说船到达对岸的时间等于船上渡河时间长的那个人的时间。
现在已知 \(N\) 个人的渡河时间 \(T\),请问最少要花费多少时间,才能使所有人都过河。

输入描述

输入文件第一行为先民的人数 \(N\)\(N≤100000\)),以下有 \(N\) 行,每行一个整数为每个人的渡河时间。

输出描述

输出文件仅包含一个数,表示所有人都渡过河的最少渡河时间。

示例1

输入

4
5
7
11
16

输出

42

说明
首先 \(1\)\(2\) 先到河对岸花费 \(7\),然后 \(1\) 回来花费 \(5\)\(3\)\(4\) 到河对岸花费 \(16\)\(2\) 回来花费 \(7\)\(1\)\(2\) 再到河对岸花费 \(7\)

解题思路

首先是贪心,将渡河时间按照递增的顺序进行排序。

  • 状态表示:\(f_i\) 表示前 \(i\) 个人渡河耗费的时间,求最小值;
  • 状态计算:两种方式,首先是耗时最少的 \(a_1\) 为来回接送的人员,\(a_1\) 先回去然后带着 \(a_i\) 过去,则 \(f_i=f_{i-1} + a_1 + a_i\);其次\(a_1\) 先回去,两个耗时相近的一起过去,然后 \(a_2\) 去接 \(a_1\)\(f_i=f_{i-2} + a_1 + a_i + a_2 * 2\)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;int n, a[N];
int f[N]; // 表示前 i 个人过河的时间int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);sort(a + 1, a + n + 1);memset(f, 127, sizeof f);f[1] = a[1], f[2] = a[2];for (int i = 3; i <= n; i++)f[i] = min(f[i - 1] + a[1] + a[i], f[i - 2] + a[1] + a[i] + a[2] * 2);printf("%d\n", f[n]);return 0;
}

1034 [USACO 2009 Dec G]Video Game Troubles

题目描述

Farmer John's cows love their video games! FJ noticed that after playing these games that his cows produced much more milk than usual, surely because contented cows make more milk.
The cows disagree, though, on which is the best game console. One cow wanted to buy the Xbox 360 to play Halo 3; another wanted to buy the Nintendo Wii to play Super Smash Brothers Brawl; a third wanted to play Metal Gear Solid 4 on the PlayStation 3. FJ wants to purchase the set of game consoles (no more than one each) and games (no more than one each -- and within the constraints of a given budget) that helps his cows produce the most milk and thus nourish the most children.
FJ researched \(N\) (\(1 <= N <= 50\)) consoles, each with a console price \(P_i\) (\(1 <= P_i <= 1000\)) and a number of console-specific games \(G_i\) (\(1 <= G_i <= 10\)). A cow must, of course, own a console before she can buy any game that is specific to that console. Each individual game has a game price \(GP_j\) (\(1 <= GP_j <= 100\)) and a production value (\(1 <= PV_j <= 1,000,000\)), which indicates how much milk a cow will produce after playing the game. Lastly, Farmer John has a budget \(V\) (\(1 <= V <= 100,000\)) which is the maximum amount of money he can spend. Help him maximize the sum of the production values of the games he buys.
Consider one dataset with \(N=3\) consoles and a $V=\(800\) budget. The first console costs \(\$300\) and has \(2\) games with cost \(\$30\) and \(\$25\) and production values as shown:

Game #    Cost    Production Value1       $30          502       $25          80

The second console costs \(\$600\) and has only \(1\) game:

Game #    Cost    Production Value1       $50          130

The third console costs \(\$400\) and has \(3\) games:

Game #    Cost    Production Value1       $40         702       $30         403       $35         60

Farmer John should buy consoles \(1\) and \(3\), game \(2\) for console \(1\), and games \(1\) and \(3\) for console \(3\) to maximize his expected production at \(210\):

                          Production ValueBudget:     $800      Console 1  -$300Game 2   -$25              80Console 3  -$400Game 1   -$40              70Game 3   -$35              60
-------------------------------------------Total:         0 (>= 0)      210

输入描述

  • Line \(1\): Two space-separated integers: \(N\) and \(V\)
  • Lines \(2..N+1\): Line \(i+1\) describes the price of and the games ?available for console \(i\); it contains: \(P_i\), \(G_i\), and \(G_i\) pairs of space-separated integers \(GP_j\), \(PV_j\)

输出描述

  • Line \(1\): The maximum production value that Farmer John can get with his budget.
示例1

输入

3 800 
300 2 30 50 25 80 
600 1 50 130 
400 3 40 70 30 40 35 60 

输出

210

解题思路

具有依赖关系的背包问题。
首先因为购买主机不增加收益,因此可以先不考虑主机,直接对主机 \(i\) 的游戏进行 \(01\) 背包问题的求解,然后再扣除消费。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = 20, V = 100010;struct Computer {int p, g;int gp[M], pv[M];
} c[N];
int n, v;
int f[V], ft[V]; // ft[i] 表示前 i 个主机和游戏,不考虑 i 主机价格的值int main() {scanf("%d%d", &n, &v);for (int i = 1; i <= n; i++) {scanf("%d%d", &c[i].p, &c[i].g);for (int j = 1; j <= c[i].g; j++)scanf("%d%d", &c[i].gp[j], &c[i].pv[j]);}for (int i = 1; i <= n; i++) {for (int j = 0; j <= v; j++)ft[j] = f[j];for (int j = 1; j <= c[i].g; j++)for (int k = v; k >= c[i].gp[j]; k--)ft[k] = max(ft[k], ft[k - c[i].gp[j]] + c[i].pv[j]);for (int j = c[i].p; j <= v; j++)f[j] = max(f[j], ft[j - c[i].p]);}int ans = 0;for (int j = 0; j <= v; j++)ans = max(ans, f[j]);printf("%d\n", ans);return 0;
}

1035 简单瞎搞题

题目描述

一共有 \(n\) 个数,第 \(i\) 个数是 \(x_i\)
\(x_i\) 可以取 \([l_i , r_i]\) 中任意的一个值。
\(S=∑x_i^2\),求 \(S\) 种类数。

输入描述

第一行一个数 \(n\)
然后 \(n\) 行,每行两个数表示 \(l_i,r_i\)

输出描述

输出一行一个数表示答案。

示例1

输入

5
1 2
2 3
3 4
4 5
5 6

输出

26

备注

\(1 ≤ n , l_i , r_i ≤ 100\)

解题思路

  • 状态表示:\(f_{i,j}\) 表示前 \(i\) 个区间取 \(i\) 个数的平方和为 \(j\),是否成立;
  • 状态计算:\(f_{i,j}=f_{i,j} | f_{i-1,j-k*k}\)
    此题目根据数据范围平方和最大为 \(100*100*100=10^6\),而 \(i\) 的范围为 \(100\),区间长度为 \(100\),故时间复杂度为 \(O(10^10)\),会超时,使用 \(bitset\) 优化平方和的范围。

C++ 代码

#include <bits/stdc++.h>
#include <bitset>
using namespace std;
const int N = 110, M = 1000010;int n, l[N], r[N];
bitset<M> f[N];
// f[i][j] 表示从前 i 个里面选数和为 j 是否可能
// f[i][j] = f[i - 1][j - k * k] 如果第 i 个选择 k
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d%d", &l[i], &r[i]);f[0][0] = 1;for (int i = 1; i <= n; i++)for (int k = l[i]; k <= r[i]; k++) {f[i] |= (f[i - 1] << (k * k));}printf("%d\n", f[n].count());return 0;
}
http://www.hskmm.com/?act=detail&tid=20406

相关文章:

  • 第2周
  • 苍穹外卖-day03(公共字段自动填充,新增菜品,菜品分页查询,删除菜品,修改菜品) - a
  • PWN手的成长之路-03-bjdctf_2020_babystack
  • 集合进阶-List集合
  • 对四大经典请求方式的疑惑
  • WordPress文章设置固定链接或永久链接 - 教程
  • 个人用云计算学习笔记 --15. (Linux 系统启动原理、Linux 防火墙管理)) - 实践
  • dotnet项目编译运行
  • linux virtualenv使用
  • 坚果云官方插件实现obsidian多端同步
  • Tk核心概念
  • 位运算的奇技淫巧:builtin内建函数
  • 数据类型-列表
  • 智表 ZCELL:纯前端 Excel 导入导出的高效解决方案,让数据处理更轻松
  • 【MySQL 高阶】MySQL 架构与存储引擎全面详解 - 实践
  • ISO 雨晨 26200.6588 Windows 11 企业版 LTSC 25H2 自用 edge 140.0.3485.81 - 教程
  • lc1039-多边形三角剖分的最低得分
  • Powershell 进阶语(三)
  • 随机函数
  • 集合进阶-collection集合
  • 115. 不同的子序列
  • 素数定理的初等证明
  • Spring Boot项目中集成MyBatis-Plus
  • 深入解析:ShellExtensionU.dll COMToolKit.dll CardRes.dll grubinst.exe vbar332.dll Vb5db.dll dao360.dll
  • 我不懂 愈完美愈是空洞 挂着张可憎面容 维系虚假脆弱的梦
  • 51c自动驾驶~合集33 - 详解
  • VSCod安装esp-idf插件 ERROR_INVALID_PIP错误解决
  • 一款在线免费 PDF AI 工具平台,PDF 拆分,合并,加水印,PDF与Word、Excel、PPT、图片、TXT、HTML、Markdown互转的在线AI工具
  • 计算机核心课
  • 【SimpleFOC】vofa+监控电机数据