AtCoder Beginner Contest 195 题意+题解【暂无 F】

评价

打完 CF Div.1 后,心态都还没稳过来就打 abc,结果可想而知/kk。

题解

A - Health M Death

询问 (M)(1le Mle 1000))是否是 H((1le Mle 1000))的因子。

B - Many Oranges

有若干物体,每个物体的重量在 ([A,B]) 中((1le A,Ble 1000),单位为),物体总重 (W) 千克(1le Wle 10^3)),求物体数的最小和最大值,或输出「无法满足」(原题中 UNSATISFIABLE)。

易得最大时必然全选最小值,个数 (le leftlfloor dfrac{w}{A} ight floor)。同时,最小时需取最大值,个数 (ge leftlceildfrac{w}{B} ight ceil)。如果这两个条件矛盾则无解。

https://atcoder.jp/contests/abc195/submissions/20876614

C - Comma

书写一个数时,每 (3) 位写一个逗号,请问写下 (1)(N)(1le Nle 10^{15}))需要写多少个逗号。

注意到对于 (10^{3t} le x<10^{3(t+1)}) 来说,需要写 (t) 个逗号。直接分类讨论即可。

当然,也可以用我这种写法,逐个判断需要写几个第 (i) 个逗号。具体可以看代码。

https://atcoder.jp/contests/abc195/submissions/20879841

D - Shipping Center

(N) 个行李,第 (i) 个体积为 (W_i),价值为 (V_i)

(M) 个箱子,第 (i) 个容积为 (X_i),一个箱子里最多只能装一件行李。

(Q) 个询问,第 (i) 此询问要求不能使用区间 ([L_i,R_i]) 的箱子,求最大价值。

(1le N,M,Qle 50)(qle W_i,V_i,X_ile 10^6)

显然是个乱搞题,我们可以有一个贪心策略:

  • 每一次选择价值最大的行李,往尽可能小的箱子里面塞。

首先,一定要往小箱子里塞,这点贪心没有问题。

而对于价值最大的行李,显而易见比价值更小,而体积更大的行李更优。

同时,如果选择优先放价值小,体积小的行李的话,与这种贪心策略等价,所以就这么干就行了。

那么,为什么这么 nt 的题赛时没有 ac 呢?因为 nt 的 5ab 将原数组 (X) 排序了。

前车之鉴:https://atcoder.jp/contests/abc195/submissions/20891745

赛后 AC:https://atcoder.jp/contests/abc195/submissions/20908800

E - Lucky 7 Battle

两个人玩游戏,规定第 (i)(X_i) 先手。每个人可以在第 (i) 轮时使 (Nleftarrow 10N)(Nleftarrow 10N+S_i)

A 希望最后的数不是 (7) 的倍数,而 B 希望是。如果每个人都聪明绝顶,求出胜利者。((1le |X|le 2 imes 10^5)

定义 (f_{i,j}) 为前 (i) 位余数为 (j) 时 A 能否胜利。则

[f_{i,j}=egin{cases} f_{i-1,j-S_imod{7}}lor f_{i-1,j}& ext{when A moves in round }i\ f_{i-1,j-S_imod{7}}land f_{i-1,j}& ext{when B moves in round }i end{cases} ]

初始条件 (f_{0,0}= ext{true}),最后即求 (f_{|X|,0})

https://atcoder.jp/contests/abc195/submissions/20900472

F - Coprime Present

给定 (A,B),求 ([A,B]cap mathbb{Z}) 的子集数满足 ([|S|le 1]lor[forall x,yin S,x eq yRightarrow gcd(x,y)=1])。((1le Ale Ble 10^{18})(B-Ale 72))。

一个奇怪的 dp。

后记

掉了 4 分。


非常感谢您读完此文章。

如果您喜欢这篇文章,请点一个赞支持一下博主。

如果您对此文有意见,欢迎在评论区留下你的看法,5ab 会尽力达到。

如果您真的不喜欢这篇文章,也请不要喷,5ab 欢迎私信反馈意见。

原文地址:https://www.cnblogs.com/5ab-juruo/p/abc195-statement_solution.html