#1 - 2021-1-21 00:07
Nanarikom (给分主观的低端萌豚而已)
按照惯例寒假我校有面向大一新生的冬季集训,然后瞎编了点题目凑了场比赛。
HEU Winter Camp 2021 Contest #1
HEU Winter Camp 2021 Contest #1 Upsolving
13 合 1 版题面及题解
预想中压轴题是可以防住某 NOIag 爷的,结果结束之后人跟我说:告辞
然而他居然有 Easy-Mid 的 J 题没过,于是成功被题数防 AK 了。而且这题居然大家都没过,有理由怀疑是 NOIag 爷把榜全带歪了。
HEU Winter Camp 2021 Contest #1
HEU Winter Camp 2021 Contest #1 Upsolving
13 合 1 版题面及题解
预想中压轴题是可以防住某 NOIag 爷的,结果结束之后人跟我说:
这不是裸题吗???
然而他居然有 Easy-Mid 的 J 题没过,于是成功被题数防 AK 了。而且这题居然大家都没过,有理由怀疑是 NOIag 爷把榜全带歪了。
(为啥不直接给定a_1,a_2是自然数算了,还得折腾一下)
设a_1,a_2中不相同负数的个数为N_0,先进行有限次生成操作将当前两个数变成自然数(因为只有有限次操作所以中间的过程略),设这两个数是A,B(不妨设A>=B,反正不影响最后的结果),
count=N_0
if B==0:
if A==0:
return count+1
else:
return count+2
do
C=A mod B
count+=[A/B](商取整)
A=B
B=C
while C !=0
return count+1
当A,B是正整数时,可以写成A=N*B+C的形式,当C=0时,显然会有A/B+1个数出现(最后的+1是最后出现的0)
当C \neq 0时,
会有N*B+C(即A),(N-1)*B+C,(N-2)*B+C,...共N个数出现(这些数都大于B,C所以不会和后面有重复),同时B也会反复出现,直到最后剩下B和C,然后把B,C当做新的A,B就好了.
复杂度大约是对数级别的?