提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助檔案

題目鏈接：糖果

一、題目描述

糖果店的老板一共有M 種口味的糖果出售，為了方便描述，我們將M種口味編號1~M，小明希望能品嘗到所有口味的糖果，遺憾的是老板并不單獨出售糖果，而是K顆一包整包出售，幸好糖果包裝上注明了其中K 顆糖果的口味，所以小明可以在買之前就知道每包內的糖果口味，給定N 包糖果，請你計算小明最少買幾包，就可以品嘗到所有口味的糖果，

輸入
第一行包含三個整數N、M 和K，
接下來N 行每行K 這整數T1,T2,…,TK，代表一包糖果的口味，
1<=N<=100，1<=M<=20，1<=K<=20，1<=Ti<=M，

輸出
一個整數表示答案，如果小明無法品嘗所有口味，輸出 ?1，

樣例輸入
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

樣例輸出
2

前言

本題是經典的重復覆寫問題，這類問題是演算法競賽里非常常見的一種題型，一般的重復覆寫問題最優解是為dancing link，不過博主實力不行 ，dancing link 的代碼太難調，所以這里就記錄下暴力做法的優化，

解題思路

相信從題目描述中不難想出暴力做法，直接從每一行中去尋找還缺少哪種糖果，但是直接查找是會查找的話肯定是會超時的，所以我們需要進行優化，但是我們應該怎么優化呢？在重復覆寫問題里，是可以用IDA* 優化的，

演算法介紹

那IDA* 是什么演算法？
其實IDA* 是由兩部分組成，迭代加深＋估價函式，

迭代加深　其實就是在我們深搜的時候，為了防止DFS在一個錯誤的方向上一直延伸向下查找，而設立每一次搜索對搜索層數的限制，如果答案在更深層，則depth＋＋，

int depth = 0;                       
    while(depth <= m && !dfs(depth,0)) depth ++ ; //IDA*迭代加深  搜索一層情況，不夠在慢慢擴散 

估價函式　其實就是我們在深搜時進行的一個可行性剪枝，在這個題目里我們是進行對目標的預估，比如總的層數有５層，如果我們現在搜索到了第三層，現在預估函式給出我們至少還需要３層,則總的層數＜現在所在的層數　＋還剩的層數，則退出，

bool h(int state)                           //可行性剪枝 /估價函式 
{
    int res = 0;
    for(int i = (1 << m) - 1 - state;i;i -= lowbit(i))
    {
        int c = Log2[lowbit(i)];
        res ++ ;
        for(auto row : col[c]){
            i &= ~row;             //因為i是反的，所以得先將row取反 
        }
    }
    return res;
}

介紹完了演算法后，代碼里面還有一些細節操作來說明一下，在一個每一行中，我們可以用０１來表示有沒有糖果，所以我們可以利用二進制來存盤，資料范圍ｍ＜20，所以用int儲存１＜＜ｍ是完全足夠的，同時在搜索的時候，可以用lowbit取得最低位的１來優化，而且搜索程序中，我們可以找每列中最少的那一行，比如在案例中，４只有一行出現過，那么它就是必選的，而１在很多行都出現，所以我們的策略直接從最少的開始查找，進一步優化速度，

代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1 << 20;
vector<int> col[N];
int Log2[M];
int n,m,k;
int lowbit(int x){return x & -x;}       //回傳最低位的1所對應的值
bool h(int state)                           //可行性剪枝 /估價函式 
{
    int res = 0;
    for(int i = (1 << m) - 1 - state;i;i -= lowbit(i))
    {
        int c = Log2[lowbit(i)];
        res ++ ;
        for(auto row : col[c]){
            i &= ~row;                                    //因為i是反的，所以得先將row取反 
        }
    }
    return res;
}
bool dfs(int depth,int state)
{
    if(!depth || h(state) > depth) return state == (1 << m) - 1;         //如果層數搜完了，或者剪枝不夠在繼續 則回傳狀態stare 
    
    // 找到選擇性最少的一列
    int t = -1;
    for(int i = (1 << m) - 1 - state; i;i -= lowbit(i))            //i這里將原本為 表示1作為有糖果，轉化為0有糖果，這樣可以讓lowbit查找優化 
    {
        int c = Log2[lowbit(i)];
        if(t == -1 || col[t].size() > col[c].size() )
        {
            t = c;
        }
    }
    
    for(auto row : col[t])                                 //搜索下一層 
    {
        if(dfs(depth - 1,state | row)){
            return true;
        }
    }
    return false;
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++ ) Log2[1 << i] = i;
    for(int i = 0 ;i < n ;i ++ )
    {
        int state = 0;
        for(int j = 0; j < k ; j ++ )
        {
            int c;
            cin >> c;
            state |= 1 << c - 1;
        }
        for(int j = 0 ;j < m ; j ++ )
            if(state >> j & 1)
            {
                col[j].push_back(state);
            }
                
    }
    int depth = 0;                       
    while(depth <= m && !dfs(depth,0)) depth ++ ; //IDA*迭代加深  搜索一層情況，不夠在慢慢擴散 
    
    if (depth > m) depth = -1;
    cout<<depth<<endl;
    return 0;
}

總結

這篇博客介紹了IDA* 演算法和一些二進制操作的運算，總而言之，本題的資訊量炸裂，在藍橋杯里面這題難度還是很高的，