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

牛客刷题-Day5

n牛客刷题-Day5

今日刷题:\(1021-1025\)

1021 失衡天平

题目描述

终于 \(Alice\) 走出了大魔王的陷阱,可是现在傻傻的她忘了带武器了,这可如何是好???这个时候,一个神秘老人走到她面前答应无偿给她武器,但老人有个条件,需要将所选武器分别放在天平的两端,若天平平衡则可以将天平上的所有武器拿走,还好这个天平锈迹斑斑,只要两端重量相差小于等于 \(m\) 就会保持平衡,\(Alice\) 傻傻的认为越重的武器越好,求 \(Alice\) 最多能拿走的武器总重量。(不限操作次数)

输入描述

第一行 \(2\) 个整数 \(n, m\);
第二行 \(n\) 个整数 \(x\),分别表示 \(n\) 件武器的重量。
\(1 <= n <= 100; 0 <= m <= 100; 1 <= x <= 100\)

输出描述

一个整数,表示 \(Alice\) 最多能拿走的武器总重量。

示例1

输入

5 4
1 5 61 65 100

输出

132

说明:可以称两次,第一次 \((1 ; 5)\),第二次 \((61 ; 65)\)

示例2

输入

5 0
10 20 30 40 100

输出

200

说明:称一次,\((10,20,30,40 ; 100)\)

解题思路

  • 状态表示:\(f_{i,j}\) 表示前 \(i\) 个武器里取若干称重,使得天平左侧减去右侧的差值为 \(j\) 的武器重量和。
  • 状态计算:考虑当前 \(f_{i,j}\),如果未取武器 \(i\),则 \(f_{i,j}=f_{i-1,j}\);若选择了武器 \(i\),则武器 \(i\) 可能放在左侧也可能放在右侧,则 \(f_{i,j}=max\{f_{i-1,j-a_i},f_{i-1,j+a_i}\}+a_i\)\(f_{i-1,j-a_i}\) 表示放在左侧之前的状态,\(f_{i-1,j+a_i}\) 放在右侧之前的状态。

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 20010;int n, m, a[N], total;
int f[N][M]; // 前 i 个武器取若干且质量差(左减右)为 jint main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);total += a[i];}memset(f, 128, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; i++)for (int j = 0; j <= total; j++) {f[i][j] = max(f[i - 1][j], max(f[i - 1][abs(j - a[i])], f[i - 1][j + a[i]]) + a[i]);}int ans = 0;for (int i = 0; i <= m; i++)ans = max(ans, f[n][i]);printf("%d\n", ans);return 0;
}

1022 Music Problem

题目描述

Listening to the music is relax, but for obsessive(强迫症), it may be unbearable.
HH is an obsessive, he only start to listen to music at 12:00:00, and he will never stop unless the song he is listening ends at integral points (both minute and second are 0 ), that is, he can stop listen at 13:00:00 or 14:00:00,but he can't stop at 13:01:03 or 13:01:00, since 13:01:03 and 13:01:00 are not an integer hour time.
Now give you the length of some songs, tell HH whether it's possible to choose some songs so he can stop listen at an integral point, or tell him it's impossible.
Every song can be chosen at most once.

输入描述

The first line contains an positive integer \(T(1≤T≤60)\), represents there are \(T\) test cases.
For each test case:
The first line contains an integer \(n(1≤n≤10^5)\), indicating there are n songs.
The second line contains \(n\) integers \(a_1,a_2…a_n (1≤a_i≤10^9)\), the \(i\)-th integer \(a_i\) indicates the \(i\)-th song lasts \(a_i\) seconds.

输出描述

For each test case, output one line "YES" (without quotes) if HH is possible to stop listen at an integral point, and "NO" (without quotes) otherwise.

示例1

输入

3
3
2000 1000 3000
3
2000 3000 1600
2
5400 1800

输出

NO
YES
YES

说明:In the first example it's impossible to stop at an integral point.
In the second example if we choose the first and the third songs, they cost 3600 seconds in total, so HH can stop at 13:00:00
In the third example if we choose the first and the second songs, they cost 7200 seconds in total, so HH can stop at 14:00:00

解题思路

容斥原理的应用:这里的数都是整数。考虑 \(sum_i=\sum_{j=1}^ia_i\),则对于 \(m+1\) 个整数,其 \(sum\)\(m+1\) 个,而余数为 \(0\)\(m-1\) 共计 \(m\) 个,那么必然存在 \(sum_i\)\(sum_j\) 的余数相同,不妨设 \(i<j\),则 \(sum_j-sum_i=\sum_{k=i+1}^j\) 的余数为 \(0\)
基于上述结论,我们可以确定如果音乐数超过 \(3600\),则必然为 YES

  • 状态表示:\(f_{j}\) 表示从音乐选择若干的和除以 \(3600\) 余数为 \(j\) 的方案是否存在。
  • 状态计算:如果 \(f_{j}\) 存在,则 \(f_{(j+a_i) \% 3600}\) 存在,最后判断 \(f_0\) 是否存在即可。

