当前位置: 首页 > news >正文

17 LCA模拟赛1T2 剧院始于演员 题解

剧院始于演员

题面

\(n\) 个演员,共 \(m\) 场演出,每场演出会给出这场演出的演员名单,共 \(k_i\) 个姓名

对于每个演员,求最早在哪一场演出结束后能够确定其对应姓名?

\(1 \le n , m \le 10^5, \sum k_i \le 10^5\)

题解

可以发现,两个演员能够区分当且仅当某场演出中,一个演员出现,一个演员不出现

所以想要让某个演员和其他演员都区分开,那这个演员在每场的演出情况一定和其他演员不同,所以我们可以记录每个演员在前面场次的出现情况,记录一个状态

如果某个演员的状态和其他演员都不同,那么就能够确定这个演员的姓名

考虑如何实现?

我们可以对状态进行哈希,以区分出现和不出现

对每个哈希值,我们需要知道其对应了多少个演员,并且要快速的插入演员,删除演员,所以可以对每个哈希值维护一个 set ,用 map 来维护 哈希值与 set 的对应关系

但还没完,在每场演出结束后,我们还需要快速获取到大小为 1 的演员集合,并将对应的哈希值从 map 里删除,我们可以用另一个 set 来维护 集合大小和对应哈希值

那么这道题就做完了,时间复杂度 \(O(n \log n)\)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <random>
#include <ctime>
#include <unordered_map>
#include <set>using namespace std;typedef unsigned long long ull;void close_stream () {ios :: sync_with_stdio (0);cin.tie (0);cout.tie (0);
}namespace solution_b {const int N = 1e5 + 10;int n, m, ans[N];ull hash[N];unordered_map <ull, set <int> > mp;set <pair <int, ull> > st;mt19937_64 rng (time (0));void solve () {close_stream ();cin >> n >> m;st.emplace (n, 0);for (int i = 1; i <= n; i ++) {mp[0].emplace (i);}for (int i = 1; i <= m; i ++) {int cnt, x;cin >> cnt;ull tmp = rng ();for (int j = 1; j <= cnt; j ++) {cin >> x;if (ans[x]) continue;// 取出当前演员st.erase ({mp[hash[x]].size (), hash[x]});mp[hash[x]].erase (x);if (mp[hash[x]].size () == 0) mp.erase (hash[x]);else st.emplace (mp[hash[x]].size (), hash[x]);hash[x] ^= tmp;// 再将其插入st.erase ({mp[hash[x]].size (), hash[x]});mp[hash[x]].emplace (x);st.emplace (mp[hash[x]].size (), hash[x]);}for (auto it = st.begin (); it != st.end (); it ++) {int siz = it->first;ull val = it->second;if (siz > 1) break;ans[*mp[val].begin ()] = i;mp.erase (val);                }while (st.size () && st.begin()->first == 1) {st.erase (st.begin ());}}for (int i = 1; i <= n; i ++) {cout << ans[i] << ' ';}cout << '\n';}
}int main () {solution_b :: solve ();return 0;
}
http://www.hskmm.com/?act=detail&tid=25008

相关文章:

  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16
  • cf296b
  • 第一次使用Ttpora
  • Apache反向代理
  • 原版 Sunshine+虚拟显示器实现熄屏串流
  • 2025国庆Day4
  • gis坐标计算
  • day17 课程()
  • NKOJ全TJ计划——NP11744
  • ROIR 2025
  • trick 小记
  • python编写AI生常用匡架及使用指令集
  • 123123
  • 1005模拟赛总结
  • 2025.10.5 2024CCPC郑州
  • 20250531MATLAB三维绘图 - 教程
  • 概率期望dp 复习笔记