2016.11.12【初中部 NOIP普及组 】模拟赛

时间:2022-11-04 20:42:54

T1:

小数加法高精度,注意进位


T2:很明显只需要枚举侧面的点数,其余面不管怎么摆和都为7


T3:比较有意思。

题目描述:

给定一01串,让你分出最多段使得每段的0和1的比例相等。


很显然的一个贪心思路,能分就分,因为当到第i位时,当前拥有的0与1的比例与所有0和1的比例相等,那么就分段,因为分了之后并不会对接下来的01分段造成影响。

想到这一点之后,还需注意,因为串的长度为10^9,则如果逐个枚举是会超时的,所以只能枚举n(<=10^5)

假设枚举到第i段,0的个数为k0,1的个数为k1,而0的总个数为tot0,1的总个数为tot1,当第i段加的是0的个数时,我们需要判断1,当加1时,我们需要判断0。

——因为每次分不可能一定可以分完整,所以当加0的个数时,当前肯定是以0结尾,所以我们判断——tot1/tot0(需被整除)*tot0就是0被分的个数w,注意,如果前i-1段0的个数就大于w,我们还不能分,直到前i-1段0的个数小于等于w,且加上第i段0的个数后就大于w才分。

为什么?

很简单,如果对于前i-1段的0就大于w,则肯定会有余下的0,那么如果有余下的0就不符合题意了。


T4:

很明显因为求个正方形,我们只需枚举其中的两点就可以推知其他点了,那么这样子的话,时间就很快了。