Codeforces Round 1083 (Div. 2)——CF-2205-C. Simons and Posting Blogs

题目大意

题目描述

有 $n$ 篇博客，第 $i$ 篇博客按顺序提到了 $l_i$ 个用户，用数组 $a_i=[a_{i,1},a_{i,2},\dots,a_{i,l_i}]$ 表示。

你需要将这 $n$ 篇博客全部发布。维护一个序列 $Q$（初始为空）来记录最近提到的用户列表。你需要选择一个所有 $n$ 篇博客的发布顺序进行发布，每次发布一篇博客 $i$ 时，会对每一个 $1 \le j \le l_i$ 依次执行以下操作：

• 如果 $a_{i,j}$ 已经存在于 $Q$ 中，则将 $a_{i,j}$ 移动到 $Q$ 的开头。

• 否则，将 $a_{i,j}$ 插入到 $Q$ 的开头。

求在发布所有 $n$ 篇博客后，所能得到的字典序最小的序列 $Q$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。
每个测试用例第一行包含一个整数 $n$（$1 \le n \le 3000$），表示博客数量。
接下来 $n$ 行，每行首先包含一个整数 $l_i$（$1 \le l_i \le 3000$），表示第 $i$ 篇博客提到的用户数量，随后跟着 $l_i$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,l_i}$（$1 \le a_{i,j} \le 10^6$），表示提到的用户列表。
保证所有测试用例中 $n$ 的总和不超过 $3000$，$\sum l_i$ 的总和不超过 $3000$。

输出格式

对于每个测试用例，输出一行包含若干个整数，表示能够得到的字典序最小的 $Q$。

样例数据

Input
5
3
5 1 2 3 4 6
3 2 5 1
4 1 9 2 3
2
2 1 6
1 6
1
3 6 1 1
5
4 2 3 3 4
5 1 2 4 3 1
2 4 1
3 3 3 1
5 4 3 2 2 2
5
4 2 3 1 4
5 2 5 5 6 5
5 3 4 7 5 5
8 3 6 4 3 1 1 5 4
2 1 1

Output
1 5 2 3 9 6 4
6 1
1 6
1 3 2 4
1 4 3 2 5 6 7

样例解释

在第一个测试用例中，可以按如下顺序发布博客：

1. 发布第一篇博客，$Q$ 变为 $[6,4,3,2,1]$。

2. 发布第三篇博客，$Q$ 变为 $[3,2,9,1,6,4]$。

3. 发布第二篇博客，$Q$ 变为 $[1,5,2,3,9,6,4]$。

这里存在其他的发布方式，例如：

1. 发布第三篇博客，$Q$ 变为 $[3,2,9,1]$。

2. 发布第一篇博客，$Q$ 变为 $[6,4,3,2,1,9]$。

3. 发布第二篇博客，$Q$ 变为 $[1,5,2,6,4,3,9]$。

可以看到 $[1,5,2,3,9,6,4]$ 的字典序比其他结果更小。如果我们不把第二篇博客放在最后发布，序列的第一个元素将不会是 $1$。因此 $[1,5,2,3,9,6,4]$ 就是能得到的字典序最小的数组 $Q$。

在第二个测试用例中，可以按如下顺序发布博客：

1. 发布第一篇博客，$Q$ 变为 $[6,1]$。

2. 发布第二篇博客，$Q$ 保持自身为 $[6,1]$。

在第三个测试用例中，只能发布唯一的一篇博客，$Q$ 会变为 $[1,6]$。

思路讲解

OPUS 4.6 的思路

这道题有一个比较干净的做法，不需要动态排序和复杂删除。核心在于把"逆序操作"的想法进一步转化成一个简单的贪心。
关键观察：如何理解最终的 Q
设发布顺序为 $\pi_1, \pi_2, \dots, \pi_n$。最终的 $Q$ 可以这样等价地构造：
按逆序发布顺序（即 $\pi_n, \pi_{n-1}, \dots, \pi_1$）依次处理每篇博客，对每篇博客从右往左扫描，遇到还没出现过的用户就追加到 $Q$ 末尾。
这是因为最后发布的博客决定了 $Q$ 最前面的部分（最近被移到前面的用户），倒数第二篇决定了下一段，以此类推。
预处理：有效序列
对每篇博客 $i$，从右往左扫描，保留每个用户的首次出现，得到"有效序列" $R_i$。例如博客 [1, 2, 1, 3] 的有效序列为 [3, 1, 2]。
贪心选择
维护一个集合 used 记录已经放入 $Q$ 的元素。每一步：

