社区讨论

自己出的(可能是毒瘤)题

学术版参与者 8已保存回复 16

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
16 条
当前快照
1 份
快照标识符
@mi6ny4h8
此快照首次捕获于
2025/11/20 07:58
4 个月前
此快照最后确认于
2025/11/20 08:27
4 个月前
查看原帖
一个图,仅包括最多A~Z共26个节点。现在给出一些节点的大小关系(不要管是什么的大小),比如A>B或C<E。大小关系有传递性,比如若A>B,B>C,则A>C。然后会有一些查询,询问两个结点的关系但是这些关系可能矛盾,比如说同时出现A>B,B>C,C>A。此时按照中间节点更少的关系算。比如在此例中,A>B,B>C可以写成A>B>C,而C<A就是C<A。因为前者在A与C之间有B,而后者没有,所以A与C的大小关系是A<C。但是如果出现了A>C和C>A,那么按较晚的为准。如果从给定条件中无法判断(比如给出A>B,B<C,询问A与C的关系),则按相等计算。(注:查询是在线的)
我想问一下能不能在多项式的时间内解决它(即它是不是P问题)
个人感觉是提高组难度,因为我一个提高1=的同学想了很久没想出来

回复

16 条回复,欢迎继续交流。

正在加载回复...