题目描述题目要求将一行文本由单词组成单词间用一个空格分隔重新格式化为指定长度以点dot\texttt{dot}dot为单位。每个字符有固定宽度单位点空格即单词间的分隔宽度可变用于填充以对齐左右边界。需要输出格式化后的行其中单词内的字母间隔用固定点数由规则计算单词间的间隔用填充点数。输出格式中字母间的间隔用/(n)表示单词间的间隔用/后跟点数表示。要求行首行尾不能有空白点。输入格式输入包含多组测试用例每组两行第一行目标长度NNNN≤5000N \le 5000N≤5000。第二行原始文本单词间用单个空格分隔无首尾空格至少两个单词总字符数≤80\le 80≤80。最后以一行0 SYMIBAA结束不处理。输出格式对于每组输入输出一行格式化后的文本格式如A/(4)I/(4)M/(18)S/...。样例输入250 AIM SSY ABABA 200 SSSS AAAA 130 AA B AA 0 SYMIBAA输出A/(4)I/(4)M/(18)S/(4)S/(4)Y/(19)A/(4)B/(4)A/(4)B/(4)A/ S/(7)S/(7)S/(7)S/(22)A/(7)A/(7)A/(7)A A/(5)A/(15)B/(16)A/(5)A题目分析本题的核心是计算字符宽度确定字母间隔和单词间隔的填充点数。字符宽度表字符宽度A18B17I10M20S16Y13空格可变字母间隔规则单词内相邻字母的最小间隔为333点。字母间隔点数 ⌊单词间隔点数/3⌋\lfloor \text{单词间隔点数} / 3 \rfloor⌊单词间隔点数/3⌋但不得小于333实际规则字母间隔由单词间隔决定且至少为333。具体计算时先确定单词间隔的基准值再按比例分配。单词间隔规则单词间的最小间隔为101010点无上限。总点数NNN减去所有字符宽度之和后剩余点数用于单词间的间隔填充。这些间隔点数应尽量平均分配多余的从行末开始逐个加111。算法步骤计算所有字符的宽度总和不包括空格记为charSum\textit{charSum}charSum。设单词数为www则单词间有w−1w-1w−1个间隔。设字母间隔的总点数为L(w−1)×letterGapL (w-1) \times \text{letterGap}L(w−1)×letterGap其中letterGap\text{letterGap}letterGap为每个字母间隔的点数。设单词间隔的总点数为S(w−1)×wordGapS (w-1) \times \text{wordGap}S(w−1)×wordGap。总点数NcharSumLSN \textit{charSum} L SNcharSumLS。已知letterGap⌊wordGap/3⌋\text{letterGap} \lfloor \text{wordGap} / 3 \rfloorletterGap⌊wordGap/3⌋且letterGap≥3\text{letterGap} \ge 3letterGap≥3wordGap≥10\text{wordGap} \ge 10wordGap≥10。枚举wordGap\text{wordGap}wordGap从101010开始递增计算letterGap\text{letterGap}letterGap检查是否满足等式。由于NNN不大直接枚举可行。输出格式字母间A/(4)表示在 A 和下一个字母之间有444个点。单词间S/后跟点数但注意单词间的点数已经包含在字母间隔计算中实际上输出中单词间的分隔符是/(n)吗从样例看单词间直接用/后跟数字表示没有字母。但A/(4)I/(4)M/(18)S/...中的S/实际上是单词 S 后的间隔需要仔细分析。复杂度分析枚举wordGap\text{wordGap}wordGap至多N/10N/10N/10次可接受。代码实现// Filling the Gaps// UVa ID: 552// Verdict: Accepted// Submission Date: 2017-05-11// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intvisited[65536];voidbacktrack(inti,intv,stringpattern){if(ipattern.length())visited[v]1;else{v*2;if(pattern[i]*){backtrack(i1,v,pattern);backtrack(i1,v1,pattern);}else{vpattern[i]-0;backtrack(i1,v,pattern);}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intlength,n;while(cinlengthn){if(length0n0){coutYES 0\n;break;}vectorstringwords;vectorintids;string word;for(inti1;in;i){cinword;intid0;for(intj0;jword.size();j){id*2;if(word[j]*)id1;}words.push_back(word);ids.push_back(id);}sort(ids.begin(),ids.end());boolduplicatedfalse;for(inti0;iids.size()-1;i)if(ids[i]ids[i1]){duplicatedtrue;break;}if(duplicated){coutNO\n;continue;}memset(visited,0,sizeof(visited));for(inti0;iwords.size();i)backtrack(0,0,words[i]);inttotalpow(2,length),appeared0;for(inti0;itotal;i)appearedvisited[i];coutYES appeared\n;}return0;}