狗家VO 挂筋

匿名的 发表于 2021-02-23 19:35:47
这题不知道N个数字是什么 没法prefix sum吧 而且题目描述有问题 2-11为什么返回false。

哈哈哈，是的naive了，数字不可见的

先前缀和搞一波再说？

要么线段数肯定能解决

二分图？

没太看懂题目 楼主可以再举几个例子么？

感觉只要算出range 里有几个奇数几个偶数就可以了，偶数相加还是偶数， 奇数个奇数相加是奇数， 奇数加偶数是奇数。

我觉得是构建graph做search。知道2-10就是2和10有一条边，11-13就是11和13有一条边。从2 travel到10, 再从11 travel到13,就知道2到13是确定的。如果不能从2 travel到9, 就说明2-9是不确定的。

cynthiameowmeow 发表于 2021-2-24 19:09
不知道楼上的都在说啥 把每个前缀和看成一个节点 然后做并查集就好啦

可以請層主再多說明一下如何使用並查集嗎? 感謝

Rieman 发表于 2021-3-3 10:01
可以請層主再多說明一下如何使用並查集嗎? 感謝

这个题其实不告诉你每个数或者prefix_sum[i]的奇偶
而每一条 i, j, 奇/偶，
其实告诉你的是prefix_sum[i]之间的相对关系
比如sum(a[i]..a[j]) = 奇数,
其实告诉你的是 prefix_sum[j] - prefix_sum[i-1] = 奇数, which means prefix_sum[j] 和prefix_sum[i-1]不是同奇偶的
所以根据这个就可以每次把prefix_sum[j], prefix_sum[i-1]对应的node放到相同/不同的set里去了(或者产生矛盾)

cynthiameowmeow 发表于 2021-3-4 07:48
这个题其实不告诉你每个数或者prefix_sum的奇偶
而每一条 i, j, 奇/偶，
其实告诉你的是prefix_sum之间 ...

层主是说用Union Find嘛，比如2，10两个点同奇偶我Union到一个集合中，但是不同奇偶怎么处理呢？
2-10 偶数  union 2 10
9-11 奇数  9 11 不同奇偶
2-11 奇数  2 11  不同奇偶

给了2-11的数据之后应该要把之前的9union到2 10 的集合里去吧，不太清楚怎么搞