Gym 101612C Consonant Fencity

时间:2024-01-03 12:32:32

原题传送门

题意:给定一个只含小写字母的字符串,假设aeiouyw为元音字母,现在要把一些字母变为大写,要求相同字母的大小写必须相同,统计变化后的字符串中有多少对相邻同为辅音字母大小写不一样的字符对,输出能这样的字符对数量最大的字符串。字符串长度≤106

分析:初读题,106的确吓了我一跳:这道题不像是有线性解法的样子。但只要仔细读题,看到相同字母的大小写必须相同这个条件,就不难发现其实106只是表象,真正有用的是字母——只要枚举字母的大小写情况,字符串多长根本不用在意。当然也不是真的不在意,考虑到相邻的字符对至多只有106种,我们完全可以预处理,将这些字符对的关系存在一个26*26的数组sum里,其中sum[i][j]表示左边为i,右边为j的字符对的数目,这样利用状态压缩(不是状压DP。。),可以在预处理106和主程序226*262的时间复杂度内求解,但是看起来不够?题目已经贴心地为我们准备了大餐——首先有7个元音字母,也就是说枚举的状态不会大于219,这就差不多够了。出题人还生怕卡掉常数大的正解,将时限设为3s。一句话,想出正解没有TLE的理由。

注意几个细节:为了能方便枚举219个状态,建议将26个字符中的辅音字母与0-18进行一一对应,最后输出时再将状态转化回来,这样避免了表面枚举219,实际上枚举226的尴尬。但是这样带来了一个问题(至少对我来说是个问题),那就是对应数组的使用有很多细节要注意,一不留神就会将下标错开一位,导致整个字符串就不对了。

代码