题目描述题目定义了一类特殊单词单词中的字母必须严格递增即后一个字母在字母表中的位置必须大于前一个字母。例如abc\texttt{abc}abc、aep\texttt{aep}aep、gwz\texttt{gwz}gwz都是有效的三字母单词而aab\texttt{aab}aab、are\texttt{are}are、cat\texttt{cat}cat不是。所有有效单词按字典序排列每个单词对应一个序号。例如a→1\texttt{a} \rightarrow 1a→1b→2\texttt{b} \rightarrow 2b→2z→26\texttt{z} \rightarrow 26z→26ab→27\texttt{ab} \rightarrow 27ab→27ac→28\texttt{ac} \rightarrow 28ac→28az→51\texttt{az} \rightarrow 51az→51bc→52\texttt{bc} \rightarrow 52bc→52vwxyz→83681\texttt{vwxyz} \rightarrow 83681vwxyz→83681对于每个输入的单词判断其是否有效。若无效则输出000若有效则输出其在列表中的序号。输入格式输入包含多行每行一个单词。单词由小写字母组成长度至少为111最多为555。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个输入的单词输出一行一个整数表示该单词的序号若无效则为000。样例输入z a cat vwxyz输出26 1 0 83681题目分析本题的核心是计算给定有效单词在严格递增字母序列中的字典序序号。问题规模由于单词长度最多为555所有有效单词的总数为∑k15(26k) \sum_{k1}^{5} \binom{26}{k}k1∑5(k26)这是因为从262626个字母中任选kkk个不同的字母按升序排列唯一对应一个有效单词。计算得(261)(262)(263)(264)(265)263252600149506578083681 \binom{26}{1} \binom{26}{2} \binom{26}{3} \binom{26}{4} \binom{26}{5} 26 325 2600 14950 65780 83681(126)(226)(326)(426)(526)263252600149506578083681因此最大序号为836818368183681。方法一预处理所有有效单词由于总数不超过10510^5105可以预先生成所有有效单词并建立从单词到序号的映射。生成方法从单个字母开始a\texttt{a}a到z\texttt{z}z序号从111开始。使用广度优先搜索BFS\texttt{BFS}BFS或递归生成对于当前单词在其末尾添加一个比最后一个字母大的字母形成新单词。将生成的新单词存入映射序号递增。生成所有长度不超过555的单词后对于每个输入单词直接查表输出。方法二组合数直接计算对于有效单词ss1s2…sks s_1 s_2 \ldots s_kss1s2…sk其序号等于所有长度小于kkk的有效单词总数。加上长度等于kkk且字典序小于sss的有效单词数。长度小于kkk的总数为∑i1k−1(26i) \sum_{i1}^{k-1} \binom{26}{i}i1∑k−1(i26)对于长度等于kkk且字典序小于sss的单词可以按位计算对于第111位可以从a\texttt{a}a开始枚举到s1−1s_1 - 1s1−1每个选择的字母ccc对应从剩余字母中选k−1k-1k−1个的排列数。对于第222位固定第111位为s1s_1s1枚举第222位从s11s_1 1s11到s2−1s_2 - 1s2−1每个选择对应从剩余字母中选k−2k-2k−2个的排列数。依此类推。参考代码采用了第一种方法预处理实现简单且直观。有效性判断输入单词需要先判断是否严格递增即每个字符大于前一个字符。若不满足直接输出000。复杂度分析预处理生成所有有效单词最多生成836818368183681个单词每个单词通过BFS\texttt{BFS}BFS扩展最多262626次总操作数约2×1062 \times 10^62×106完全可接受。查询为O(1)O(1)O(1)。代码实现// Word Index// UVa ID: 417// Verdict: Accepted// Submission Date: 2016-07-15// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;mapstring,intindexer;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string lettersabcdefghijklmnopqrstuvwxyz;intcounter1;queuestringgenerator;for(inti0;iletters.length();i){generator.push(string(1,letters[i]));indexer[string(1,letters[i])]counter;}while(!generator.empty()){string currentgenerator.front();generator.pop();if(current.length()5)continue;for(inti0;iletters.length();i){if(letters[i]current.back()){generator.push(currentletters[i]);indexer[currentletters[i]]counter;}}}string line;while(cinline){boolvalidtrue;for(inti0;iline.length()-1;i)if(line[i]line[i1]){validfalse;break;}if(!valid){cout0endl;continue;}coutindexer[line]endl;}return0;}
UVa 417 Word Index
发布时间：2026/6/7 16:31:46
题目描述题目定义了一类特殊单词单词中的字母必须严格递增即后一个字母在字母表中的位置必须大于前一个字母。例如abc\texttt{abc}abc、aep\texttt{aep}aep、gwz\texttt{gwz}gwz都是有效的三字母单词而aab\texttt{aab}aab、are\texttt{are}are、cat\texttt{cat}cat不是。所有有效单词按字典序排列每个单词对应一个序号。例如a→1\texttt{a} \rightarrow 1a→1b→2\texttt{b} \rightarrow 2b→2z→26\texttt{z} \rightarrow 26z→26ab→27\texttt{ab} \rightarrow 27ab→27ac→28\texttt{ac} \rightarrow 28ac→28az→51\texttt{az} \rightarrow 51az→51bc→52\texttt{bc} \rightarrow 52bc→52vwxyz→83681\texttt{vwxyz} \rightarrow 83681vwxyz→83681对于每个输入的单词判断其是否有效。若无效则输出000若有效则输出其在列表中的序号。输入格式输入包含多行每行一个单词。单词由小写字母组成长度至少为111最多为555。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个输入的单词输出一行一个整数表示该单词的序号若无效则为000。样例输入z a cat vwxyz输出26 1 0 83681题目分析本题的核心是计算给定有效单词在严格递增字母序列中的字典序序号。问题规模由于单词长度最多为555所有有效单词的总数为∑k15(26k) \sum_{k1}^{5} \binom{26}{k}k1∑5(k26)这是因为从262626个字母中任选kkk个不同的字母按升序排列唯一对应一个有效单词。计算得(261)(262)(263)(264)(265)263252600149506578083681 \binom{26}{1} \binom{26}{2} \binom{26}{3} \binom{26}{4} \binom{26}{5} 26 325 2600 14950 65780 83681(126)(226)(326)(426)(526)263252600149506578083681因此最大序号为836818368183681。方法一预处理所有有效单词由于总数不超过10510^5105可以预先生成所有有效单词并建立从单词到序号的映射。生成方法从单个字母开始a\texttt{a}a到z\texttt{z}z序号从111开始。使用广度优先搜索BFS\texttt{BFS}BFS或递归生成对于当前单词在其末尾添加一个比最后一个字母大的字母形成新单词。将生成的新单词存入映射序号递增。生成所有长度不超过555的单词后对于每个输入单词直接查表输出。方法二组合数直接计算对于有效单词ss1s2…sks s_1 s_2 \ldots s_kss1s2…sk其序号等于所有长度小于kkk的有效单词总数。加上长度等于kkk且字典序小于sss的有效单词数。长度小于kkk的总数为∑i1k−1(26i) \sum_{i1}^{k-1} \binom{26}{i}i1∑k−1(i26)对于长度等于kkk且字典序小于sss的单词可以按位计算对于第111位可以从a\texttt{a}a开始枚举到s1−1s_1 - 1s1−1每个选择的字母ccc对应从剩余字母中选k−1k-1k−1个的排列数。对于第222位固定第111位为s1s_1s1枚举第222位从s11s_1 1s11到s2−1s_2 - 1s2−1每个选择对应从剩余字母中选k−2k-2k−2个的排列数。依此类推。参考代码采用了第一种方法预处理实现简单且直观。有效性判断输入单词需要先判断是否严格递增即每个字符大于前一个字符。若不满足直接输出000。复杂度分析预处理生成所有有效单词最多生成836818368183681个单词每个单词通过BFS\texttt{BFS}BFS扩展最多262626次总操作数约2×1062 \times 10^62×106完全可接受。查询为O(1)O(1)O(1)。代码实现// Word Index// UVa ID: 417// Verdict: Accepted// Submission Date: 2016-07-15// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;mapstring,intindexer;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string lettersabcdefghijklmnopqrstuvwxyz;intcounter1;queuestringgenerator;for(inti0;iletters.length();i){generator.push(string(1,letters[i]));indexer[string(1,letters[i])]counter;}while(!generator.empty()){string currentgenerator.front();generator.pop();if(current.length()5)continue;for(inti0;iletters.length();i){if(letters[i]current.back()){generator.push(currentletters[i]);indexer[currentletters[i]]counter;}}}string line;while(cinline){boolvalidtrue;for(inti0;iline.length()-1;i)if(line[i]line[i1]){validfalse;break;}if(!valid){cout0endl;continue;}coutindexer[line]endl;}return0;}
 详解：虚拟路径到物理路径的映射原理与实战)
