题目描述题目要求将给定的正整数十进制无前导零通过一系列变换规则转换为一个非“有害”数。有害数的定义是能被333或777整除十进制表示中包含数字333或777存在连续333个或777个相同的数字。变换规则可重复应用若能被333整除则除以333若能被777整除则除以777若包含数字333则删除一个333可删除任意一个若包含数字777则删除一个777若存在连续333个相同数字则删除这一子串若存在连续777个相同数字则删除这一子串。删除后若有前导零则去除。若所有数字被删除结果为000。要求输出通过任意顺序应用这些规则能得到的最大的非有害数。输入格式第一行一个整数nnn表示测试用例的数量。接下来nnn行每行一个整数长度不超过212121无前导零。输出格式对于每个测试用例输出一行即能得到的最大非有害数。样例输入3 999 273 2331输出11 2 11题目分析本题的核心是搜索所有可能的变换结果并找出最大值。搜索空间由于每次操作都会减少数字的长度除法或删除且输入长度≤21\le 21≤21状态总数有限。可以使用广度优先搜索BFS\texttt{BFS}BFS或深度优先搜索DFS\texttt{DFS}DFS遍历所有可达状态并记录最大值。变换规则除法若当前数字能被333整除则除以333得到新数同样处理777。删除单个数字删除任意一个333或777。删除连续相同数字子串删除任意一个长度为333或777的连续相同数字子串。注意删除后需去除前导零。剪枝使用集合visited\textit{visited}visited记录已访问过的状态避免重复搜索。只在当前数字可能成为最大值时才继续搜索即当前数字大于当前最大值时才扩展。复杂度分析状态数有限可接受。代码实现// Magic// UVa ID: 560// Verdict: Accepted// Submission Date: 2017-05-13// UVa Run Time: 0.010s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;boolbigger(stringn1,stringn2){if(n1.length()!n2.length())returnn1.length()n2.length();for(inti0;in1.length();i)if(n1[i]!n2[i])returnn1[i]n2[i];returnfalse;}pairbool,stringmod3(stringn){intremainder0;string quotient;for(autoc:n)remainder(c-0);if(remainder%3!0)returnmake_pair(false,quotient);remainder0;for(autoc:n){remainder*10;remainder(c-0);if(quotient.size()0remainder3)continue;quotient(char)(0remainder/3);remainder%3;}returnmake_pair(true,quotient);}pairbool,stringmodK(stringn,intk){intremainder0;string quotient;for(autoc:n){remainder*10;remainder(c-0);if(quotient.size()0remainderk)continue;quotient(char)(0remainder/k);remainder%k;}returnmake_pair(remainder0,quotient);}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0,times[2]{3,7};cincases;unordered_setstringvisited;queuestringunvisited;string number;for(intc1;ccases;c){cinnumber;visited.clear();unvisited.push(number);string maxNumber0;while(!unvisited.empty()){string currentunvisited.front();unvisited.pop();if(!bigger(current,maxNumber))continue;booladdedfalse;pairbool,stringrmod3(current);if(r.firstvisited.find(r.second)visited.end()){visited.insert(r.second);unvisited.push(r.second);}if(r.first)addedtrue;rmodK(current,7);if(r.firstvisited.find(r.second)visited.end()){visited.insert(r.second);unvisited.push(r.second);}if(r.first)addedtrue;for(inti0;icurrent.size();i)if(current[i]3||current[i]7){stringnext(current);next.erase(next.begin()i);while(next.size()0next.front()0)next.erase(next.begin());if(visited.find(next)visited.end()){visited.insert(next);unvisited.push(next);}addedtrue;}for(inti0;icurrent.size();i)for(intk0;k1;k){boolsametrue;for(intj0;jtimes[k];j)if((ij)current.size()||current[ij]!current[i]){samefalse;break;}if(same){stringnext(current);next.erase(next.begin()i,next.begin()itimes[k]);while(next.size()0next.front()0)next.erase(next.begin());if(visited.find(next)visited.end()){visited.insert(next);unvisited.push(next);}addedtrue;}}if(!addedbigger(current,maxNumber))maxNumbercurrent;}coutmaxNumber\n;}return0;}