校内OJ 2019.3.17 NOIP 模拟赛

前言

Rank 7,Rating +48。

第二道题 $STL$ 莫名玄学炸 T 掉 40 分。

P1 电阻

题面

题目描述

询问要得出一个电阻值为 $\frac ab$ 的电阻。

元件由 $3$ 种方式组成:

  1. 一个电阻
  2. 一个元件与一个电阻串联
  3. 一个元件与一个电阻并联

输入格式

一行两个数, $a$ 和 $b$ 表示询问元件的阻值为 $\frac ab$ 。

输出格式

一行一个数 $ans$ ,表示最少需要的电阻数。

样例

输入 #1

233 666

输出 #1

27

思路

两个电阻 $R1,R2$ 串联,总电阻 $R0=R1+R2$。

两个电阻 $R1,R2$ 并联,总电阻 $R_0=\frac{1}{\frac1{R_1}+\frac1{R_2}}$ ,变形一下即为 $\frac1{R_0}=\frac1{R_1}+\frac1{R_2}$ 。

考虑一组较为简单的样例,$R=\frac 75 \Omega$。

因为 $\frac 75 > 1$,所以一定为两个电阻(元件)串联而成。其中一个电阻值为整数,另一个为小数。我们将其拆分为 $\frac 75 = 1 + \frac 25$ 。(整数部分和小数部分)

其中的 $1$ 为整数,不用再分。$\frac 25$ 不是整数,所以要再分。因为 $\frac 25 < 1$ ,所以是由两个元件并联而成的。我们取倒数(根据公式)后将其拆分为 $\frac 52 = 2+\frac 12$ 。

后者 $\frac 12$ 的倒数为整数 $2$ ,无需再分。前者 $2$ 的倒数为 $\frac 12$ ,由于 $\frac 12 < 0$ ,所以它是并联而成的。我们取倒数后拆分为 $\frac 2 = 2$ 。我们发现,它已经为整数,无法拆分了。

上面这组样例为整数的电阻数一共用了 $5$ 个,所以答案为 $5$ ,下面是电路图:

现在我们推广开来,对于任意的 $\frac ab$ ,都可以用这种方法求得需要用到的电阻个数。

我们还发现,不管 $R$ 大于还是小于 $1$ ,其实拆分都是一样的,因为取倒数后的拆分相同。

所以我们在并联情况时可以 $swap$ 一下。

代码

P2 找零

题面

题目描述

现在小A就要出去购物了

他的手头上有 $n$ 种不同面值的硬币,每种面值的硬币有无数个

为了携带方便,他希望带最少数量的硬币

同时为了防止再收到找零,他希望他可以用这些硬币组合出 $1 \sim x$ 之间的任意值

输入格式

第一行两个数字, $x$ 和 $n$ 。

第二行共 $n$ 个数字,表示 $n$ 种不同硬币的面值

输出格式

一行一个数,表示最少需要的硬币数

如果小A无论怎么取硬币都无法避免被找零的命运,请直接输出 $-1$。

代码

P3 2048

题面

给定一个长度为 $n$ 的数列,在这个数列中选取一个子序列使得这个子序列中的数能合出 $2048$

对于合并操作,可以选择这个序列中的任意两个数进行合并,当然这两个数必须是相同的(即2个 $x$ 合并后成为一个 $2x$)

对于每个序列,只要进行若干次合并操作后,这个序列中至少有一个$2048$(可以有其他数剩余),就称这个序列是合法的

我们可以认为只要选取的数在原数列中的位置不同,这些序列就是不同的

对于给定的数列,小朋友们需要算出有多少子序列是合法的,并把这个数 对 $998244353$ 取模。

思路

粘一段学长的题解

一个子序列或者说子集合法的条件是:只要二的次幂的和 不小于 $2048$ 即可。

可以想象,二进制加法即 $2048$ 合并的过程。

转化为用 $DP$ 统计有多少子集的和不小于 $2048$ ,很简单的一个背包问题。

评论

  1. yzx1798106406

    Orz

    8月前
    2019-3-31 16:09:39

发送评论


				
上一篇
下一篇