武汉大学新生寒假集训测试---Day3题解

因为这次有两道题根本没看+没写,而且因为状态不好代码很丑,所以这次太丑的题就不放代码了,只说思路qwq

A – Personalized Cup

把一个字符串变成一个矩形,要求是行数尽可能少,一行不能超过20个字符
如果有空的地方可以用*填进去,但是不可以出现相邻行的星号数目之差>1的情况。
比如可以
asdf
asd*
但是不可以
asdf
as**
那么行数可以确定,就是length/20向上取整。
以42举例,行数是3,我们要尽可能让字符平均分配,43 % 3=1,所以一定会有一行比其它行多一个,那另外两行就多填一个*
于是可以第一行填43/3+1个,第二行43/3个+*,第三行和第二行一样
再例如98,要填五行,98%5=3,所以一定会有三行比其它两行多一个字符,随便找两行加个*

B – Playing Piano

(看到题目浑身难受,为啥不是playing the piano
贪心一定可以做,但是想策略很累,看了看数据范围不大,就愉快暴搜了。
当然,如果枚举每个位置的指法是什么,然后再判断是否合法,要算5^n次,可怕的指数级别复杂度……
所以要用到记忆化搜索。
利用一个数组tag[i][j],记录第j个指法是i的情况有没有出现过。
首先枚举第一个键的指法。

搜索过程:
如果当前音的当前指法出现过,说明我们已经尝试过之后的所有方法,都不能达到条件,所以就不继续搜了,直接回溯剪枝;
如果下一个音比当前音高,就枚举每一个比当前指法大的指法,试图按下一个音,继续dfs;
如果下一个音比当前音低,就枚举每一个比当前指法低的指法,试图按下一个音,继续dfs;
如果一样高,就枚举1~5的所有和当前指法不同的指法,试图按下一个音,继续dfs;
回溯。

C – A Prank

直接枚举区间左端点i和右端点j,O(n^2)
如果num[j]-num[i]+1==j-i+1,则中间可以删去,更新答案
细节:
1 2 3 4 5这种序列,可以删去4个而非3个
998 999 1000 这种可以删去2个而非1个
原因是所有的数字都是1~1000的
所以可以把num[0]赋值为0,num[n+1]赋值为1001,再按照正常操作就可以了
还有一个细节, n=1的时候不可以删,所以应该输出0

D – Fun with Integers

没看,明天一定补(咕咕咕

E – Banh-mi

每次一定是贪心地选取1,再选0。用前缀和维护一个区间内0和1的数量。
那么我们可以分开想,先算所有的1拿完之后得到的值,这个时候对所有0的贡献是固定的。
我们拿到的1分别是,1,2,4,8……
所以假设有n个1,等比数列求和:2^n-1
剩下m个0,已经变成了m个2^n-1。没关系,算完了之后再乘上2^n-1是一样的。这m个0单独看,数列是这样的:
0,1,3,7……
求和之后*(2^n-1),则为拿0所得到的总和。
把他们加在一起,最后得到一个公式:(2^x-1)*2^y。用快速幂可以快速求2的次方。
注意一下取模之后可能为负。

F – Barcelonian Distance

没看

G – Kitchen Utensils

开始怀疑自己的英语水平
题意我猜的,看代码罢

H – Math

不要被题意骗了……
先说结论:能够得到的最小值是所有质因数去重之后相乘得到的值。
关于操作次数:
如果需要乘,最多只需要乘一次,因为分好几次乘的效果是一样的。
什么时候需要乘:当所有质因数的个数不同,或所有质因数的个数相同但不是2^x
需要开方几次:最大的质因数个数取log2,向上取整
没了

代码里全是qwqQAQ 就不放了qwqqq

点赞

发表评论

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