Checkpoint 6 tháng đầu năm 2023 (Bài tham khảo)

Hello mọi người, đây là solution của e cho checkpoint 6 tháng đầu năm 2023.

Code tham khảo:

N = int(input());
arr = [int(i) for i in input().split()];
CurrentMin = 1000000;
CurrentMaxProfit = 0;
for i in arr:
    if i < CurrentMin:
        CurrentMin = i;
        continue;
    if CurrentMaxProfit < i - CurrentMin:
        CurrentMaxProfit = i - CurrentMin;
print(CurrentMaxProfit);

Để người tại vị trí i đứng khi kết thúc thì số ước số của i phải là số lẻ, để điều đó xảy ra i phải là số chính phương.

=> Đề bài : Tìm số chính phương lớn nhất <= N

Code ví dụ:

import math
print(int(math.sqrt(int(input())) // 1))

Ý tưởng:

Gom các máy được liên kết với nhau thành cụm => Số dây ít nhất = Số cụm – 1

Thuật toán dùng để gom cụm có thể dùng DSU (Disjoint Sets Union)

Code tham khảo:

class GomCum:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def findRoot(self, x):
        if self.parent[x] != x:
            return self.findRoot(self.parent[x])
        return self.parent[x]

    def noi2May(self, x, y):
        x_root = self.findRoot(x)
        y_root = self.findRoot(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        elif self.rank[x_root] > self.rank[y_root]:
            self.parent[y_root] = x_root
        else:
            self.parent[y_root] = x_root
            self.rank[x_root] += 1
    def soDayItNhat(self, n):
        return len(set([self.findRoot(i) for i in range(n)])) - 1

[n, m] = [int(i) for i in input().split()]
res = GomCum(n)
for i in range(m):
    [a, b] = [int(i) for i in input().split()]
    res.noi2May(a, b)
if m < n - 1 :
    print(-1)
print(res.soDayItNhat(n))

Chạy vòng lặp. Khi 1 trong 2 chuỗi đã hết ký tự trong vòng lặp, thực hiện so sánh

Các case có thể gặp:

• 2 chuỗi khác tiền tố => Lấy ký tự đầu của chuỗi nhỏ hơn
• 2 chuỗi cùng tiền tố =>Lấy ký tự đầu của chuỗi có ký tự sau phần tiền tố chung nhỏ hơn (‘ABCD’ vs ‘ABCC’ => Lấy A trong ABCC)
• 2 chuỗi giống nhau => Lấy ký tự đầu của dãy nào cũng được
• 1 chuỗi là tiền tố của 1 chuỗi khác => Lấy ký tự đầu của dãy dài hơn ( Test thử với các case trong trường hợp này có thể đúc kết ra)

Code tham khảo:

def GetKey(d1, d2):
    res = ''
    while len(d1) and len(d2) :
        Len = min(len(d1), len(d2))
        if d1[:Len] < d2[:Len]:
            res += d1[0]
            d1 = d1[1:]
            continue                            

        if d2[:Len] < d1[:Len]:
            res += d2[0]
            d2 = d2[1:]
            continue    

        if len(d1) > len(d2):
            res += d1[0]
            d1 = d1[1:]
            continue                                        
        if len(d2) >= len(d1):
            res += d2[0]
            d2 = d2[1:]
            continue                                        

    if len(d1) != 0:
        return res + d1
    if len(d2) != 0:
        return res + d2    
    return res

n = int(input())
key = []
for i in range(n):
    d1 = input() 
    d2 = input() 
    key.append(GetKey(d1, d2))
[print(i) for i in key]

Bài này chúng ta có thể giải bằng quy hoạch động:

Dùng 1 list ArrRes N phần tử, ArrRes[i] = (Min tổng các dự án bị loại bỏ từ 0 -> i) + Vi

Triển khai:

Tạo 1 store để lưu min tổng các dự án bị loại bỏ từ 0 -> i

Duyệt từ dự án đầu đến dự án cuối:

1) Nếu: i < k + 1: thêm vi vào store, ArrRes[i] = Vi, continue

2) ArrRes[i] = Vi + min(store)

3) xóa ArrRes[i – k – 1] khỏi store

Tối ưu store dùng BinarySearchTree

Code tham khảo:

class BinarySearchTree:
    class Node:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None
        self.min_value = None

    def add(self, value):
        if self.root is None:
            self.root = self.Node(value)
            self.min_value = value
        else:
            self._add_recursive(self.root, value)

        if value < self.min_value:
            self.min_value = value

    def _add_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = self.Node(value)
            else:
                self._add_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = self.Node(value)
            else:
                self._add_recursive(node.right, value)

    def remove(self, value):
        self.root = self._remove_recursive(self.root, value)

        if value == self.min_value:
            if self.root is None:
                self.min_value = None
            else:
                node = self.root
                while node.left is not None:
                    node = node.left
                self.min_value = node.value

    def _remove_recursive(self, node, value):
        if node is None:
            return None

        if value < node.value:
            node.left = self._remove_recursive(node.left, value)
        elif value > node.value:
            node.right = self._remove_recursive(node.right, value)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                successor = self._find_min(node.right)
                node.value = successor.value
                node.right = self._remove_recursive(node.right, successor.value)

        return node

    def _find_min(self, node):
        if node.left is None:
            return node
        return self._find_min(node.left)

    def begin(self):
        return self.min_value

    def add_list(self, values):
        for value in values:
            self.add(value)


def solve(n, x):
    if n == 0:
        return 0

    Max = sum(arr)
    if x >= n:
        return Max

    store = BinarySearchTree()
    store.add_list(arr[:x + 1])

    for i in range(x + 1, n):
        arr[i] = arr[i] + store.begin() 
        store.remove(arr[i - x - 1])
        store.add(arr[i])
    return Max - store.begin()

n, x = map(int, input().split())
arr = [int(input()) for _ in range(n)]
print(solve(n, x))