2021年寒假热身赛1

2021年寒假热身赛1

A. 新年计划

Bob在一年365天之内,每一天只有玩游戏或不玩游戏,建立一个下标从1到365的数组,初始化均为0,如果Bob这一天有游戏玩,则将相应下标的值改为1。数据全部读取完成之后,统计整个数组中有多少个1,就说明Bob玩了多少天的游戏。

参考代码(C++)

B. 配制溶液

只需要判断发生化学反应的这几对的出现次数即可,可以利用下标为1至8的数组记录哪些数字被使用了,然后二者之和是否符合相应值即可。

参考代码(C++)

C. Backspace

准备一个字符数组,最后将会把这个数组作为结果直接输出。从输入数据中逐字符读取,若是普通字符就写到字符数组里,若是'<'符号就将字符数组的读写位置退一个,直到输入数据读取完毕。

参考代码(C++)

D. 无法整除

按题意直接逐元素取余,时间复杂度在 \( O(N^2) \),由于N在\(10^5\)数量级,这样大的运算量不能拿到全部的分数。

类似于质数筛,将\( \{ A \} \)从小到大排序, \( \{ A \} \) 中最大的元素为M,开一个长为M的数组bucket[],初始值为0。对于每个\( A_i\),将\(2 A_i,3 A_i,\cdots, k A_i \leq M\)置为1,说明数组下标为1的就表示相应数字会被\(A_i\)整除。

最后重新访问数组A,统计bucket[\(A_i\)]==0的就是均不会被其它任何元素整除的。时间复杂度为\( O(M \log(M) + N \log(N)) \)

同时,要对同一元素出现多次的情况稍作处理:可以用一个set结构,或visited[]数组,若\(A_i\)曾出现过,则直接置bucket[\(A_i\)]=1.

参考代码(C++)

E. 数位相加

输出最多100位,那么最多就是100个9,也就是各位数之和p最大为900,各位数平方之和q最大是8100,如果输入的p与q超过了其最大值,直接就No solution。

有解的情况,利用一个dp[p][q]保存数字各位之和为p,各位平方之和为q的数字的最小位数,并用sel[p][q]记录是哪个数字得到了最小位数,以便于回溯求其最小解。

dp[][]与sel[][]的计算只需要做1次。读取N组数据p,q ,每组数据根据dp[p][q]与sel[p][q]得到数字序列,将待输出序列先从小到大排序再逐位输出即可。

参考代码(C++)

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注