A. 神奇天平

Solution

考虑 $m>=nm\; >=\; n$，一次就能达到目的。

现在考虑 的情况，显然需要分组：

• $n\mathrm{\%}(m+1)==0n\; \backslash \%\; (m\; +\; 1)\; ==\; 0$， 可以分成 $m+1m\; +\; 1$堆，每一堆数量相同，在天平上要么前 $mm$ 堆重量相同，要么有一个重量比其他的大，显然可以1次找到重的哪一堆，再递归做这一堆。

• $n\mathrm{\%}(m+1)!=0n\; \backslash \%(m\; +\; 1)\; !=\; 0$，做法类似，只是最后一堆的数量与其他的不同。

于是总的次数是 $\lceil lo{g}_{m+1}n\rceil \backslash lceil\; log\_\{m\; +\; 1\}\; n\; \backslash rceil$, 时间复杂度 $O(lo{g}_{m+1}n)O(log\_\{m\; +\; 1\}\; n)$。

ps：似乎可以用信息论的知识去解释，虽然没学过（）

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49351695&returnHomeType=1&uid=105308122

B. 魔法学院(easy version)/C. 魔法学院(hard version)

Solution

经典并查集问题，我们可以对 $c_{i}c\_i$ 从大到小排序，只要当前点 $ii$ 被当前区间覆盖，设当前区间为 $[l,r][l,\; r]$，只需要让 $ii$ 与 $r+1r\; +\; 1$ 做并查集的链接即可，后面的点如果发现区间里的点已经被覆盖就不用管了，由于排序的原因，这样是最优的。

时间复杂度 $O(n+mlo{g}_{2}m)O(n\; +\; mlog\_2m)$。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49351701&returnHomeType=1&uid=105308122

D. 监狱逃亡

Solution

设第一层走到 $ii$ 就往下，第二层走到 $jj$ 就往下，那么总的和为 $sum1[i]+(sum2[j]-sum2[j-1])+(sum3[n]-sum3[j-1])sum1[i]\; +\; (sum2[j]\; -\; sum2[j\; -\; 1])\; +\; (sum3[n]\; -\; sum3[j\; -\; 1])$，而我们需要$sum1[i]+(sum2[j]-sum2[j-1])+(sum3[n]-sum3[j-1])\ge 0sum1[i]\; +\; (sum2[j]\; -\; sum2[j\; -\; 1])\; +\; (sum3[n]\; -\; sum3[j\; -\; 1])\; \backslash geq\; 0$，将式子变形一下就变成了: $sum2[j]-sum3[j-1]\ge -sum3[n]+sum1[i]-sum2[i-1](i\le j)sum2[j]\; -\; sum3[j\; -\; 1]\; \backslash geq\; -sum3[n]\; +\; sum1[i]\; -\; sum2[i\; -\; 1](i\; \backslash leq\; j)$

离散化后直接用树状数组维护即可，时间复杂度 $O(nlo{g}_{2}n)O(nlog\_2n)$。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49353683&returnHomeType=1&uid=105308122

E. 游戏人生

Solution

一开始看觉得是个dp问题，但实际上是反悔贪心和分类讨论。 首先问题需要找到满足题意的最小初始血量，由于单调性，血量越多越好，显然我们可以二分答案然后检验是否可行。

对于每次攻击，因为只能是造成 $AA$ 或者 $2A2A$的攻击，代价分别是 $a_{i}a\_i$ 和 $B+a_{i}B\; +\; a\_i$。不同时间段的攻击只有$a_{i}a\_i$不同，所以我们可以考虑用一个优先队列存每个 $a_{i}a\_i$。

一开始我们先尽量用狂暴攻击（花费 $B+a_{i}B\; +\; a\_i$），那么我们的血量如果在某个时间点满足条件 $x\le 0x\; \backslash leq\; 0$，就进行后悔操作。怎么反悔呢？我们发现你可以把狂暴攻击变成普通攻击，此时你可以让 $x=x+Bx\; =\; x\; +\; B$，但是怪物的血量会 $res=res+Ares\; =\; res\; +\; A$，或者对于这一次攻击进行防御，此时 $x=x+(a_i-\lfloor \frac{a_i}{2}\rfloor )x\; =\; x\; +\; (a\_i\; -\; \backslash lfloor\; \backslash frac\{a\_i\}\{2\}\; \backslash rfloor)$，怪物血量还是会 $res=res+Ares\; =\; res\; +\; A$。因此怪物在血量上的增加是相同的，完全只需要考虑 $(a_i-\lfloor \frac{a_i}{2}\rfloor )(a\_i\; -\; \backslash lfloor\; \backslash frac\{a\_i\}\{2\}\; \backslash rfloor)$ 和 $BB$ 的大小关系判断采取哪种贪心模式即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49991789

F. 卡牌大师

Soltuion

这个题属实有点难，关键题意也不太清晰，总的来说就是你需要从 $[1,n][1,\; n]$ 里挑选一个最大的集合，使得他们两两的和不会有 $mm$ 的后缀。比如 $m=13m\; =\; 13$，那么 5 + 8 = 13， 30 + 83 = 113, 都是不可取的互斥对。

由于本人太菜了，所以还是看了b站视频+题解半天才看懂怎么做

首先考虑两个数字加起来为 $mm$，那么可以分成两块，分别是 $[0,\lfloor \frac{m}{2}\lfloor ][0,\; \backslash lfloor\; \backslash frac\{m\}\{2\}\; \backslash lfloor\; ]$ 和 $[\lceil \frac{m}{2}\rceil ,m][\backslash lceil\; \backslash frac\{m\}\{2\}\; \backslash rceil,\; m]$ 这两个区间。这两个区间的取值是互斥的，例如 $m=5m\; =\; 5$，那么会分成 $t_1=[1,2]t\_1\; =\; [1,\; 2]$ 和 $t_2=[3,4,5]t\_2\; =\; [3,\; 4,\; 5]$，显然不能同时取 $1+4=51\; +\; 4\; =\; 5$，当然你可以两个集合交换着取，比如取[1,3,5]，但是可以证明跟取$t_{1}t\_1$ 和 $t_{2}t\_2$ 两者中更大的集合答案是一样的。

当然你可能会问，$t_{1}t\_1$ 和 $t_{2}t\_2$ 不是一直都是一样大或者相差1吗？当然不是，因为这里要考虑 $nn$ 的大小，比如在上述的例子里， $n=3n\; =\; 3$，我们就取不到 4 和 5，所以答案只能取 $t_{1}t\_1$。

接着考虑另一种情况， 令 $mm$ 的长度为 $lenlen$, 得到 $p=10^{len}p\; =\; 10^\{len\}$，此时有另一对互斥区间：$[m+1,\frac{p+m}{2}][m\; +\; 1,\; \backslash frac\{p\; +\; m\}\{2\}]$和$[\frac{p+m}{2}+1,p+m][\; \backslash frac\{p\; +\; m\}\{2\}\; +\; 1,\; p\; +\; m]$ 满足题意。简单的讲就是上面的 $m=5m\; =\; 5$的时候，如果 $nn$ 很大，还会出现 [6, 7], [8,9]这两个区间，因为6 + 9 = 15, 7 + 8 = 15,显然互斥，依旧是取更大的区间即可，注意这里也要考虑 $nn$ 的情况，可能8/9取不到。

所以我们只需要找到每一堆互斥的集合，取更大的一直做就行了。

（个人觉得应该讲的听明白的，毕竟我看了一上午）

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50008580&returnHomeType=1&uid=105308122