題目1——烤雞

題目描述

題解

這是一個簡單的暴搜題目，由于一共由10種配料，每種配料可以放1到3克，因此只需要用dfs對每種配料放入的質量進行暴力搜索即可，如果放入的配料質量之和等于題目給出的美味程度$n$，記錄一下，最終將所有得到的符合題目要求的答案輸出一遍。
代碼：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;int n;
int res[N][10];
int temp[10];
int idx;void dfs(int u, int sum)
{if(u == 10){if(sum == n){for(int i = 0; i < 10; i ++)res[idx][i] = temp[i];idx ++;}return ;}// 枚舉for(int i = 1; i <= 3; i ++){// 選擇itemp[u] = i;dfs(u + 1, sum + i);}
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n;dfs(0, 0);if(idx){cout<<idx<<'\n';for(int i = 0; i < idx; i ++){for(int j = 0; j < 10; j ++)cout<<res[i][j]<<' ';cout<<'\n';}}else{cout<<"0"<<'\n';}return 0;
}

題目2——外星人

題目描述

題解

乍一看題目感覺很復雜，但看了樣例手動模擬了一下之后發現就是簡單的排列組合，即給定一組數（輸入的第三行），從這組數開始，按照從小到大（數字的大小）進行全排列第$M$次后的結果。

題目樣例
1 2 3 4 5 ? —— ? 原始序列
1 2 3 5 4 ? —— ? 第一次排列得到的序列
1 2 4 3 5 ? —— ? 第二次排列得到的序列
1 2 4 5 3 ? —— ? 第三次排列得到的序列（$M=3$）

也就是說，我們以給定的初始序列為起點，使用dfs進行全排列，排列到第$M$次的時候輸出答案，退出即可
代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;int n, m, num;  //num記錄第幾次
int figure[N];
int temp[N];
bitset<N> bt;void dfs(int u)
{// 找到一種排列if(u == n){num ++;if(num == m + 1) // 第一次找到排序是原始序列 因此要找m+1次{for(int i = 0; i < n; i ++)cout<<temp[i]<<' ';exit(0);}return ;}for(int i = 1; i <= n; i ++){if(num == 0) i = figure[u];  // 從指定位置開始搜索if(!bt[i]){bt[i] = true;temp[u] = i;dfs(u + 1);// 恢復現場bt[i] = false;}}
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m;for(int i = 0; i < n; i ++) cin>>figure[i];dfs(0);return 0;
}

題目3——火柴棒等式

題目描述

題解

首先閱讀題目，總的來說就是找到A、B、C三個數字，要求滿足：

• $A+B=C$
• 三個數字使用的火柴棒總數為n - 4（加號和等號一共要消耗4個火柴棒）

對于這種題目，我們可以對每個位置（A、B、C 一種三個位置）上可以選擇的數字進行爆搜，每次搜索完之后檢查找到的三個數字是否滿足以上的兩個條件
由于A、B、C可能會為兩位數或者三位數，因此我們還要開一個數組（dic）來維護每個數字需要多少根火柴棒，這里我使用了記憶搜索的思想，即如果dic[x]（x為數字）在之前使用過，則記錄下來；如果沒使用過，則計算后再保存下來，方便下次調用時使用。具體代碼如下所示：

int dic[1005] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int cal(int x)
{if(dic[x] > 0) return dic[x];int sum = 0, t = x;
//	cout<<t<<'\n';while(x){sum += dic[x % 10];x /= 10;}dic[t] = sum;return sum;
}

整體代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 30;int n;
int dic[1005] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int temp[N];
int res;int cal(int x)
{if(dic[x] > 0) return dic[x];int sum = 0, t = x;
//	cout<<t<<'\n';while(x){sum += dic[x % 10];x /= 10;}dic[t] = sum;return sum;
}
void dfs(int u, int sum)
{if(sum > n) return ;if(u == 3){if((temp[0] + temp[1] == temp[2]) && sum == n)res ++;return ;}for(int i = 0;  i <= 1000; i ++){temp[u] = i;  // 第u個位置選擇idfs(u + 1, sum + cal(i));}
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n; n -= 4;dfs(0, 0);cout<<res;return 0;
}

題目4——PERKET

題目描述

題解

這道題目也比較簡單，是一種指數類問題，即大致思路就是對每一種配料選和不選進行暴力搜索，最后維護一下最小的酸度和苦度的絕對值即可。
注意由于題目所述必須至少添加一種配料，因此每次枚舉完所有的配料選擇方案時，要加一個判斷，把一種配料都不選的方案篩掉。
代碼

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 20;ll n;
ll s[N], b[N];
int bt[N];
ll res = 1e9;void dfs(int u)
{if(u == n){int sum = 0;for(int i = 0; i < n; i ++) sum += bt[i];if(sum == 0) return;  // 一種材料都沒選ll ss = 1, bb = 0;for(int i = 0; i < n; i ++){if(bt[i]) ss *= s[i];bb += bt[i] * b[i];}res = min(res, abs(ss - bb));return ;}// 選擇第u種材料bt[u] = 1;dfs(u + 1);// 不選擇第u種材料bt[u] = 0;  //恢復現場dfs(u + 1);
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n;for(int i = 0; i < n; i ++){cin>>s[i];  cin>>b[i];}dfs(0);cout<<res;return 0;
}

題目5——奇怪的電梯

題目描述

題解

這道題剛上來覺得很復雜，但仔細想了一下之后，就是一個簡單的dfs，從樓層a開始，分別搜索上行和下行兩種方案，最終看能不能到達樓層b，注意不要忘記判斷樓層是否合法
！！！但是這樣會TLE
于是后來我進行了優化（參考洛谷題解里的大佬hhh），即使用一個數組去維護從樓層a開始，到當前樓層的最短距離，根據這個數組進行剪枝。舉個例子：

假如我們第一次到達樓層c，此時按按鈕的次數為3，由于這是第一次到達樓層c，因此我們把這個數字記錄下來；
而當我們再后續搜索時，再次到達了樓層c，按按鈕的次數為9，因為9 > 3，肯定得不到最優解，因此剪枝

代碼

#include<bits/stdc++.h>
using namespace std; 
const int N = 210;int n, a, b;
int k[N], dic[N];
int res = 0x3f3f3f3f;// u代表當前是第幾層 num 是按電梯次數
void dfs(int u, int num)  
{// 越界if(u > n || u <= 0) return ;// 不是最優if(num >= dic[u]) return ;else dic[u] = num;if(num > res) return ;// resif(u == b){res = min(res, dic[u]);}// 向上dfs(u + k[u], num + 1);// 向下dfs(u - k[u], num + 1);return ;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>a>>b;for(int i = 1; i <= n; i ++) cin>>k[i];memset(dic, 0x3f, sizeof(dic));dfs(a, 0);  // 從a樓開始if(res == 0x3f3f3f3f) cout<<"-1"<<'\n';else cout<<res;return 0;
}