题解：P6090 [CEOI 2019] 立方填词

AC_love · 2025-03-27 08:00:57 · 题解

首先枚举正方形的边长，然后考虑对于某个边长该怎么做。

首先注意到只有角上的字母会重复使用，因此我们可以直接枚举八个角上的字母，然后两两计算贡献即可。

令字符集大小为 |\sum|，复杂度 O(l|\sum|^8)。

考虑怎么优化这个玩意。

注意到对于一个顶点，它会且仅会与三个顶点共用一条边。如果我们确定了另外三个与它共用一条边的顶点填什么并计算出了贡献，那么这个顶点填什么都无所谓了。

这样就可以减掉一个顶点的枚举，降低一维的复杂度。

那么最多可以减掉几个顶点的枚举呢？

注意到，只需要枚举正方体底部正方形对角线上的两个点和顶部正方形另一条对角线上两个点即可，剩下四个点都与刚才枚举过的某三个点共用一条边。

于是复杂度被降低到了 O(l|\sum|^4)。

略微卡常。