P8948 [YsOI2022] NOIp 和省选 题解

题目传送门

这道题是一个构造题,只要是一个构造题就不用管样例的输入输出,样例的输入输出仅用于理解题意对于一般的构造题来说,并不需要那么多花里胡哨的方法。

题目中说明四舍五入保留到整数,但是为什么题目说什么你就做什么呢?当然可以不用四舍五入,而且代码也非常的简洁,但是完成代码前的推导是需要一点时间的。

题目中说明 $A$ 的最大值为 $400$,$B$ 的最大值为 $600$,但不能使用最大值来完成题目。通俗的讲,如果除数是 $600$ ,那么商可能是一个无限循环小数,这并不有利于我们进行操作。干脆 $B$ 直接取 $500$ 好了,又方便。$A$ 可以等于 $400$。理论上来说 $A$ 为 $200$ ,$B$ 为 $400$ 等。也是可行的。如果他们被当作除数的话有利于我们进行计算。在这里我们取 $A = 400,B=500$ 。他们足够大,能覆盖到所有 $[10,1990]$ 的数。

确定完 $A,B$ 的值后,我们开始考虑求 $a_i,b_i$ 。已知 $c_i = 1000(\frac{a_i}{A}+\frac{b_i}{B})$ ,故 $c_i = 1000\cdot \frac{a_i}{A}+1000\cdot\frac{b_i}{B}$ ,我们发现 当 $(1000\cdot\frac{b_i}{B})$ 是奇数时,$b_i$ 不可能为整数,只可能是以 $.5$ 为结尾的小数,你可能会想直接四舍五入,但是那样子太麻烦了,我们可以直接从 $1000\cdot \frac{a_i}{A}$ 中找一个 $0.5$ ,使二者抵消。如 $a_i=2$ 时,$1000\cdot \frac{a_i}{A}=5$ ,此时可以轻易的推出 $b_i = 495$。若 $(1000\cdot\frac{b_i}{b})$ 不是奇数的时候,这时就可以随便拿一个你喜欢的奇数来进行运算,反正最终的答案一定都能满足。但是在这两种情况下, $a_i$ 的值都不应该大于 $4$,若大于则可能导致取不到最小值。

在实现程序的时候可以先实现 $c_i < 1000$ 的情况,接着推广到 $c_i \ge 1000$ 的情况,请读者自行思考如何实现程序。

综上所述,若 $(1000\cdot\frac{b_i}{B})$ 为奇数,则 $(1000\cdot\frac{a_i}{A})$ 是以 $.5$ 结尾的小数。若 $(1000\cdot\frac{b_i}{B})$ 是偶数,则 $a_i$ 是一个奇数。

这意味着在实现程序的时候对于每一种情况都需要找到一个固定的 $a’$ 来求解 $b_i$ 。$a_i \le 4(c_i < 1000)$

这道题目的解法说明了什么?面对构造题我们不能掉进出题人的圈套。

AC代码

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