2021牛客國慶集訓派對day5 題解-A,B,F,G,J

★

J-plan

有n個學生要去旅行。酒店有兩種類型的房間：雙人房和三人間。雙人房的價格是p2，三人房的價格是p3

現在你需要計算這些學生的最低總成本。

求得最小公倍數為6

當 p32 >= p23 時（雙人間更實惠）

兩種情況：

一：當n%2 == 0 即剛好雙人間可住滿 ， 輸出 n/2 p2

二：當n%2 == 1 可分為兩種方案，剩一個人住雙人間和剩三個人住三人間 去最小值：

min( n/2p2+p2 , (n/2-1)p2+p3 )

當 p32 < p23 時

三種情況：

if( n%3 == 0 ) cout << n/3p3 << endl ;三人間住滿

else if( n%3 == 1 ) cout << min( n/3p3+p2 , (n/3-1)p3+2p2 ) << endl ;餘下一個人，選擇雙人間或者餘下四人選兩個雙人間

else cout << min( n/3p3+p2 , n/3*p3+p3 ) << endl ;餘下兩個人，選擇雙人間或者選三人間

AC代碼：

void solve() 
{
    int n , p2 , p3 ;
    cin >> n >> p2 >> p3 ;
    if( p3*2 >= p2*3  ){
        if( n%2 == 0 ) cout << n/2 *p2 << endl ;
        else cout << min( n/2*p2+p2 , (n/2-1)*p2+p3 ) << endl ;
    }
    else {
        if( n%3 == 0 ) cout << n/3*p3 << endl ;
        else if( n%3 == 1 ) cout << min( n/3*p3+p2 , (n/3-1)*p3+2*p2 ) << endl ;
        else cout << min( n/3*p3+p2 , n/3*p3+p3 ) << endl ;
    }
    return ;
}
           

★

G-Max

給出兩個正整數c，n。你需要找到一對滿足1<=a，b<=n的整數（a，b），a和b的最大公除法是c。你需要最大化a和b的乘積

當c > n 時 無解

當 n==c 時 輸出 cc

當c < n 時 輸出 cc*(n/c)*(n/c-1)

★★

A-gpa

經典二分 對于答案 res,

∑ i = 1 n s [ i ] ∗ c [ i ] ∑ i = 1 n s [ i ] \frac{\sum_{i=1}^ns[i]*c[i]}{\sum_{i=1}^ns[i]} ∑i=1n​s[i]∑i=1n​s[i]∗c[i]​ > res

<=> ∑ i = 1 n s [ i ] ∗ c [ i ] \sum_{i=1}^ns[i]*c[i] ∑i=1n​s[i]∗c[i] > ∑ i = 1 n ( s [ i ] ∗ r e s ) \sum_{i=1}^n(s[i]*res) ∑i=1n​(s[i]∗res)

<=> ∑ i = 1 n s [ i ] ∗ ( c [ i ] − r e s ) \sum_{i=1}^ns[i]*(c[i]-res) ∑i=1n​s[i]∗(c[i]−res) > 0

sort一遍減去最小的k個即可

AC代碼：

int n , k ;
double s[N] ;
double c[N] ;
double w[N] ;
bool cmp( double x , double y )
{
    return x > y ;
}
int check( double x )
{
    double ans = 0 ;
    for( int i = 1 ; i <= n ; i ++ ){
        w[i] = s[i]*( c[i] - x ) ; 
    }
    sort( w+1 , w+n+1 , cmp ) ;
    for( int i = 1 ; i <= n-k ; i ++ ){
        ans += w[i] ;
    }
    if( ans >= 0 ) return 1 ;
    return 0 ;
}
void solve() 
{
    cin >> n >> k ;
    for( int i = 1 ; i <= n ; i ++ ){
        cin >> s[i] ;
    }
    for( int i = 1 ; i <= n ; i ++ ){
        cin >> c[i] ;
    }
    double l = 0 ;
    double r = 1e3 ;
    while( r-l > 0.000001 ){
        double mid = ( l+r ) / 2.0 ;
        if( check( mid ) ) l = mid ;
        else r = mid ; 
    }
    cout << fixed << setprecision(10) << l << endl ;
    return ;
}
           

★★★★

B-div

題意：求 x ∈ \in ∈ { n 2 + 1 n^2+1 n2+1 , n 2 + 2 n n^2+2n n2+2n } 滿足 x 是 n 4 n^4 n4 的因子

規律推算

∵ \because ∵ x ∈ \in ∈ { n 2 + 1 n^2+1 n2+1 , n 2 + 2 n n^2+2n n2+2n } 即 n 2 + a n^2+a n2+a( 1 <= a <= 2n )是 n 4 n^4 n4 的因子