时间复杂度为 \(O(T*n*3600)\)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010, M = 4010, MOD = 3600;int T, n;
LL a[N];
LL f[M]; // f[i][j] 表示从前 i 个里选若干个之和int main() {scanf("%d", &T);while (T--) {memset(f, 0, sizeof f);scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);a[i] %= MOD;}if (n > 3600) { // 容斥原理puts("YES");continue;}for (int i = 1; i <= n; i++) {vector<int> last;for (int j = 0; j < MOD; j++)if (f[j])last.push_back((j + a[i]) % MOD);for (int j = 0; j < last.size(); j++)f[last[j]] = 1;f[a[i]] = 1;if (f[0]) break;}if (f[0])puts("YES");elseputs("NO");}return 0;
}

1023 美味菜肴

题目描述

小明是个大厨,早上起来他开始一天的工作。他所在的餐厅每天早上都会买好 \(n\) 件食材(每种食材的数量可以视为无限),小明从到达餐厅开始就连续工作 \(T\) 时间。每道菜肴的制作需要特定的一种食材以及一段时间,但是食材一旦放久就不新鲜了,菜的美味值会降低。第 \(i\) 道菜肴有三个属性 \(a_i\)\(b_i\)\(c_i\)\(a_i\) 是该菜肴的美味值,\(b_i\) 是该菜肴所选食材不新鲜的速率,如果在第 \(t\) 时刻完成第 \(i\) 道菜则美味值为:\(a_i−t∗b_i\),完成这道菜需要 \(c_i\) 的时间。小明希望在这 \(T\) 时间内能做出菜肴使得总美味值最大,所以小明求助于你。

输入描述

\(1\) 行输入三个整数 \(n\)\(m\)\(T\),分别代表食材种类,菜肴种类和工作时间。
\(2\) 行输入 \(n\) 个整数 \(b_i\),代表第 \(i\) 个食材不新鲜的速率。
接下来的 \(m\) 行,每行输入三个整数 \(j\)\(a_i\)\(c_i\),分别代表第 \(i\) 道菜肴需要的食材编号,菜肴的美味值,完成时间。
数据保证:\(0<n,m≤50\)\(0<j≤n\),其他值均 \(<10^6\),美味值必须通过完整做出菜肴得到,数据保证在规定时间内至少能完整做出 \(1\) 道菜肴。

输出描述

输出一行,一个整数,表示最大总美味值。

示例1

输入

1 1 74
2
1 502 47

输出

408
示例2

输入

2 2 10
2 1
1 100 8
2 50 3

输出

84

备注

最大总美味值可能为负。

解题思路

这里初步想法是利用 \(01\) 背包的思路进行求解,但是细想会存在一个问题,即如果菜肴 \(A\)\(B\) 都做的话,那么顺序不同,最终获取的美味值是不同的,因此我们需要对原数据进行排序,确定菜肴的顺序。
设当前时间为 \(T\),则先做 \(A\) 后做 \(B\),美味值为 \(A.a-(T+A.c)*b_{A.j}+B.a-(T+A.c+B.c)*b_{B.j}\);先做 \(B\) 后做 \(A\),美味值为 \(B.a-(T+B.c)*b_{B.j}+A.a-(T+A.c+B.c)*b_{A.j}\);前者大于后者,简化后为 \(A.c*b_{B.j}<B.c*b_{a.j}\)
排序之后的做法就和背包问题类似。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 60;
typedef long long LL;int n, m, T;
LL b[M];
struct Dish {LL j, a, c;
} d[M];
LL f[N]; // f[i] 表示在 t 时刻已完成菜肴的美味值bool cmp(Dish x, Dish y) {return x.c * b[y.j] < y.c * b[x.j];
}int main() {memset(f, 128, sizeof f);scanf("%d%d%d", &n, &m, &T);for (int i = 1; i <= n; i++)scanf("%lld", &b[i]);for (int i = 1; i <= m; i++)scanf("%lld%lld%lld", &d[i].j, &d[i].a, &d[i].c);sort(d + 1, d + m + 1, cmp);f[0] = 0;for (int i = 1; i <= m; i++) {for (int t = T; t >= d[i].c; t--)f[t] = max(f[t], f[t - d[i].c] + d[i].a - t * b[d[i].j]);}LL ans = -1e18;for (int i = 1; i <= T; i++)ans = max(ans, f[i]);printf("%lld\n", ans);return 0;
}

1024 [NOIP2006] 金明的预算方案