1. 对每个还未选过的博客，把其有效序列中 used 里的元素跳过，得到"剩余有效序列"。
2. 选择剩余有效序列字典序最小的博客。
3. 把它的剩余有效序列追加到 $Q$，并将这些元素加入 used。
   重复直到所有博客选完。
   正确性（交换论证）：如果两个博客 $A$、$B$ 的剩余有效序列满足 $A' < B'$（字典序），那么先处理 $A$ 再处理 $B$，$Q$ 的前缀就是 $A'$ 开头，一定不劣于 $B'$ 开头。当 $A'$ 是 $B'$ 的前缀时，两种顺序结果相同，不影响。
   用第一个样例验证
   博客有效序列：

• 博客 1：[6, 4, 3, 2, 1]
• 博客 2：[1, 5, 2]
• 博客 3：[3, 2, 9, 1]
  第一步：博客 2 的 [1, 5, 2] 字典序最小（以 1 开头），选它。$Q = [1, 5, 2]$。
  第二步：博客 1 剩余 [6, 4, 3]，博客 3 剩余 [3, 9]。选博客 3（3 < 6）。$Q = [1, 5, 2, 3, 9]$。
  第三步：博客 1 剩余 [6, 4]。$Q = [1, 5, 2, 3, 9, 6, 4]$。与期望答案完全一致。
  复杂度
  时间 $O(L^2)$，其中 $L = \sum l_i \le 3000$。空间 $O(L)$。只需要一个哈希集合来判断元素是否已使用，不需要任何平衡树、动态排序等复杂结构。

哎，其实这个思路和我一模一样，这个思路其实和我一模一样，我说白了你不会更加有更加简单的做法，实际上你就是这个做法，绷不住了。

也看了各路大神的代码，确实是没有更加简单的做法了。

while (!g.empty()) {
    sort(all(g));
    for (auto a:g[0]) {
        ans.push_back(a);
        used.insert(a);
    }
    vector<vector<ll>> new_g;
    for (int i=1;i<g.size();++i) {
        new_g.push_back(gen_uni(g[i]));
    }
    swap(new_g,g);
}

AC代码

AC
http://codeforces.com/contest/2205/submission/365031780

源代码

/**
 * Problem: C. Simons and Posting Blogs
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/C
 * Created: 2026-02-28 22:53:22
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll>> g(N);
    for (int i=0;i<N;++i) {
        ll sz;
        cin>>sz;
        g[i].resize(sz);
        for (int j=0;j<sz;++j) {
            ll u;
            cin>>u;
            g[i][j]=u;
        }
        reverse(all(g[i]));
        vector<ll> b;
        set<ll> st;
        for (auto a:g[i]) {
            if (st.contains(a)) {
                continue;
            }
            b.push_back(a);
            st.insert(a);
        }
        swap(g[i],b);
    }
    set<ll> used;
    auto gen_uni=[&](const vector<ll> & vec) -> vector<ll> {
        vector<ll> res;
        for (auto a:vec) {
            if (used.contains(a)) {
                continue;
            }
            res.push_back(a);
        }
        return res;
    };
    vector<ll> ans;
    while (!g.empty()) {
        sort(all(g));
        for (auto a:g[0]) {
            ans.push_back(a);
            used.insert(a);
        }
        vector<vector<ll>> new_g;
        for (int i=1;i<g.size();++i) {
            new_g.push_back(gen_uni(g[i]));
        }
        swap(new_g,g);
    }
    for (auto a:ans) {
        cout<<a<<" ";
    }
    cout<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
http://codeforces.com/contest/2205/submission/365031780

*/

心路历程（WA，TLE，MLE……）