P2564 [SCOI2009] 生日礼物题解

CleverRaccoon · 2025-07-28 23:17:03 · 题解

前言

我是不是好久没来写题解了。题解区无 STL 大法，特此申请添加。

题目简述

有一个很长的序列，每个位置上有一种的颜色（同一位置可能有多个颜色）。取序列上长度为 w 的一段，使得包含全部种类的颜色，最小化 w。

前置知识

STL 里的 containers 相信都不陌生。介绍一下用到的。

map

含义是，对于每一个位置，映射一个数组记录当前位置上所有的元素种类。单次操作时间复杂度约 \mathcal{O}(\log n)。其中元素自动按 key 升序排序，且可遍历。

map<int,vector<int>> e;

unordered_map

含义同 map，区别在于该映射容器底层实现为哈希表，故操作时间复杂度不带 log，无需排序则使用。代码中为记录每个颜色种类的出现次数。

unordered_map<int,int> omo;

deque

双端队列，可双端增删，无需多言。但题外话，注意若开 10^6 个 deque 是会 MLE 的。

deque<int> q;

思路

题目的输入给的很乱。我们要学会归纳总结信息。其实此题与 P1638 逛画展非常类似。但问题就在于要先处理好输入信息。

step 1 转化信息

总的来说，即将输入数据处理为按照位置信息升序排序的数组，借助 map 的自动排序，也相当于一个离散化过程。即可转化为类似逛画展的输入数组。

具体地，我们可以用一个 map 映射每个位置对应的几个种类，具体见前置知识部分。由于 map 能够自动按照 key 排序，所以遍历一遍 map，每次遍历取出每个位置对应的种类，并直接加入数组 c 中。数组 c 就是按照位置信息排好序的每一个种类每一个位置的点的信息。

cin>>n>>k;
for(int i=1;i<=k;i++){
    cin>>t[i];
    for(int j=1;j<=t[i];j++){
        int tmp;cin>>tmp;
        e[tmp].push_back(i);
    }
}
for(auto &p:e){
    int m=p.first;
    vector<int> v=p.second;
    for(auto &y:v)c[++cnt]={y,m};
}

step 2 处理

其实之后的处理工作就和逛画展很一样了。这里提供逛画展的一种 STL 写法。

用 unordered_map（具体前置知识提到过）记录每个种类出现的个数，用 deque 记录当前选中的部分序列的元素（即为了记录删除头部哪一个元素）。

想象一个滑动窗口，由于已经得到位置升序的有序数组了，所以可以从 1\sim n 遍历。

对于每次遍历，将当前的种类加入 unordered_map 和 deque，并将当前的位置向后推移，直到 unordered_map 的长度（即种类数）达到 k 即停止。记录开头结尾分别截止到哪一个位置，取这两个位置之差并与之前的答案比较是否为更小即可。

int st;
if(!q.empty())st=q.front();
else st=1;
while(i<=n&&omo.size()<k){
    q.push_back(i);
    if(omo.count(c[i].cs))omo[c[i].cs]++;
    else omo.insert({c[i].cs,1});
    ++i;
}
--i;
ans=min(ans,c[i].id-c[st].id);

之后每一次都需要向后滑动，才能减少种类，并找到新的合适的位置，增加种类，实现答案最小化。滑动的时候就需要删除队首的元素。如果元素数量为 0，则直接删除这一类。

if(!q.empty()){
  omo[c[q.front()].cs]--;
  if(!omo[c[q.front()].cs])omo.erase(c[q.front()].cs);
    q.pop_front();
}

实现

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n,k,t[N],cnt,ans=INT_MAX;
map<int,vector<int>> e;
struct node{
    int cs;// 种类
    int id;// 位置
}c[N];

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>t[i];
        for(int j=1;j<=t[i];j++){
            int tmp;cin>>tmp;
            e[tmp].push_back(i);// 位置映射种类
        }
    }
    for(auto &p:e){
        int m=p.first;
        vector<int> v=p.second;
        for(auto &y:v)c[++cnt]={y,m};// 记录到新数组中
    }
    deque<int> q;
    unordered_map<int,int> omo;
    for(int i=1;i<=n;i++){
      if(!q.empty()){// 滑动
        omo[c[q.front()].cs]--;
        if(!omo[c[q.front()].cs])omo.erase(c[q.front()].cs);
          q.pop_front();
      }
      int st;
      if(!q.empty())st=q.front();
      else st=1;
      while(i<=n&&omo.size()<k){// 寻找一组种类达到 k 的可行解
      q.push_back(i);
      if(omo.count(c[i].cs))omo[c[i].cs]++;
      else omo.insert({c[i].cs,1});
      ++i;
    }
    --i;
    ans=min(ans,c[i].id-c[st].id);// 取更小的答案
  }
  cout<<ans;
  return 0;
}

后记

泥萌给她送过生日礼物吗 QwQ。

我没有。

P2564 [SCOI2009] 生日礼物 题解

前言