活動(dòng)地址： ?？痛赫兴㈩}訓(xùn)練營 - 編程打卡活動(dòng)

簡單題 小美的外賣訂單編號

• 訂單編號從 1 開始，每發(fā)起一個(gè)訂單編號加 1。當(dāng)訂單編號達(dá)到上限 m 后，下一個(gè)訂單編號又從 1 開始。
• 這種規(guī)則可以用數(shù)學(xué)中的取模運(yùn)算來描述：
  • 如果當(dāng)前訂單編號為 x，則其對應(yīng)的實(shí)際編號可以通過公式 (x-1)%m + 1 計(jì)算。
    • (x - 1) → 讓編號從 0 開始好做循環(huán)。
    • % m → 保證編號在 0 ~ m-1 之間循環(huán)。
    • + 1 → 讓編號重新回到 1 ~ m。

package main

import "fmt"

func main() {
	var q int
	fmt.Scan(&q)
	for i := 0; i < q; i++ {
		var m, x int
		fmt.Scan(&m, &x)
		fmt.Println((x-1)%m + 1)
	}
}

中等題 買賣股票的最好時(shí)機(jī)(一)

• 如果在某一天買入股票，那么我們需要在之后價(jià)格最高的那一天賣出，才能獲得最大利潤。
• 因此，問題的核心是記錄當(dāng)前最低買入價(jià)格，并計(jì)算每一天賣出時(shí)的潛在利潤。

package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)
	ans, minPrice := 0, math.MaxInt
	for i := 0; i < n; i++ {
		var v int
		fmt.Scan(&v)
		if v < minPrice {
			minPrice = v
		}
		if v-minPrice > ans {
			ans = v - minPrice
		}
	}
	fmt.Println(ans)
}

困難題 數(shù)位染色

1. 問題轉(zhuǎn)化：子集和問題

首先，計(jì)算所有數(shù)字的總和 sum 。

• 如果 sum 是奇數(shù)，則無法平分，直接返回 "No"。
• 如果 sum 是偶數(shù)，則問題轉(zhuǎn)化為：是否能從這些數(shù)字中選出一個(gè)子集，使得子集的數(shù)字之和等于 sum/2 。

這實(shí)際上是一個(gè)經(jīng)典的子集和問題（Subset Sum Problem）。

2. 動(dòng)態(tài)規(guī)劃解決子集和問題

我們使用動(dòng)態(tài)規(guī)劃來判斷是否存在一個(gè)子集，其數(shù)字之和等于 sum/2 。

動(dòng)態(tài)規(guī)劃的狀態(tài)定義

• 定義 dp[i] 表示是否可以通過選擇某些數(shù)字，使得它們的和為 i 。
• 初始狀態(tài)：dp[0] = true（和為 0 的情況總是可行的）。

狀態(tài)轉(zhuǎn)移方程

• 對于每個(gè)數(shù)字 d（即 x 的每一位數(shù)字），從大到小更新 dp 數(shù)組： ，其中 j 從 到 0。
  • 這里的從大到小更新是為了避免重復(fù)使用同一個(gè)數(shù)字。

package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)
	sum := 0
	for _, c := range s {
		sum += int(c - '0')
	}
	if sum%2 != 0 {
		fmt.Println("No")
		return
	}
	dp := make([]bool, sum/2+1)
	dp[0] = true
	for _, c := range s {
		d := int(c - '0')
		for j := sum/2 - d; j >= 0; j-- {
			dp[j+d] = dp[j+d] || dp[j]
		}
	}
	if dp[sum/2] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}