题目描述题目涉及一个分子工程问题。给定四条等长的分子链每条链由121212个字母组成字母范围为A\texttt{A}A到P\texttt{P}P需要将它们放置成一个矩形互锁结构。该结构由两个水平槽和两个垂直槽组成四条链分别放置在其中。链在槽中不能翻转必须保持原始方向水平槽保持从左到右的顺序垂直槽保持从上到下的顺序对应原始链从左到右的顺序。四条链在矩形边界处通过共享分子相互连接形成一个中央矩形区域。要求中央矩形区域的面积即内部空位数量尽可能大且面积不能为零。每条链超出矩形边界的尾部前后两端必须至少有一个分子元素。输入格式输入包含多组数据。每组数据由四行组成每行一个长度为121212的字符串表示一条分子链。第一条链的第一个字符为Q\texttt{Q}Q时表示输入结束。每条链的分子设计符限制在A\texttt{A}A到P\texttt{P}P之间。输出格式对于每组数据输出一行一个整数表示能形成的合法结构中最大的中央矩形面积。如果无法形成任何合法结构输出000。样例输入CDBADCBBEFEF DACCBDAFEAB EFBDCAADBDCD ABCDABCDABCD DACCBDADFAB EFBDCAADBDCD ABCDABCDABCD CDBADCBEFEF ABABABABABAB CDCDCDCDCDD EEEEEEEEEEE FFFFFFFFFFF ABAAAAAAAABA CBCCCCCCCBC DBDDDDDDDDDBD EBEEEEEEEEBE ABBBBBBBBBBA ACCCCCCCCCCA ADDDDDDDDDDA AEEEEEEEEEEA BBBABBABBBB CCACCCACCCCC DDDADDADDDDD EEAEEAEEEEE Q输出48 48 0 64 0 6题目分析本题的核心是将四条分子链排列成一个矩形互锁结构计算中央矩形区域的最大面积。结构描述矩形互锁结构由两个水平链上边和下边和两个垂直链左边和右边组成。四条链在矩形的四个角处通过共享分子相互连接。设四条链的编号为0,1,2,30, 1, 2, 30,1,2,3分别对应上、下、左、右四个位置。约束条件水平链上、下保持原始从左到右的顺序。垂直链左、右保持原始从上到下的顺序对应原始链从左到右的顺序。每条链的尾部超出矩形的部分长度至少为111即链的第一个和最后一个分子不能位于矩形边界上。中央矩形面积不能为零即矩形的宽度和高度均至少为222。矩形角部匹配设四条链的索引排列为p0,p1,p2,p3p_0, p_1, p_2, p_3p0,p1,p2,p3分别对应上、下、左、右。矩形四个角部的匹配条件为左上角上链的第iii个分子与左链的第jjj个分子相同。右上角上链的第kkk个分子与右链的第lll个分子相同且kik iki。左下角下链的第mmm个分子与左链的第nnn个分子相同且njn jnj。右下角下链的第ppp个分子与右链的第qqq个分子相同且pmp mpm同时需要满足矩形封闭条件。设上链的交叉点位置为x1x_1x1左和x2x_2x2右左链的交叉点位置为y1y_1y1上和y2y_2y2下右链的交叉点位置为z1z_1z1上和z2z_2z2下下链的交叉点位置为w1w_1w1左和w2w_2w2右。则宽度x2−x1 x_2 - x_1x2−x1高度y2−y1 y_2 - y_1y2−y1右下角需满足w2w1widthw_2 w_1 \text{width}w2w1width且z2z1heightz_2 z_1 \text{height}z2z1height且分子匹配。枚举策略由于只有四条链可以枚举所有4!244! 244!24种排列方式将链分配到上、下、左、右四个位置。对于每种排列枚举可能的交叉点组合检查是否满足匹配条件计算矩形面积记录最大值。链的长度固定为121212且尾部至少为111因此交叉点的索引范围是111到101010000和111111为尾部。枚举量约为24×104≈2.4×10524 \times 10^4 \approx 2.4 \times 10^524×104≈2.4×105完全可接受。实现细节预处理任意两条链之间的所有匹配位置对即相同字母的位置存入数组intersection[i][j]\textit{intersection}[i][j]intersection[i][j]。枚举排列对于当前排列枚举左上角匹配对(p0,p3)(p_0, p_3)(p0,p3)和右上角匹配对(p0,p2)(p_0, p_2)(p0,p2)要求右上角的位置大于左上角的位置。枚举左下角匹配对(p1,p3)(p_1, p_3)(p1,p3)要求左下角的位置大于左上角在左链上的位置。根据宽度和高度计算右下角预期位置检查下链和右链在预期位置处是否有匹配的分子对。边界条件如果找不到任何合法匹配面积为000。面积计算公式为(width−1)×(height−1)(\text{width} - 1) \times (\text{height} - 1)(width−1)×(height−1)因为矩形顶点处分子不占用内部空位。复杂度分析每条链长度固定为121212枚举所有排列和所有交叉点组合时间复杂度O(4!×L4)O(24×124)≈5×105O(4! \times L^4) O(24 \times 12^4) \approx 5 \times 10^5O(4!×L4)O(24×124)≈5×105完全可接受。代码实现// Molecules// UVa ID: 418// Verdict: Accepted// Submission Date: 2016-07-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorstringmolecules;vectorintindexer(4);vectorpairint,intintersection[4][4];voidfindIntersection(inti,intj){for(intx1;xmolecules[i].size()-1;x)for(inty1;ymolecules[j].size()-1;y)if(molecules[i][x]molecules[j][y])intersection[i][j].push_back(make_pair(x,y));}intfindMaxVacant(){intcounter0;for(autop1:intersection[indexer[0]][indexer[1]]){for(autop2:intersection[indexer[0]][indexer[2]]){if(p2.firstp1.first){for(autop3:intersection[indexer[1]][indexer[3]]){if(p3.firstp1.second){intwidthp2.first-p1.first;intheightp3.first-p1.second;if(p3.secondwidthmolecules[indexer[3]].size()-1p2.secondheightmolecules[indexer[2]].size()-1molecules[indexer[3]][p3.secondwidth]molecules[indexer[2]][p2.secondheight]){countermax(counter,(width-1)*(height-1));}}}}}}returncounter;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line),line.front()!Q){molecules.clear();molecules.push_back(line);for(inti1;i3;i){getline(cin,line);molecules.push_back(line);}for(inti0;i4;i)for(intj0;j4;j)intersection[i][j].clear();for(inti0;i4;i)for(intj0;j4;j){if(ij)continue;findIntersection(i,j);}iota(indexer.begin(),indexer.end(),0);intmax_counter0;do{intcounterfindMaxVacant();max_countermax(max_counter,counter);}while(next_permutation(indexer.begin(),indexer.end()));coutmax_counter\n;}return0;}
UVa 418 Molecules
发布时间：2026/6/7 12:52:54
题目描述题目涉及一个分子工程问题。给定四条等长的分子链每条链由121212个字母组成字母范围为A\texttt{A}A到P\texttt{P}P需要将它们放置成一个矩形互锁结构。该结构由两个水平槽和两个垂直槽组成四条链分别放置在其中。链在槽中不能翻转必须保持原始方向水平槽保持从左到右的顺序垂直槽保持从上到下的顺序对应原始链从左到右的顺序。四条链在矩形边界处通过共享分子相互连接形成一个中央矩形区域。要求中央矩形区域的面积即内部空位数量尽可能大且面积不能为零。每条链超出矩形边界的尾部前后两端必须至少有一个分子元素。输入格式输入包含多组数据。每组数据由四行组成每行一个长度为121212的字符串表示一条分子链。第一条链的第一个字符为Q\texttt{Q}Q时表示输入结束。每条链的分子设计符限制在A\texttt{A}A到P\texttt{P}P之间。输出格式对于每组数据输出一行一个整数表示能形成的合法结构中最大的中央矩形面积。如果无法形成任何合法结构输出000。样例输入CDBADCBBEFEF DACCBDAFEAB EFBDCAADBDCD ABCDABCDABCD DACCBDADFAB EFBDCAADBDCD ABCDABCDABCD CDBADCBEFEF ABABABABABAB CDCDCDCDCDD EEEEEEEEEEE FFFFFFFFFFF ABAAAAAAAABA CBCCCCCCCBC DBDDDDDDDDDBD EBEEEEEEEEBE ABBBBBBBBBBA ACCCCCCCCCCA ADDDDDDDDDDA AEEEEEEEEEEA BBBABBABBBB CCACCCACCCCC DDDADDADDDDD EEAEEAEEEEE Q输出48 48 0 64 0 6题目分析本题的核心是将四条分子链排列成一个矩形互锁结构计算中央矩形区域的最大面积。结构描述矩形互锁结构由两个水平链上边和下边和两个垂直链左边和右边组成。四条链在矩形的四个角处通过共享分子相互连接。设四条链的编号为0,1,2,30, 1, 2, 30,1,2,3分别对应上、下、左、右四个位置。约束条件水平链上、下保持原始从左到右的顺序。垂直链左、右保持原始从上到下的顺序对应原始链从左到右的顺序。每条链的尾部超出矩形的部分长度至少为111即链的第一个和最后一个分子不能位于矩形边界上。中央矩形面积不能为零即矩形的宽度和高度均至少为222。矩形角部匹配设四条链的索引排列为p0,p1,p2,p3p_0, p_1, p_2, p_3p0,p1,p2,p3分别对应上、下、左、右。矩形四个角部的匹配条件为左上角上链的第iii个分子与左链的第jjj个分子相同。右上角上链的第kkk个分子与右链的第lll个分子相同且kik iki。左下角下链的第mmm个分子与左链的第nnn个分子相同且njn jnj。右下角下链的第ppp个分子与右链的第qqq个分子相同且pmp mpm同时需要满足矩形封闭条件。设上链的交叉点位置为x1x_1x1左和x2x_2x2右左链的交叉点位置为y1y_1y1上和y2y_2y2下右链的交叉点位置为z1z_1z1上和z2z_2z2下下链的交叉点位置为w1w_1w1左和w2w_2w2右。则宽度x2−x1 x_2 - x_1x2−x1高度y2−y1 y_2 - y_1y2−y1右下角需满足w2w1widthw_2 w_1 \text{width}w2w1width且z2z1heightz_2 z_1 \text{height}z2z1height且分子匹配。枚举策略由于只有四条链可以枚举所有4!244! 244!24种排列方式将链分配到上、下、左、右四个位置。对于每种排列枚举可能的交叉点组合检查是否满足匹配条件计算矩形面积记录最大值。链的长度固定为121212且尾部至少为111因此交叉点的索引范围是111到101010000和111111为尾部。枚举量约为24×104≈2.4×10524 \times 10^4 \approx 2.4 \times 10^524×104≈2.4×105完全可接受。实现细节预处理任意两条链之间的所有匹配位置对即相同字母的位置存入数组intersection[i][j]\textit{intersection}[i][j]intersection[i][j]。枚举排列对于当前排列枚举左上角匹配对(p0,p3)(p_0, p_3)(p0,p3)和右上角匹配对(p0,p2)(p_0, p_2)(p0,p2)要求右上角的位置大于左上角的位置。枚举左下角匹配对(p1,p3)(p_1, p_3)(p1,p3)要求左下角的位置大于左上角在左链上的位置。根据宽度和高度计算右下角预期位置检查下链和右链在预期位置处是否有匹配的分子对。边界条件如果找不到任何合法匹配面积为000。面积计算公式为(width−1)×(height−1)(\text{width} - 1) \times (\text{height} - 1)(width−1)×(height−1)因为矩形顶点处分子不占用内部空位。复杂度分析每条链长度固定为121212枚举所有排列和所有交叉点组合时间复杂度O(4!×L4)O(24×124)≈5×105O(4! \times L^4) O(24 \times 12^4) \approx 5 \times 10^5O(4!×L4)O(24×124)≈5×105完全可接受。代码实现// Molecules// UVa ID: 418// Verdict: Accepted// Submission Date: 2016-07-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorstringmolecules;vectorintindexer(4);vectorpairint,intintersection[4][4];voidfindIntersection(inti,intj){for(intx1;xmolecules[i].size()-1;x)for(inty1;ymolecules[j].size()-1;y)if(molecules[i][x]molecules[j][y])intersection[i][j].push_back(make_pair(x,y));}intfindMaxVacant(){intcounter0;for(autop1:intersection[indexer[0]][indexer[1]]){for(autop2:intersection[indexer[0]][indexer[2]]){if(p2.firstp1.first){for(autop3:intersection[indexer[1]][indexer[3]]){if(p3.firstp1.second){intwidthp2.first-p1.first;intheightp3.first-p1.second;if(p3.secondwidthmolecules[indexer[3]].size()-1p2.secondheightmolecules[indexer[2]].size()-1molecules[indexer[3]][p3.secondwidth]molecules[indexer[2]][p2.secondheight]){countermax(counter,(width-1)*(height-1));}}}}}}returncounter;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line),line.front()!Q){molecules.clear();molecules.push_back(line);for(inti1;i3;i){getline(cin,line);molecules.push_back(line);}for(inti0;i4;i)for(intj0;j4;j)intersection[i][j].clear();for(inti0;i4;i)for(intj0;j4;j){if(ij)continue;findIntersection(i,j);}iota(indexer.begin(),indexer.end(),0);intmax_counter0;do{intcounterfindMaxVacant();max_countermax(max_counter,counter);}while(next_permutation(indexer.begin(),indexer.end()));coutmax_counter\n;}return0;}
