题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
int id = 0;
int main(){
    int n;
    cin >> n;
    vector<int> a;
    for(int i = 0;i < n;i++){
        string s;
        cin >> s;
        if(!mp.count(s)){
            mp[s] = id++;
        }
        a.push_back(mp[s]);
    }
    int m;
    cin >> m;
    vector<int> b;
    for(int i = 0;i < m;i++){
        string s;
        cin >> s;
        if(!mp.count(s)){
            mp[s] = id++;
        }
        b.push_back(mp[s]);
    }
    vector<vector<int>> g(id);
    for(int i = 0;i < m;i++){
        g[b[i]].push_back(i);
    }
    int now = a[0];
    for(int i = 0;i < n;i++){
        if(g[now].empty())break;
        if(g[a[i]].empty() || g[a[i]][0] > g[now][0]){
            now = a[i];
        }
    }
    int ans = 0;
//  cout << now << endl;
    for(int t = 0;t < m;t++){
        if(now == b[t]){
            if(n == 1){
                cout << "-1\n";
                return 0;
            }
            int ch = 0;
            for(int i = 0;i < n;i++){
                if(lower_bound(g[now].begin(), g[now].end(), t) == g[now].end())break;
                if(lower_bound(g[a[i]].begin(), g[a[i]].end(), t) == g[a[i]].end() 
                    || *lower_bound(g[a[i]].begin(), g[a[i]].end(), t) > *lower_bound(g[now].begin(), g[now].end(), t)){
                    now = a[i];
//                  cout << now << endl;
                    ch = 1;
                }
            }
//          if(ch == 0){
//              cout << "-1\n";
//              return 0;
//          }
            ans++;
        }
    }
//   cout << now << endl;
    // for(auto x:a){
    //     cout << x << endl;
    // }
    cout << ans << "\n";
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla