社区讨论
自己出的(可能是毒瘤)题
学术版参与者 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 条回复,欢迎继续交流。
正在加载回复...