Codeforces Round 857 (Div. 2)

Buying gifts

算法本质

思维、STL应用

题目大意（抽象）

给定n张卡牌，每张有黑白两面，每一面都有数值。
玩家可以选择让卡牌某面朝上。

输出最小化的| max(黑色面数值) - max(黑色面数值) |。

思路推演

这种题相当简单。

因为是最大值，所以我们可以枚举黑色面选取的最大值x。
除了当前这卡牌，黑面值>x的卡牌必须选择白面，黑面值<=x的卡牌都可以任意选择黑白面。
在这个情况下，凑一个白面最大值使得其与x最近即可。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    cin>>n;
    vector<pair<int,int>> v;
    multiset<int> st1, st2;
    for (int i=0; i<n; i++)
        v.push_back({in(), in()});
    sort(v.begin(), v.end());
    for (int i=0; i<n; i++)
        st2.insert(v[i].second);
    int ans = 1e9;
    for (int i=0; i<n; i++)
    {
        st2.erase(st2.find(v[i].second));
        int res=1e9, x=v[i].first, top=-1;    // top是必须白面卡牌中的最大值
        if (st2.size())        // st2是必选的部分
        {
            top = *st2.rbegin();
            res = abs(top-x);
        }
        auto it = st1.lower_bound(x);        // st1是可选的部分
        if (it!=st1.end() && *it>=top)        // 可选部分找离x最近的，同时需要>=top才能生效
            res = min(res, abs(*it - x));
        if (it!=st1.begin() && *prev(it)>=top)
            res=min(res, abs(*prev(it)-x));

        ans = min(ans, res);
        st1.insert(v[i].second);
    }
    cout<<ans<<endl;
    return;
}

Music Festiva

算法本质

思维

题目大意

给定若干个不同长度数组，现在玩家需要排列数组的顺序（数组内部元素顺序不会改变），组成一个数组a[]。

定义数组的美丽值：

• 若某个元素比其之前的所有元素都大，则+1美丽值（首元素必+1）

输出a[]的最大美丽值。

元素个数、数组个数、总元素个数、元素大小 <= 2e5

思路推演

稍加模拟即可发现，每个数组的其实仅需保留>数组之前所有元素的元素。
比如[2, 1, 3, 3, 1]就可以简化成[2, 3]

这其实变成了一个区间问题，显然我们应该优先处理那些靠前的区间，但是此题中，区间的质量分布并非均匀的，而是随机侧重的。
这让贪心很难解决，于是开始思考dp能否搞定。

思考区间的含义，区间l r来说，其值可以由<r的所有可能转移而来，这就是dp。
构建dp[x]=t表示可选最大值x时美丽值最大是t。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    cin>>n;
    map<int, vector<int>> cod, mp;        // cod[x]表示第x个数组的形态（简化后），mp[x]表示以x为右端点的区间的id
    vector<int> alive;        // 离散化，记录关键点（这点有点毛病，纯粹没有招硬加离散化加点难度）
    for (int i=0; i<n; i++)
    {
        cin>>m;
        vector<int> v;
        while (m--)
        {
            int x=in();
            if (v.size()==0 || x>v.back())
                v.push_back(x), alive.push_back(x);
        }
        mp[v.back()].push_back(i);
        cod[i] = v;
    }
    alive.push_back(0);        // 手动添加一个0，可以省去一些边界检查的代码
    sort(alive.begin(), alive.end());
    alive.erase(unique(alive.begin(), alive.end()), alive.end());        // 排序去重
    vector<int> dp(alive.size());        // dp[x]=t选完元素后的最大是x时美丽值为t
    for (int i=0; i<dp.size(); i++)
    {
        if (i>0)    dp[i] = max(dp[i], dp[i-1]);    // 直接继承
        int val = alive[i];
        for (int id:mp[val])    
        {
            vector<int> &v = cod[id];
            int cnt=v.size();
            for (int x:v)
            {
                int p=lower_bound(alive.begin(), alive.end(), x) - alive.begin();
                dp[i] = max(dp[i], dp[p-1] + cnt);    // dp转移公式
                cnt--;
            }
        }
    }
    int ans = dp.back();
    cout<<ans<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。