Hello 2020
B. New Year and Ascent Sequence C C C n 2 − C n^2 - C n 2 − C
这样我们任意一个序列就可以用二元组 ( l i , r i ) (l_i, r_i) ( l i , r i ) l i ← A [ 0 ] ， r i ← A [ n − 1 ] l_i \leftarrow A[0]， r_i \leftarrow A[n-1] l i ← A [ 0 ] ， r i ← A [ n − 1 ] r i ⩾ l j , ( i , j ) r_i \geqslant l_j, \quad (i, j) r i ⩾ l j , ( i , j )
for ∀ j : x ← l j \textbf{for} \ \forall j: \ x \leftarrow l_j for ∀ j : x ← l j \quad r i ⩾ x r_i \geqslant x r i ⩾ x r i r_i r i [ r i , e n d ) [r_i, end) [ r i , e n d ) r i r_i r i ( r i , l i ) (r_i, l_i) ( r i , l i )
C. New Year and Permutation tricky ，其实观察后发现[ l , r ] [l, r] [ l , r ] [ min i = l r p i ⋯ max i = l r p i ] [\min_{i = l}^{r} p_i \cdots \max_{i = l}^{r} p_i] [ min i = l r p i ⋯ max i = l r p i ] [ l , r ] [l, r] [ l , r ] l e n = r − l + 1 len = r-l+1 l e n = r − l + 1
长度为 n n n n − l e n + 1 n-len+1 n − l e n + 1 l e n len l e n
将子段缩点，剩下有 n − l e n n-len n − l e n n − l e n + 1 n-len+1 n − l e n + 1
所以最后答案就是 ( n − l e n + 1 ) ⋅ ( n − l e n + 1 ) ⋅ ( l e n ) ! ⋅ ( n − l e n ) ! (n-len+1)\cdot (n-len+1) \cdot (len)! \cdot (n-len)! ( n − l e n + 1 ) ⋅ ( n − l e n + 1 ) ⋅ ( l e n ) ! ⋅ ( n − l e n ) !
D. New Year and Conference a , b a, b a , b [ s a i , e a i ] , [ s b i , e b i ] [sa_i, ea_i], [sb_i, eb_i] [ s a i , e a i ] , [ s b i , e b i ] venue-sensitive \text{venue-sensitive} venue-sensitive S S S size ( S ) ⩾ 2 \textbf{size}(S) \geqslant 2 size ( S ) ⩾ 2 S S S a a a b b b b b b a a a venue-sensitive \text{venue-sensitive} venue-sensitive yes \text{yes} yes no \text{no} no
对于课程 i i i ( s a i , e a i , s b i , e b i ) (sa_i, ea_i, sb_i, eb_i) ( s a i , e a i , s b i , e b i ) [ s a , e a ] [sa, ea] [ s a , e a ] a a a S S S S S S 是否存在一组 ( i , j ) , i ≠ j (i, j), i \neq j ( i , j ) , i = j [ s b i , e b i ] , [ s b j , e b j ] [sb_i, eb_i], \ [sb_j, eb_j] [ s b i , e b i ] , [ s b j , e b j ] 不重合 ，即存在有 在 b b b venue-sensitive \text{venue-sensitive} venue-sensitive true \text{true} true
活动选择模型，可以先根据 s a i sa_i s a i STL \text{STL} STL S S S 所有活动 [ s a 1 ⋯ s a n ] [sa_1 \cdots sa_n] [ s a 1 ⋯ s a n ] i i i [ s a i , e a i ] [sa_i, ea_i] [ s a i , e a i ] S S S p p p s a p > e a i sa_p > ea_i s a p > e a i s a i ⩽ s a i + 1 ⩽ ⋯ ⩽ s a p − 1 ⩽ e a i sa_i \leqslant sa_{i+1} \leqslant \cdots \leqslant sa_{p-1} \leqslant ea_i s a i ⩽ s a i + 1 ⩽ ⋯ ⩽ s a p − 1 ⩽ e a i i , [ s a i , e a i ] i, \ [sa_i, ea_i] i , [ s a i , e a i ] V = [ i + 1 , p − 1 ] V = [i+1, p-1] V = [ i + 1 , p − 1 ] a a a
接下来要判断活动 i , [ s b i , e b i ] i, \ [sb_i, eb_i] i , [ s b i , e b i ] V = [ i + 1 , p − 1 ] V=[i+1, p-1] V = [ i + 1 , p − 1 ] b b b b b b [ i + 1 , p − 1 ] [i+1, p-1] [ i + 1 , p − 1 ] maxS , minE \text{maxS}, \ \text{minE} maxS , minE e b i < maxS or s b i > minE eb_i < \text{maxS} \ \textbf{or} \ sb_i > \text{minE} e b i < maxS or s b i > minE V V V i i i venue-sensitive \text{venue-sensitive} venue-sensitive
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class SegTree { public: void build(int p, int l, int r) { t[p].l = l, t[p].r = r; if (l >= r) { t[p].maxS = a[l].sb; t[p].minE = a[l].eb; return ; } int mid = (l + r) >> 1; build(p<<1, l, mid); build(p<<1 |1, mid+1, r); pull(p); } }; bool solve sort(a+1, a+1+n); // according to eb seg.build(1, 1, n); vector<int> V; V.push_back(0); for (int i = 1; i <= n; i++) V.push_back(a[i].sa); for (int i = 1; i <= n; i++) { int p = upper_bound(V.begin(), V.end(), a[i].ea) - V.begin(); p--; int maxS = seg.find(1, i+1, p, 0); int minE = seg.find(1, i+1, p, 1); if (a[i].eb < maxS || a[i].sb > minE) return false ; } return true ; }
codeforces round 714 div2
F. Swapping Problem
很显然，对于最左边的情况，不论交换前后，绝对值都为 p i + 2 ⋅ over + p j p_i + 2\cdot \text{over} + p_j p i + 2 ⋅ over + p j p i , p j p_i, p_j p i , p j over \text{over} over
能够使得结果变好的情况，按照向量方向为从小到大，如图所示 ，可以分为两类A i < B i A_i < B_i A i < B i B i < A i B_i < A_i B i < A i { X : A i < B i } , { Y : B i < A i } \{X: A_i < B_i\}, \ \{Y: B_i < A_i\} { X : A i < B i } , { Y : B i < A i } a n s = ∑ abs i − 2 ⋅ over , over ans = \sum {\text{abs}_i} - 2 \cdot \text{over}, \quad \text{over} a n s = ∑ abs i − 2 ⋅ over , over
对于 A i < B i A_i < B_i A i < B i A i A_i A i B j ⩽ A i B_j \leqslant A_i B j ⩽ A i A j A_j A j 这样使得线段overlap部分最大 ，即 over ( ( A i , B i ) , ( B j , A j ) ) \text{over}((A_i, B_i), (B_j, A_j)) over ( ( A i , B i ) , ( B j , A j ) )
对于 B i < A i B_i < A_i B i < A i
具体的算法如下
每个集合 X ( A i → B i ) , Y ( B i → A i ) X(A_i \to B_i), \quad Y(B_i \to A_i) X ( A i → B i ) , Y ( B i → A i ) X 1 ( A i , B i ) , X 2 ( B i , A i ) , Y 1 ( B i , A i ) , Y 2 ( A i , B i ) X1(A_i, B_i), X2(B_i, A_i), Y1(B_i, A_i), Y2(A_i, B_i) X 1 ( A i , B i ) , X 2 ( B i , A i ) , Y 1 ( B i , A i ) , Y 2 ( A i , B i )
A i < B i A_i < B_i A i < B i X 1 X1 X 1 ∀ A i \forall A_i ∀ A i
在集合 Y Y Y B j ⩽ A i B_j \leqslant A_i B j ⩽ A i B j B_j B j B j B_j B j B j ∈ Y 1 B_j \in Y1 B j ∈ Y 1 ∀ B j ∈ Y 1 \forall B_j \in Y1 ∀ B j ∈ Y 1 B j B_j B j A j A_j A j set \textbf{set} set
取 A j = set . r b e g i n ( ) A_j = \textbf{set}.rbegin() A j = set . r b e g i n ( ) over ← max { min ( A j , B i ) − A i } \text{over} \leftarrow \max \{\min(A_j, B_i) - A_i\} over ← max { min ( A j , B i ) − A i }
B i < A i B_i < A_i B i < A i
最后 ∑ i ∣ A i − B i ∣ − 2 ⋅ over \sum_i |A_i - B_i| - 2\cdot \text{over} ∑ i ∣ A i − B i ∣ − 2 ⋅ over
Add One x x x f ( i , b ) f(i, b) f ( i , b ) i i i b b b
f ( 0 , b ) = 1 , b ∈ digit ( x ) f ( i , b + 1 ) = f ( i , b + 1 ) + f ( i − 1 , b ) b ∈ [ 0 , 8 ] f ( i , 0 ) = f ( i , 0 ) + f ( i − 1 , 9 ) f ( i , 1 ) = f ( i , 1 ) + f ( i − 1 , 9 ) b = 9 \begin{aligned}
&f(0, b) = 1, \quad b \in \text{digit}(x) \\
&f(i, b+1) = f(i, b+1) + f(i-1, b) \quad b \in [0, 8] \\
&f(i, 0) = f(i, 0) + f(i-1, 9) \quad f(i, 1) = f(i, 1) + f(i-1, 9) \quad b = 9
\end{aligned}
f ( 0 , b ) = 1 , b ∈ digit ( x ) f ( i , b + 1 ) = f ( i , b + 1 ) + f ( i − 1 , b ) b ∈ [ 0 , 8 ] f ( i , 0 ) = f ( i , 0 ) + f ( i − 1 , 9 ) f ( i , 1 ) = f ( i , 1 ) + f ( i − 1 , 9 ) b = 9
但这样每个询问都必须重新计算遍，会超时，这里可以反着来 d p dp d p m m m 0 0 0 数位的影响 ，是相互独立的，所以算法正确
b ∈ [ 0 , 8 ] b \in [0, 8] b ∈ [ 0 , 8 ] i i i b b b i − 1 i-1 i − 1 b + 1 b+1 b + 1 f ( i , b ) = f ( i − 1 , b + 1 ) f(i, b) = f(i-1, b+1) f ( i , b ) = f ( i − 1 , b + 1 ) b = 9 b = 9 b = 9 i i i 9 9 9 i − 1 → i i-1 \to i i − 1 → i ( 0 → 9 ) , ( 1 → 9 ) (0 \to 9), (1 \to 9) ( 0 → 9 ) , ( 1 → 9 ) i i i 9 9 9 i − 1 i-1 i − 1 0 , 1 0, 1 0 , 1 f ( i , 9 ) = f ( i − 1 , 0 ) + f ( i − 1 , 0 ) f(i, 9) = f(i-1, 0) + f(i-1, 0) f ( i , 9 ) = f ( i − 1 , 0 ) + f ( i − 1 , 0 ) 最后统计 b ∈ [ 0 , 9 ] b \in [0, 9] b ∈ [ 0 , 9 ] b b b x x x f ( m , b ) f(m, b) f ( m , b )
微信
支付宝