又 n 4 n^4 n4 - ( n 2 + a n^2+a n2+a)( n 2 − a n^2-a n2−a) = a 2 a^2 a2

∴ \therefore ∴ n 2 + a n^2+a n2+a 是 a 2 a^2 a2 的 因子

即 （ n 2 + a n^2+a n2+a）*m = a 2 a^2 a2

又 a <= 2n 故可得 m < 4 ,即 m = 1 ，2 ，3 ；

暴力枚舉推算得到方程有兩個

1: n 2 n_2 n2​ = 6 n 1 6n_1 6n1​- n 0 n_0 n0​( n 0 n_0 n0​=0 , n 1 n_1 n1​=2)

2: n 2 n_2 n2​ = 14 n 1 14n_1 14n1​- n 0 n_0 n0​( n 0 n_0 n0​=0 , n 1 n_1 n1​=6)

AC代碼（python）：

m = int(input())
x = 0
y = 2
while x<m:
    t = 6*y-x
    x = y
    y = t

ans = x
x = 0
y = 6

while x<m:
    t = 14*y-x
    x = y
    y = t

ans = min(ans, x)
print(ans)
           

★★★★

F-take

Kanade有n個盒子，第i個盒子有**p[i]機率有d[i]**大小的鑽石。

起初，卡納德有一顆0号的鑽石。她将從1号到n号打開盒子。當她打開一個盒子時，如果盒子裡有一顆鑽石，而且它比她的鑽石大，她會用她的鑽石替換它。

現在需要計算預期的替換數量。

您隻需要輸出%998244353。

數學期望+樹狀數組

E(a+b+c+d…) = E(a)+E(b)+E©+…

枚舉每個盒子的期望即可，因為盒子隻有打開與不打開兩種情況即0和1

sort鑽石大小，從大到小排列，保證每次開第i個寶箱時，前面寶箱一定不打開

故推算公式為

∏ j = 1 i − 1 ( 100 − p [ j ] ) ∗ p [ i ] \prod_{j=1}^{i-1}( 100-p[j] )*p[i] ∏j=1i−1​(100−p[j])∗p[i] , i ∈ ( 1 , n ) i\in(1,n) i∈(1,n)

AC代碼：

int QuickPow( int x , int pow )
{
    int res = 1 ;
    x %= Max ;
    // x %= mod ;
    while( pow ){
        if( pow & 1 ) res = ( res * x ) % Max  ;
        // if( pow & 1 ) res = ( res * x ) % mod  ;
        // if( pow & 1 ) res = res * x ;
        x = ( x * x ) % Max ;
        // x = ( x * x ) % mod ;
        // x = x*x ;
        pow >>= 1 ;
    }
    return res % Max ;
    // return res ;
    // return res % mod ;
}

int gcd( int a , int b )
{
    if(!b) return a ;
    return gcd( b , a%b ) ;
}
// 解決方案代碼區--------------------------------------------------
const int N = 1e5+7 ;
const int M = 2e6+7 ;
struct node
{
    int w ;
    int p ;
    int id ;
    /* data */
};
node a[N] ;
int b[N] ;
int n ;
int lowbit( int x )
{
    return x & (-x) ;
}
bool cmp( node x , node y )
{
    if( x.w == y.w ) return x.id < y.id ;
    return x.w > y.w ;
}
int mul( int x )
{
    int ans = 1 ;
    while( x ){
        ans = ( ans*b[x] )%Max ;
        x -= lowbit(x) ;
    }
    return ans ;
}
void add( int x , int p )
{
    while( x <= n ){
        b[x] = ( b[x]*p )%Max ;
        x += lowbit( x ) ;
    }
}
void solve() 
{
    cin >> n ;
    for( int i = 1 ; i < N ; i ++ ) b[i] = 1 ;
    for( int i = 1 ; i <= n ; i ++ ){
        cin >> a[i].p >> a[i].w ;
        a[i].id = i ;
        // cout << b[i] << endl ;
    }
    sort( a+1 , a+n+1 , cmp ) ;
    int res = 0 ;
    for( int i = 1 ; i <= n ; i ++ ){
        res = ( res + 1ll*mul( a[i].id )%Max*( a[i].p%Max*( QuickPow( 100 , Max-2 )%Max )%Max)%Max )%Max ;
        // cout <<res << endl ;
        add( a[i].id , QuickPow( 100 , Max-2 )%Max*(100-a[i].p)%Max ) ;
    }
    cout << res << endl ;
    
    return ;
}