题目描述本题模拟Scrabble\texttt{Scrabble}Scrabble游戏的一个变种。给定一副Scrabble\texttt{Scrabble}Scrabble棋盘15×1515 \times 1515×15含双倍/三倍字母分、双倍/三倍单词分等特殊位置对手已放置了一个水平单词长度不超过777且其中一个字母落在棋盘中心双倍单词分位置。你手中有777个字母需要放置一个垂直单词长度不超过777该单词必须与对手的单词恰好共用一个字母即你的单词中使用对手单词的某个字母且该字母在棋盘上的位置固定。你需要从给定词典中选出得分最高的单词并输出该单词、你使用的对手单词中的字母位置111基、你的单词中该字母的位置111基以及你的得分包括字母分、字母位置加成、单词加成和全用777个字母的505050分奖励。输入格式输入包含两部分先是一系列谜题每行一个然后是一个词典每行一个单词。每个谜题行由一个777个字母的字符串你的字母、一个数字111到777表示对手单词中落在中心位置的字母序号以及对手的单词组成三者直接相连无空格。词典部分每行一个单词全部为大写字母长度不超过888数量不超过300003000030000。输入以文件结束符终止。输出格式对于每个谜题输出一行依次为你的单词左对齐占888个字符不足补空格你使用的对手单词中的字母序号右对齐占222个字符你的单词中该字母的位置右对齐占222个字符你的得分右对齐占444个字符样例输入RDAWEER1ABDOMEN OADPZBI5OPIATE RTWXAIB3SMELL AEFGOOS1BILLION CYOKDAR7DOLTISH CYOKDAR1DOLTISH ABDOMEN ABSTAIN AXIS BILLION CURRENT DOCKYARD DOLTISH ELEPHANT FALSE FALSETTO GRAPE HEROIC IMPETUS JOKE JOKER OPIATE SMELL VERIFY WANDER XANTHIC ZAP ZENITH输出1234567890123456 WANDER 7 3 20 ZAP 4 2 27 AXIS 1 4 27 FALSE 3 3 18 DOCKYARD 1 1 100 DOCKYARD 1 8 122题目分析本题核心是枚举所有可能单词并计算每个单词在特定棋盘位置上的得分。由于单词长度不超过888词典大小300003000030000每个谜题需要检查所有单词但每个单词需与你的字母和对手字母匹配因此实际检查量有限。关键是正确计算得分包括字母基础分、字母位置加成双倍/三倍字母、单词整体加成双倍/三倍单词以及505050分奖励。解题思路棋盘预处理将15×1515 \times 1515×15棋盘特征存入二维数组board[15][15]其中111表示普通222双倍字母333三倍字母444双倍单词555三倍单词。字母分值建立数组scores[26]对应A–Z的基础分。对每个谜题解析出你的字母串candidates、对手单词previous以及对手单词中落在中心位置的字母序号head111基。由于对手单词水平放置中心位置在棋盘第888列索引777。对手单词的第head个字母落在中心因此该单词第iii个字母000基所在的列坐标为column 8 - head i即column 7 - head i000基。你的单词垂直放置必须与对手单词在第i个字母处相交。因此你的单词的第j个字母000基将与对手的第i个字母重合其行坐标为row 7 - j因为你的单词垂直放置第j个字母在中心位置上方/下方中心在第888行索引777所以row 7 - j。枚举词典中的每个单词word检查它是否可由candidates previous[i]的字母组成即你的字母加上对手的一个字母且必须包含previous[i]。对于每个可能的相交位置对手单词中的位置i你的单词中的位置j且word[j] previous[i]计算得分遍历你的单词的每个位置k000到len-1计算该字母的基础分score scores[word[k]-A]。获取该位置在棋盘上的特征feature board[row k][column i]注意row k表示行坐标column i表示列坐标因为你的单词垂直对手单词水平相交点固定。若k j即该字母是相交字母其位置已被对手占用因此不应用任何位置加成字母或单词。否则若feature 3表示字母位置加成则将该字母分乘以feature若feature 3表示单词加成则将单词倍数times乘以(feature - 2)因为444代表222倍555代表333倍。累加字母分。单词总分 字母分之和 ×times。若你的单词用到了全部777个字母则额外加505050分。记录最高得分对应的单词、相交位置iii和jjj需转为111基输出。输出按格式输出最佳单词、bestI、bestJ、bestScores。复杂度分析每个谜题枚举词典中所有单词D≤30000D \le 30000D≤30000每个单词检查字母组成和所有可能相交位置最多7×7497 \times 7 497×749种得分计算O(L)O(L)O(L)L≤8L \le 8L≤8总时间复杂度O(P⋅D⋅49⋅8)O(P \cdot D \cdot 49 \cdot 8)O(P⋅D⋅49⋅8)在可接受范围内PPP较小。空间复杂度O(D⋅L)O(D \cdot L)O(D⋅L)。代码实现// Scrabble// UVa ID: 655// Verdict: Accepted// Submission Date: 2017-06-23// UVa Run Time: 0.380s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intscores[]{1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};intboard[15][15]{{5,1,1,2,1,1,1,5,1,1,1,2,1,1,5},{1,4,1,1,1,3,1,1,1,3,1,1,1,4,1},{1,1,4,1,1,1,2,1,2,1,1,1,4,1,1},{2,1,1,4,1,1,1,2,1,1,1,4,1,1,2},{1,1,1,1,4,1,1,1,1,1,4,1,1,1,1},{1,3,1,1,1,3,1,1,1,3,1,1,1,3,1},{1,1,2,1,1,1,2,1,2,1,1,1,2,1,1},{5,1,1,2,1,1,1,4,1,1,1,2,1,1,5},{1,1,2,1,1,1,2,1,2,1,1,1,2,1,1},{1,3,1,1,1,3,1,1,1,3,1,1,1,3,1},{1,1,1,1,4,1,1,1,1,1,4,1,1,1,1},{2,1,1,4,1,1,1,2,1,1,1,4,1,1,2},{1,1,4,1,1,1,2,1,2,1,1,1,4,1,1},{1,4,1,1,1,3,1,1,1,3,1,1,1,4,1},{5,1,1,2,1,1,1,5,1,1,1,2,1,1,5}};boolcontains(stringword,stringcandidates){stringnextWord(word);for(intk0;kcandidates.length();k){intidxnextWord.find(candidates[k]);if(idxnextWord.npos)returnfalse;elsenextWord[idx]1;}returntrue;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string line;vectorstringpuzzles,dictionary;while(cinline,line.length()8)puzzles.push_back(line);dictionary.push_back(line);while(cinline)dictionary.push_back(line);string candidates,previous;inthead;for(autoentry:puzzles){for(inti0;ientry.length();i)if(isdigit(entry[i])){candidatesentry.substr(0,i);previousentry.substr(i1);headentry[i]-0;break;}string bestWord,nextWord;intbestScores0,bestI,bestJ;intcolumn8-head;for(inti0;iprevious.length();i){for(autoword:dictionary){nextWord.assign(candidates),nextWord.push_back(previous[i]);if(!contains(nextWord,word))continue;for(intj0;jword.length();j)if(word[j]previous[i]){inttempScores0,times1;introw7-j;for(intk0;kword.length();k){intfeatureboard[rowk][columni];intscorescores[word[k]-A];if(feature3){if(k!j)score*feature;}else{if(k!j)times*(feature-2);}tempScoresscore;}tempScores*times;nextWord.assign(word),nextWord[j]1;if(contains(nextWord,candidates))tempScores50;if(tempScoresbestScores){bestScorestempScores;bestWordword;bestIi1;bestJj1;}}}}coutsetw(8)leftbestWord;coutsetw(2)rightbestI;coutsetw(2)rightbestJ;coutsetw(4)rightbestScores\n;}return0;}总结本题通过枚举词典单词和所有可能的相交位置并结合棋盘位置加成规则计算得分从而找出最佳单词。关键点包括正确解析谜题格式字母串、数字、对手单词。精确计算每个单词的得分注意相交位置不得使用加成且单词加成倍数累积。检查全用777个字母的505050分奖励。输出格式对齐左/右对齐宽度控制。该解法体现了复杂规则模拟和枚举优化的结合适合作为竞赛题练习。