题解：P7021 [NWRRC 2017] Consonant Fencity

· · 题解

题意

给你一串字符串，改变一些字母的大小写使得所有相同的字母大小写相同，并且辅音密度尽可能的小， 辅音密度指有多少组相邻且大小写不同的辅音字母。

思路

大致思路：由题可知元音字母有 7 个，则辅音字母有 19 个，那么我们可以直接暴力搜索所有可能，对于每一种可能都求取当前的辅音密度，求出最大的辅音密度并记录当前字母大小写情况。

那么如何快速求取辅音密度呢？我们可以用 c[i][j] 来表示 ASCLL 码为 i 和 j 的两个字母相邻的次数，这样我们只用遍历 26^2 次就可以求出当前情况的辅音密度。

for (int i = 97; i < 123; ++ i) {
            for (int j = 97; j < 123; ++ j) {
                if (st[i] && !st[j]) res += c[i][j]; // st[i]和st[j]表示ASCLL码为i和j的两个字母的大小情况
            }
        }

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 200; // 'z'的ASCLL码为122所以至少要开123的数组

int c[N][N], maxn;
bool st[N], ans[N]; // st记录每一种情况的字母大小情况，ans记录辅音密度最大时的每个字母大小写情况
char g[] = {' ', 'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'x', 'z'}; // 方便dfs暴搜

bool fy(char s) { // 判断当前字母是否是辅音字母
    if (s != 'a' && s != 'e' && s != 'i' && s != 'o' && s != 'u' && s != 'w' && s != 'y') return true;
    return false;
}

void dfs(int x) { // 用dfs搜索每一种可能
    if (x > 19) {
        int res = 0;
        for (int i = 97; i < 123; ++ i) {
            for (int j = 97; j < 123; ++ j) {
                if (st[i] && !st[j]) res += c[i][j];
            }
        }
        if (maxn < res) {  //如果这种情况比目前最大的辅音密度还大的话就更新
            maxn = res;
            for (int i = 97; i < 123; ++ i) ans[i] = st[i];
        }

        return;
    }
    st[g[x]] = true; //选或不选下一个字母
    dfs(x + 1);
    st[g[x]] = false;
    dfs(x + 1);
}

signed main() {
    string s; cin >> s;

    for (int i = 0; i < s.size() - 1; ++ i) {
        if (fy(s[i]) && fy(s[i + 1])) {
            int x = s[i], y = s[i + 1];
            c[x][y] += 1;  // 使用二维数组记录这两个相邻字母相邻了多少次
            c[y][x] += 1;
        }
    }

    dfs(1); // x为当前字母在g数组中的下标

    for (int i = 0; i < s.size(); ++ i) { // 输出
        if (ans[s[i]]) cout << char(s[i] - 32);
        else cout << s[i];
    }

    return 0;
}