Skip to content

1207: 你猜

题目

题目描述

你的朋友写下一串包含$1$和$0$的串让你猜,你可以从中选择一个连续的子串(例如其中的第$3$到第$5$个数字)问他,该子串中包含了奇数个还是偶数个$1$,他会回答你的问题,然后你可以继续提问

听了几个答案后,你怀疑朋友的答案可能有错,或说同他之前的答案相互矛盾,例如:$1 - 2$ 奇数,$3 - 4$ 奇数,那么可以确定$1 - 4$ 一定是偶数,如果你的朋友回答是奇数,就产生了矛盾。给出所有你朋友的答案,请你找出第一个出现矛盾的答案

朋友看你在苦思冥想决定给你一点小提示(可跳过):聪明的你应该很快发现只需要考虑$01$串前缀和$S_i$的奇偶性,即若朋友说$3-4$是偶数,那么$S_2$与$S_4$奇偶性相同,否则相反。那么是不是相同就可以合并,但相反怎么办呢?尝试思考一种合理方式去表征这两种性质。

输入格式

第一行有两个数字,为 $n$,$Q$ ,表示$01$串长度为$n$,共有$Q$个询问

第$2-Q+1$行每行包括两个数以及一个字符串来描述朋友的回答,$2$个数中间用空格分隔,分别表示区间的起点和终点,后面的字符为"even"(偶数)或"odd"(奇数),表示朋友的答案。

输出格式

输出仅一行一个数,表示朋友的答案中第一个错误答案的位置,如果所有答案均不矛盾,则输出$-1$。

样例输入

样例输入 1

text 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd

样例输入 2

text 20 10 9 16 odd 13 16 even 2 10 even 18 19 even 4 16 even 4 5 odd 1 9 even 8 10 odd 6 16 even 3 6 even

样例输出

样例输出 1

text 4

样例输出 2

text 9

数据范围

对于$30\%$的数据,保证$1 \leq n \leq 10$

对于$60\%$的数据,保证$1 \leq n \leq 1000$

对于$100\%$的数据,保证$2 \leq n \leq 100000$,$2 \leq Q \leq 50000$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!