#P17751. 「RSOI-2D」星光 / star
「RSOI-2D」星光 / star
背景
题目来源:【HT-124-Div.3】核桃 CSP-J 组模拟赛
题目描述
一所幼儿园里有 颗魔法星星,编号从 到 。每颗星星都可以是亮或灭两种状态,分别对应 1 和 0。
一个星光组合是一个长度为 的只由 0 和 1 组成的字符串,字符串的每一位分别表示每颗星星的状态。幼儿园里的小朋友各自喜欢一个星光组合,且任意两名小朋友喜欢的星光组合互不相同。
今天,老师指定了两个星光组合 和 。对于任意两个喜欢的星光组合为 和 的小朋友,当且仅当同时满足以下两个条件时,他们会成为好朋友:
- 第一个条件:在 中所有星星是亮着的位置上, 和 亮着的星星数量相同(换句话说,对于 ,满足 且 的 的数量,与满足 且 的 的数量相等);
- 第二个条件:下面两个情况至少有一个成立:
- 第一种情况: 和 状态不同的星星总数是奇数;
- 第二种情况: 和 状态不同的星星恰好就是 中亮着的那些星星(换句话说,对于任意 , 和 不同当且仅当 )。
初始时,幼儿园里没有小朋友。接下来会发生 个事件,每次事件为以下两种情况之一:
+ x:喜欢的星光组合为 的小朋友来到幼儿园(保证这位小朋友此时不在幼儿园中)。- x:喜欢的星光组合为 的小朋友离开幼儿园(保证这位小朋友此时在幼儿园中)。
每次事件发生后,你需要回答:当前在幼儿园的小朋友中,是否存在至少三个小朋友,他们两两互为好朋友。如果存在,则答案为 YES;否则答案为 NO。
输入格式
第一行,包含一个整数 ,表示事件的数量。
第二行,包含两个长度为 的字符串 和 ,仅包含字符 和 ,中间用一个空格隔开。字符串的从左到右第 个字符对应星星 的状态。
接下来 行,每行一个字符(+ 或 -)和一个长度为 的字符串 ,中间用空格隔开,表示一个事件。字符串 仅包含 和 ,第 个字符对应星星 的状态。
输出格式
共 行,每行一个字符串 YES 或 NO,表示每次事件对应的答案。
5
000000000000000000000000000101 000000000000000000000000000010
+ 000000000000000000000000000000
+ 000000000000000000000000000001
+ 000000000000000000000000000101
- 000000000000000000000000000001
+ 000000000000000000000000000100
NO
NO
YES
NO
YES
提示
【样例解释 #1】
注:下文“仅 亮”中“”的指的是编号为 的星星,其他类似表述亦然。
+ 000000000000000000000000000000:当前仅有一位小朋友,显然没有至少三人两两为友,答案为NO。+ 000000000000000000000000000001:两位小朋友的星光组合分别为全灭和仅 亮。在 中亮着的星星 上,两者均为灭,亮星数相同,满足第一个条件;两者状态不同的星星数量是奇数(有 颗星星状态不同),满足第一种情况。因此,两人成为好朋友。虽然两人互为好友,但题目要求至少三人,因此答案为NO。+ 000000000000000000000000000101:三位小朋友的组合分别为全灭、仅 亮和 亮。其中0(此处省略前导0,下同)和101状态不同的星星与 中亮着的星星()相同,满足第二种情况,成为朋友。1和101状态不同的星星有 颗(星星 ),满足第一种情况,成为朋友。加上已有的0和1的朋友关系,三人两两为友,构成一个三角形友谊,答案为YES。- 000000000000000000000000000001:组合为1的小朋友离开,剩余两人人数不足,因此答案为NO。
剩余一个事件不再解释。
【数据范围】
对于所有测试数据,保证:, 的长度为 且仅包含 0 和 1。 不全为 0;
注:下表中“前 位为
0”是指字符串从左到右的前 个字符均为0;“无特殊限制”指除了对于所有测试数据的限制和特殊性质以外,没有其他限制。
| 测试点编号 | 所有 | 特殊性质 | |||
|---|---|---|---|---|---|
前 位为 0 |
无 | ||||
前 位为 0 |
|||||
前 位为 0 |
全为 0 |
||||
| 无 | |||||
前 位为 0 |
|||||
| 无特殊限制 | 中 1 的个数为奇数 |
||||
| 无 | |||||