窝补药军训啊啊啊啊啊啊啊啊啊啊啊
T1 一眼。
考虑每个形如 ABB...BBC \texttt{ABB...BBC} ABB...BBC CBB...BBA \texttt{CBB...BBA} CBB...BBA 1 1 1 l , r l,r l , r l × ( n − r + 1 ) l \times (n - r + 1) l × ( n − r + 1 ) l × ( n − r + 1 ) l \times (n - r + 1) l × ( n − r + 1 )
T2 毕特塞特神力！！！！如题面所说，O ( n 3 ω × log n 2 4 ) O(\frac{n^3}{\omega} \times \log \frac{n^2}{4}) O ( ω n 3 × log 4 n 2 )
首先，我们有简单的 O ( n 3 ) O(n^3) O ( n 3 ) d p l , r dp_{l,r} d p l , r [ l , r ] [l,r] [ l , r ]
然后我们看到 最大值最小，直接想到二分答案。我们二分出来一个 m i d mid mi d d p l , r dp_{l,r} d p l , r [ l , r ] [l,r] [ l , r ] m i d mid mi d d p l , r dp_{l,r} d p l , r d p r , k dp_{r,k} d p r , k d p l , k dp_{l,k} d p l , k bitset 维护，表现为 dp[l] |= dp[r]。
注意枚举的顺序是 l l l r r r
T3 & T4 没改，军训回来改。
upd: 军训回来也没改
设 d p i dp_{i} d p i ( 1 , 1 ) (1,1) ( 1 , 1 ) ( x i , y i ) (x_i,y_i) ( x i , y i ) d p i = calc ( x i − 1 , y i − 1 ) − ∑ j = 1 j − 1 d p j × calc ( x i − x j , y i − y j ) dp_{i} = \operatorname{calc}(x_i - 1,y_i - 1) - \sum_{j = 1}^{j - 1}dp_j \times \operatorname{calc}(x_i - x_j,y_i - y_j) d p i = calc ( x i − 1 , y i − 1 ) − ∑ j = 1 j − 1 d p j × calc ( x i − x j , y i − y j ) calc ( h , w ) \operatorname{calc}(h,w) calc ( h , w ) x x x h h h y y y w w w
后日谈 话说这个军训要训 10 10 10 10 10 10
日记 481 字 · 2 分钟
