题目描述给定101010块长度为555的010101板每块板描述了一条长度为555的缝隙序列其中0表示深缝1表示浅缝。将这些板中的555块作为水平板其余555块作为垂直板并排布成一个5×55 \times 55×5的格子。水平板放在555个行位置垂直板放在555个列位置。要求每个交叉点处的两个缝隙深度互补若水平板在该列的值为000则垂直板在该行的值必须为111反之亦然。求在所有可能的板划分、排列和翻转板可以左右翻转即010101串反转下本质不同的配置数量。旋转和镜像视为同一种配置。输入格式输入包含多组测试数据每组数据占一行包含101010个长度为555的010101字符串相邻字符串之间用空格分隔。每个010101串表示一块板的缝隙描述。输入以单独一行END结束。输出格式对于每组测试数据输出一行一个整数表示本质不同的配置数量。样例输入10000 01000 00100 11000 01100 11111 01110 11100 10110 11110 10101 01000 00000 11001 01100 11101 01110 11100 10110 11010 END输出40 6题目分析本题的核心是在101010块板中选出555块作为水平板其余555块作为垂直板然后分别对水平板和垂直板进行排列并允许每块板选择是否左右翻转使得所有交叉点满足互补条件。最后需要统计在旋转和镜像意义下互不相同的配置数。直接枚举所有可能的划分、排列和翻转会得到天文数字但101010块板的数量适中可以通过剪枝回溯和归一化去重解决。关键难点在于枚举方式需要一种高效的搜索顺序能够尽早发现不合法分支并剪枝。去重处理旋转和镜像会使同一配置产生多个等价表示需要归一化或利用对称性破缺来保证唯一性。板的翻转对称板左右翻转后相同的翻转不会产生新板需要避免重复计数。解题思路枚举策略交替回溯由于555个水平行和555个垂直列相互制约我们采用交替放置的方式依次放置行000列000行111列111…行444列444。每放置一个行或列时立即检查它与已放置部分是否冲突若冲突则回溯。这种顺序能够尽早剪枝大大减少搜索空间。板翻转控制对于每一块板我们预先计算其原始值original[i]\textit{original}[i]original[i]和左右翻转值reversed[i]\textit{reversed}[i]reversed[i]。若两者相同则该板为对称板翻转不会产生新板因此搜索时只尝试原始方向若不同则尝试原始和翻转两个方向。归一化去重当101010个行和列全部放置完毕时我们得到一个完整的5×55 \times 55×5水平矩阵每个H[r]H[r]H[r]是第rrr行的555位值。将其编码为一个252525位整数然后应用888个二面体群变换444个旋转 444个镜像取字典序最小的252525位字符串作为该配置的规范表示插入集合all\texttt{all}all。这保证了旋转等价被消除。镜像重复处理由于我们在枚举中没有固定水平/垂直的角色即任意555块板都可以作为水平板水平镜像左右翻转整个格子会将一个配置变换为另一个配置而这两个配置在归一化后可能得到不同的字符串因为镜像交换了水平板和垂直板的角色但它们在物理上是同一种配置。因此每个本质配置会被计数两次最终答案应为∣all∣2\displaystyle \frac{|\texttt{all}|}{2}2∣all∣​。正确性说明完备性枚举覆盖了所有可能的水平板集合、排列和翻转垂直板由剩余板匹配因此所有合法配置都会被生成。无漏解交替回溯保证了每个合法布局至少被访问一次。无重解通过归一化和最终除以222消除了旋转和镜像引起的重复。复杂度分析搜索树节点数最坏情况约为(105)×5!×25≈106\binom{10}{5} \times 5! \times 2^5 \approx 10^6(510​)×5!×25≈106但剪枝大幅减少了实际访问量。归一化每次对252525位整数做888次变换开销极小。总时间复杂度O(实际访问节点数×8)O(\text{实际访问节点数} \times 8)O(实际访问节点数×8)在101010组测试数据下运行时间远小于111秒。空间复杂度O(去重集合大小)O(\text{去重集合大小})O(去重集合大小)最多为本质配置数不超过10410^4104。代码实现// Lattice Practices// UVa ID: 687// Verdict: Accepted// Submission Date: 2026-07-05// UVa Run Time: 0.230s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intoriginal[10],reversed[10],H[5],V[5];boolsymmetry[10],used[10];intgetReverse(intx){inty0;for(inti0;i5;i)if(x(1i))y|(1(4-i));returny;}inttoMask(conststrings){intx0;for(inti0;i5;i)if(s[i]1)x|(1i);returnx;}boolcheckRow(intr){for(intc4;c0;c--){if(V[c]-1)continue;inthb(H[r]c)1;intvb(V[c]r)1;if(hbvb!1)returnfalse;}returntrue;}boolcheckCln(intc){for(intr4;r0;r--){if(H[r]-1)continue;inthb(H[r]c)1;intvb(V[c]r)1;if(hbvb!1)returnfalse;}returntrue;}pairint,inttransform(intop,intr,intc){switch(op){case0:return{r,c};case1:return{c,4-r};case2:return{4-r,4-c};case3:return{4-c,r};case4:return{r,4-c};case5:return{4-r,c};case6:return{c,r};case7:return{4-c,4-r};}return{r,c};}stringtoString(intbits){string s;for(intr0;r5;r)for(intc0;c5;c)s(bits(1(r*5c)))?1:0;returns;}setstringall;voidnormalize(){intbits0;for(inti0;i5;i)bits|H[i](5*i);string besttoString(bits);for(intop1;op8;op){intnb0;for(intr0;r5;r)for(intc0;c5;c)if(bits(1(r*5c))){autoptransform(op,r,c);nb|(1(p.first*5p.second));}string stoString(nb);if(sbest)bests;}all.insert(best);}voiddfs(intstep){if(step10){normalize();return;}if(step%20){intrstep/2;if(H[r]!-1){dfs(step1);return;}for(intid0;id10;id){if(used[id])continue;used[id]true;H[r]original[id];if(checkRow(r))dfs(step1);H[r]-1;used[id]false;if(!symmetry[id]){used[id]true;H[r]reversed[id];if(checkRow(r))dfs(step1);H[r]-1;used[id]false;}}}else{intcstep/2;if(V[c]!-1){dfs(step1);return;}for(intid0;id10;id){if(used[id])continue;used[id]true;V[c]original[id];if(checkCln(c))dfs(step1);V[c]-1;used[id]false;if(!symmetry[id]){used[id]true;V[c]reversed[id];if(checkCln(c))dfs(step1);V[c]-1;used[id]false;}}}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string token;while(cintoken){if(tokenEND)break;vectorintboards(10);boards[0]toMask(token);for(inti1;i10;i){cintoken;boards[i]toMask(token);}for(inti0;i10;i){original[i]boards[i];reversed[i]getReverse(original[i]);symmetry[i](original[i]reversed[i]);}all.clear();memset(used,0,sizeof(used));for(inti0;i5;i)H[i]V[i]-1;dfs(0);coutall.size()/2\n;}return0;}总结本题的核心技巧是交替回溯 二面体群归一化 镜像除以二。交替回溯利用行与列的互补约束进行强剪枝避免指数级枚举。归一化通过888个变换取最小字符串简洁地消除了旋转重复。由于枚举中没有固定水平/垂直角色镜像会导致双重计数输出时除以222即得正确结果。这种策略在面对小规模组合计数如5×55 \times 55×5格子且要求去重时非常有效也适用于类似“棋盘覆盖”、“拼图计数”等问题。最终代码简洁高效通过了在线评测的所有测试数据。