题目链接

题目大意

有 $N$ 个人，$S$ 项技能，这些技能用 $1, 2, 3, \dots, S$ 表示 。第 $i$ 个人会 $c_i$ 项技能（$ 1 \le c_i \le 5 $）。对于两个人 $i$, $j$，若 $i$ 会某项技能而 $j$ 不会，则称 $i$ 可以辅导 $j$ 。试问有多少个有序数对 $(i, j)$ 满足 $i$ 可以辅导 $j$ 。

数据范围

• 多组测试数据（不超过 100 组）
• $ 2 \le N \le 5 \times 10^4 $
• $ 1 \le S \le 1000 $
• Time limit: 20 s
• Memory limit: 1 GB

分析

考虑 $i$ 不能辅导 $j$，即 $i$ 的技能集是 $j$ 的技能集的子集（凡是 $i$ 会的 $j$ 都会）。

固定 $i$，我们来求满足 $i$ 不能辅导 $j$ 的二元组 $(i, j)$ 的数量。

枚举 $i$ 的技能集的非空子集 $t$，计算技能集等于 $t$ 的人有多少个。

实现

用 std::vector<int> 表示技能集，用 std::map<std::vector<int>>, int> 统计人数；结果在大数据上超时了。

虽然至少 std::map 常数大，但是看到时限是 20 秒就没太在意。除此之外，还有其他几处可以优化的地方，不过，超时主要是因为 std::map。

本来能打进前 30 名的，太可惜了。这道题是最后写的，提交时距离比赛结束还有 72 分钟

最新文章

1. elasticsearch 之mapping
2. scala学习----柯里化
3. 信息安全系统设计基础实验一 20135210&20135218
4. 【BZOJ】1089: [SCOI2003]严格n元树（递推+高精度/fft）
5. yii2的windows下安装及前期步骤
6. 反弹SHELL汇总
7. 4k 对齐，你准备好了吗？
8. Silverlight中DataGrid的显示指定列、修改默认列名和格式化日期数据和小数数据
9. JQuery操作下拉框 select
10. mysql 基础技术
11. Codeforces 353D Queue（构造法）
12. 高级UNIX环境编程3 FILE IO
13. 遍历Javascript数组的一种方法！
14. 用beego开发服务端应用
15. matlab求导数
16. static_assert enable_if 模板编译期检查
17. Git常用指令和GitHub操作总结
18. seo:与优化相关的熊掌号
19. 一个命令查看mysql的所有配置（原创）
20. 使用TuShare下载历史逐笔成交数据并生成1分钟线

热门文章

1. 二叉树的序遍历x（内含结构体与非结构体版x）
2. 灰度图像--图像分割 Marr-Hildreth算子（LoG算子）
3. TensorFlow使用记录 (八）： 梯度修剪 和 Max-Norm Regularization
4. php 解析json失败,解析为空,json在线解析器可以解析,但是json_decode()解析失败(原)
5. sql注入的基本小知识
6. （五）C语言之表达式
7. Nginx配置文件详细说明 （转）
8. Linux之tar命令
9. tensorflow简介与结构介绍
10. 百度AI---语音识别