整体来说我的表现很差，经常卡题 (做不出来或者调半天)，拿成绩主要还是靠着西电大区优秀的匹配机制 (以及土豆摆烂)。
给定正整数组成的序列 { b i } { b i }
1 ≤ l ≤ i 1 < i 2 < i 3 ≤ r ≤ ∣ { b i } ∣ b i 1 + b i 2 + b i 3 − ( r − l ) 1 ≤ l ≤ i 1 < i 2 < i 3 ≤ r ≤ ∣ { b i } ∣ max b i 1 + b i 2 + b i 3 − ( r − l )
显然取 l = i 1 l = i 1 r = i 3 r = i 3
1 ≤ i 1 < i 2 < i 3 ≤ ∣ { b i } ∣ ( b i 1 − i 1 ) + b i 2 + ( b i 3 + i 3 ) 1 ≤ i 1 < i 2 < i 3 ≤ ∣ { b i } ∣ max ( b i 1 − i 1 ) + b i 2 + ( b i 3 + i 3 )
这样就是个经典的“多阶段决策最优化问题”，可以 DP：用 f x ( i ) f x ( i ) i i x x { i k } { i k }
f 1 ( i ) = max ( f 1 ( i − 1 ) − 1 , b i ) f 2 ( i ) = max ( f 2 ( i − 1 ) − 1 , f 1 ( i − 1 ) − 1 + b i ) f 3 ( i ) = max ( f 3 ( i − 1 ) , f 2 ( i − 1 ) − 1 + b i ) f 1 ( i ) = max ( f 1 ( i − 1 ) − 1 , b i ) f 2 ( i ) = max ( f 2 ( i − 1 ) − 1 , f 1 ( i − 1 ) − 1 + b i ) f 3 ( i ) = max ( f 3 ( i − 1 ) , f 2 ( i − 1 ) − 1 + b i )
答案就是 f 3 ( ∣ { b i } ∣ ) f 3 ( ∣ { b i } ∣ ) O ( n ) O ( n ) x x O ( 1 ) O ( 1 )
交互题。每次可以询问一个整数，对方会告诉你这个数是大于，小于，还是等于答案 (保证答案是不超过 m m i i p i n p i m o d n 1 1 60 6 0 n n m m 1 ≤ n ≤ 1 0 9 1 ≤ n ≤ 1 0 9 1 ≤ m ≤ 30 1 ≤ m ≤ 3 0
直接问 n n 1 1 1 1 1 1 { p i } { p i }
这题十分甚至九分地无聊。
给定整数序列 { a i } { a i } l , r , x l , r , x { a l , ⋯ , a r } { a l , ⋯ , a r } x x i , y i , y a i a i y y 0 < a i ≤ 1 0 9 0 < a i ≤ 1 0 9 ∣ { a i } ∣ ≤ 5 × 1 0 5 ∣ { a i } ∣ ≤ 5 × 1 0 5 4 × 1 0 5 4 × 1 0 5
容易看出如果 x ∣ g c d ( a l , ⋯ , a r ) x ∣ g c d ( a l , ⋯ , a r ) x x k k l ≤ k ≤ r l ≤ k ≤ r x ∤ g c d ( a l , ⋯ , a k ) x ∤ g c d ( a l , ⋯ , a k ) k k a k a k x x g c d ( a k + 1 , ⋯ , a r ) g c d ( a k + 1 , ⋯ , a r ) x x
这样的时间复杂度是 O ( ( n + q log n ) log max a i ) O ( ( n + q log n ) log max a i ) O ( ( n + q ( log n ) 2 ) log max a i ) O ( ( n + q ( log n ) 2 ) log max a i )
比赛的时候 latato 选手搁那摆烂，在注释里面用自然语言打出了算法，然后打出“但是我不想写”，结果输了。
给定整数序列 { a i } , { b i } { a i } , { b i } p p q q { a q , a q + p , a q + 2 p , ⋯ , a q + ( ∣ { b i } ∣ − 1 ) p } { a q , a q + p , a q + 2 p , ⋯ , a q + ( ∣ { b i } ∣ − 1 ) p } { b i } { b i } 1 ≤ ∣ { a i } ∣ , ∣ { b i } ∣ , p ≤ 2 × 1 0 5 1 ≤ ∣ { a i } ∣ , ∣ { b i } ∣ , p ≤ 2 × 1 0 5
先把所有下标 1 , 2 , ⋯ , ∣ { a i } ∣ 1 , 2 , ⋯ , ∣ { a i } ∣ p p p = x p = x p = x + q p = x + q a x a x a x + ∣ { b i } ∣ p a x + ∣ { b i } ∣ p std::map 维护一下元素值的出现次数，和 { b i } { b i } std::map 最坏是线性时间复杂度的，所以要进一步维护一下出现次数不正确的元素的个数，这样次数不正确的元素个数为 0 0
因为数据出水了，所以强行比较两个 std::map 能过，可以用数据 { a i } = { 1 , 2 , ⋯ , 1 0 5 , 1 , 2 , ⋯ , 1 0 5 } { a i } = { 1 , 2 , ⋯ , 1 0 5 , 1 , 2 , ⋯ , 1 0 5 } { b i } = { 1 , 2 , ⋯ , 1 0 5 } { b i } = { 1 , 2 , ⋯ , 1 0 5 } p = 1 p = 1
有一个无向图 G = ( N + , E ) G = ( N + , E ) E = { ( u , v ) ∈ ( N + ) 2 ∣ ∣ u − v ∣ ∈ B } E = { ( u , v ) ∈ ( N + ) 2 ∣ ∣ u − v ∣ ∈ B } B B B ′ B ′ B B G G ∣ B ∣ ∣ B ∣ 1 ≤ ∣ B ′ ∣ ≤ 2 × 1 0 5 1 ≤ ∣ B ′ ∣ ≤ 2 × 1 0 5 B ′ ⊂ N + B ′ ⊂ N + max ∣ B ′ ∣ ≤ 1 0 18 max ∣ B ′ ∣ ≤ 1 0 1 8
根据二分图的定义，判断 G G
∀ { a i } ∈ { ( N 0 ) ∣ B ∣ ∣ ( ∑ i a i 2 ) = 1 } : ∑ i a i b i ≠ 0 ∀ { a i } ∈ { ( N 0 ) ∣ B ∣ ∣ ∣ ∣ ∣ ∣ ∣ ( i ∑ a i m o d 2 ) = 1 } : i ∑ a i b i = 0
手玩几个样例，我们能够发现 G G 不是 二分图的一个充分条件是 ∃ b i , b j ∈ B : 2 ∣ ( b i / g ) ∃ b i , b j ∈ B : 2 ∣ ( b i / g ) g = g c d ( b i , b j ) g = g c d ( b i , b j ) 2 ∤ ( b j / g ) ) 2 ∤ ( b j / g ) ) a i = − b j / g a i = − b j / g a j = b i / g a j = b i / g ( a i + a j ) ∤ 2 ( a i + a j ) ∤ 2 a i b i + a j b j = ( − b j / g ) ⋅ b i + ( b i / g ) ⋅ b j = 0 a i b i + a j b j = ( − b j / g ) ⋅ b i + ( b i / g ) ⋅ b j = 0 ∀ b i , b j ∈ B : 2 ∤ ( b i / g c d ( b i , b j ) ) ∀ b i , b j ∈ B : 2 ∤ ( b i / g c d ( b i , b j ) ) 2 t ∣ g c d ( b 1 , b 2 , ⋯ b n ) 2 t ∣ g c d ( b 1 , b 2 , ⋯ b n ) b i / 2 t b i / 2 t
0 = ( ∑ i a i b i ) / 2 t = ∑ i a i ⋅ ( b i / 2 t ) ≡ ∑ i a i ( m o d 2 ) 0 = ( i ∑ a i b i ) / 2 t = i ∑ a i ⋅ ( b i / 2 t ) ≡ i ∑ a i ( m o d 2 )
即环都是偶环，所以一定是二分图。
这样我们把 B ′ B ′ 2 114514 2 1 1 4 5 1 4
五维空间中有 n n p 1 , p 2 , ⋯ , p n p 1 , p 2 , ⋯ , p n ∃ i , j : ∠ p i p x p j > π ∃ i , j : ∠ p i p x p j > π p x p x 1 ≤ n ≤ 1000 1 ≤ n ≤ 1 0 0 0
首先我们对于所有 i , j i , j q i j = O p i ⃗ ⋅ O p j ⃗ q i j = O p i ⋅ O p j ∠ p i p x p j > π ∠ p i p x p j > π p x p i ⃗ ⋅ p x p j ⃗ = ( O p i ⃗ − O p x ⃗ ) ⋅ ( O p j ⃗ − O p x ⃗ ) = q i j − q i x − q j x + q x x p x p i ⋅ p x p j = ( O p i − O p x ) ⋅ ( O p j − O p x ) = q i j − q i x − q j x + q x x O ( n 3 ) O ( n 3 ) i , j i , j p x p x 1 / 27 1 / 2 7
有 n n i i a i a i b i b i i i x x j j x ≤ a i x ≤ a i b i b i b i − x b i − x b j b j min ( a j , b j + x / 2 ) min ( a j , b j + x / 2 ) j j 0 0 i i i = 1 , 2 , ⋯ , n i = 1 , 2 , ⋯ , n 1 ≤ n ≤ 100 1 ≤ n ≤ 1 0 0 0 ≤ b i ≤ a i ≤ 100 0 ≤ b i ≤ a i ≤ 1 0 0 a i > 0 a i > 0
首先容易看出每个水分子最多倒一次，所以最后肯定是选出 i i i i
类似背包，用 f ( i , j , k ) f ( i , j , k ) i i j j k k
f ( i , j , k ) = min { f ( i − 1 , j , k ) + 0.5 b i , f ( i − 1 , j − 1 , k − a i ) } f ( i , j , k ) = min { f ( i − 1 , j , k ) + 0 . 5 b i , f ( i − 1 , j − 1 , k − a i ) }
第 i i
j min ( j , ( ∑ b i ) − f ( n , i , j ) ) j max min ( j , ( ∑ b i ) − f ( n , i , j ) )
这样做时间复杂度和空间复杂度都是 O ( n 2 ∑ a i ) O ( n 2 ∑ a i ) double 类型 (8 8 O ( n ∑ a i ) O ( n ∑ a i )
给定一个有根树，它包含 n n k k k k 1 1 2 ≤ n ≤ 3 × 1 0 5 2 ≤ n ≤ 3 × 1 0 5
有 n n { a i } ∈ { 1 , 2 , ⋯ , x } n { a i } ∈ { 1 , 2 , ⋯ , x } n 1 1 1 1 { a i } { a i } 2 ≤ n ≤ 500 2 ≤ n ≤ 5 0 0 1 ≤ x ≤ 500 1 ≤ x ≤ 5 0 0
定义 f ( i , j ) f ( i , j ) j j i i i ≥ j i ≥ j
f ( i , j ) = ∑ t = 2 j ( j t ) ( j − 1 ) j − t f ( i − ( j − 1 ) , t ) f ( i , j ) = t = 2 ∑ j ( t j ) ( j − 1 ) j − t f ( i − ( j − 1 ) , t )
其中 t t ( j t ) ( t j ) j j t t ( j − 1 ) j − t ( j − 1 ) j − t j − t j − t 1 , 2 , ⋯ , j − 1 1 , 2 , ⋯ , j − 1 j − 1 j − 1 j − t j − t i − ( j − 1 ) i − ( j − 1 ) j − 1 j − 1 j − 1 j − 1
而 1 < i < j 1 < i < j j j i i
f ( i , j ) = i j − ( i − 1 ) j f ( i , j ) = i j − ( i − 1 ) j
答案就是
∑ i = 1 x f ( i , n ) i = 1 ∑ x f ( i , n )
这样就可以 O ( n 2 x ) O ( n 2 x )