欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Gym101612 Problem C. Consonant Fencity(状压枚举)

程序员文章站 2022-06-09 19:02:41
...

Gym101612 Problem C. Consonant Fencity(状压枚举)

题意:
要求你将一些种类字母变成大写,使得最后相邻且都为辅音,且大小写不同的字符对最多。

思路:
一开始的贪心想法是只要碰到相邻两个辅音,就把后面这个变成大写。
但是题目要求是同一种类字符全部都得边,那就有后效性了。
不过观察可得,嘿嘿,辅音一共19个,2^19,那不就是直接状压枚举了吗。


#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
 
typedef long long ll;
using namespace std;
const int maxn = 1e6 + 7;
 
char s[maxn];
int vis[30];
int mp[30]; //每个位置对应的辅音字母
int MP[30]; //每个字母对应的辅音字母位置
int a[30][30];
 
int check(char ch) {
    if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'y' || ch == 'w') return 0; //小写元音
    return 1;
}
 
void init() {
    int cnt = 0;
    for(int i = 0;i < 26;i++) {
        if(check(i + 'a')) {
            mp[cnt] = i;
            MP[i] = cnt;
            cnt++;
        }
    }
}
 
int get(int sta) {
    memset(vis,0,sizeof(vis));
    for(int i = 0;i < 19;i++) {
        if(sta & (1 << i)) {
            vis[i] = 1;
        }
    }
    int ans = 0;
    for(int i = 0;i < 19;i++) {
        for(int j = 0;j < 19;j++) {
            if(i == j) continue;
            if(vis[i] && !vis[j]) {
                ans += a[mp[i]][mp[j]];
            }
        }
    }
    return ans;
}
 
int main() {
    freopen("consonant.in","r",stdin);
    freopen("consonant.out","w",stdout);
    
    init();
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    
    for(int i = 1;i <= n - 1;i++) {
        int num1 = check(s[i]),num2 = check(s[i + 1]);
        if(num1 && num2) {
            a[s[i] - 'a'][s[i + 1] - 'a']++;
            a[s[i + 1] - 'a'][s[i] - 'a']++;
        }
    }
    
    int sta = 0,mx = 0;
    for(int i = 0;i < (1 << 19);i++) {
        int num = get(i);
        if(num > mx) {
            mx = num;
            sta = i;
        }
    }
    
    get(sta);
    for(int i = 1;i <= n;i++) {
        if(!check(s[i])) printf("%c",s[i]);
        else if(vis[MP[s[i] - 'a']]) printf("%c",s[i] - 'a' + 'A');
        else printf("%c",s[i]);
    }
    return 0;
}