社区讨论
警示后人:如果你的 WA 60 的代码挂了后面八个点
P5021[NOIP 2018 提高组] 赛道修建参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lrj0oeat
- 此快照首次捕获于
- 2024/01/18 17:36 2 年前
- 此快照最后确认于
- 2024/01/18 20:34 2 年前
你大概是把符合要求的边也加入 multiset 里了。比如这种写法:
CPPwhile(!a[u].empty()){
int x = *a[u].begin(), val = k - x; //k是你二分出来的最小链的最大值
a[u].erase(a[u].begin());
if(val <= 0){
cnt ++;
continue;
}
multiset<int>::iterator iter = a[u].lower_bound(val);
if(iter == a[u].end()) ret = max(ret, x);
else cnt ++, a[u].erase(iter);
}
绝对不可以!!
因为这样会让较小的边和长度已经符合要求的边配对,但是当前根节点可能需要这条较小边组成更长的链(即增加当前根节点点权)
所以在往 multiset 里放边时,把长度符合要的边剔除掉并统计答案。
回复
共 0 条回复,欢迎继续交流。
正在加载回复...