题解：P13454 [GCJ 2008 Qualification] Saving the Universe

· · 题解

被橙题坑得最惨的一次。

贪心思路：连续取一段区间，直到出现 S 种引擎为之，即选出若干个区间，使区间内字符串种类数为 S - 1。

证明：
设区间 [l,r]，其中 [l,k],[k + 1,R](k < r) 满足以上贪心条件。假设先选 [l,k_2],(k_2 < k) 为最优，应该发现了吧，区间 [k_2 + 1,r] 之间必须再分出一个区间，因为内部字符串种类至少为 S。

提几点细节。

1.字符串之间可能有空格。

2.如果是像我一样这么写的：

        getline(cin,s);
        ...
        for(int i = 2;i <= q;i ++) {
            ...
        }
        ...

不要忘了：

        if (q == 0) {//被卡了2天 QAQ
            cout << "Case #" << t << ": 0\n";
            continue;
        }

若果 Q = 0，你读取引擎 a_1 会……

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1050;
int T,n,a[N],g,v[N],cnt,k,ans,q;
string s;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> T;
    for(int t = 1;t <= T;t ++) {
        cin >> n;
        map <string,int> p;
        cnt = 0;
        getline(cin,s);//吃掉'\n'
        for(int i = 1;i <= n;i ++) {
            getline(cin,s);
            p[s] = ++ cnt;
        }
        cin >> q;
        if (q == 0) {
            cout << "Case #" << t << ": 0\n";
            continue;
        }
        getline(cin,s);//吃掉'\n'
        getline(cin,s);//读入引擎
        a[1] = p[s];
        k = 1,ans = 0,g = 1;
        v[a[1]] ++;
        for(int i = 2;i <= q;i ++) {
            getline(cin,s);
            a[i] = p[s];
            if(!v[a[i]]) g ++;
            v[a[i]] ++;
            if(g == cnt) {
                g = 1;
                ans ++;
                while(k < i) v[a[k]] --,k ++;
                continue;
            }
        }
        while(k <= q) v[a[k]] --,k ++;
        cout << "Case #" << t << ": " << ans << '\n';
    }
    return 0;
}