题目描述

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过 \(N\) 元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:
image
如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有 \(0\) 个、\(1\) 个或 \(2\) 个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的 \(N\) 元。于是,他把每件物品规定了一个重要度,分为 \(5\) 等:用整数 \(1~5\) 表示,第 \(5\) 等最重要。他还从因特网上查到了每件物品的价格(都是 \(10\) 元的整数倍)。他希望在不超过 \(N\) 元(可以等于 \(N\) 元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第 \(j\) 件物品的价格为 \(v[j]\),重要度为 \(w[j]\),共选中了 \(k\) 件物品,编号依次为 \(j_1\)\(j_2\)\(…\)\(j_k\),则所求的总和为:\(v[j_1]*w[j_1]+v[j_2]*w[j_2]+…+v[j_k]*w[j_k]\)。(其中 \(*\) 为乘号)
请你帮助金明设计一个满足要求的购物单。

输入描述

\(1\) 行,为两个正整数,用一个空格隔开:\(N\)\(<32000\))表示总钱数,\(m\)\(<60\))为希望购买物品的个数。
从第 \(2\) 行到第 \(m+1\) 行,第 \(j\) 行给出了编号为 \(j-1\) 的物品的基本数据,每行有 \(3\) 个非负整数 \(v\) \(p\) \(q\)(其中 \(v\) 表示该物品的价格(\(v < 10000\)),\(p\) 表示该物品的重要度(\(1~5\)),\(q\) 表示该物品是主件还是附件。如果 \(q=0\),表示该物品为主件,如果 \(q>0\),表示该物品为附件,\(q\) 是所属主件的编号)。

输出描述

输出一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(\(<200000\))。

示例1

输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出

2200

解题思路

  • 状态表示:\(f_j\) 表示选择若干物品花费不超过 \(j\) 的值。
  • 状态计算:因为每个主件有 \(0-2\) 个附件,因此如果存在附件,则考虑主件与附件共同购买的情况,进行状态转移的计算。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 65, M = 40010;
