AGC 12 D - Colorful Balls ( Math, Combination )
D: Colorful Balls - AtCoder Grand Contest 012 | AtCoder
題意:
有若干個球排成一排,第 i 個球用顏色 C[ i ],重量 W[ i ] 描述。可以進行的操作有兩種:
1. 選擇兩個相異位置的相同顏色的球,若它們的重量和不超過 X,將它們交換位置
2. 選擇兩個相異位置的相異顏色的球,若它們的重量和不超過 Y,將它們交換位置
問可以進行任意次操作的前提下,可以有幾種不同的顏色的排列方式,輸出模 1e9 + 7 後的答案
資料規模:
1≦N≦2e5
1≦X,Y≦1e9
1≦ci≦N
1≦wi≦1e9
X,Y,ci,wi はいずれも整数
解法:
首先考慮相同顏色內,和重量最小的球的重量和為 X 以內的所有球都是一群的,這裡一群指群內所有元素被允許任意進行排列。接著考慮整體重量最小的那顆球,如果它和某另一個顏色的重量第 K 小的球的重量和在 Y 以內,那麼這顆重量最小的球可以說是和高度在那另一個顏色中 K 小的一群。再一個小小觀察是只要考慮這個重量最小的球所在的群就可以了,因為若重量最小的球都無法結合,那不提更大的了。
賽中只有想到以上,漂亮的 WA 了 6% 的測資死到最後。
原因是,還必須考慮重量最小的球所屬的顏色以外的重量最小的球,因為就算重量最小的那顆球很會跟其他顏色結合,也許輸入給的 X 會很小, 導致它所在的顏色無法結合太高。這時候會形成特例,需要其他顏色的球來幫忙結合。
這就是很會救人,卻救不了自己呢。這種傢伙最容易被忘記了,要多注意呢。
時間 / 空間複雜度:
O( N lg N ) / O( N )
#TLE but a little easier to read N, X, Y = map( int, input().split() ) C = [] W = [] for i in range( N ): c, w = map( int, input().split() ) C.append( c - 1 ) W.append( w ) c2w = [ [] for i in range( N ) ] for i in range( N ): c2w[ C[ i ] ].append( W[ i ] ) for i in range( N ): c2w[ C[ i ] ].sort() minw, _minwp = 2e9, -1 for i in range( N ): if len( c2w[ i ] ) == 0: continue if minw > c2w[ i ][ 0 ]: minw = c2w[ i ][ 0 ] _minwp = i minw2 = 2e9 # minimum weight of a ball with different color from minw's for i in range( N ): if len( c2w[ i ] ) == 0: continue if i == _minwp: continue if minw2 > c2w[ i ][ 0 ]: minw2 = c2w[ i ][ 0 ] merged = [ False for i in range( N ) ] hi = [ 1 for i in range( N ) ] for i in range( N ): if len( c2w[ i ] ) == 0: continue lb, ub = 2, len( c2w[ i ] ) while lb <= ub: mid = lb + ub >> 1 if c2w[ i ][ 0 ] + c2w[ i ][ mid - 1 ] <= X: hi[ i ] = max( hi[ i ], mid ) lb = mid + 1 else: ub = mid - 1 lb, ub = 1, len( c2w[ i ] ) www = minw2 if minw != minw2 and c2w[ i ][ 0 ] == minw else minw while lb <= ub: mid = lb + ub >> 1 if www + c2w[ i ][ mid - 1 ] <= Y: hi[ i ] = max( hi[ i ], mid ) merged[ i ] = True lb = mid + 1 else: ub = mid - 1 MOD = int( 1e9 + 7 ) fact = [ 1 ] inv_fact = [ 1 ] for i in range( 1, N + 1, 1 ): fact.append( fact[ i - 1 ] * i % MOD ) inv_fact.append( pow( fact[ i ], MOD - 2, MOD ) ) ans = fact[ sum( merged[ i ] * hi[ i ] for i in range( N ) ) ] for i in range( N ): if not merged[ i ]: continue ans = ans * inv_fact[ hi[ i ] ] % MOD print( ans )
_
#include <bits/stdc++.h> using namespace std; const int MAXN = ( int ) 2e5; int N, X, Y; int C[ MAXN ], W[ MAXN ]; vector< int > c2w[ MAXN ]; int cmax[ MAXN ]; int fact[ MAXN + 1 ]; int inv_fact[ MAXN + 1 ]; int int_pow( int v, int p, int m ){ int res = not ( v == 0 and p != 0 ); while( p ){ if( p & 1 ){ res = 1LL * res * v % m; } p >>= 1; v = 1LL * v * v % m; } return res; } int unite[ MAXN ]; signed main(){ ios::sync_with_stdio( 0 ); { cin >> N >> X >> Y; for( int i = 0; i < N; ++i ){ cin >> C[ i ] >> W[ i ]; --C[ i ]; c2w[ C[ i ] ].emplace_back( W[ i ] ); } for( int i = 0; i < N; ++i ){ sort( c2w[ i ].begin(), c2w[ i ].end() ); } } { int minw = ( int ) 2e9, minwp; for( int i = 0; i < N; ++i ){ if( c2w[ i ].empty() ) continue; if( minw > c2w[ i ][ 0 ] ){ minw = c2w[ i ][ 0 ]; minwp = i; } } int minw2 = ( int ) 2e9; for( int i = 0; i < N; ++i ){ if( c2w[ i ].empty() ) continue; if( i == minwp ) continue; if( minw2 > c2w[ i ][ 0 ] ){ minw2 = c2w[ i ][ 0 ]; } } for( int i = 0; i < N; ++i ){ if( c2w[ i ].empty() ) continue; { for( int lb = 2, ub = c2w[ i ].size(); lb <= ub; ){ int mid = lb + ub >> 1; if( c2w[ i ][ 0 ] + c2w[ i ][ mid - 1 ] <= X ){ cmax[ i ] = mid; lb = mid + 1; } else{ ub = mid - 1; } } } { for( int lb = 1, ub = c2w[ i ].size(); lb <= ub; ){ int mid = lb + ub >> 1; if( minw != minw2 and c2w[ i ][ 0 ] == minw ){ if( minw2 + c2w[ i ][ mid - 1 ] <= Y ){ unite[ i ] = mid; lb = mid + 1; } else{ ub = mid - 1; } continue; } if( minw + c2w[ i ][ mid - 1 ] <= Y ){ unite[ i ] = mid; lb = mid + 1; } else{ ub = mid - 1; } } } } } { const int MOD = ( int ) 1e9 + 7; { for( int i = fact[ 0 ] = inv_fact[ 0 ] = 1; i <= MAXN; ++i ){ fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD; inv_fact[ i ] = int_pow( fact[ i ], MOD - 2, MOD ); } } int sum = 0; for( int i = 0; i < N; ++i ){ if( not unite[ i ] ) continue; sum += max( unite[ i ], cmax[ i ] ); } int ans = fact[ sum ]; for( int i = 0; i < N; ++i ){ if( c2w[ i ].empty() ) continue; if( not unite[ i ] ) continue; ans = 1LL * ans * inv_fact[ max( unite[ i ], cmax[ i ] ) ] % MOD; } cout << ans << "\n"; } return 0; }