专栏文章

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

DDevilsFlame
P13454题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mion3ssg
此快照首次捕获于
2025/12/02 21:54
3 个月前
此快照最后确认于
2025/12/02 21:54
3 个月前
查看原文
被橙题坑得最惨的一次。
贪心思路：连续取一段区间，直到出现 SS 种引擎为之，即选出若干个区间，使区间内字符串种类数为 S−1S - 1。
证明：
设区间 [l,r][l,r]，其中 [l,k],[k+1,R](k<r)[l,k],[k + 1,R](k < r) 满足以上贪心条件。假设先选 [l,k2],(k2<k)[l,k_2],(k_2 < k) 为最优，应该发现了吧，区间 [k2+1,r][k_2 + 1,r] 之间必须再分出一个区间，因为内部字符串种类至少为 SS。
提几点细节。
1.字符串之间可能有空格。
2.如果是像我一样这么写的：
CPP
        getline(cin,s);
        ...
        for(int i = 2;i <= q;i ++) {
            ...
        }
        ...
不要忘了：
CPP
        if (q == 0) {//被卡了2天 QAQ
            cout << "Case #" << t << ": 0\n";
            continue;
        }
若果 Q=0Q = 0，你读取引擎 a1a_1 会……
完整代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...