首页 > 试题广场 >

小红开宝箱

[编程题]小红开宝箱

热度指数：1137 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红来到了一个宝箱面前，但这个宝箱上锁了，开这个宝箱需要进行解密。

解密的方式是：给出了 $n$ 根柱子，小红必须按照规定的次序依次击打这 $n$ 根柱子。

现在小红通过贿赂地下城的设计者小紫，得出了每次应击打的柱子的可能性。小红想让你帮忙设计一个击打顺序，使得该顺序和小紫给出的信息不冲突。

输入描述:

第一行输入一个正整数，代表柱子的数量。
接下来的行，每行首先输入一个正整数，代表对于第次击打小紫给出的信息（柱子的可能性）数量。紧接着是个正整数，代表该次击打有可能是哪一个柱子。

输出描述:

如果不存在一个合法解，代表小紫欺骗了小红，请输出"kou is angry"。否则输出一个长度为的排列，代表一个合法的击打序列。有多解时输出任意即可。

示例1

输入

输出

2 1 3

说明

输出2 3 1也是可以的。

算法知识视频讲解

小男娘

发表于 2026-03-26 01:00:49

注意到，于是我们可以将每一个条件当作一条边建立无向图（可以转为并建立自环）。目标为将每一个点匹配一条边。第一步，不断寻找度数为的点并将其唯一邻边和此点匹配；第二步，对于剩余的点，如果度数为，则无解，否则此时图必然为若干个环，对于每一个环，按同一方向匹配环上的边和点即可。维护点的度数，在展开全文

此在Dasein

发表于 2026-03-26 05:24:09

1. 问题分析本问题的核心在于从给定的约束中寻找一个排列。每个“步骤”（Step）对应 1 或 2 个可选的“柱子”（Pillar）。我们需要在满足每个步骤选且仅选一个柱子的前提下，确保所有柱子都被恰好使用一次。核心约束：规模：，要求算法必须在线性或复杂度内完成。结构：这是一个展开全文

olone

发表于 2026-03-26 11:59:56

#include<bits/stdc++.h> #define pii pair<int,int> using namespace std; const int N = 1e5+5; int n; int cnt[N], ans[N]; vector<int&g 展开全文

25大数据唐文韬

发表于 2024-11-09 22:16:07

本题大致题意是，给出打击柱子数量即打击次数，然后给出每次打击中可能的目标对象，然后确定一个合理的打击序列，这让我们想到了基于二分图匹配的匈牙利算法：确定一个元素的匹配值，如果匹配值已经有其他元素占领，那么让占领此匹配值的元素换一个匹配值，最终达到一个合理的匹配。代码如下： #include<b 展开全文

牛客524077229号

发表于 2026-03-26 22:18:46

#include <iostream> #include <vector> #include <cstring> using namespace std; const int N = 1e5 + 10; int n; vector<int>a[N]; 展开全文

腌萝卜干

发表于 2026-03-26 12:02:48

匈牙利算法 + 时间戳优化 #include <bits/stdc++.h> #define x first #define y second #define all(x) x.begin(), x.end() using namespace std; using i128 = __ 展开全文

quchen666

发表于 2026-03-26 13:00:24

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5+10; vector<ll>e[N]; int match[N]; bool vis[N]; bool 展开全文

yycx219

发表于 2026-03-29 15:27:57

题解：匈牙利算法求解击打顺序题意理解有 (n) 次击打操作，每次操作必须选择一根柱子，每根柱子只能被击打一次。题目给出每次操作可能的柱子集合（(k_i \leq 2)），要求找到一个合法的击打顺序（一个 (1) 到 (n) 的排列）。如果不存在合法解，输出 "kou is angry&qu 展开全文