用户工具

站点工具


2020-2021:teams:farmer_john:jjleo:codeforces_round_643_div._2_virtual_participation

这是本文档旧的修订版!


目录

A

  • 题意:递推公式$a_{n+1} = a_{n} + minDigit(a_{n}) \cdot maxDigit(a_{n})$,给定$a_1$,求$a_K$。$(1 \le a_{1} \le 10^{18},1 \le K \le 10^{16})$
  • 题解:签到题不会,正好物理实验课,直接溜了。其实最多迭代$54$次就会出现$0$,然后就一直是那个数,所以模拟即可。

B

  • 题意:有$n$个人,组队探险,可以有人不去探险,第$i$个人如果去探险所在队伍人数必须$\ge e_i$,问最多能组多少队。
  • 题解:根据$e_i$排序,然后从小到大,贪心地能一个个人入队,什么时候队伍合法直接把队里的人分为一队然后继续。直观看上去是正确的,因为每个队伍人数越少肯定越优。(不会证,不证了

C

  • 题意:$A \le x \le B \le y \le C \le z \le d$,问有多少个三元组$(x,y,z)$可以组成三角形。$(1 \leq A \leq B \leq C \leq D \leq 5 \cdot 10^5)$
  • 题解:枚举$x$,画图个数轴就可以看出选不同的$y$能选对应$z$的个数,然后求和一下即可。

D

  • 题意:如果存在一种方案,将正数$S$分为$N$份,并指定一个正整数$K$使得不能用这$N$个数字组成$K$,那么获胜,问能否获胜。
  • 题解:如果$2N \le S$一定可以,方案有很多。反过来则不可以,然而题解给的证明并没有看懂。

E

  • 题意:$n$个数,让一个数$+1$需要$A$元,$-1$需要$B$元,让一个数$+1$另一个数$-1$需要$C$元,问让所有数相等最小代价是多少。
  • 题解:如果$A+B>C$显然可以将尽可能多的$A+B$合并为$C$,那么只需要知道最终的数是多少即可。题解证明这是个单谷函数,所以可以三分。题解证明并没有看懂,写的时候也不能直观地猜想出是三分,还是太菜了。。

F

  • 题意:摸了,有时间来补
  • 题解:也摸了
2020-2021/teams/farmer_john/jjleo/codeforces_round_643_div._2_virtual_participation.1590150038.txt.gz · 最后更改: 2020/05/22 20:20 由 jjleo