专栏文章

题解：P13792 [SWERC 2023] Card game

llinzongyi_520
P13792题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minhe70e
此快照首次捕获于
2025/12/02 02:27
3 个月前
此快照最后确认于
2025/12/02 02:27
3 个月前
查看原文
题目链接

题目大意

有五种花色的牌，分别为银色 S，白色 W，绿色 E，红色 R，还有一个更加高级的青色 C。每种花色有 NN 张牌，我们的手里也有 NN 张牌。现在我们需要让同一花色的所有牌按递增顺序相邻排列，并且青色牌要放在末尾（同样按递增顺序排列）。

思路分析

  • 核心：将求最少操作次数转换为求最长上升子序列

    对于无需移动的牌，它们已经构成了符合要求的序列，因此不需要移动。对于需要移动的牌，我们需要把它放到符合要求的序列中。

  • 考虑 “贪心 ++ 二分” 优化

    我们可以用一个 dp 数组来维护上升子序列的最小结尾。dp 的每个元素是 优先级，牌编号其结尾的优先级和编号尽可能小。这样可以让后续更多牌能满足“优先级非递减 ++ 数字递增”，从而加入子序列。
    对于每张新牌，通过二分查找 dp 中第一个“不满足条件”的位置（即优先级 >> 当前牌，或优先级相等但编号 ≥\ge 当前牌），将新牌插入或替换该位置，确保 dp 始终维持最小结尾的特性。

  • 整体思路

    1. 读入 NN 和手中的 NN 张牌，将花色转为编码，存入数组。
    2. 建立 SWERSWER 的初始排列，再用 get_len 计算该排列下的上升子序列长度，更新最大值。
    3. 枚举剩余 2323 种排列，对于每种排列：
      先用 pos 数组更新优先级，再用 get_len 计算当前排列的上升子序列长度，更新最大值。
    4. 最后用总牌数减去上升子序列的最大值即为最小操作次数。

AC Code

不要抄袭
CPP
#include<bits/stdc++.h>
using namespace std;

int N;
int pos[4];
vector<pair<int,int>> card;
vector<int> a={0,1,2,3};//记录四种颜色的位置，转换为优先值  
int max_len=INT_MIN;

int get_len()
{
	vector<pair<int,int>> dp;
	//遍历每一张卡片 
	for(int i=0;i<card.size();i++)
    {
        int color=card[i].first;//当前卡片的颜色  
        int num=card[i].second;//当前卡片的编号  
        
        //计算当前卡片对应的优先级p：
        //若为'C'，p固定为4，其他颜色则使用其在当前排列中的位置pos[color]
        int p=(color == 4) ? 4 : pos[color];
        
        int l=0,r=dp.size();
        while(l < r)
        {
            int mid=l+(r-l)/2;
            if(dp[mid].first > p || (dp[mid].first == p && dp[mid].second >= num))
                r=mid;
            else
                l=mid+1;
        }
        if(l == dp.size())
            dp.emplace_back(p,num);
        else
            dp[l]={p,num};
    }
    //返回在当前颜色排列下上升子序列的长度 
    return dp.size();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N;
    
    for(int i=0;i<N;i++)
    {
        string s;
        cin >> s;
        int color;
        if(s[0] == 'S')
            color=0;
        else if(s[0] == 'W')
            color=1;
        else if(s[0] == 'E')
            color=2;
        else if(s[0] == 'R')
            color=3;
        else//'C'
            color=4;
        int num=stoi(s.substr(1));
        card.emplace_back(color,num);
    }
    
    //处理初始排列 
    for(int i=0;i<4;i++)
        pos[a[i]]=i;
    max_len=max(max_len,get_len());
    
    //处理剩余排列 
    while(next_permutation(a.begin(),a.end()))
    {
        for(int i=0;i<4;i++)
            pos[a[i]]=i;
        max_len=max(max_len,get_len());
    }
    
    cout << N-max_len;
    
    return 0;
}

评论

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

正在加载评论...