线上集训第一期开始啦~
说来,好久没打过一场完整的比赛了。这场学长说是手速场,大概也没错。
睡前整理一下解题报告,还有三题没写(回来后其实根本没看)…
Rank 90; Solved out 8 of 12.
Problem A.
读题还是要仔细一点,最好把数据玩清楚了再开始写。大致思路简单,就是统计+排序,最后的答案显然是个 C(a, b) 这样的东西,令n是最大set中石头最少的颜色的石头数量,a就是所有颜色中有n个石头的颜色数,b就是最大set中取到的有n个石头的颜色数。
WA点在于C没写好 – C(a, b),当 a-b < b时可以 b = a-b,这样a在29内都不会超。
Problem B.
这个显然就是平均分结果最优,大概可以不等式证一下?
式子虽然挺长但其实很简单,大概就是a^2+a*b+b^2这样的感觉(当然不是这个样子的)。
Problem C.
题目虽然说从1开始,不过为了写代码方便我还是从0开始,偶负奇正。
首先-1的条件是很显然的,现有字母数量加上问号数量无法满足k就丢出去了。
然后所有的负号位置显然应该尽量放a,所有正号位置显然应该尽量放z。不过,由于有个k的限制,还是要先解决掉这个限制问题的。
分别计算使用MINUS位置和PLUS位置的损失,取较小者(当然,如果没有空余位置就直接取另一边了)来放置。比方说,负已经有了abc,而正只用了z,那就优先放y。
TLE了一次,原因未知,明早试试。
Problem D.
这题是个解释器,乍一看有些吓人,不过其实就是个模拟题,挺简单的。
WA了一次,错在少打个0,不应该。
Problem E.
最后半小时没来得及调出来,比较可惜。
用上一题的神秘语言写代码,计算SUM(1, N)。
我的思路是这样的:
读取N到内存->复制内存到A和B->把B的数字转移到C->读取A并减一->若非0则回到开头;为0则输出
现在仔细想想,直接这样就好了:
读取N到内存->复制内存到A和C->读取A并减一->判断是否回到开头
噫,如果早想到可能就不会死了。
果然是太紧张心态崩了吗)
不过可视化编程(不)其实超有趣的!有点画电路的感觉。
Problem F.
汉诺塔题,一开始妄图找规律,没找着,也浪费了不少时间。
后来就冷静推,一发过了。
数据其实给了提示,把N个盘子从A柱挪到B柱要2^N-1的步数。
那我们就从最大的一个盘子往前倒推,需要把它上面的盘子都给挪到”既非最大盘子的目标柱子也非原来所在柱子”的那个柱子上。
如果目标柱子恰好是所在柱子就不用移动了,continue,开心。
然后就变成了一道愉快的模拟题……
Problem G.
这题没做,赋BFS序,树状数组。
Problem H.
简单模拟题。要注意的是这其实和谜题没什么关系,所求序列里是不能有87这种东西的。
Problem I.
没做。
Problem J.
两个map A下去就过了。
Problem K.
好像是最短路,但是没写。
Problem L.
A+B级别的题目。
要注意A不要取超过X了。
晚安
明日も頑張るぞい!