全国青少年信息学奥林匹克竞赛
CCF NOI 2024
第一试
时间：2024年7月18日08:00∼13:00
题目名称 集合 百万富翁 树的定向
题目类型 传统型 交互型 传统型
目录 set richest tree
可执行文件名 set richest tree
输入文件名 set.in richest.in tree.in
输出文件名 set.out richest.out tree.out
每个测试点时限 1.0秒 6.0秒 3.0秒
内存限制 512 MiB 512 MiB 2048 MiB
测试点数目 20 2 25
测试点是否等分 是 否 是
预测试点数目 20 2 25
提交源程序文件名
对于C++语言 set.cpp richest.cpp tree.cpp
编译选项
对于C++语言 ‐O2 ‐std=c++14 ‐static
.
注
.
意
.
事
.
项（
.
请
.
仔
.
细
.
阅
.
读）
1.文件名（程序名和输入输出文件名）必须使用英文小写。赛后正式测试时将以选
手留在题目目录下的源代码为准。
2.main函数的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3.因违反以上两点而出现的错误或问题，申诉时一律不予受理。
4.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
5.选手提交的程序源文件必须不大于 100 KB。
6.程序可使用的栈空间内存限制与题目的内存限制一致。
7.禁止在源代码中改变编译器参数（如使用 #pragma命令），禁止使用系统结构相
关指令（如内联汇编）和其他可能造成不公平的方法。
8.选手可使用快捷启动页面中的工具 selfEval进行自测。在将待测程序（不必是全
部题目）放到题目目录下后，即可选择全部或部分题目进行自测。注意：自测有
次数限制，且自测结果仅用于选手调试，并不做为最终正式成绩。
全国青少年信息学奥林匹克竞赛 第一试 集合（ set）
集合（set）
【题目描述】
小Y和小S在玩一个游戏。
给定正整数 m，定义
.
基
.
本
.
集
.
合为大小为 3、元素在 1∼m内的集合。例如，给定
m= 4，则集合 {1,2,3}与集合{2,3,4}都是基本集合。
定义
.
集
.
合
.
序
.
列为由基本集合构成的序列。例如， A= [{1,2,3},{2,3,4}]是一个集合
序列，其中 A[1] ={1,2,3}, A[2] ={2,3,4}都是基本集合。
对于一个 1∼m的排列p[1], p[2], . . . , p[m]与集合S⊆ {1,2, . . . , m}，定义fp(S)为
将S内每一个元素 x置换为p[x]后的所得到的集合，即 fp(S) ={p[x]|x∈S}。
对于两个长度为 k的集合序列 A, B，定义A和B
.
等
.
价当且仅当存在一个 1∼m
的排列p，使得A置换排列 p后得到B，即对于所有 1≤i≤k，fp(A[i]) =B[i]。
给定两个长度为 n的集合序列 A, B。有q次询问：每次小 S会询问小 Y，在给定
l, r
全国青少年信息学奥林匹克竞赛 CCF NOI 2024 第一试真题