模拟题

2024-10-18

P1026

P1054

2024-10-17

题目背景

在商店中，每一种商品都有一个价格（用整数表示）。例如,一朵花的价格是 $2$ ，而一个花瓶的价格是 $5$ 。为了吸引更多的顾客，商店举行了促销活动。

题目描述

促销活动把一个或多个商品组合起来降价销售，例如：

三朵花的价格是 $5$ 而不是 $6$ ，$2$ 个花瓶和一朵花的价格是 $10$ 而不是 $12$ 。 请编写一个程序，计算顾客购买一定商品的花费，尽量地利用优惠使花费最少。尽管有时候添加其他商品可以获得更少的花费，但是你不能这么做。

对于上面的商品信息，购买三朵花和两个花瓶的最少花费的方案是：以优惠价购买两个花瓶和一朵花（$10$），以原价购买两朵花（$4$）。

输入格式

输入文件包括一些商店提供的优惠信息，接着是购物清单。（最多有 $5$ 种商品）

第一行 优惠方案的种类数（$0\leq s\leq99$）。

第 $2$ 行 $\sim$ 第 $s+1$ 行 每一行都用几个整数来表示一种优惠方式。第一个整数 $n$ （$\leq n\leq5$），表示这种优惠方式由 $n$ 种商品组成。后面 $n$ 对整数 $c$ 和 $k$ 表示 $k$ （$1\leq k\leq5$）个编号为 $c$ （$1\leq c\leq999$）的商品共同构成这种优惠，最后的整数 $p$ 表示这种优惠的优惠价（$1\leq p\leq9,999$）。优惠价总是比原价低。

第 $s+2$ 行 这一行有一个整数 $b$ （$0\leq b\leq5$），表示需要购买 $b$ 种不同的商品。

第 $s+3$ 行 $\sim$ 第 $s+b+2$ 行 这 $b$ 行中的每一行包括三个整数：$c,k,p$ 。 $c$ 表示唯一的商品编号（$1\leq c\leq999$），$k$ 表示需要购买的 $c$ 商品的数量（$1\leq k\leq5$）。$p$ 表示 $c$ 商品的原价（$1\leq p\leq999$）。最多购买 $5\times5=25$ 个商品。

输出格式

只有一行，输出一个整数：购买这些物品的最低价格。

样例 #1

样例输入 #1

2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5

样例输出 #1

14

提示

题目翻译来自NOCOW。

USACO Training Section 3.3

2024-10-16

题目描述

老师想从 $n$ 名学生中选 $m$ 人当学霸，但有 $k$ 对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的 $m$ 尽可能接近。

输入格式

第一行，三个正整数 $n,m,k$。

接下来 $k$ 行，每行 $2$ 个数，表示一对实力相当的人的编号（编号为 $1,2,\cdots n$）。

输出格式

共一行，表示既不让同学们抗议，又与原来的 $m$ 尽可能接近的选出学霸的数目。

如果有两种方案与 $m$ 的差的绝对值相等，选较小的一种。

样例 #1

样例输入 #1

4 3 2
1 2
3 4

样例输出 #1

2

提示

对于 $100%$ 的数据，满足 $1 \le n,m \le 2 \times 10^4$。

2024-10-15

题目

rnd函数如下：

inline int rnd () {
    static const int MOD = 1e9;
    return Seed = ( 1LL * Seed * 0x66CCFF % MOD + 20120712 ) % MOD;
}

样例 #1

样例输入 #1

5 3 4 1 0
1 2 3 4 5

样例输出 #1

27

样例 #2

样例输入 #2

10 30630 56910 2 0
7484 99194 86969 17540 29184 68691 91892 81564 93999 74280

样例输出 #2

717318

样例 #3

样例输入 #3

10000000 899999999 923456655 213111 1
1314520

样例输出 #3

9231813656566921

2024-10-12

题目

样例 #1

样例输入 #1

13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13

样例输入 #1

11000