ZZULI-2019年3月份月赛（个人赛）EF题解

问题 E: 小P的字母子串

题意：给一段01串从任意位置进行截取，问最多能截取出多少个7位串对应字母的ASCLL值

题解：利用map将所有字母的7位ASCALL值存起来，然后对字符串进行暴力7位一截取。看看截取出来的串是否是字母的ASCALL值，如果是则位置i+6（因为有for里i++，会再加1），ans++。

对于字母的ASCALL，可以写个10进制转2进制程序跑一遍，输出到文件。或者手动转化’a’,’A’的二进制然后往后推25

#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
#define max_n 10050   //串长度
#define max_tot 100050  //节点数
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e4 + 7;
string s;
string zm[60]={"1000001","1000010","1000011","1000100","1000101","1000110","1000111","1001000","1001001","1001010","1001011","1001100","1001101","1001110","1001111","1010000","1010001","1010010","1010011","1010100","1010101","1010110","1010111","1011000","1011001","1011010","1100001","1100010","1100011","1100100","1100101","1100110","1100111","1101000","1101001","1101010","1101011","1101100","1101101","1101110","1101111","1110000","1110001","1110010","1110011","1110100","1110101","1110110","1110111","1111000","1111001","1111010"};
map<string,int>mp;
int main(int argc, char *argv[]) {
    for(int i=0;i<52;i++){
        mp[zm[i]]=1;	//把所有字母的ASCALL值扔进map
    }
    while(cin>>s){
        int ans=0;
        int len=s.size();
        string sub;
        for(int i=0;i+6<len;i++){
            if(s[i]==0)continue;
            else{
                sub=s.substr(i,7);	//截取7位子串
                if(mp[sub])ans++,i+=6;	//判断是不是个字母
            }
        }
        cout<<ans<<endl;
    }
    //cout<<s<<endl;
 
    return 0;
}

问题 F: 小P的秘籍

题意：给一个长度为n的AK串，求一个长度为len的子串满足该子串的所有前缀和后缀中K的数量不小于A，求最大len

题解：数据水了，用的尺取法。题目要求从前往后和从后往前都要满足K的数量大于等于A的数量。先用尺取法来确定从前往后满足的区间，然后内部从后往前判断是否成立，成立了就更新答案

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    int i=0,j=0;//[i，j]
    int a=0,k=0;
    int ans=0;
    while(1){
        while(j<str.size()&&k>=a){
        if(str[j]=='A')a++;
        if(str[j]=='K')k++;
        j++;
        if(k>=a){
            int cnt=0;
            for(int r=j-1;r>=i;r--){
            if(str[r]=='A')cnt--;
            if(str[r]=='K')cnt++;
            if(cnt<0)break;
            }
            if(cnt>=0)ans=max(ans,j-i);
        }
        }
        if(k>=a)break;
        while(i<j && k<a){
            if(str[i]=='A')a--;
            if(str[i]=='K')k--;
            i++;
        }
    }
    cout<<ans<<endl;
    return 0;
}