題干：

把26個(gè)字母分成19個(gè)輔音字母和7個(gè)元音字母，讓你通過 將某些字母改為大寫狀態(tài)，使得字符串中連續(xù)的兩個(gè)大小寫狀態(tài)不同的輔音字母組成的字母對(duì)數(shù)量最多，輸出該狀態(tài)下的字符串。注意輸出的字符串中同一字母必須形態(tài)統(tǒng)一，也就是對(duì)于同一個(gè)字母，不能既有大寫狀態(tài)的，也有小寫狀態(tài)的。如果有多種可能的解，輸出任意一種。?

解題報(bào)告：

注意到除去元音字母，還剩下19個(gè)輔音字母，這樣我們第一步可以2^19枚舉變換的福音字母。

接下來首先想到的是O(n)的check，但是注意到其實(shí)需要統(tǒng)計(jì)的信息只是相鄰字母無序?qū)Χ?#xff0c;而無序?qū)Φ姆N類一共19*19種。所以我們check的時(shí)候不需要跑一遍字符串，只需要統(tǒng)計(jì)著19*19個(gè)無序?qū)?shù)量即可。

總復(fù)雜度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]]++;//已對(duì)應(yīng)到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++) {//枚舉不同的兩個(gè)數(shù) 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

?

總結(jié)

以上是生活随笔為你收集整理的【Gym - 101612C】【2017-2018NEERC】Consonant Fencity（状压枚举，预处理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。