猿辅导 笔试 8.26 做题记录

//不区分大小写  将大写转化为小写
// 哈希，看是否为停用词
#include<iostream>
#include<string>
#include<sstream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int M,N,K;
string str;
map<string,int> mp;
vector<string> v;
void in(){
    mp.clear();
    v.clear();
    cin>>N;
    getline(cin,str);
    // cout<<str<<endl;
    stringstream ss(str);
    while(ss>>str){
        for(int i=0;i<str.length();i++){
            if('A'<=str[i] && str[i]<='Z'){
                str[i]=str[i]+'a'-'A';
            }
        }
        mp[str]++;
    }
    cin>>K;
    getline(cin,str);
    stringstream sss(str);
    while(sss>>str){
        v.push_back(str);
    }
}
bool check_word(string a,string b){
    // cout<<a<<" "<<b<<endl;
    int l1=a.length(),l2=b.length();
    int pos1=0,pos2=0;
    while(pos1<l1 && pos2<l2 && (a[pos1]==b[pos2] || b[pos2]=='?')){
        pos1++;
        pos2++;
    }
    if(pos1==l1 && pos2==l2)  return true;
    else  return false;
}
bool check(map<string,int>::iterator i){
    string str=(*i).first;
    for(int j=0;j<v.size();j++){
        if(check_word(str,v[j]))  return true;
    }
    return false;
}
void solve(){
    cin>>M;
    for(int i=0;i<M;i++){
        int ans=0;
        in();
        for(auto i=mp.begin();i!=mp.end();i++){
            if(check(i)){
                continue;
            }
            else{
                ans=max(ans,(*i).second);
            }
        }
        cout<<ans<<"\n";
    }   
}
int main(){
    solve();
    return 0;
}
/*
2
4 ab ac cd c
2 a? c 
5 e e h h h
1 e
*/

#include<iostream>
#include<string>
#include<sstream>
#include<map>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;
const ll maxn=5e5+11;
ll M,K,N;
ll val[maxn];
map<ll,ll> mp;
map<ll,ll> cnt;
void in(){
    // cin>>M;
    cin>>K>>N;
    for(ll i=0;i<N;i++)  cin>>val[i];
}
void work1(){
    ll t=K;
    ll num=2;
    // cout<<"hello"<<endl;
    while(t!=1){
        while(t%num==0){
            t/=num;
            mp[num]++;
        }
        num++;
    }
    // cout<<"ok"<<endl;
}
bool check(){
    for(auto i=mp.begin();i!=mp.end();i++){
        ll a=(*i).first;
        ll b=(*i).second;
        if(b<cnt[a])  return false;
    }
    return true;
}
void work2(){
    ll left=0,right=0;
    ll ans=1e15;
    while(right<N){
        if(mp.find(val[right])!=mp.end()){
            cnt[val[right]]++;
            if(check()){
                while(check()){
                    if(mp.find(val[left])!=mp.end()){
                        cnt[val[left]]--;
                    }
                    left++;
                }
                ans=min(ans,right-left+2);
            }            
        }
        right++;
    }
    if(ans==1e15)  cout<<0<<"\n";//题目好像是说没答案为0吧，记不清了
    else  cout<<ans<<"\n";
}
void solve(){
    cin>>M;
    for(ll i=0;i<M;i++){
        mp.clear();
        cnt.clear();
        in();
        work1();
        work2();
    }
}
int main(){
    
    solve();
    return 0;
}
/*
2
20 8
1 2 3 2 6 5 2 1
17 10
1 4 5 7 10 8 7 17 2 8
*/