NOIP2023T2有人和我做法一样吗
  • 板块学术版
  • 楼主封禁用户
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/11/18 22:37
  • 上次更新2023/11/19 09:28:00
查看原帖
NOIP2023T2有人和我做法一样吗
676498
封禁用户楼主2023/11/18 22:37

我的做法:先 Θ(m)\Theta(m) 算出每个值最后变成了什么(xj,−xj,T,F,Ux_j,-x_j,T,F,U),然后是 xj,−xjx_j,-x_j 的就连无向边,每个连通块两遍 dfsdfs

第一遍算出连通块大小,并判断是否有固定值(T,F,UT,F,U),有的话因为存在一种构造,所以可以判断出是否需要全是 UU

第二遍是第一遍没有的时候执行的,用边来进行染色,判定是否可以构成非 UU 染色

有人跟我一样吗(考试的时候莫名其妙乱搞的,似乎别人都是基环树/并查集/2-SAT,但是我想到并查集不敢写,怕带权权值写错挂掉)

违规自删

2023/11/18 22:37
加载中...