#PQJ3493x17303. QOJ 3493_17303
QOJ 3493_17303
2026 联合省选 第一试夜空(night) 夜空(night) 【题目背景】 传说在很久以前,小怪兽Nexus 作恶多端,大法师便将其封印于夜空之中。为了完 成封印,大法师施展法术重排了星辰,令夜空呈现出特定的星象。 据说这道封印一直留存至今,再无人知晓它昔日的全貌。 【题目描述】 小H 在阅读古籍时发现,夜空中的星辰可以抽象为一个非负整数序列。远古时期 的星辰序列为A = [a1, . . . , an],而如今所观测到的序列则为B = [b1, . . . , bm]。 古籍中还记载了大法师重排星辰时使用的两种法术。具体而言,对于当前长度不小 于2 的星辰序列,大法师可以施展以下两种法术之一:
- 删除序列.最.左.侧的两个元素,并在.最.右.侧插入它们的异或和;
- 删除序列.最.右.侧的两个元素,并在.最.左.侧插入它们的异或和。 可以发现,每施展一次法术,星辰序列的长度都会恰好减少1。小H 猜测,或许大 法师当年仅使用了这两种法术,恰好施展n −m 次,就将最初的序列A 变成了如今的 序列B。你需要帮助他判断这是否可能;若可能,还需找出一组具体的施法方案。 【输入格式】 从文件night.in 中读入数据。 .本.题.包.含.多.组.测.试.数.据。 输入的第一行包含两个非负整数c, t,分别表示测试点编号与测试数据组数。c = 0 表示该测试点为样例。 接下来依次输入每组测试数据,对于每组测试数据: • 第一行包含两个正整数n, m。 • 第二行包含n 个非负整数a1, . . . , an。 • 第三行包含m 个非负整数b1, . . . , bm。 【输出格式】 输出到文件night.out 中。 对于每组测试数据: • 第一行输出一个字符串Yes 或No,表示大法师是否可能仅施展了这两种法术就 将序列A 变成了序列B。 • 若可能,则第二行输出n −m 个{1, 2} 中的正整数,分别表示大法师每次施展的 法术种类。 正确回答上述第一项即可获得部分分数,具体评分规则请参见【评分方式】。 第9 页 共13 页
2026 联合省选 第一试夜空(night) 【样例1 输入】 1 0 5 2 2 2 3 1 2 4 1 2 5 3 2 6 3 4 2 7 6 3 8 5 3 9 2 3 4 5 6 10 6 1 1 11 6 1 12 1 2 3 4 5 6 13 0 14 7 2 15 3 3 5 6 1 2 8 16 11 3 【样例1 输出】 1 Yes 2 3 Yes 4 2 5 Yes 6 1 1 7 No 8 Yes 9 2 1 2 1 1 【样例1 解释】 该样例共包含五组测试数据。 对于第一组测试数据,序列A 与序列B 相同,因此无需施展任何法术。 对于第二组测试数据,施展一次第2 种法术后,删除了序列A 最右侧的4 和2,并 在最左侧插入4 xor 2 = 6,得到序列B。 第10 页 共13 页
2026 联合省选 第一试夜空(night) 对于第三组测试数据, • 施展一次第1 种法术后,删除了序列A 最左侧的2 和3,并在最右侧插入2 xor 3 = 1,得到序列[4, 5, 6, 1]; • 再次施展一次第1 种法术后,删除了最左侧的4 和5,并在最右侧插入4 xor 5 = 1, 得到序列B。 对于第四组测试数据,可以证明,仅施展这两种法术无法将序列A 变成序列B。 【样例2】 见选手目录下的night/night2.in 与night/night2.ans。 该样例满足测试点1, 2 的约束条件。 【样例3】 见选手目录下的night/night3.in 与night/night3.ans。 该样例满足测试点4 的约束条件。 【样例4】 见选手目录下的night/night4.in 与night/night4.ans。 该样例满足测试点7 ∼9 的约束条件。 【样例5】 见选手目录下的night/night5.in 与night/night5.ans。 该样例满足测试点12 ∼14 的约束条件。 【数据范围】 对于所有测试数据,均有: • 1 ≤t ≤103; • 1 ≤m ≤n ≤250; • 对于所有1 ≤i ≤n,均有0 ≤ai < 230; • 对于所有1 ≤i ≤m,均有0 ≤bi < 230。 第11 页 共13 页
2026 联合省选 第一试夜空(night) 测试点编号 n ≤ m ≤ T ≤ 特殊性质 1, 2 16 16 103 无 3 250 1 30 4 2 5, 6 A 7 ∼9 50 50 50 B 10, 11 250 250 30 12 ∼14 50 50 50 C 15, 16 250 250 30 17 ∼19 50 50 50 D 20, 21 250 250 30 22, 23 50 50 50 无 24, 25 250 250 30 定义序列S = [s1, . . . , sk] 是.奇.异.的,当且仅当k ≥3,且s1 = s2 = s3 = 1,且对于 所有4 ≤i ≤k,均有2 | si。 定义序列S = [s1, . . . , sk] 的.循.环.移.位如下:对于正整数p (1 ≤p ≤k),序列 [sp, sp+1, . . . , sk, s1, . . . , sp−1] 是序列S 的一个循环移位。 特殊性质A:3 | n。 特殊性质B:序列A, B 都是.奇.异.的。 特殊性质C:序列A 与序列B 各自存在一个.循.环.移.位是.奇.异.的。 特殊性质D:2m ≥n。 【评分方式】 本题包含两个小问。对于每个测试点: • 小问1:对该测试点中每组测试数据,正确判断可行性,即可获得该测试点50% 的分数; • 小问2:在此基础上,若对每组答案为Yes 的测试数据还能正确给出一组合法的 施法方案,即可获得该测试点另外50% 的分数。 .注.意:.对.于.答.案.为Yes .的.测.试.数.据,.无.论.选.手.是.否.尝.试.给.出.正.确.的.施.法.方.案,.都 .需.要.在.第.二.行.输.出n −m .个{1, 2} .中.的.正.整.数,.以.满.足.输.出.格.式。 【提示】 本题目录下提供了一份checker.cpp 用于检验施法方案的可行性。.注.意:.提.供.的 checker.cpp .只.会.检.验.答.案.为Yes .的.测.试.数.据.中.施.法.方.案.的.正.确.性,.而.不.会.检.查.可 .行.性.判.断.的.正.确.性。 选手可以在本题目录下使用如下命令编译得到可执行程序: 第12 页 共13 页
2026 联合省选 第一试夜空(night) 1 g++ checker.cpp -o checker -std=gnu++14 -O2 -static 编译得到可执行程序后,选手可以在本题目录下使用如下命令进行测试: 1 ./checker <input_file> <output_file> 其中<input_file> 与<output_file> 分别表示输入文件与输出文件的路径。 .注.意:.选.手.提.供.的.输.入.文.件.需.满.足.题.目.给.定.的.输.入.格.式.与.数.据.范.围,.输.出.文.件.需.满 .足.给.定.的.输.出.格.式,.否.则.不.保.证.检.验.结.果.的.正.确.性,.并.可.能.发.生.无.法.预.料.的.错.误。 第13 页 共13 页