edu112
A
憨憨题,6,8,10的性价比都一样,奇数铁不行,只能用偶数。
偶数就直接除2。随便组合就行。特判 2,4即可。
B
憨憨题,发现直接沿着 x 轴,y 轴平移即可。
新的矩形只能放在四角,判一判平移会不会出界即可。
C
憨憨题,Alice只能选择一个 \((1,y)\) 向下走到 \((2,y)\)。
所以 Bob 能走的是 \(\max(suf_{y+1},pre_{y-1})\)。
模拟即可。
D
憨憨题,发现因为字符集大小为 3,合法串只可能长成 \(\texttt{abcabcabc}\cdots\texttt{abc}\) 的样子,所以直接就枚举字符集全排列,判一判就好了。
前缀和模拟即可,复杂度 \(\mathcal{O(6n)}\)
E
发现这个1与n联通等价于把选出的 segment +1,看是不是全大于0.
然后最大减最小尽可能小?
我会 binary search 发现 \(m\leq 10^6\) 好像不大行。
那我会 two pointers!
先按 \(w\) 排序,显然,枚举右端点,看此时合法到哪里,移动左端点。
正确性显然。
复杂度:\(\mathcal{O(n\log m)}\)。
憨憨题考试都做不对,呜呜呜
F
憨憨DS,睡了一觉就会了。(其实考试时都没看到,充分说明自己菜)
如何快速看一个边合不合法?
如果存在套环的情况,考虑对于对于环 \(c_1,c_2\) 。
一个最大的边的子集 \(s\) ,如果\(s\subset c_1,s\subset c_2\)。那么 \(c_1,c_2\) 的异或都为一,并且\(c_1\) 并 \(c_2\) 去除 \(s\) 的简单回路异或就为 \(0\) 不合法。
所以不可能存在套环的情况。
这就提示我们这玩意是个边仙人掌。
直接考虑树。
如果是一条连接一颗树上的两个节点的边,那么首先判断是否路径上的边都不在任意一个连通块内。
然后再看新形成的一个环的 \(\texttt{xor}\) 是否为1。
如果是一条连接两个连通块的边,一定行。
LCT (le ci te) 不好写,嘤嘤嘤。
离线把最终的树建出,考虑对树的形态产生影响的边只有连接连通块的边,用并查集维护即可。
然后随便剖一剖就好了。
复杂度 \(\mathcal{O(q\log^2n)}\) 大概率比 LCT 快吧((((。