专栏文章

20251125

1123456ph
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0oxaj
此快照首次捕获于
2025/12/01 18:39
3 个月前
此快照最后确认于
2025/12/01 18:39
3 个月前
查看原文

T1

一个纯贪心题。难度在于直接贪心的错误性的发现或证明，以及超水的大样例。
简单来说。直接贪心是错的，需要打补丁。但是大样例能全过，所以就看你发没发现它是错的。
在看到大样例 T=1T=1 的时候我愣了一下。但是我只想到 T=1T=1 我多测可能出问题，没有想到 T=1T=1 可以放过去错解。我就把大样例copy10遍再测了一次。过了。我就没有考虑正确性的问题了。
然后就WA了。

T2

傻傻的去模样例。模了30min后找到规律。
【图片位招租】
很美妙的样例图，一眼就能看出很多性质。最后代码10min打完，感觉画这一张图30min不亏。
赛后得知可以直接dp。dpi=min⁡(max⁡(dpj+t2j,ik)+t2j+(i−j)t1)dp_i = \min(\max(dp_j+t_2j,ik)+t_2j+(i-j)t_1)。然后我发现我的柿子和这个一模一样。
但是呢。我这样省去了证明单调性的苦恼，也不会陷入【数据删除】的数据结构优化dp中。

T3

感觉挺版。由于楼梯左部一定是一列，直接枚举。向右的最长长度是可 O(hw)O(hw) 预处理的。然后就是单调栈例题了。

T4

有两种解法：
  • 转化为图论。断环为链 (n→2nn \rightarrow 2n)。
  • 倍增，枚举左端点(n→nn \rightarrow n)。
最重要的就是 所有带环的问题全部换成序列上的问题。
（其实不止是环，树上的也可以拍成序列）。

T5

我猜过不出现 010010 或者 101101 就是 YES 的结论（也就是一定可以调换顺序使得成立）。不会证。
如果我顺着刚刚那玩意往下的话，我会考虑最优的顺序，然后说不定就推出来了。
考场上想的是：第一问都不会，那还做啥。
这是错的。因为正解是构造最优，看能否满足条件。

总结

  • 贪心要打对拍
  • 有环，断环为链

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...