[acwing weekly rematch] game 60 20220716

One 、 Summary of this week's race

• First time acwing, Three questions in total , Difficult jump .
• acwing python I don't support from math import comb, shock ！ You have to do it yourself .
• 
  

Two 、 4494. having dinner

link : 4494. having dinner

1. Title Description

2. Thought analysis

grading Easy.
Sign in problem , Obviously as long as m and k At the same time greater than or equal to n that will do .

3. Code implementation

import io
import os
import sys
from collections import deque

if os.getenv('LOCALTESTACWING'):
    sys.stdin = open('input.txt')
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

if __name__ == '__main__':
    n, m, k = map(int, input().split())
    if n <= m and n <= k:
        print('Yes')
    else:
        print('No')

3、 ... and 、4495. Array operation

link : 4495. Array operation

1. Title Description

2. Thought analysis

It's hard , I almost didn't learn much , Study on the spot .

• Because you want to find the minimum number , We can a Sort , The leftmost non 0 Number is the answer every time .
• But every time, we have to check all the non 0 Subtract a value from the data , This kind of interval operation is to think about whether it can lazy, Only record the first value , Then I think this is the difference method .
• a Create a differential array after sorting diff,diff[0]=a[0], Other positions represent a[i] A few larger than the previous position .
• So we just need diff Find the first non 0 Elements x, because x There must be 0, therefore a[i]=diff[i], That is the answer to the first operation x.
• At the same time, the following numbers should be subtracted x, Give Way diff[i]=0 that will do .
• Follow up answers continue to find the first non 0 Number of numbers , If you can't find it , return 0.

3. Code implementation

import io
import os
import sys
from collections import deque

if os.getenv('LOCALTESTACWING'):
    sys.stdin = open('input.txt')
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    diff = [a[0]]
    for i in range(1, n):
        diff.append(a[i] - a[i - 1])
    j = 0
    for _ in range(k):
        while j<n and diff[j] == 0:
            j += 1
        if j >= n:
            print(0)
        else:
            print(diff[j])
            diff[j] = 0

Four 、4496. Eat fruit

link : 4496. Eat fruit

1. Title Description

2. Thought analysis

Combinatorial mathematics .

• The title means to ignore the leftmost child , But he can choose m Kind of fruit , The first ans Initialize to m.
• Then in addition to the position of the front row , choose k Change the type of fruit in one place ,C(n-1,k) Seed selection .
• Change fruit every time , Yes m-1 Methods ,(m-1)^k.
• The most annoying thing is acwing python3 Can't even introduce math.comb, So write your own combinatorial formula

3. Code implementation

import io
import os
import sys
from collections import deque
from math import factorial

if os.getenv('LOCALTESTACWING'):
    sys.stdin = open('input.txt')
else:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MOD = 998244353
if __name__ == '__main__':
    n, m, k = map(int, input().split())
    def comb(m,r):
        return factorial(m)//(factorial(r)*factorial(m-r))
    ans = m*comb(n-1,k)*((m-1)**k)

    print(ans % MOD)

6、 ... and 、 Reference link

• nothing