企业官网建设流程全解析

网站建设与管理实用教程课后答案,做网络推广的多少钱一个月,找做网站的上什么app,哪家云服务器性价比高题目描述 给定一组形式为 xyx yxy 的变量约束条件#xff0c;要求输出所有满足这些约束条件的变量排列。变量均为单个小写字母#xff0c;每个测试用例包含至少 222 个、至多 202020 个变量#xff0c;以及至少 111 个、至多 505050 个约束条件。满足条件的排…题目描述给定一组形式为x y x yxy的变量约束条件要求输出所有满足这些约束条件的变量排列。变量均为单个小写字母每个测试用例包含至少2 22个、至多20 2020个变量以及至少1 11个、至多50 5050个约束条件。满足条件的排列数量在1 11到300 300300之间。输入以文件结束EOF \texttt{EOF}EOF终止每个测试用例的输出之间用空行分隔排列需按字典序字母序输出。输入格式每个测试用例由两行组成第一行变量列表字符间用空格分隔第二行约束条件列表每对x y x \\ yxy表示x y x yxy输出格式每个测试用例输出所有满足约束的排列每行一个按字典序排列。不同测试用例的输出之间用一个空行分隔。样例输入a b f g a b b f w u x y z v y x v z v w v样例输出abfg abgf agbf gabf wzxyy wzxyy xwzyy xzwyy zuxvy zxwy题目分析本题本质上是拓扑排序的枚举问题给定一个有向图变量为节点约束x y x yxy为有向边x → y x \to yx→y要求输出所有可能的拓扑序列且按字典序输出。由于变量数量最多为20 2020约束最多为50 5050可能的排列数不超过300 300300因此我们可以采用回溯法Backtracking \texttt{Backtracking}Backtracking结合剪枝来生成所有满足条件的排列。核心思路建模将变量视为图中的节点。每个约束x y x yxy对应一条从x xx指向y yy的有向边。我们需要输出所有拓扑排序即满足所有约束的线性顺序。算法选择使用深度优先搜索DFS \texttt{DFS}DFS回溯生成排列。在生成排列的过程中检查当前部分排列是否违反约束若违反则提前剪枝。为了按字典序输出首先对变量列表进行排序然后在回溯时按顺序尝试变量。剪枝策略记录每个变量在已生成排列中的位置。每添加一个变量检查所有约束条件如果某个约束x y x yxy中x xx和y yy都已出现在排列中且x xx的位置大于等于y yy的位置则当前排列无效回溯。这样可以在早期排除无效分支减少搜索空间。时间复杂度最坏情况下需要生成所有拓扑排序数量不超过300 300300回溯搜索的剪枝效果较好实际运行效率可以接受。解题步骤读取变量列表排序以保证输出字典序。读取约束条件存储为边的列表。初始化访问标记数组visited \texttt{visited}visited和位置数组value \texttt{value}value。从第一个位置开始回溯生成排列若当前排列长度达到n nn输出。否则按变量顺序尝试每个未使用的变量放入当前位。更新位置信息检查约束是否满足。递归下一层回溯时恢复状态。每个测试用例输出后打印空行最后一个除外。代码实现// Following Orders// UVa ID: 124// Verdict: Accepted// Submission Date: 2015-11-27// UVa Run Time: 0.000s//// 版权所有C2015邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;#defineMAXN20boolvisited[MAXN];intnChar,value[2*MAXN],nLimit;charoutput[MAXN],input[MAXN],limit[MAXN][2];voidprint(){for(inti0;inChar;i)coutoutput[i];coutendl;}boolisValid(){for(inti0;inLimit;i)if(value[limit[i][0]-a]0value[limit[i][1]-a]0value[limit[i][0]-a]value[limit[i][1]-a])returnfalse;returntrue;}voidlexicographical(intcurrent){if(current2!isValid())return;if(currentnChar){print();return;}for(inti0;inChar;i)if(!visited[i]){visited[i]true;output[current]input[i];value[input[i]-a]current;lexicographical(current1);value[input[i]-a]-1;visited[i]false;}}boolcmp(chara,charb){returnab;}intmain(intac,char*av[]){string line;intcases0;while(getline(cin,line),line.length()0){// 输出间隔空行。if(cases0)coutendl;// 读取字符初始化相关变量。istringstreamfirst(line);nChar0;while(firstinput[nChar]){output[nChar]0;visited[nChar]false;nChar;}for(inti0;i2*MAXN;i)value[i]-1;sort(input,inputnChar,cmp);// 读取限制。nLimit0;getline(cin,line);istringstreamnext(line);while(nextlimit[nLimit][0])nextlimit[nLimit][1];// 使用回溯生成字典序排列然后检查是否符合限制条件。lexicographical(0);cases;}return0;}总结本题是一道典型的拓扑排序枚举问题通过回溯法生成所有可能的排列并利用约束条件进行剪枝从而在合理时间内得到结果。需要注意输出格式字典序、空行分隔和边界条件变量数、约束数、排列数。代码实现简洁剪枝策略有效能够在给定的限制下快速求解。