惠州的企业网站建设交通网站建设方案

当前位置： 首页 > news >正文

惠州的企业网站建设,交通网站建设方案,宿迁网站建设联系电话,设计灵感网站整理进位制与字符串专题 目录 MT2179 01操作MT2182 新十六进制MT2172 萨卡兹人MT2173 回文串等级MT2175 五彩斑斓的串 MT2179 01操作 难度#xff1a;黄金    时间限制#xff1a;1秒    占用内存#xff1a;128M 题目描述 刚学二进制的小码哥对加减乘除还不熟#xff0c;他…进位制与字符串专题 目录 MT2179 01操作MT2182 新十六进制MT2172 萨卡兹人MT2173 回文串等级MT2175 五彩斑斓的串 MT2179 01操作 难度黄金    时间限制1秒    占用内存128M 题目描述 刚学二进制的小码哥对加减乘除还不熟他希望你帮他复习操作。 对于二进制数有如下几个操作 整个二进制数加1整个二进制数减1整个二进制数乘2整个二进制数除2。 (本题不会导致最高位进退位即若全是1之后操作加1的情况不会出现)以上的操作是二进制数的对应操作乘2或除2会导致进退位。 格式 输入格式第一行两个正整数 n , m n,m n,m 表示二进制数长度和操作数      接下来一行一个二进制数      第三行 m m m 个字符-* /对应操作1-4。 输出格式一行字符表示操作后的二进制数。 样例 1 输入4 10    1101    /---// 输出10110 备注 对于30%的数据 1 ≤ n , m ≤ 1000 1≤n,m≤1000 1≤n,m≤1000 对于60%的数据 1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1≤n,m≤105 对于100%的数据 1 ≤ n , m ≤ 5 × 1 0 7 1≤n,m≤5×10^7 1≤n,m≤5×107。 相关知识点数学、进位制 题解 对二进制数进行简单运算最简单的办法就是将输入的二进制数字串转换为二进制数然后再按要求进行运算并输出。但注意到一点题目给出的二进制数的长度非常大因此这样的求解方法不一定可行。实际上这道题考察的是对二进制数的加减乘除操作因此求解的关键是理解这四则运算在二进制数中的法则。 加 1 运算。二进制数的加 1 运算在末尾位为0时直接将该位置为 1否则就需要进位同时将该位置为 0 。这种情况可以推广至更高位。如对二进制数 1011 执行加 1 运算时由于末位为 1则加 1 会使末位发生进位此时末位将变为 0即得到 101’0进位后由于较高位的数依然为 1则在该位也会发生这种情况即继续进位并置当前位为 0即得到 10’00再次进位后较高位为 0则直接置该位为1即可即得到 1100。从该过程不难看出二进制数的加 1 运算实际上就是从低位往高位不断扫描直到遇到一个 “0” 时将 “0” 换为 “1” 即可。在此过程中只要遇到 “1” 就将 “1” 换为 “0”。减 1 运算。二进制数的减 1 运算实际上和加 1 运算是互逆的。即若二进制数的末位已经为 1则直接将该位置为 0否则就需要借位同时将该位置位 1。这种情况可以推广至更高位。如对二进制数 1100 执行减 1 运算时由于末位为 0则减 1 会使末位发生借位此时末位将变为 1即得到 110,1借位后由于较高位的数依然为 0则在该位也会发生这种情况即继续借位并置当前位为 1即得到 11,11再次借位后较高位为 1则直接置该位为0即可即得到 1011。从该过程不难看出二进制数的减 1运算实际上就是从低位往高位不断扫描直到遇到一个 “1” 时将 “1” 换为 “0” 即可。在此过程中只要遇到 “0” 就将 “0” 换为 “1”。乘 2 运算。二进制数的减 2 运算只需要在二进制数的末尾添加一个 0 即可本质上是将原二进制数向左移1位。如二进制数 101 对应的十进制数是 55×210而 10 对应的二进制数是 1010。除 2 运算。二进制数的除 2 运算与乘 2 运算互逆即只需要将原二进制数向右移 1 位。 下面给出基于上述思路得到的完整代码已 AC /*MT2179 01操作用 char * 才能获得满分 */ #includebits/stdc.h using namespace std;const int MAX 5e75; char num[MAX];int main( ) {// 录入数据 int n,m,p; char opt;cinnm;cinnum;// 执行 m 次操作while(m–){cinopt;switch(opt){// 加法操作 case :for(int in-1; i0;i–){if(num[i] 0){num[i] 1;break;}else{num[i] 0;}}break;// 减法操作 case -:for(int in-1; i0; i–){if(num[i] 1){num[i] 0;break;}else{num[i] 1;}}break;// 乘法操作 case *:num[n] 0;num[n] \0;break;// 除法操作 case /:num[–n] \0;break;}}// 输出结果coutnum; return 0; }MT2182 新十六进制 难度钻石    时间限制1秒    占用内存128M 题目描述 小码哥基于之前的十六进制定义了一种新的进制其仍然由十六个基数构成即 012 …9ABCDEF并且大小关系保持不变即 012…9ABCDEF唯一不同的是数字只能按照大小关系升序排列即 1121 这样的数是不合法的1F 的下一个数是 23,但前导 0 会被忽略即 00012 等于 12也同样合法。 现在小码哥想为这种进制制作转换器能够把这种进制下的数转换成十进制数但小码哥不懂怎么下手于是他来找你帮忙。 小码哥希望对于输入的数字能进行判断如果这个数字不合法转换器会报错如果合法转换器会输出对应的十进制数。 格式 输入格式一个字符串为标准十六进制数。 输出格式一个整数表示转换成的十进制数如果输入的十六进制数不合法输出 error。 样例 1 输入12 输出16 备注 字符串长度小于等于 20可能出现负数输出文件不存在 -0。 相关知识点 数学、进位制 题解 首先对题目提出的新进制进行解读。我们来看原十六进制的前18个数 根据题目的意思“新十六进制下的数字只能按照大小关系升序排列”因此上表中的十六进制数 “10”、“11” 是不合法的于是在新十六进制下数 “F” 的下一个数应该为 “12”即新十六进制数的前 18 个数为 这便是题目所说的新十六进制与十进制数的对应关系。 对于输入的任意新十六进制字符串如果要找到其对应的十进制数我们可以通过顺序查找的方式进行求解。即从 0 开始依次枚举该数对应的十六进制数同时再定义一个计数器 cnt 来记录当前找到的合法的新十六进制数个数当存在某个十进制数对应的十六进制数与输入的新十六进制数一致时计数器 cnt 保存的值即为所求。根据这样的思路可写出以下代码 /*MT2182 新十六进制数Search string.erase(string.begin())会将指定字符串的首位字符进行抹除 */#includebits/stdc.h using namespace std;// 字符串处理消除多余的前导0同时反馈输入数据的正负性 int Formatting(string str) {int flag 1;// 正负性判别 if(str[0] -){flag -1;str.erase(str.begin());}// 消除前导 0 while(str[0] 0 str.size()1)str.erase(str.begin());return flag; } // 字符串的合法性检测 bool isLegal(string str) {int strlen str.size();if(strlen1) return true;for(int i1; istrlen; i)if(str[i] - str[i-1] 0)return false;return true; }// 根据新十六进制数的规则顺序枚举 int getDecOfNewHex(string str) {int cnt 0; string tmp;stringstream ss;for(int i0; ; i){// 将当前数字转换为 16 进制ss.clear();sshexi;sstmp;// 判断该十六进制数与输入字符是否一致 if(tmp str) return cnt;// 若该十六进制数合法则向后计数 if(isLegal(tmp)) cnt; } }int main( ) {// 输入数据 string str;cinstr;// 格式处理int flag Formatting(str);// 合法性检测if(!isLegal(str)){couterrorendl;return 0;}// 顺序查找该新十六进制字符串对应的十进制数 coutflag*getDecOfNewHex(str)endl;return 0; }这份代码出现了超时情况只能得一半的分原因很简单每次枚举一个十进制数都涉及到进制转换以及合法性检测两个环节特别是合法性检测这肯定是有超时风险的。 那要如何解决这个问题呢其实上面的求解之所以会超时是因为我们枚举的目标集合是十进制数据集而这个数据集中具有相当一部分数据在转换为十六进制数后为非新十六进制数说简单点就是花了些时间枚举计算非合法的结果这就是在做无用功。换个角度我们可以枚举所有的新十六进制数然后再按序为其编号不就能得到不同新十六进制数对应的十进制数了么这里需要提一点新十六进制数是存在最大值的最大值显然为 123456789ABCDEF也就是说新十六进制数是有限的将其用树来表示得到的效果如下 这为我们提供了枚举的可行性。 于是现在我们的问题是如何枚举新十六进制数一种简单直接的办法是用深度优先搜索算法传递参数为上图所示根节点对应的数字每次搜索时都从当前根节点的下一个数字进行递归搜索。这样就能将所有合法十六进制数全部枚举出具体代码如下。 char chr[] 0123456789ABCDEF; int cnt 1, flag 1; string tmp, str, s[100000]{0}; void dfs(int num){if(tmp.size()) s[cnt] tmp;for(int inum1; i16; i){tmp.push_back(chr[i]);dfs(i);tmp.pop_back();} } 在得到了所有新十六进制字符串后我们只需要再对这些字符串进行排序并为其标记顺序即可这些顺序即指示了其对应的十进制数。而对新十六进制的排序即 012…9ABCDEF恰好与各字符在 ASCII 码值上的大小关系一致。但考虑到数字越长表示的数越大这点与依赖 ASCII 码值的字符串排序不同因此需要单独写一个用于比较新十六进制数字符串大小关系的函数如下 bool cmp(string a, string b){if(a.size() b.size()) return ab;return a.size() b.size(); }最后只需要通过一重循环对得到的新十六进制数集合进行扫描便能查找到指定输入对应的十进制数下面给出基于以上思路得到的完整代码已 AC /*MT2182 新十六进制数 */ #includebits/stdc.h using namespace std;const int MAX 1e55; char chr[] 0123456789ABCDEF; int cnt 1; string tmp, str, s[MAX]{0};// 利用深搜将所有的合法数字举例出来 void dfs(int num){if(tmp.size()) s[cnt] tmp;for(int inum1; i16; i){tmp.push_back(chr[i]);dfs(i);tmp.pop_back();} } // 字符串处理消除多余的前导0同时反馈输入数据的正负性 int Formatting(string str) {int flag 1;// 正负性判别 if(str[0] -){flag -1;str.erase(str.begin());}// 消除前导 0 while(str[0] 0 str.size()1)str.erase(str.begin());return flag; } // 自定义数字比较规则 bool cmp(string a, string b){if(a.size() b.size()) return ab;return a.size() b.size(); }int main( ) {// 枚举所有的新十六进制数 dfs(0);// 获取输入 cinstr;// 对输入字符串进行处理 int flag Formatting(str);// 排序 sort(s,scnt,cmp);// 查找指定新十六进制数的位置 for(int i0;icnt;i)if(s[i] str){couti*flag;return 0;}couterror;return 0; }MT2172 萨卡兹人 难度黄金    时间限制2.5秒    占用内存128M 题目描述 很久很久以前卡西米尔里住着萨卡兹人他们彼此争斗不休。有一天他们想要研究自己的 DNA 序列来证明他们是一个种群。首先选取一个好长好长的序列DNA 序列包含 26 个小写英文字母然后每次选择两个区间这两个区间代表两个萨卡兹人的 DNA 序列这两个萨卡兹一模一样的唯一可能是他们的 DNA 序列一模一样。 格式 输入格式第一行输入一个DNA字符串 S      接下来一个数字 m m m 表示 m m m 次询问      接下来 m m m 行每行四个数字 l 1 , r 1 , l 2 , r 2 l_1,r_1, l_2,r_2 l1​,r1​,l2​,r2​ 分别表示此次询问的两个区间      注意字符串的位置从1开始编号。 输出格式对于每次询问输出一行表示结果。如果两个萨卡兹完全相同输出 Yes否则输出 No。 样例1 输入aabbaabb    3    1 3 5 7    1 3 6 8    1 2 1 2 输出Yes    No    Yes 备注 其中 1 ≤ l 1 ≤ r 1 ≤ l e n g t h ( S ) , 1 ≤ l 2 ≤ r 2 ≤ l e n g t h ( S ) 1≤ l_1≤r_1≤length(S),1≤ l_2≤ r_2≤length(S) 1≤l1​≤r1​≤length(S),1≤l2​≤r2​≤length(S) 1 ≤ l e n g t h ( S ) , m ≤ 1000000 1≤length(S),m≤1000000 1≤length(S),m≤1000000。 相关知识点字符串 题解 这道题考察了字符串的子串判等比较简单下面直接给出求解的完整代码已 AC /*MT2172 萨卡兹人 */ #includebits/stdc.h using namespace std;int main( ) {// 输入数据string S;int m,l1,r1,l2,r2,p,len;cinSm;// 字符串移位满足题目“字符串位置从1编号”的要求 S 0S;// 执行询问while(m–) {cinl1r1l2r2;p0, len r1-l1;while(S[l1p] S[l2p] plen) p;if(p len) coutYesendl;else coutNoendl;}return 0; }MT2173 回文串等级 难度黄金    时间限制1秒    占用内存128M 题目描述 所谓量变产生质变就比如低级的材料攒多了可以合成更高级的玩意儿高级的回文串也可以由低级的组成。任意一个字符串都可以是 0 级的回文串。而一个更高级的长为 n n n 的 i i i 级回文串则满足其长为 ⌊ 2 n ⌋ \lfloor \frac2n \rfloor ⌊n2​⌋ 向下取整的前后缀都为 i − 1 i-1 i−1 级回文串。现在给你一个字符串问你其每个前缀的回文串等级。 格式 输入格式一行一个字符串S。 输出格式|S| 个数表示其长为 1,2,3,…,|S| 的前缀的回文串等级。 样例 1 输入aaa 输出1 2 2 备注 其中 1 ≤ ∣ S ∣ ≤ 500000 1≤|S|≤500000 1≤∣S∣≤500000。 相关知识点字符串、字符串哈希 题解 首先需要弄清楚题中所说回文串等级。例如对字符串 “aba” 当取前缀为 1 时即 “a”该字符串的长为 ⌊ 1 2 ⌋ 0 \lfloor \frac12 \rfloor0 ⌊21​⌋0 的前后缀不存在即认为前后缀回文串等级为 0且字符串 “a” 本身是一个回文串因此认为 “a” 的回文串等级为 011实际上可以认为长度为 1 的字符的回文串等级就为 1当取前缀为 2 时即 “ab”该字符串的长为 ⌊ 2 2 ⌋ 1 \lfloor \frac22 \rfloor1 ⌊22​⌋1 的前后缀分别为 “a” 和 “b”且各自的回文串等级均为 1但字符串 “ab” 本身不是一个回文串因此 “ab” 的回文串等级为 0当取前缀为 3 时即 “aba”该字符串的 ⌊ 3 2 ⌋ 1 \lfloor \frac32 \rfloor1 ⌊23​⌋1 的前后缀子串均为 “a”都是 1 级回文串因此 “aba” 的回文串等级为 112 根据这样的思路可写出以下代码 // 输入数据(通过移位限定输入字符串的起始地址从1开始) cin(s1); len strlen(s1); // 初始化第1个前缀的回文串等级必定是1 ans[1]1; cout1 ; // 遍历原字符串的所有前缀并求出各前缀的回文串等级 for(int i2;ilen;i){if(isPlalindrome(s,1,i))ans[i] ans[i1] 1;coutans[i] ; }其中函数 isPlalindrome(char *s, int start, int end) 用于判断字符串 s 从 start 到 end 的子串是否为回文。 该代码完整描述了求解本题的整体思路但存在严重的超时风险。因为每次扫描指定字符串的所有前缀时都需要单独判断此前缀串是否为回文这在题目所给的数据范围内是必定超时的。因此为了能完整通过全部测试数据就必须想办法解决 “判断指定字符串的所有前缀串是否为回文” 这一难题。 这便需要用到字符串哈希。我们知道回文串是正着和倒着读结果都不变的字符串基于这种性质假设现在有一个长为 n n n 的回文字符串 S S S。如果我们随机取一个数 p p p则总存在 S 1 p n − 1 S 2 p n − 2 ⋯ S n S 1 S 2 p ⋯ S n p n − 1 S_1 p^{n-1}S_2 p^{n-2}⋯S_nS_1S_2 p⋯S_n p^{n-1} S1​pn−1S2​pn−2⋯Sn​S1​S2​p⋯Sn​pn−1 其中 S i S_i Si​ 表示字符串 S S S 中的第 i i i 个字符对应的 ASCII 值。例如数字回文串 “11311” 始终满足 1 p 4 1 p 3 3 p 2 1 p 1 1 1 p 3 p 2 1 p 3 1 p 4 1p^41p^33p^21p111p3p^21p^31p^4 1p41p33p21p111p3p21p31p4 根据该等式我们可以通过计算一个字符串的前缀和与后缀和数组来快速地判断该字符串中任意前缀是否为一个回文串。例如对于数字字符串 “112113”我们可以维护以下两个数组取 p 5 p5 p5 基于这两个数组我们能在常数时间内判断出字符串 “112113” 的任意前缀子串是否为回文串 长度为 1 的前缀 “1”数组 H 1 H_1 H1​ 记录的该子串的前缀和为 H 1 [ 1 ] 1 H_1 [1]1 H1​[1]1数组 H 2 H_2 H2​ 记录的该子串的前缀和为 H 2 [ 1 ] − H 2 [ 1 1 ] ∗ 5 1 H_2 [1]-H_2 [11]*51 H2​[1]−H2​[11]∗51因此有 P r e H 1 P r e H 2 PreH_1PreH_2 PreH1​PreH2​所以前缀 “1” 是一个回文串长度为 2 的前缀 “11”数组 H 1 H_1 H1​ 记录的该子串的前缀和为 H 1 [ 2 ] 6 H_1 [2]6 H1​[2]6数组 H 2 H_2 H2​ 记录的该子串的前缀和为 H 2 [ 1 ] − H 2 [ 2 1 ] ∗ 5 2 6 H_2 [1]-H_2 [21]*5^26 H2​[1]−H2​[21]∗526因此有 P r e H 1 P r e H 2 PreH_1PreH_2 PreH1​PreH2​所以前缀 “11” 是一个回文串长度为 3 的前缀 “112”数组 H 1 H_1 H1​ 记录的该子串的前缀和为 H 1 [ 3 ] 32 H_1 [3]32 H1​[3]32数组 H 2 H_2 H2​ 记录的该子串的前缀和为 H 2 [ 1 ] − H 2 [ 3 1 ] ∗ 5 3 56 H_2 [1]-H_2 [31]*5^356 H2​[1]−H2​[31]∗5356因此有 P r e H 1 ≠ P r e H 2 PreH_1\neq PreH_2 PreH1​PreH2​所以前缀 “112” 不是一个回文串长度为 4 的前缀 “1121”数组 H 1 H_1 H1​ 记录的该子串的前缀和为 H 1 [ 4 ] 161 H_1 [4]161 H1​[4]161数组 H 2 H_2 H2​ 记录的该子串的前缀和为 H 2 [ 1 ] − H 2 [ 4 1 ] ∗ 5 4 206 H_2 [1]-H_2 [41]*5^4206 H2​[1]−H2​[41]∗54206因此有 P r e H 1 ≠ P r e H 2 PreH_1\neq PreH_2 PreH1​PreH2​所以前缀 “1121” 不是一个回文串长度为 5 的前缀 “11211”数组 H 1 H_1 H1​ 记录的该子串的前缀和为 H 1 [ 5 ] 1 × 5 4 1 × 5 3 2 × 5 2 1 × 5 1 × 1 H_1 [5]1×5^41×5^32×5^21×51×1 H1​[5]1×541×532×521×51×1数组 H 2 H_2 H2​ 记录的该子串的前缀和为 H 2 [ 1 ] − H 2 [ 5 1 ] ∗ 5 5 1 × 1 1 × 5 2 × 5 2 1 × 5 3 1 × 5 4 H_2 [1]-H_2 [51]*5^51×11×52×5^21×5^31×5^4 H2​[1]−H2​[51]∗551×11×52×521×531×54显然 P r e H 1 P r e H 2 PreH_1 PreH_2 PreH1​PreH2​所以前缀 “11211” 是一个回文串长度为 6 的前缀 “112113”数组 H 1 H_1 H1​ 记录的该子串的前缀和为 H 1 [ 6 ] 1 × 5 5 1 × 5 4 2 × 5 3 1 × 5 2 1 × 5 3 × 1 H_1 [6]1×5^51×5^42×5^31×5^21×53×1 H1​[6]1×551×542×531×521×53×1数组 \(H_2 \) 记录的该子串的前缀和为 H 2 [ 1 ] 1 × 1 1 × 5 2 × 5 2 1 × 5 3 1 × 5 4 3 × 5 5 H_2 [1]1×11×52×5^21×5^31×5^43×5^5 H2​[1]1×11×52×521×531×543×55显然 P r e H 1 ≠ P r e H 2 PreH_1\neq PreH_2 PreH1​PreH2​所以前缀 “112113” 不是一个回文串。 这便是利用字符串哈希判断任意字符串的所有前缀子串是否为回文的方法。下面给出基于该思路的完整代码已 AC /*MT2173 回文串等级 哈希求解 */ #includebits/stdc.h using namespace std;// 定义一个较大的质数 const int Z 111; const int MAX 5e57; unsigned long long p[MAX], h1[MAX], h2[MAX]; char s[MAX]; int len, ans[MAX];// 预处理哈希函数的前缀和 void init(int n){p[0]1;for(int i1; in; i){p[i] p[i-1]*Z;h1[i] h1[i-1]*Z s[i];h2[n-i1] h2[n-i2]*Z s[n-i1];} }int main( ) {// 输入数据(通过移位限定输入字符串的起始地址从1开始)cins1; len strlen(s1);init(len);// 初始化第1个前缀的回文串等级必定是1ans[1]1;cout1 ;// 遍历原字符串的所有前缀并求出各前缀的回文串等级for(int i2;ilen;i){// 判断当前的前缀子串是否是回文串if(h1[i] h2[1]-h2[i1]*p[i])ans[i] ans[i1] 1;coutans[i] ;}return 0; }MT2175 五彩斑斓的串 难度钻石    时间限制1秒    占用内存128M 题目描述 小码哥是一个喜欢字符串的男孩子。 小码哥在研究字典序的性质。他发现他可以通过改变字母表的顺序来改变两个字符串的大小关系。 例如通过将现有的字母表顺序 “abcdefghijklmnopqrstuvwxyz” 改为 “abcdefghijklonmpqrstuvwxyz”字符串 “omm” 会小于 “mom”。 现在小码哥有 n n n 个字符串对于其中的一个字符串如果存在某种字母表顺序使得它在这 n n n 个字符串中字典序最小那这个字符串就是一个五彩斑斓的串。 现在小码哥想找出所有五彩斑斓的串由于小码哥忙于他的研究找出所有五彩斑斓的串的重任被交到了你的身上。 格式 输入格式第一行一个正整数 n n n表示字符串的个数      接下来 n n n 行每行一个字符串。 输出格式输出第一行为一个正整数为五彩斑斓的串的个数      接下来对于每个五彩斑斓的串输出一行。      注意输出的串的顺序应该和输入一致 样例 1 输入4    omm    moo    mom    ommnom 输出2    omm    mom 备注 测试数据保证 1 ≤ n ≤ 3 × 1 0 4 1≤n≤3×10^4 1≤n≤3×104 所有字符串的总长不超过 3 × 1 0 5 3×10^5 3×105且字符集为小写英文字母。 相关知识点字符串、字典树 题解 题目的意思是对输入的一系列字符串判断其中的每个字符串是否存在一种字典序使得其在这些字符串集中最小。例如对于题目给出的字符串集 {omm, moo, mom, ommnom} 字符串 “omm” 在给定满足 “om” 的字典序中总存在omm ommnom moo mom此时字符串 “omm” 是最小的。于是称字符串 “omm” 是五彩斑斓的串字符串 “moo” 无论是在给定满足 “om” 的字典序此时有omm ommnom moo mom中还是在给定满足 “mo” 的字典序此时有 mom moo omm ommnom中字符串 “omm” 均不是最小的。于是认为字符串 “moo” 不是五彩斑斓的串字符串 “mom” 在给定满足 “mo” 的字典序中总存在mom moo omm ommnom此时字符串 “mom” 是最小的。于是称字符串 “mom” 是五彩斑斓的串字符串 “ommnom” 在给定的字符串集中存在它的前缀字符串 “omm”因此无论在怎样的字典序下字符串 “ommnom” 总是比 “omm” 大因此字符串 “ommnom” 不可能是五彩斑斓的串。 为了判断一个字符串是否为 “五彩斑斓的串”最直接的办法就是枚举全部的字典序并求出在各字典序下的最小的字符串。但这样的求解在极端情况下即给定的字符串集中含有全 26 个字符将存在 26! 个字典序这肯定超时无疑此时要如何求解这个问题呢这便需要用到字典树。 字典树是一种可高效地存储和检索字符串的树形数据结构例如对于题目给出的字符串集 {omm, moo, mom, ommnom}可构建如下字典树 需要说明的是字典树并没有严格的字母表顺序他只是一种存储结构。所以在上面的字典树中各分支之间的位置关系并不代表这些字符之间的顺序他们彼此之间的地位对等。 为了找到本题所说的 “五彩斑斓的串”我们必须单独构建一个字母之间大小关系的表。为此定义一个规格为 26×26 的矩阵 m它的含义如下 m [ i ] [ j ] 1 m[i][j] 1 m[i][j]1表示字符 i i i 的字典序大于字符 j j j m [ i ] [ j ] − 1 m[i][j] -1 m[i][j]−1表示字符 i i i 的字典序小于字符 j j j。 根据这个矩阵以及字典树我们便能快速的判断出一个字符是否能成为一个 “五彩斑斓的串”。以题目给出的字符串集为例下面阐述其具体的判别过程 字符串 “omm”首先初始化矩阵 m 中的各取值为 0。接下来来到字典树的第一层该层有两个分支且对应节点中存放的字符分别为 “o” 和 “m”。为了使得字符串 “omm” 最小就必须要求字母 “o” 的字典序小于 “m”于是置 m[o][m] -1, m[m][o] 1。接下来沿着字符串 “omm” 的分支继续往下来到第二层该层仅有一个分支因此无需添加字典序规则。继续往下来到第三层该层依然只有一个分支因此无需添加字典序规则。字符串 “omm” 扫描结束从矩阵 m 中的结果可知要使字符串 “omm” 成为 “五彩斑斓的串” 的字典序为 “om”。字符串 “moo”首先初始化矩阵 m 中的各取值为 0。接下来来到字典树的第一层该层有两个分支且对应节点中存放的字符分别为 “o” 和 “m”。为了使得字符串 “moo” 最小就必须要求字母 “m” 的字典序小于 “o”于是置 m[m][o] -1, m[o][m] 1。接下来沿着字符串 “moo” 的分支继续往下来到第二层该层仅有一个分支因此无需添加字典序规则。继续往下来到第三层该层有两个分支且对应节点中存放的字符分别为 “o” 和 “m”。为了使得字符串 “moo” 最小就必须要求字母 “o” 的字典序小于 “m”但是现存 m 矩阵中已经存在 m[m][o] -1, m[o][m] 1。这与现在的要求相矛盾因此认为字符串 “moo” 不可能成为 “五彩斑斓的串”。字符串 “mom”首先初始化矩阵 m 中的各取值为 0。接下来来到字典树的第一层该层有两个分支且对应节点中存放的字符分别为 “o” 和 “m”。为了使得字符串 “mom” 最小就必须要求字母 “m” 的字典序小于 “o”于是置 m[m][o] -1, m[o][m] 1。接下来沿着字符串 “omm” 的分支继续往下来到第二层该层仅有一个分支因此无需添加字典序规则。继续往下来到第三层该层有两个分支且对应节点中存放的字符分别为 “o” 和 “m”。为了使得字符串 “mom” 最小就必须要求字母 “m” 的字典序小于 “o”这与现存 m 矩阵中的规则一致故无需更新。字符串 “mom” 扫描结束从矩阵 m 中的结果可知要使字符串 “mom” 成为 “五彩斑斓的串” 的字典序为 “mo”。字符串 “ommnom”在给定的字符串集中存在它的前缀字符串 “omm”因此对 m 矩阵进行更新时其前半段的更新与对字符串 “omm” 的更新一致。接下来当程序继续往下扫描时它将读取到一个字符结束标记即系统将识别到字符串 “ommnom” 在给定字符串集中存在前缀因此直接退出程序并反馈字符串 “ommnom” 不可能是五彩斑斓的串。 此外需要注意一点字母之间的大小关系是可传递的。例如假设现在得到了字母顺序 “abc”。接下来当我们得到一个新的顺序 “cd” 时除了要更新 m[c][d] 和 m[d][c]还需要将所有原先就比 “c” 小的字母统一规定小于 “d”即需要更新 m[a][d]、m[d][a]、m[b][d] 和 m[d][b]所有原先就比 “d” 大的字母统一规定大于 “c”。即要充分考虑 m 矩阵中的所有现存规则并实时地动态更新。 下面给出基于以上思路写出的完整代码已 AC /*MT2175 五彩斑斓的串 */ #includebits/stdc.h using namespace std;const int N 3e55; int n, ans[N], cnt; string s[N]; char tmp[N];struct Trie{// m 矩阵指示了各字符的大小关系从而形成一个字典序 // m[i][j] 1表示字符 i 的字典序大于字符 j // m[i][j] -1表示字符 i 的字典序小于字符 j // A 数组存放所有比指定字符小的字符B 数组存放所有比指定字符大的字符 int id, nex[N][26], m[26][26], A[30], B[30];// 字符串的结束标记 bool end[N];// 插入字符串 void insert(string s){int p 0, ls.size(), c;// 构建字符串中各字符在字典树中的位置关系 for(int i0; il; i){c s[i] - a;if(!nex[p][c]) nex[p][c] id;p nex[p][c];}end[p]1; }// 判断给定字符串是否存在一个能使其最小的字典序 bool check(string s){// 每次执行判断时必须重置字符的大小关系矩阵 memset(m, 0, sizeof(m));int p0, l s.size();for(int i0; il; i){int c s[i] - a;// 1. 查看是否有已知的更短的前缀字符串 if(end[p]) return false;// 2. 查看是否有兄弟之间的关系 for(int j0; j26; j)if(nex[p][j] m[c][j]0 j!c)return false;// 3. 更新前后序的节点组合A[0] B[0] 0;for(int j0; j26; j) {// 如果存在兄弟节点要使当前字符串为“五彩斑斓的串”即当前字符在字典序里最小 // 就必须使得字符 c 小于 字符 j即 m[c][j] -1 if(nex[p][j] j!c){m[c][j] -1;m[j][c] 1;// 接下来必须将字符 c 的大小关系传递至整个已有的字典序 m 中 for(int k0; k26; k){// 维护前序字符集的规则所有本来就比 c 小的字符也应该小于 j if(m[c][k] 1){// 将所有比字符 c 小的字符记录进入 A 数组为了节省计数变量这里就用 A[0] A[A[0]] k;m[j][k] 1;m[k][j] -1;}// 维护后序字符集的规则所有本来就比 j 大的字符也应该大于 c if(m[j][k] -1){// 将所有比字符 c 大的字符记录进入 B 数组为了节省计数变量这里就用 B[0] B[B[0]] k;m[c][k] -1;m[k][c] 1;}}}}// 建立字典关系A 数组中的所有字符自然是小于 B 数组中的所有字符 for(int j1; jA[0]; j)for(int k1; kB[0]; k){m[A[j]][B[k]] -1;m[B[k]][A[j]] 1;}p nex[p][c];}return true;} }; Trie trie;int main( ) {// 获取输入cinn;// 插入所有的字符串构建字典树for(int i1; in; i){cins[i];trie.insert(s[i]);}// 依次扫描每个字符串检测其是否能成为“五彩斑斓的串”for(int i1; in; i){if(trie.check(s[i]))ans[cnt] i;}// 输出coutcntendl;for(int i1; icnt; i)couts[ans[i]]endl;return 0; }END