Atcoder ARC-062

ARC062(2020.7.13)

A

可以考虑直接同时扩大这次的两个票数,那么使得两数均大于之前位置的票数就是最优的,扩大的话直接除一下上取整即可。

B

贪心即可。

C

可以发现这个东西如果直接计数非常不好记,于是首先的一个想法是记正方体展开图的数量,实际上这个更为麻烦,需要我们换一种思路。注意到 (n le 400) 应该是个 (O(n ^ 3)) 的样子,于此同时可以发现一个正方体有八个角,如果我们暴力枚举颜色肯定是可以做的,但这样复杂度爆炸,换一个角度想,我们可以枚举对顶的两面,那么这八个角的颜色都将确定,那么那么接下来剩余的四个面实际上需要的砖是固定的,我们可以考虑使用 ( m Hash) 再用 ( m unordered map) 来存储每种颜色即可。注意这样是会记重的,首先我们在枚举对顶面的时候要保证上顶面 (i),下顶面 (j)(i < j),其次当上下底面同时旋转答案相同,因此我们固定上顶面不动,让下底面旋转,这部分的重复就可以解决了。还有一个问题,因为转是不能重复选的,因此在没选一种后就要将其旋转后能选的砖删去,至于问什么能固定优先选择转的顺序,因为如果这一面的砖旋转能影响到别的砖,那么说明这两个面能选择的砖都应该是一样的,因此顺序就不会影响答案了。实际上复杂度是 (O(n ^ 2)) 的,然而跑得慢的一批。

D

( m Polya?) 咕咕咕...

GO!
原文地址:https://www.cnblogs.com/Go7338395/p/13675946.html