【美团杯2020】字符串处理：查查查乐乐

大家好，我是讯享网，很高兴认识大家。

美团杯：签到题
我：一个小时自闭题

查查查乐乐

【题目】

“查查查乐乐”是一段古老神秘的咒语，只有被选中的魔法师才有资格使用这一段咒语并享用它所带来的力量；而如果这段咒语出现在了不具资格的魔法师的口中，这个魔法师将会遭到咒语的反噬并付出可怕的代价。

这个学期，镁团在一家魔法早教学校做兼职，他的任务是教小学生们魔法并帮助他们准备一年一度的全国魔法奥林匹克竞赛 (NOMP)。今天，镁团在整理图书的时候，突然发现一本课外教材中包含了 tt 段只由查和乐组成的咒语。让小学生们阅读这些咒语是非常危险的：他们可能会在无意识中念出“查查查乐乐”。

因此，作为一名富有责任心的儿童教师，镁团打算修改这些咒语，从而最大程度地杜绝这方面的隐患。镁团认为一段由查和乐组成的咒语是危险的当且仅当在删去咒语中的若干个字（也可以不删）后，剩下的咒语可能变成查查查乐乐。举例来说，“查查查乐乐”，“查查乐查乐乐” 就是危险的，而 “乐乐查查查”，“乐查乐乐查乐查查”就不是危险的。

对于每一段咒语，镁团都可以选择若干个位置并对这些位置进行修改：他可以把“查”变成“乐”，也可以把“乐”变成“查”。为了最大限度地保留教学效果，镁团希望使用尽可能少的修改来消除所有的危险性：对于每一段咒语，镁团都希望你帮他计算一下最少的修改次数。

对于每组数据，输入包含一行一个只包含字符 x 和 l 的字符串 s(1≤|s|≤100)，描述了一段咒语。其中 x 表示“查”，l 表示 “乐”。

3
xxxll
xxlxllllxl
xxxxxlllll

output

1
1
3

【题意翻译】
一个只包含x与l的串。修改一些（或不修改），修改是把x改成l，l改成x，使得最后串的子串（在原串删除几个字符或不删除）不包含xxxll。

【思路】
既然是修改，那优先修改肯定是最左边的x改成l，最右边的l改成x是**修改的。不然如果中间有一些修改之后，可能又会在某个子串里有xxxll了。

我们使用两个后缀数组
hz[i]表示下标i与其之后含有多少个l
hz[i]2表示下标i与其之后含有多少个x

接下来我们从左到右遍历。如果当前下标为i，然后考虑一些修改方法。
比较简单易得的有：如果hz2[i]<=1，表示后面两个l都没有，跳出。
然后我们再考虑修改x还是修改l。
在这里插入图片描述
【1】如果我们当时选择了这三个x，那么其前面的b个x都要修改成l，并且之后的c个l要修改到只剩下1个l。

【2】如果我们选择只修改x，那么只要把前面a个x、后面b个x与选择的这三个其一修改成l即可。（这一步可以单独拎出来，因为答案就是x的个数-2，当然要注意不能小于0）

我们只要用cnt记录一下当前有几个x了。如果cnt为3了，我们需要判断上面的两个方法，不断更新答案的最小值。然后就像尺取一样，我们舍弃掉最左边的x，cnt变为2，继续遍历该数组。

时间复杂度O(N)

AC代码：

#include <bits/stdc++.h> #define show(x) std::cerr << #x << "=" << x << std::endl #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); using namespace std; typedef long long ll; const int MAX=120; const int INF=1e9; const double EPS = 0.00000001; const ll MOD=; string aa; int hz[MAX]; ///后缀l的个数 int hz2[MAX]; ///后缀x的个数 int main() { 
    IOS; int T; cin >> T; while(T--){ 
    cin >> aa; memset(hz,0,sizeof(hz)); memset(hz2,0,sizeof(hz2)); for(int i=aa.size()-1;i>=0;--i){ 
    hz[i]=hz[i+1]; if(aa[i]=='l')hz[i]++; hz2[i]=hz2[i+1]; if(aa[i]=='x')hz2[i]++; } int cnt=0,you=0;; int ans=INF; for(int i=0;i<aa.size();++i){ 
    if(aa[i]=='l'){ 
    continue; } cnt++; if(cnt==3){ 
    if(hz[i]<=1){ 
    ///break可以算的更快些 ans=min(ans,you); break; } else{ 
    ans=min(ans,you+hz[i]-1); ///修改前面x与后面l ans=min(ans,you+hz2[i]-1+1); ///修改前面x与后面x } cnt--; you++; } } if(ans==INF)ans=0; cout << ans << endl; } return 0; }

讯享网

~~真的签到题吗？？？~~
在这里插入图片描述

【美团杯2020】字符串处理：查查查乐乐

查查查乐乐

相关推荐