C19-team4

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

前面我们做的很不错, 败笔是J题...因为懒得离散化, 所以一直WA. 虽然到现在还是不知道什么样的数据会WA...

另外D题因为错误地分析了时间复杂度... 让我们放弃了hash的做法... 

by yxdb

--------------------------------

赛后过了J题, 离散化时间点, 时间复杂度是 O(n^2^log(n)), (用了priority_queue来维护切水果的个数...)

{{{
/*
 * 8850. Juice Extractor
 * Problem code: JUICE
 */

#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n, a[1005], b[1005], dp[2005] = {};
        scanf("%d", &n);
        map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", a+i, b+i);
            ++mp[a[i]];
            ++mp[b[i]];
        }
        int m = mp.size();
        map<int, int>::iterator it = mp.begin();
        for (int i = 0; i < m; ++i, ++it) {
            it->second = i;
        }
        for (int i = 0; i < n; ++i) {
            a[i] = mp[a[i]];
            b[i] = mp[b[i]];
        }
        for (int i = 0; i < m; ++i) {
            priority_queue<int> q;
            for (int j = 0; j < n; ++j) {
                if (a[j] <= i && i <= b[j]) {
                    q.push(-a[j]);
                }
            }
            dp[i] = (q.size() > 2 ? q.size() : 0);
            for (int j = 0; j < i; ++j) {
                for (; !q.empty() && -q.top() <= j; q.pop());
                dp[i] = max(dp[i], dp[j] + (q.size() > 2 ? (int)q.size() : 0));
            }
        }
        printf("Case #%d: %d\n", cas, dp[m-1]);
    }
}

}}}

稍微修改了一下, 先sort, 然后用vector来维护切水果数.. 于是变成O(n^2^)的了..

{{{
/*
 * 8850. Juice Extractor
 * Problem code: JUICE
 */

#include <cstdio>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <vector>
using namespace std;

#define X first
#define Y second

int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n, dp[2005] = {};
        pair<int, int> v[1005];
        scanf("%d", &n);
        map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &v[i].X, &v[i].Y);
            ++mp[v[i].X];
            ++mp[v[i].Y];
        }
        int m = mp.size();
        map<int, int>::iterator it = mp.begin();
        for (int i = 0; i < m; ++i, ++it) {
            it->second = i;
        }
        for (int i = 0; i < n; ++i) {
            v[i].X = mp[v[i].X];
            v[i].Y = mp[v[i].Y];
        }
        sort(v, v+n);
        reverse(v, v+n);
        for (int i = 0; i < m; ++i) {
            vector<int> t;
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if (v[j].X <= i && i <= v[j].Y) {
                    t.push_back(v[j].X);
                    ++cnt;
                }
            }
            dp[i] = (cnt > 2 ? cnt : 0);
            for (int j = 0; j < i; ++j) {
                for (; cnt && t[cnt-1] <= j; --cnt);
                dp[i] = max(dp[i], dp[j] + (cnt > 2 ? cnt : 0));
            }
        }
        printf("Case #%d: %d\n", cas, dp[m-1]);
    }
}

}}}

by yxdb

前面我们做的很不错, 败笔是J题...因为懒得离散化, 所以一直WA. 虽然到现在还是不知道什么样的数据会WA...

另外D题因为错误地分析了时间复杂度... 让我们放弃了hash的做法...

by yxdb

赛后过了J题, 离散化时间点, 时间复杂度是 O(n²log(n)), (用了priority_queue来维护切水果的个数...)

/*
 * 8850. Juice Extractor
 * Problem code: JUICE
 */
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n, a[1005], b[1005], dp[2005] = {};
        scanf("%d", &n);
        map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", a+i, b+i);
            ++mp[a[i]];
            ++mp[b[i]];
        }
        int m = mp.size();
        map<int, int>::iterator it = mp.begin();
        for (int i = 0; i < m; ++i, ++it) {
            it->second = i;
        }
        for (int i = 0; i < n; ++i) {
            a[i] = mp[a[i]];
            b[i] = mp[b[i]];
        }
        for (int i = 0; i < m; ++i) {
            priority_queue<int> q;
            for (int j = 0; j < n; ++j) {
                if (a[j] <= i && i <= b[j]) {
                    q.push(-a[j]);
                }
            }
            dp[i] = (q.size() > 2 ? q.size() : 0);
            for (int j = 0; j < i; ++j) {
                for (; !q.empty() && -q.top() <= j; q.pop());
                dp[i] = max(dp[i], dp[j] + (q.size() > 2 ? (int)q.size() : 0));
            }
        }
        printf("Case #%d: %d\n", cas, dp[m-1]);
    }
}

稍微修改了一下, 先sort, 然后用vector来维护切水果数.. 于是变成O(n²)的了..

/*
 * 8850. Juice Extractor
 * Problem code: JUICE
 */
#include <cstdio>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <vector>
using namespace std;
#define X first
#define Y second
int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int n, dp[2005] = {};
        pair<int, int> v[1005];
        scanf("%d", &n);
        map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &v[i].X, &v[i].Y);
            ++mp[v[i].X];
            ++mp[v[i].Y];
        }
        int m = mp.size();
        map<int, int>::iterator it = mp.begin();
        for (int i = 0; i < m; ++i, ++it) {
            it->second = i;
        }
        for (int i = 0; i < n; ++i) {
            v[i].X = mp[v[i].X];
            v[i].Y = mp[v[i].Y];
        }
        sort(v, v+n);
        reverse(v, v+n);
        for (int i = 0; i < m; ++i) {
            vector<int> t;
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if (v[j].X <= i && i <= v[j].Y) {
                    t.push_back(v[j].X);
                    ++cnt;
                }
            }
            dp[i] = (cnt > 2 ? cnt : 0);
            for (int j = 0; j < i; ++j) {
                for (; cnt && t[cnt-1] <= j; --cnt);
                dp[i] = max(dp[i], dp[j] + (cnt > 2 ? cnt : 0));
            }
        }
        printf("Case #%d: %d\n", cas, dp[m-1]);
    }
}

by yxdb

附加文件

c19.zip by yuxingdubai