typedef long long LL;
typedef pair<int, int> PII;int n, m;
struct A {int v, w;
} a[N]; // 主件
int b_v[N][3], b_w[N][3]; // 主件 i 对应附件// 0 表示数量、1 表示附件 1、2 表示附件 2
int f[M];int main() {scanf("%d%d", &m, &n);for (int i = 1; i <= n; i++) {int v, p, q;scanf("%d%d%d", &v, &p, &q);if (q) { // 附件b_v[q][0]++;b_v[q][b_v[q][0]] = v;b_w[q][b_v[q][0]] = v * p;} else {a[i] = {v, v * p};}}for (int i = 1; i <= n; i++)for (int j = m; j >= a[i].v; j--) {f[j] = max(f[j], f[j - a[i].v] + a[i].w);if (j >= a[i].v + b_v[i][1])f[j] = max(f[j], f[j - (a[i].v + b_v[i][1])] + a[i].w + b_w[i][1]);if (j >= a[i].v + b_v[i][2])f[j] = max(f[j], f[j - (a[i].v + b_v[i][2])] + a[i].w + b_w[i][2]);if (j >= a[i].v + b_v[i][1] + b_v[i][2])f[j] = max(f[j], f[j - (a[i].v + b_v[i][1] + b_v[i][2])] + a[i].w + b_w[i][1] + b_w[i][2]);}printf("%d\n", f[m]);return 0;
}

1025 队伍配置

题目描述

萌学姐在玩大型手游《\(futa\, go\)》,他现在准备进入作战环节,所以他准备安排自己的队伍。
队伍配置里,可供玩家选择的作战人物被称作“从者”,玩家可以对每个“从者”可以装备至多 \(1\) 件的“概念礼装”,玩家具有一个 \(cost\) 上限值。详细定义如下:

  1. 每个从者和概念礼装都具有攻击值 \(ATK\)
  2. 每个从者和概念礼装都会占据一定的 \(cost\) 值。
  3. 每个从者和概念礼装只能上场一次,不能重复使用。
  4. 概念礼装只能装备在从者上,不能单独存在。
  5. 选择的从者和概念礼装的 \(cost\) 值之和不能超过玩家的 \(cost\) 上限值。
  6. 最多可以选择 \(5\) 名从者(在 \(cost\) 值限制下)。
    现在给出玩家仓库的每个从者和每件概念礼装的 \(ATK\) 值和 \(cost\) 值,问在满足定义的条件下,队伍可以凑出的最大 \(ATK\) 值。

输入描述

\(1\) 行输入三个整数 \(n\)\(m\)\(d\),代表玩家仓库的从者数量、概念礼装数量和 \(cost\) 上限值。
\(2-n+1\) 行,每行输入两个整数 \(a_1\)\(b_1\),表示第 \(i\) 个从者的 \(ATK\) 值和 \(cost\) 值。
\(n+2-n+m+1\) 行,每行输入两个整数 \(a_2\)\(b_2\),表示第 \(i\) 个概念礼装的 \(ATK\) 值和 \(cost\) 值。
数据保证:\(0<n,m≤300\)\(25≤d≤138\)\(1000≤a_1≤15488\)\(500≤a_2≤2500\)\(3≤b_1,b_2≤12\)

输出描述

输出一行,一个整数,代表可以凑出的最大 \(ATK\) 值。

示例

输入

4 2 25
2001 5
2002 5
2003 5
4010 10
2004 10
2005 10

输出

10016

说明:派上前 \(4\) 名从者,最大 \(ATK\)\(=2001+2002+2003+4010=10016\)\(cost\) 总值为 \(25=\)玩家 \(cost\) 上限)

解题思路

  • 状态表示:\(f_{i,j,k}\) 表示从者 \(i\) 个、礼装 \(j\) 个、花费值不超过 \(k\)\(ATK\) 值。
  • 状态计算:首先考虑礼装数为零的情况,因为礼装的选择会受到从者人数的限制,则 \(f_{i,0,k}=max\{f_{i,0,k},f_{i-1,0,k-a_i.cost}+a_i.atk\}\);然后考虑礼装,\(f_{k,u,j}=max\{f_{k,u,j}, f_{k,u-1,j-b_i.cost} + b_i.atk\}\),礼装数小于等于从者数。

参考:NC14699 队伍配置

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 310, M = 150, K = 10;int n, m, d;
struct Node {int atk, cost;
} a[N], b[N];
int f[K][K][M]; // f[i][j][k] 表示 i 个从者 j 个礼装 k 花费int main() {scanf("%d%d%d", &n, &m, &d);for (int i = 1; i <= n; i++)scanf("%d%d", &a[i].atk, &a[i].cost);for (int i = 1; i <= m; i++)scanf("%d%d", &b[i].atk, &b[i].cost);memset(f, 128, sizeof f);f[0][0][0] = 0;for (int i = 1; i <= n; i++)for (int j = d; j >= a[i].cost; j--)for (int k = 1; k <= 5; k++)f[k][0][j] = max(f[k][0][j], f[k - 1][0][j - a[i].cost] + a[i].atk);for (int i = 1; i <= m; i++)for (int j = d; j >= b[i].cost; j--)for (int k = 1; k <= 5; k++)for (int u = 1; u <= k; u++)f[k][u][j] = max(f[k][u][j], f[k][u - 1][j - b[i].cost] + b[i].atk);int ans = 0;for (int i = 0; i <= 5; i++)for (int j = 0; j <= 5; j++)for (int k = 0; k <= d; k++)ans = max(ans, f[i][j][k]);cout << ans << '\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=17794

相关文章:

  • 用标准版平板干翻上代Pro,小米又想学苹果了?
  • VonaJS多租户同时支持共享模式和独立模式
  • 记录一下第一次为Dify贡献插件的经历
  • 物联网字节校验常用方法
  • STM32H743-ARM例程2-UART命令控制LED - 实践
  • 完整教程:Zookeeper与Kafka:分布式系统中的协调与消息队列
  • vite-vue3 项目优化首屏加载速度
  • 12_TCP和UDP实现服务端和客户端的通信
  • 各种软件的官方文档和安装包下载地址记录
  • 基于导频的OFDM系统的信道估计(使用LS估计算法)
  • Day22super详解
  • 外发图纸如何控制的最佳实践与注意事项
  • Gitee:中国开发者生态的数字底座正在重构技术格局
  • 快递100
  • 文件同步软件是什么?主要有哪几种类型?
  • “铸网2025”山东省工业和互联网CTF竞赛-web
  • 领嵌iLeadE-588网关AI边缘计算盒子一键部署二次开发
  • 2025年值得选的文件摆渡系统品牌解析
  • 全球知名的Java Web开发平台Vaadin上线慧都网!
  • C#实现与欧姆龙PLC通信
  • linux docker 配置外网拉镜像
  • 什么是跨网文件摆渡系统?IT运维效率提升300%的秘密武器
  • 借助Aspose.Email,在 Python中创建事件日历
  • 实用指南:【JavaEE初阶】多线程重点知识以及常考的面试题-多线程进阶(三)
  • C++ map 和unordered_map 的区别
  • 【英语启蒙动画合集】0基础宝宝必看的动画,超全!直接下载~
  • 基于OPC UA协议的SIMATIC PLC通信实现
  • AI 自动化智能体训练营 | 借助人工智能提升工作效率,打造自己的智能体工作流
  • MX-X21
  • Kubernetes Cilium网络组件和CoreDNS配置