33OJ
登录 注册

#P17751. 「RSOI-2D」星光 / star

「RSOI-2D」星光 / star

背景

题目来源:【HT-124-Div.3】核桃 CSP-J 组模拟赛

题目描述

一所幼儿园里有 3030 颗魔法星星,编号从 11 到 3030。每颗星星都可以是亮或灭两种状态,分别对应 1 和 0。

一个星光组合是一个长度为 3030 的只由 0 和 1 组成的字符串,字符串的每一位分别表示每颗星星的状态。幼儿园里的小朋友各自喜欢一个星光组合,且任意两名小朋友喜欢的星光组合互不相同。

今天,老师指定了两个星光组合 kk 和 rr。对于任意两个喜欢的星光组合为 uu 和 vv 的小朋友,当且仅当同时满足以下两个条件时,他们会成为好朋友:

  • 第一个条件:在 rr 中所有星星是亮着的位置上,uu 和 vv 亮着的星星数量相同(换句话说,对于 1≤i≤301 \le i \le 30,满足 ri=1r_i = 1 且 ui=1u_i = 1 的 ii 的数量,与满足 ri=1r_i = 1 且 vi=1v_i = 1 的 ii 的数量相等);
  • 第二个条件:下面两个情况至少有一个成立:
    • 第一种情况:uu 和 vv 状态不同的星星总数是奇数;
    • 第二种情况:uu 和 vv 状态不同的星星恰好就是 kk 中亮着的那些星星(换句话说,对于任意 1≤i≤301 \le i \le 30,uiu_i 和 viv_i 不同当且仅当 ki=1k_i = 1)。

初始时,幼儿园里没有小朋友。接下来会发生 qq 个事件,每次事件为以下两种情况之一:

  • + x:喜欢的星光组合为 xx 的小朋友来到幼儿园(保证这位小朋友此时不在幼儿园中)。
  • - x:喜欢的星光组合为 xx 的小朋友离开幼儿园(保证这位小朋友此时在幼儿园中)。

每次事件发生后,你需要回答:当前在幼儿园的小朋友中,是否存在至少三个小朋友,他们两两互为好朋友。如果存在,则答案为 YES;否则答案为 NO。

输入格式

第一行,包含一个整数 qq,表示事件的数量。

第二行,包含两个长度为 3030 的字符串 kk 和 rr,仅包含字符 00 和 11,中间用一个空格隔开。字符串的从左到右第 ii 个字符对应星星 ii 的状态。

接下来 qq 行,每行一个字符(+ 或 -)和一个长度为 3030 的字符串 xx,中间用空格隔开,表示一个事件。字符串 xx 仅包含 00 和 11,第 ii 个字符对应星星 ii 的状态。

输出格式

共 qq 行,每行一个字符串 YES 或 NO,表示每次事件对应的答案。

5
000000000000000000000000000101 000000000000000000000000000010
+ 000000000000000000000000000000
+ 000000000000000000000000000001
+ 000000000000000000000000000101
- 000000000000000000000000000001
+ 000000000000000000000000000100
NO
NO
YES
NO
YES

提示

【样例解释 #1】

注:下文“仅 3030 亮”中“3030”的指的是编号为 3030 的星星,其他类似表述亦然。

  • + 000000000000000000000000000000:当前仅有一位小朋友,显然没有至少三人两两为友,答案为 NO。
  • + 000000000000000000000000000001:两位小朋友的星光组合分别为全灭和仅 3030 亮。在 rr 中亮着的星星 3030 上,两者均为灭,亮星数相同,满足第一个条件;两者状态不同的星星数量是奇数(有 11 颗星星状态不同),满足第一种情况。因此,两人成为好朋友。虽然两人互为好友,但题目要求至少三人,因此答案为 NO。
  • + 000000000000000000000000000101:三位小朋友的组合分别为全灭、仅 3030 亮和 29,3029, 30 亮。其中 0(此处省略前导 0,下同)和 101 状态不同的星星与 kk 中亮着的星星(29,3029, 30)相同,满足第二种情况,成为朋友。1 和 101 状态不同的星星有 11 颗(星星 2929),满足第一种情况,成为朋友。加上已有的 0 和 1 的朋友关系,三人两两为友,构成一个三角形友谊,答案为 YES。
  • - 000000000000000000000000000001:组合为 1 的小朋友离开,剩余两人人数不足,因此答案为 NO。

剩余一个事件不再解释。

【数据范围】

对于所有测试数据,保证:1≤q≤2×1051 \le q \le 2 \times 10^5,k,r,xk, r, x 的长度为 3030 且仅包含 0 和 1。kk 不全为 0;

注:下表中“前 tt 位为 0”是指字符串从左到右的前 tt 个字符均为 0;

“无特殊限制”指除了对于所有测试数据的限制和特殊性质以外,没有其他限制。

测试点编号 q≤q \le kk rr 所有 xx 特殊性质
1∼41 \sim 4 2×1022\times 10^2 前 2222 位为 0 无
5∼85 \sim 8 2×1032\times 10^3 前 1919 位为 0
99 5×1035\times 10^3 前 1616 位为 0 rr 全为 0
10∼1210 \sim 12 10510^5 无
13∼1513 \sim 15 2×1052 \times 10^5 前 1010 位为 0
1616 无特殊限制 kk 中 1 的个数为奇数
17∼2017 \sim 20 无