Codeforces Round #643 Div2

A.数学

给定起始数n，给定k次操作

每次操作选取n所有位上最小和最大的两个digit相乘，再加回给n

如375，最小3，最大7，加数为21

求k次后的值，k很大，1e12

思路：

遇0则停

估计很多人都想到了，那么为什么这样就很快嘞？

我们考虑两个相乘的数，他们最大不超过81，最小大于等于0

也就是说一定不大于一百

那么不管百位是什么，每次后面十位个位的增加最多会让百位+1，或者不加，所以百位很快就能出现0了

一旦出现0，死活就是0了

代码：https://codeforces.com/contest/1355/submission/80318403

B.贪心

给定n个人，每个人给一个标号，他只能归属于一个组，此组中的人数必须不小于他的标号

可以有人不从属任意组，求最多分组数

思路：

桶存即可，自低位到高位，注意两点：

1）像2 3 3 这样的，2单独不行，它剩下来了，就可以和3组合,所以要记录每步剩余人数

2)提前终止条件，枚举到了一定值，如果此值大于没有分配的人数，可以提前终止

代码:https://codeforces.com/contest/1355/submission/80341563

C.数学

给定4个端点

他们相邻的两两组成一个区间，该区间表示一条边的取值范围

问有多少种可能使形成的三条边，成为三角形

思路：

这题一定要细心，耐心

四个端值记为abcd

三条边分别记为ABC

根据三角形的定义，两条边之和一定大于第三条边，而本题显然C比AB要大，所以我们要找什么时候能够满足A与B的和大于C

接下来就是讨论情况了

C从c枚举到d

我们先要大于等于的值reach=i+1

接下来考虑第一条边（可选范围较小的）中每个点对应的情况

它从多少开始存在可行解嘞？reach-c与a之间取大者

那它对应的起始值（解数）是多少嘞，取bc区段长与sta+c-reach+1的小者

接下来，就是等差数列的求解，en为结束位置，它最高是到b和reach-b两者的小者

这里别忘记它有个限制因素，一定要比sta大

再计算一下等差数列

如果到b终止，说明直到了b都是严格递增序列，那么直接进入下一步

如果没到b就终止了，说明前面已经到了最高值，后面终止处到b之间均是最高值，再把这部分加上去即可

代码：https://codeforces.com/contest/1355/submission/80371297

D.数学，贪心

给定n，s

你现在要将s划分成为n个数，使得他们的和为s，并且让你选定k

现在问你是否能从这n个数中你任选多少个，让他们的和不为s-k或者k

否输出no，能输出yes，并且提供划分方案和k

思路：先看不能的情况，即n*2>s一定不行，这个自己比划比划

接下来，只要保证n-1个数取1，剩下一个数取s-n+1即可，k为n

WHY？

解释一下，这个方法其实是把n到s-n这段直接隔离了出来，如何加都不可能出现此区段的任何数

代码:https://codeforces.com/contest/1355/submission/80364495