不是今晚打的也不是昨晚打的。
速写这一块。
下次巅峰赛一定要快点出难一点的 T6 啊,这是我了解算法模板的唯一途径
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1
显然能翻转就翻转。这不需要证吧。
然后随便写一下就行了。
时间复杂度:O(n)O(n)O(n)。
T2
强烈谴责 ACGO 没标数据范围这一行为。
显然加到刚好大于就行了。这不需要证吧。
然后随便写一下就行了。
时间复杂度:O(n)O(n)O(n)。
T3
叽里咕噜说什么呢。
先转化一下,将边权对 222 取模显然没有影响。然后求的就是这些路径的和为偶数。注意到一个 0,10,10,1 数列和为偶数,那异或和一定为 000。
考虑强化问题。我们统计出所有路径异或之和,然后拿总路径数减去它即可。
注意到求路径异或和这个问题我刚好做过,是 A75099。具体可以参考这个题解。
然后稍微改改就出来了。
时间复杂度:O(nk)O(nk)O(nk),其中 k=60k=60k=60。其实 kkk 可以直接取到 111,但我懒得改了。
T4
好题。
注意到先不下降再不上升可以拆成两段:不下降,不上升。
所以考虑建分层图。对于不下降部分,将点权小的连向点权大的;对于不上升部分,将点权大的连向点权小的;然后每个不下降部分的点都连向不上升部分的对应点。
然后跑不下降 S→S\rarrS→ 不上升 TTT 最短路即可。
时间复杂度:O(mlogn)O(m\log n)O(mlogn)。
T5
注意到只选一个即可使得 C=0C=0C=0,所以 Cmin=0C_{\min}=0Cmin =0。
然后发现第一个数只要不是 000,要想 C=0C=0C=0,那后面的必须是正数;第一个数是 000 那后面的选啥都行。
所以我们求出后缀的正数数量,然后分为 000 和非 000 处理。
时间复杂度:O(n)O(n)O(n)。