题目分析本题涉及一种名为四叉树的图像编码格式。四叉树的基本思想是将图像递归地划分为四个象限直到每个象限内的像素颜色一致为止。每个节点可以是以下三种类型p\texttt{p}pparent表示内部节点需要进一步划分四个子象限。f\texttt{f}ffull表示该区域全部为黑色像素。e\texttt{e}eempty表示该区域全部为白色像素。题目中处理的图像尺寸为32×3232 \times 3232×32像素总计102410241024个像素。艺术家要执行的操作是将两张图像进行叠加在结果图像中若某个像素在至少一张原图像中为黑色则该像素为黑色否则为白色。输入包含多个测试用例每个测试用例给出两个字符串分别代表两张图像的四叉树先序遍历序列。树的深度不超过555因为25322^5 322532。输出需要计算叠加后图像中黑色像素的数量。样例分析以第一个样例为例输入ppeeefpffeefe和pepeefe输出640640640个黑色像素解题思路核心问题转化直接对四叉树进行“叠加”操作比较棘手因为两棵树的结构可能不同深度、分支情况各异。一个更简单的方法是将四叉树的表示还原为32×3232 \times 3232×32的像素网格。在两幅网格上分别进行“着色”。最后统计黑色像素的数量。由于图像尺寸固定为32×3232 \times 3232×32我们可以使用一个二维数组image[32][32]来存储每个像素的颜色状态。四叉树的解析与着色四叉树的先序遍历序列中每个节点按以下规则处理遇到p\texttt{p}p该区域需要继续划分。按照固定的象限顺序题目图示中明确递归处理四个子区域。遇到e\texttt{e}e该区域全部为白色将其标记为白色。遇到f\texttt{f}f该区域全部为黑色将其标记为黑色。象限划分顺序从题目图示可以看出四叉树的子节点顺序先序遍历为右上象限- 实际上根据代码实现第一个递归(x, y width/2)—— 右上第二个递归(x, y)—— 左上第三个递归(x width/2, y)—— 左下第四个递归(x width/2, y width/2)—— 右下叠加逻辑的实现在代码中叠加操作是通过顺序执行两次解析隐式完成的首先解析第一棵树将对应区域标记为黑色b\texttt{b}b或白色w\texttt{w}w。然后解析第二棵树。在解析过程中如果遇到白色区域e\texttt{e}e只将尚未被标记为黑色的像素设为白色。如果遇到黑色区域f\texttt{f}f将对应区域强制覆盖为黑色无论之前是什么颜色。这样最终image数组中b\texttt{b}b表示该像素在至少一张图像中为黑色w\texttt{w}w表示两张图像中均为白色0表示尚未被任何树处理过的区域实际上在解析完两棵树后不会存在。为什么这样做是正确的叠加的定义是结果图像中某像素为黑色⟺ \iff⟺它在图像A中为黑色或在图像B中为黑色。第一棵树解析后黑色像素已被正确标记。第二棵树解析时遇到黑色区域直接将其涂黑这符合“或”操作。白色区域不会覆盖已有的黑色这保证了黑色像素不会被错误地擦除。因此最终统计b\texttt{b}b的数量即可得到答案。复杂度分析每个测试用例需要遍历32×32102432 \times 32 102432×321024个像素。四叉树的节点数最多为1442434445≈13651 4 4^2 4^3 4^4 4^5 \approx 13651442434445≈1365个每个节点处理的区域大小与深度相关。总体时间复杂度为O(像素数节点数)O(\text{像素数} \text{节点数})O(像素数节点数)对于本题规模完全可行。代码实现// Quadtrees// UVa ID: 297// Verdict: Accepted// Submission Date: 2016-05-10// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 存储 32x32 图像的像素颜色// 0 表示未处理b 表示黑色w 表示白色charimage[32][32];// 递归解析四叉树的先序遍历序列// tree: 先序遍历字符串// index: 当前处理到的位置引用传递便于递归推进// x, y: 当前区域左上角坐标// width: 当前区域的边长voidparse(stringtree,intindex,intx,inty,intwidth){if(indextree.length()tree[index]p){// 内部节点递归处理四个子象限// 顺序右上、左上、左下、右下parse(tree,index,x,ywidth/2,width/2);parse(tree,index,x,y,width/2);parse(tree,index,xwidth/2,y,width/2);parse(tree,index,xwidth/2,ywidth/2,width/2);}elseif(indextree.length()tree[index]e){// 空节点整个区域为白色// 只有当像素尚未被标记为黑色时才标记为白色for(intix;ixwidth;i)for(intjy;jywidth;j)if(image[i][j]0||image[i][j]w)image[i][j]w;}elseif(indextree.length()tree[index]f){// 满节点整个区域为黑色直接覆盖for(intix;ixwidth;i)for(intjy;jywidth;j)image[i][j]b;}}// 统计图像中黑色像素的数量intcount(){intcounter0;for(inti0;i32;i)for(intj0;j32;j)if(image[i][j]b)counter;returncounter;}intmain(intargc,char*argv[]){cin.tie(0);cin.sync_with_stdio(false);intn;cinn;string first,second;while(n--){// 初始化图像数组所有像素标记为未处理 0for(inti0;i32;i)for(intj0;j32;j)image[i][j]0;cinfirstsecond;// 解析第一棵树标记黑色和白色区域intindex0;parse(first,index,0,0,32);// 解析第二棵树叠加黑色区域index0;parse(second,index,0,0,32);coutThere are count() black pixels.\n;}return0;}总结本题的核心技巧是将树形结构的图像表示展开为二维网格利用网格的固定尺寸简化叠加操作。这种方法避免了直接对两棵不同结构的四叉树进行合并的复杂性代码实现清晰且易于理解。对于图像处理类问题当图像尺寸固定且较小时这种“暴力展开”的策略往往是高效且可靠的。