UVa 140 Bandwidth

设出现的字母数为 \(n\)，注意到 \(n\) 很小（\(n\leq8\)），因此枚举全排列即可，尽管可以 DFS 然后剪枝。时间复杂度为 \(\mathcal O(n!n)\)。

这题在洛谷上评蓝...主要难点在于奇葩的输入格式。我们考虑按顺序遍历 \(\mathtt{A\sim Z}\)，把在读入字符串中出现的分别以编号和实体的方式存进数组 \(\text{id[],letter[]}\)，这方便我们之后按顺序计算全排列。

然后，遍历读入的字符串，设置两个指针 \(p,q\)，其中 \(p\) 每次遇到一个:再停下来；\(q\) 每次遇到一个;再停下来；然后 \(\text s[p\sim q]\) 构成了一组对应关系。设置两个 vector \(u,v\)，遍历 \([p+1,q-1]\) ，每次u.push_back(id[(int)s[p-1]]);v.push_back(id[(int)s[i]]);。这样，在之后计算带宽时，就可以通过这两个 vector 找到距离。

在计算带宽时，还要记得把对应字母的位置记录一下。

#include
#include
#include
#include
#include
#include
using namespace std;
int id[1050],letter[15];
int main()
{
    char s[1050];
    while(scanf("%s",s)==1&&s[0]!='#')
    {
        int n=0;
        for(char ch='A';ch<='Z';ch++)
        {
            if(strchr(s,ch)!=NULL)
            {
                id[(int)ch]=n++;
                letter[id[(int)ch]]=(int)ch;
            }
        }
        int len=strlen(s),p=0,q=0;
        vectoru,v;
        while(1)
        {
            while(p %d\n",ans);
    }
    return 0;
}