题干：
把26个字母分成19个辅音字母和7个元音字母，让你通过 将某些字母改为大写状态，使得字符串中连续的两个大小写状态不同的辅音字母组成的字母对数量最多，输出该状态下的字符串。注意输出的字符串中同一字母必须形态统一，也就是对于同一个字母，不能既有大写状态的，也有小写状态的。如果有多种可能的解，输出任意一种。
解题报告：
注意到除去元音字母，还剩下19个辅音字母，这样我们第一步可以2^19枚举变换的福音字母。
接下来首先想到的是O(n)的check，但是注意到其实需要统计的信息只是相邻字母无序对而已，而无序对的种类一共19*19种。所以我们check的时候不需要跑一遍字符串，只需要统计着19*19个无序对数量即可。
总复杂度O(19 * 19 * 2^19)
AC代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1e6 + 5; const int up = 19; char s[MAX]; int cnt[226]; int num[666][666]; int buf[2],pos[666]; bool yy[555];//是元音则为1 //char biao[55]; int tot; int ok[222],ansok[222];//在本轮中选还是没选 ll ans,anssta; int main() { freopen("consonant.in","r",stdin); freopen("consonant.out","w",stdout); yy['a']=yy['e']=yy['i']=yy['o']=yy['u']=yy['w']=yy['y']=1; for(char ch = 'a'; ch <= 'z'; ch++) { if(yy[ch] == 1) continue; pos[ch]=tot++; } // printf("%d\n",tot); // for(int i = 0; i<tot; i++) printf("%c ",biao[i]); scanf("%s",s+1); int len = strlen(s+1); for(int i = 2; i<=len; i++) { if(s[i] == s[i-1] || yy[s[i]] || yy[s[i-1]]) continue; // cnt[pos[s[i]]]++;cnt[pos[s[i-1]]]++; buf[0]=pos[s[i]];buf[1]=pos[s[i-1]]; if(buf[0] > buf[1]) swap(buf[0],buf[1]); num[buf[0]][buf[1]]++;//已对应到0~18 } for(int sta = 0; sta<(1<<up); sta++) { ll cur = 0; for(int bit = 0; bit<up; bit++) { if(sta & (1<<bit)) ok[bit]=1; else ok[bit]=0; } for(int i = 0; i<up; i++) { for(int j = i+1; j<up; j++) {//枚举不同的两个数 if(ok[i] + ok[j] == 1) cur += num[i][j]; } } if(cur > ans) { ans = cur; for(int bit = 0; bit<up; bit++) ansok[bit] = ok[bit]; } } for(int i = 1; i<=len; i++) { if(ansok[pos[s[i]]]) printf("%c",s[i] + 'A'-'a'); else printf("%c",s[i]); } return 0; } //qqqqq
