联合省选 2025 集中讨论贴

站务版

chen_zhe @ 2025-03-01 00:04:38

祝各位考生 ++RP！游记将在周日开放提交通道。

本帖的内容可能会对考生造成显著心态影响。建议考生至少在 Day2 结束后再观看本帖内容。

  • 游记征集：https://www.luogu.com.cn/article/collection/209
  • Day1 T1：https://www.luogu.com.cn/problem/P11830
  • Day1 T2：https://www.luogu.com.cn/problem/P11831
  • Day1 T3：https://www.luogu.com.cn/problem/P11832
  • Day2 T1：https://www.luogu.com.cn/problem/P11833
  • Day2 T2：https://www.luogu.com.cn/problem/P11834
  • Day2 T3：https://www.luogu.com.cn/problem/P11835

发布 ++RP 请前往 https://www.luogu.com.cn/discuss/1062233

本贴中单纯的 ++RP 等祝福（而不带学术交流的内容）可能会被删除。

by Poncirus @ 2025-03-01 15:41:29

@a1co0av5ce5az1cz0ap_ 意思是线段树下标是 a，为了和同一句话后文的下标是时间做区分，dbq 不太会说话 qwq

by zcz0263 @ 2025-03-01 15:42:34

@Ace_FutureDream 我写了一个不如大多数人2log跑得快的1log。

by IkunTeddy @ 2025-03-01 15:42:57

@Poncirus 我说，在DAG上线段树合并的复杂度不是错的吗

by Xy_top @ 2025-03-01 15:43:38

@a1co0av5ce5az1cz0ap_ 对于每个点开一个长度为 n 的 01 序列，第 x 个位置表示能不能到 a_v = x 的点，能到的话这个位置给 b_v。然后点 u 的 01 序列就是所有点 u 能到的点的 01 序列合起来。

查询就是区间最大值，需要动态开点。

by wangzqh2025 @ 2025-03-01 15:43:58

@Xy_top 不容易呀，终于找到跟我一样的做法了

by Xy_top @ 2025-03-01 15:44:49

但是这个时间复杂度是错的，可以对询问分块，然后每 \sqrt{n} 个点跑一个多源 BFS，这样是 O((n+q)\sqrt{n}) 的

by wangzqh2025 @ 2025-03-01 15:45:18

@Xy_top 我本机大样例O2跑0.6s，应该差不多能过

by Xy_top @ 2025-03-01 15:46:03

@wangzqh2025 复杂度是错的，可以构造长为 n/2 的链，点的编号分别是 1 3 5 7，然后你就被卡死了。

by wangzqh2025 @ 2025-03-01 15:46:25

@Xy_top 但是这次评测机据说很慢，而且大样例还没卡满

by lznxes_xh @ 2025-03-01 15:46:30

@Xy_top 不是哥们又不修改，我 3 个差分 （前面，后面，有没有）

上一页 | 下一页