自动搬运

查看原文

来自洛谷，原作者为

	lizs ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็

搬运于2025-08-24 22:25:57，当前版本为作者最后更新于2025-08-19 18:33:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

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

思路

大致思路：由题可知元音字母有 $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;
}