HDU 5535 Cake：構造 + 記憶化搜索解題報告

HDU 5535 Cake：構造 + 記憶化搜索解題報告

題目大意

給定 n 和 m（1 ≤ n ≤ 1e5，2 ≤ m ≤ 10），判斷能否將 1 ~ n 分成 m 組，使每組數字之和相等。若可能，輸出任意一種分組方案；否則輸出 NO。測試組數 T ≤ 1000。

核心觀察

1. 總和 S = n(n+1)/2 必須能被 m 整除，否則無解。
2. 每組目標和 avg = S / m 必須 ≥ n（因為最大數 n 必須放入某組，且組和至少為 n），即 avg ≥ n，否則無解。

構造策略：週期性配對

當 n ≥ 4m - 1 時，可採用「首尾配對」構造法：

• 取最大的 2m 個數：n-2m+1, n-2m+2, ..., n。
• 將其兩兩配對：(n-2m+1, n)、(n-2m+2, n-1) ... 每對和為 2n - 2m + 1。
• 每組分配一對，共 m 組，每組和相等。
• 問題規模縮減為 n' = n - 2m，遞歸處理。

此構造保證每次減少 2m，最終將 n 縮減至 [2m, 4m-2] 區間。

小規模 n 的記憶化 DFS 搜索

當 時，n ≤ 4m-2 ≤ 38（因 m ≤ 10），可用狀態壓縮 + DFS 搜索：

• 狀態：board = n（剩餘最大數）、m（剩餘組數）、ave（目標和）、vs[]（數字使用標記）。
• DFS 參數：tot（當前組已選和）、id（當前組索引）、start（下一可選最小數，保證單調避免重複）。
• 剪枝：tot + i > ave 直接返回；dp[board][m] 記憶化結果（0=未訪問，1=可行，-1=不可行）。
• 找到方案後，將 aux 中的分組複製到全局 ans。

關鍵優化點

• 縮減條件 n >= 4*m - 1 而非 n > 4*m - 1，避免多一次遞歸導致 TLE（題目常數較緊）。
• DFS 中 start 參數保證單調選擇，避免排列重複。
• 記憶化數組 dp[50][11]、方案存儲 rec[50][11][11][50] 覆蓋所有小規模狀態。

完整代碼結構

bool dfs(int tot, int id, int start);
bool solve(int top);  // 返回是否可行，並填充 ans/def

int main() {
    int T; read(T);
    while (T--) {
        read(n, m);
        ll sum = 1LL * n * (n + 1) / 2;
        if (sum % m || sum / m < n || !solve(n)) {
            puts("NO");
        } else {
            puts("YES");
            // 輸出 ans + def 合併的分組
        }
    }
}

複雜度分析

• 構造階段：O(n/m) 步驟，每步 O(m)，總 O(n)。
• DFS 階段：狀態數 ≤ 40 * 10 = 400，每狀態搜索分支極少，實際極快。
• 總時間：O(T * n)，滿足 1000 組、n=1e5 限制。

總結

本題結合「大規模構造縮減」與「小規模記憶化搜索」，巧妙利用數學性質將問題規模壓縮到可暴力搜索範圍，是構造類問題中「分治 + 兜底搜索」的經典范式。