社区讨论

警示后人:如果你的 WA 60 的代码挂了后面八个点

P5021[NOIP 2018 提高组] 赛道修建参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lrj0oeat
此快照首次捕获于
2024/01/18 17:36
2 年前
此快照最后确认于
2024/01/18 20:34
2 年前
查看原帖
你大概是把符合要求的边也加入 multiset 里了。比如这种写法:
CPP
while(!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 条回复,欢迎继续交流。

正在加载回复...