|
我充满了 茫然 迷茫 和无措
why I re 是上天嫉妒我的可爱机灵聪明才智吗
我oj上有50 luogu 上也可以跑 就你lemon上过不去 嘎嘎
sad
时间安排
8.00-9.00
我预判了我会犯困 于是一早就喝了红牛 （虽然还是犯困但没那么困了）
然后推了好久的T1（正做） 感觉没有什么想法 sad
9.00-10.30
推了会T2 感觉越推越迷茫 我是想O（1） 推规律什么的）
这里犯了一个太雨露均沾到毛病
10.30-11.30
打了T3 写了一车优化试图冲50 （然后lemon re why why why
11.30-12.30
猛地反应过来T1可以反做 转化成：如果一个路径上 没有被覆盖的边只有一条的话 那么这个路径就可以覆盖上去
我想了很久 还是只会
n
2
?
l
o
g
2
n^2~log^2
n2?log2 做这个
upd:赛后我看luogu 第一篇题解 完美的表达了我想干的事 真的 什么树剖 什么线段树 just启发式合并+set+堆
12.30-13.00
算了算T2的复杂度 发现暴力冲不过去（忘了打表 主要是有一点点不会写check）
题目分析
T1
正做困难 考虑反做
然后考虑 转换后 其实可以等价于每次如果一条边上既有蓝色又有红色 可以把这一坨点合并
然后高妙set+map
T2
不太懂 但我认为可以分类讨论三种情况做）
T3
我预处理了质因数分解 邻接表拉链 可以判断出 一个点最多分不超过10个质因数出来 然后搞个桶check一下
理论复杂度
n
n
8
n\sqrt n8
nn
?8 但是实际应该比这个小得多
so why re！！！！！！！
|