UVa 553 Simply Proportion

题目描述

题目要求将一行文本（由单词组成，单词间用一个空格分隔）重新格式化为指定长度（以点dot\texttt{dot}dot为单位）。每个字符有固定宽度（单位：点），空格（即单词间的分隔）宽度可变，用于填充以对齐左右边界。需要输出格式化后的行，其中单词内的字母间隔用固定点数（由规则计算），单词间的间隔用填充点数。输出格式中，字母间的间隔用/(n)表示，单词间的间隔用/后跟点数表示。要求行首行尾不能有空白点。

输入格式

输入包含多组测试用例，每组两行：

• 第一行：目标长度NNN（N≤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

题目分析

本题的核心是计算字符宽度，确定字母间隔和单词间隔的填充点数。

字符宽度表

字母间隔规则

• 单词内相邻字母的最小间隔为333点。
• 字母间隔点数 =⌊单词间隔点数/3⌋\lfloor \text{单词间隔点数} / 3 \rfloor⌊单词间隔点数/3⌋，但不得小于333？实际规则：字母间隔由单词间隔决定，且至少为333。具体计算时，先确定单词间隔的基准值，再按比例分配。

单词间隔规则

• 单词间的最小间隔为101010点，无上限。
• 总点数NNN减去所有字符宽度之和后，剩余点数用于单词间的间隔填充。这些间隔点数应尽量平均分配，多余的从行末开始逐个加111。

算法步骤

1. 计算所有字符的宽度总和（不包括空格），记为charSum\textit{charSum}charSum。
2. 设单词数为www，则单词间有w−1w-1w−1个间隔。
3. 设字母间隔的总点数为L=(w−1)×letterGapL = (w-1) \times \text{letterGap}L=(w−1)×letterGap，其中letterGap\text{letterGap}letterGap为每个字母间隔的点数。
4. 设单词间隔的总点数为S=(w−1)×wordGapS = (w-1) \times \text{wordGap}S=(w−1)×wordGap。
5. 总点数N=charSum+L+SN = \textit{charSum} + L + SN=charSum+L+S。
6. 已知letterGap=⌊wordGap/3⌋\text{letterGap} = \lfloor \text{wordGap} / 3 \rfloorletterGap=⌊wordGap/3⌋，且letterGap≥3\text{letterGap} \ge 3letterGap≥3，wordGap≥10\text{wordGap} \ge 10wordGap≥10。
7. 枚举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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intvisited[65536];voidbacktrack(inti,intv,string&pattern){if(i>=pattern.length())visited[v]=1;else{v*=2;if(pattern[i]=='*'){backtrack(i+1,v,pattern);backtrack(i+1,v+1,pattern);}else{v+=pattern[i]-'0';backtrack(i+1,v,pattern);}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intlength,n;while(cin>>length>>n){if(length==0&&n==0){cout<<"YES 0\n";break;}vector<string>words;vector<int>ids;string word;for(inti=1;i<=n;i++){cin>>word;intid=0;for(intj=0;j<word.size();j++){id*=2;if(word[j]=='*')id+=1;}words.push_back(word);ids.push_back(id);}sort(ids.begin(),ids.end());boolduplicated=false;for(inti=0;i<ids.size()-1;i++)if(ids[i]==ids[i+1]){duplicated=true;break;}if(duplicated){cout<<"NO\n";continue;}memset(visited,0,sizeof(visited));for(inti=0;i<words.size();i++)backtrack(0,0,words[i]);inttotal=pow(2,length),appeared=0;for(inti=0;i<total;i++)appeared+=visited[i];cout<<"YES "<<appeared<<'\n';}return0;}