# MDCPP 模擬賽 題目 / 題解
RANK :
## 1 Increasing Array
### Author : 91XB41
### Time Limit : 1000 ms
### Description
:::spoiler 題敘(左側三角形點開)
---
給你一個陣列 $A$，你需要透過修改使得這個陣列呈非嚴格遞增，也就是後一個數字要大於等於前一個數字。
每次修改你可以任選一個 $i$，讓 $A_i = A_i + 1$ 。
求最少需要修改幾次才能完成。
---
:::
### Input Description
:::spoiler 輸入說明(左側三角形點開)
---
給你一個數字 $N$
代表接下來有長為$N$的陣列
接下來一行有$N$個數字$N_i$
$N \leq 10^6$
$A_i \leq 10^{18}$
---
:::
### Output Description
:::spoiler 輸出說明(左側三角形點開)
---
輸出最少修改次數
---
:::
### Sample
:::spoiler 輸出說明(左側三角形點開)
---
input 1:
```
5
3 2 5 1 7
```
output 1:
```
5
```
---
:::
---
這題既然是第一題解法自然用最基礎的方式去想就好了
不過因為一些技術上的問題，很遺憾的只能讓你們拿到98分
好正式進入題解
這題因為要非嚴格遞增，所以基本上我們只要抓出不符合狀況(後面比前面小的)
然後把他加到跟前面一樣大(非嚴格)，就能在改變最少東西的情況下修正
就能夠得出需要花費的最少費用
如果覺得有點疑惑的話，建議還是多想一下吧
因為這題真的滿簡單的，所以我們還是直接上code吧
範例code
:::spoiler
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main () {
int n , ans = 0;
cin >> n;
int a[n];
for(int i = 0;i < n;i++){
cin >> a[i];
}
for(int i = 1;i < n;i++){
if(a[i] < a[i - 1]){ // 判斷是否有後面比前面小
ans += a[i - 1] - a[i]; // 把他加到跟前面一樣大的花費
a[i] = a[i - 1]; // 讓他跟前面一樣大
}
}
cout << ans;
}
```
:::
## 2 大富翁
### Author : oolala
### Time Limit : 1000 ms
### Description
:::spoiler 題敘(左側三角形點開)
---
有一位小朋友在玩大富翁，一共有 $N$ 個格子，有些格子已經被佔領，若停在該格上，則需要付過路費 $A_i$。
已知這位小朋友從第零格開始，擲了 $M$ 次骰子，每次前進擲中的結果 $B_i$，請問到終點時 (抵達 or 超過第 $N$ 格) 這位小朋友須付出多少錢 ?
---
:::
### Input Description
:::spoiler 輸入說明(左側三角形點開)
---
第一行輸入兩整數 $N, M$
第二行輸入 $N$ 個整數 $A_i$，代表每隔的過路費 ( 0 代表該格尚未被占領 )
第三行輸入 $M$ 個整數 $B_i$，代表每次擲中的結果
$M \leq N \leq 10000$
$A_i \leq 1000$, $1 \leq Bi \leq 6$
---
:::
### Output Description
:::spoiler 輸出說明(左側三角形點開)
---
輸出所需的過路費
---
:::
### Sample
:::spoiler 輸出說明(左側三角形點開)
---
input 1:
```
6 3
3 2 1 3 2 1
3 1 4
```
output 1:
```
4
```
input 2:
```
14 6
0 0 0 359 0 0 0 473 0 867 487 0 0 0
4 1 1 4 3 5
```
output 2:
```
1226
```
---
:::
---
這題要怎麼解決呢 ? 模擬就好啦 ~
我們就設立一個變數 s = 0
每次加上走的步數，就會是目前走到的那個步數
當我們知道目前走到的那個步數，就可以知道當格需要花費多少的費用
只要把每格需要花費的費用加在一起，就可以成功得到最終費用了
順利拿到AC~~
範例code
:::spoiler
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
int arr[10050];
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>arr[i];
int s = 0; // 起始點
int cost = 0; // 總共的花費
int plus; // 增加的步數
for(int i=1;i<=m;i++){
cin>>plus;
s += plus; // 從起始點多走了plus步
cost += arr[s]; // 加上當前那格的花費
}
cout<<cost<<endl; // 輸出總花費
}
```
:::
## 3 TC 與9x9立可帶
### Author : 91XB41
### Time Limit : 1000 ms
### Description
:::spoiler 題敘(左側三角形點開)
---
TC 覺得9x9的39元立可帶實在太便宜、太好用了
因此他決定要把口袋裡所有錢通通拿來買39元立可帶
假設他每隔5分鐘就買一個立可帶
請你記錄他買立可帶的過程
---
:::
### Input Description
:::spoiler 輸入說明(左側三角形點開)
---
輸入為一正整數 $money$ ($39 \leq money \leq 1000$)
代表 TC 有多少錢
---
:::
### Output Description
:::spoiler 輸出說明(左側三角形點開)
---
每買一個立可帶就輸出兩行
格式如下方sample output
第一次買立可帶的時間為0:00
---
:::
### Sample
:::spoiler 輸出說明(左側三角形點開)
---
input 1:
```
200
```
output 1:
```
0:00 TC bought white-out
money : 161
5:00 TC bought white-out
money : 122
10:00 TC bought white-out
money : 83
15:00 TC bought white-out
money : 44
20:00 TC bought white-out
money : 5
```
---
:::
---
其實不難看出本題是此次模擬賽的送分題，這題最主要就是測驗輸出文字的能力
但是在簡單的題目中其實藏有細節，有些人在輸出"money"時並沒有換行，導致WA
所以這題還是在提醒各位要注意輸出範例格式!!!
範例code
:::spoiler
```cpp=
#include<iostream>
using namespace std;
int main()
{
int money;
int minute = 0;
cin >> money;
while( money >=39)
{
money = money-39;
cout << minute << ":00 Eric bought white-out" << endl;
cout << " money : " << money << endl;
minute = minute+5;
}
return 0;
}
```
:::
## 4 TC 的燙手山芋
### Author : reset007
### Time Limit : 1000 ms
### Description
:::spoiler 題敘(左側三角形點開)
---
TC 有 $n-1$ 個好朋友
這天他突然得到一顆不知道哪來的燙手山芋
果不其然
懶惰的 TC 想把他丟給他的朋友們處理
然而他的朋友們也有相同的想法
結果
傳來傳去還是傳回了 TC 手上
假設一開始燙手山芋一定在 TC 手上
每個人都不會傳給自己
傳了 $k$ 次後
燙手山芋仍在 TC 手上的方法數為 $a_k$
請求出 ($n \times a_k$)除以48763的餘數是多少
為了讓 TC 不那麼可憐
保證 TC 一定有朋友
---
:::
### Input Description
:::spoiler 輸入說明(左側三角形點開)
---
輸入為兩整數 $n, k$
$n$ 代表總共有多少人在傳這顆燙手山芋 ( $2 \leq n \leq 1000$ )
$k$ 代表傳了多少次 ( $1 \leq k \leq 1000$ )
20%的測資滿足 $n,k \leq 5$
30%的測資滿足 $n \leq 100, k \leq 5$
49%無其他限制
(SPECIAL)1%( $n \leq 8763, k \leq 10^9$ )
---
:::
### Output Description
:::spoiler 輸出說明(左側三角形點開)
---
輸出為一個介於[0,48762]之間的整數
代表有多少種方法
---
:::
### Sample
:::spoiler 輸出說明(左側三角形點開)
---
input 1:
```
2 3
```
output 1:
```
0
```
input 2:
```
5 4
```
output 2:
```
260
```
input 3:
```
87 87
```
output 3:
```
270
```
---
:::
### 文本內容
:::spoiler 在這
以下為提供語法班看的額外補充資料
可能會對這題有幫助
也可能不會
#### 遞迴與動態規劃(Recursive & DP)
這是一個「大事化小 小事化無」的解法
具體來說
我們會將較難的問題分解成小一點的 比較好理解或解決的問題
舉個栗子
「總共有n層階梯 你目前站在第0階
你每次可以選擇要走1階或是2階的階梯 請問你走到第n階有幾種方法數?」
思考一下就能發現
「走到第n階」只能透過「從第n-1階走一階上來」和「從第n-2階跨兩階上來」這兩個步驟來完成
若我們記F(n)為走到第n階的方法數
則F(n)=F(n-1)+F(n-2)
而且透過簡單計算可以知道F(1)=1, F(2)=2
這麼一來 我們知道它的規律
就能輕鬆求出所有答案了
他甚至只是個費氏數列
對了
階乘(!)也是遞迴喔
小結:
---
然而
遞迴是非常慢的
因為他會不斷的去call那些已經知道的東西
F(5)=F(4)+F(3)=( F(3)+F(2) )+F(3) (F3被叫了兩次)
所以會另外開設一個dp[]陣列
來存放我們已經知道的東西
我們可以寫說
```cpp=
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
```
這樣只要跑n次就能得到答案了
這就是最基本的DP概念
#### 計數原理-乘法原理
例題
從你家出發有8種公車路線可以到台中車站
並且台中車站有8個車次的火車可以到達整修過還是很醜的彰化車站
$\Rightarrow$你有==8 $\times$ 8=64==種方式可以到彰化車站
像這種一次一次慢慢進行的行動
我們把每次小行動的方法數相乘
通常就能得到最終方法數
再來個栗子
今天有一隻青蛙和10片荷葉
青蛙一開始在其中一片荷葉上
他每次會往其他9片荷葉的其中一片跳
我們要求跳2次後回到一開始那片荷葉的跳法數
$\Rightarrow$第一跳有9種方法
但第二跳只能往原本的葉子跳
$\Rightarrow$總共有==9 $\times$ 1=9==個跳法
---
#### 快速冪
今天你想求$3^8$
你會慢慢的算$3\times 3\times 3\times 3\times 3\times 3\times 3\times 3$
還是把$3$平方平方再平方?
這就是快速冪的核心思想
與其一次一次自乘
不如用平方快速解決
那如果今天要求$487^{63}$呢?
我們拆成$487^{32} \times 487^{16} \times 487^8 \times 487^4 \times 487^2 \times 487$
其中較大的數都能透過小數平方得到
總共只要進行10次就能得到$487^{63}$囉(包括平方自乘與計算答案的相乘)
:::
### 題解
本題身為介於語法班和算法班之間的~~魔王~~過渡題
我分配了一些測資
是光靠基礎排列組合就能求出來的數學部分
以下解釋各配分的解法
:::spoiler 滿分解答code
先解釋一下這題的key point
>如果要在第$k$次傳給 TC
>那第$k-1$次就不能給 TC
>方法數 = 隨便亂傳-第$k-1$次在 TC 手上的方法
>而每次傳遞都有$n-1$種方法
>遞迴式$a_k=(n-1)^{(k-1)}-a_{k-1}$
>而且$a_1=0$(第1次不可能在TC手上)
到這裡你可以選擇開始解DP
但拿不到滿分
所以重點就是把這個遞迴式解成通式啦!
code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int mod = 48763;
long long int fpow(int a, int b){
long long int base = a, power = 1;
while(b){
if(b&1)power = (power*base)%mod;
base = (base*base)%mod;
b/=2;
}
return power%mod;
}
int solve(int n,int k){
long long int answer;
answer = fpow(n-1, k-1);
if(k&1)answer--;
else answer++;
answer *= (n-1);
return answer % 48763;
}
int main(){
int n,k;
cin>>n>>k;
cout<<solve(n,k);
return 0;
}
```
:::
:::spoiler 0~50分解
事實上小題1和2是幾乎一樣的
只是2的底數稍大
如果窮舉$n \leq 5, k \leq 5$的所有答案就能拿20分
如果能稍微把公式推廣到多一點人數的情形
就能再拿30
:::
:::spoiler 99分解
等到$k$變大後
單純套公式做遞迴鐵定會爆炸
所以就是我們dp的使用時機啦
dp陣列開到[1000][1000]是沒問題的喔
:::
## 5 地鐵
### Author : explosionnn
### Time Limit : 2000 ms
### Description
:::spoiler 提敘(右側三角形點開)
---
explosionnn喜歡在別人的minecraft伺服器蓋地鐵，而所有的地鐵路線呈網狀，代表某站與東西南北四站接連通。如今explosionnn從左上角的站點$(1, 1)$出發，欲前往右下角的站點$(n, m)$，一路上只往右或是下走。此外他有一顆終界珍珠，使用它能夠瞬間移動至下一站，而不花費任何時間，但是使用完珍珠即消滅。
現在給你移動到各站的時間，請求出從左上角移動到右下角最少需花費多少時間
---
:::
### Input Description
:::spoiler 輸入說明(右側三角形點開)
---
第一行有兩個整數 $N$ 和 $M$，代表這是此路網大小為$N*M$
接下來有$N$列，每一列有$M$個整數，第$i$列$j$行的整數$A_{i,j}$代表從左方或是上方的站點到達此站點須花費$A_{i,j}$的時間
---
:::
### Output Description
:::spoiler 輸出說明(右側三角形點開)
---
輸出從左上角移動到右下角最少需花費多少時間
---
:::
### Sample
:::spoiler 輸出說明(右側三角形點開)
---
input 1:
```
3 3
1 7 3
50 8 8
1 8 8
```
output 1:
```
18
```
input 2:
```
3 4
2 6 5 4
7 6 8 7
4 3 9 8
```
output 2:
```
24
```
---
:::
### 題解
想必大家剛接觸dp有寫過這種二維dp的經典題吧：
給定一個二維陣列，從左上走到右下，只能往右或是下走，問你怎麼走路上經過的點的和會最大或是最小？
而這題是加強版，多了一個終界珍珠，讓你可以忽視其中一點的值，那麼要怎麼做呢？
dp的陣列我們可以再開一個維度，最後一個維度的大小只有二，紀錄走到$A_{i, j}$的時候是不是已經用終界珍珠了，所以轉移式如下：
```cpp=
dp[i][j][0] = min(dp[i-1][j][0], dp[i][j-1][0]) + station[i][j];
dp[i][j][1] = min(min(dp[i-1][j][1], dp[i][j-1][1]) + station[i][j], min(dp[i-1][j][0], dp[i][j-1][0]));
```
$dp[i][j][0]$代表走到$A_{i, j}$的時候還沒使用過終界珍珠，這也代表走過來的路上也都沒有使用過。因此只能從$dp[i-1][j][0], dp[i][j-1][0]$這兩個第三維度同為$0$的值轉移過來，並且加上到達$A_{i, j}$的時間$station[i][j]$
$dp[i][j][1]$則代表走到$A_{i, j}$的時候已經使用過終界珍珠，可以分為兩個情況：
第一種情況為早就使用過了，所以從$dp[i-1][j][1]$或是$dp[i][j-1][1]$走到$A_{i, j}$的時候沒有珍珠可以用了，只能用走的。因此要從$dp[i-1][j][1], dp[i][j-1][1]$這兩個第三維度同為$1$的值轉移過來，並且加上到達$A_{i, j}$的時間$station[i][j]$
第二種情況為走到$A_{i, j}$的時候才用終界珍珠，因此在那之前是沒使用過的，轉移式為$min(dp[i-1][j][0], dp[i][j-1][0])$，最後不需要加上$station[i][j]$，因為是使用珍珠到達$station[i][j]$的
AC code
:::spoiler code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int MAXN = 2e3+5;
int INF = 1e18;
int station[MAXN][MAXN], dp[MAXN][MAXN][2];
int n, m;
signed main(){
cin >> n >> m;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
dp[i][j][0] = dp[i][j][1] = INF;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> station[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i == 1 && j == 1){
dp[1][1][0] = dp[1][1][1] = station[i][j];
continue;
}
dp[i][j][0] = min(dp[i-1][j][0], dp[i][j-1][0]) + station[i][j];
dp[i][j][1] = min(min(dp[i-1][j][1], dp[i][j-1][1]) + station[i][j], min(dp[i-1][j][0], dp[i][j-1][0]));
}
}
cout << dp[n][m][1] << "\n";
}
```
:::
## 6. TC 出遊去
### Author : 極速車神大佬
### Time Limit : 4000 ms
### Description
暑假了 ! 最近風和日麗，而 TC 打算帶他的眾多ㄌㄌ出去玩。
這個國家有 $N$ 個村莊，而由 $M$ 個道路連接村莊 $u$ 和 村莊 $v$，每個道路有一個長度 $W_i$。
他們打算每個村莊都要前往，但是 TC 為了照顧他的ㄌㄌ，所以他要盡量讓每次ㄌㄌ走的路不要太長。換句話說，他要選擇幾條道路，讓選擇的道路的最大值最小，並且能夠走完各個村莊。
註：TC 可以從任意一點開始，且道路是雙向的。
### Input Description
輸入有多筆測資。
第一行有個整數 $T$，代表測資個數
接下來一行有兩個整數 $N$ 和 $M$，代表有幾個村莊及道路。
接下來有 $M$ 行，每行有三個數字，
分別是 $u_i$、$v_i$、$w_i$，代表連接 $u_i$ 到 $v_i$ 的道路長度是 $w_i$
$1 \leq T \leq 100$
$2 \leq N \leq 10^5$
$1 \leq M \leq 10^6$
$1 \leq u_i, w_i \leq N$
$1 \leq w_i \leq 10^5$
$\ \sum_{i=1}^{T} N_T \leq 10^5$
部份給分 :
30 % 給的圖是由 $N$ 個村莊，$N-1$ 個邊連接，並且保證能夠互相到達
30 % $w_i \leq 10$
40 % 無其他限制
### Output Description
請輸出道路最大值最小，若無論如何都無法到達，請輸出 impossible
### Sample
```
// Sample input 1
1
4 4
1 2 1
2 3 2
1 3 1
1 4 1
// Sample output 1
1
// Sample input 2
2
4 5
1 2 1
2 3 3
1 3 2
2 4 4
3 4 3
6 5
1 2 2
2 3 5
4 6 2
5 6 3
1 3 4
// Sample output 2
3
impossible
// Sample input 3
1
2 1
1 2 10
// Sample output 3
10
```
這題究竟要怎麼完成呢 ?
對於 第一個 subtask:
我們可以發現為了要走到全部的點，每條邊一定要走到，所以將全部路徑長取 $max$ 即可
對於 第二個 subtask:
我們可以枚舉上限，從 1 ~ 10，依據上限來判斷可不可以走。
對於全部:
透過題目敘述可以發現，題目要你求道路長度的上限最小值。
而這又是一個外掛二分搜的模型：最大值最小。
我們知道如果上限越大的話，就越容易到達，這就構成了二分搜單調性
那要怎麼完成確認函數呢 ? 很簡單，我們就 DFS / BFS 一次就好，
而如果超過上限的邊就不去走他。
複雜度：$O((N+M)*logC)$
$O(N+M)$ 來自 DFS / BFS
$O(logC)$ 來自外掛二分搜
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = 1e5 + 5 ;
vector<pii>g[maxn];
int vis[maxn],cnt,n,m;
void dfs(int x,int p,int c) {
if(vis[x]++) return ;
cnt++;
for(auto [v,e]:g[x]) {
if(v==p or e>c) continue;
dfs(v,x,c);
}
}
bool check(int c) {
cnt=0;
mset(vis,0);
dfs(1,-1,c);
if(cnt==n) return true;
else return false;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--) {
cin>>n>>m;
for(int i=1;i<=n;i++) g[i].clear();
while(m--) {
int u,v,w;
cin>>u>>v>>w;
g[u].pb({v,w});
g[v].pb({u,w});
}
int l=1,r=1e4,best=-1;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) best=mid,r=mid-1;
else l=mid+1;
}
if(~best) cout<<best<<endl;
else cout<<"impossible\n";
}
}
```
而其實這題有另一個更好的方法，就是利用最小生成樹 (MST) !
這個算是比較進階的內容，有興趣的同學可以看[這裡](https://oi-wiki.org/graph/mst/#kruskal)
複雜度：$O(M*logM)$
這裡附上程式碼：
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define tup tuple<int,int,int>
using namespace std;
const int maxn = 1e5 + 5 ;
int pa[maxn],mx,cnt;
int findset(int x) {
return x==pa[x]?x:pa[x]=findset(pa[x]);
}
vector<tup>edge;
void uni(int u,int v,int w) {
u=findset(u),v=findset(v);
if(u==v) return ;
pa[u]=v;
mx=w;
cnt++;
}
bool cmp(tup t1,tup t2) {
return get<2>(t1)<get<2>(t2); // tuple 用法
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t,n,m;
cin>>t;
while(t--) {
cin>>n>>m;
for(int i=1;i<=n;i++) pa[i]=i;
edge.clear();
while(m--) {
int u,v,w;
cin>>u>>v>>w;
edge.pb({u,v,w});
}
sort(edge.begin(),edge.end(),cmp);
for(auto [u,v,w]:edge) {
uni(u,v,w);
}
if(cnt!=n-1) cout<<"impossible\n";
else cout<<mx<<endl;
}
}
```
## 7 Tim Chen與黑市的白毛ㄌㄌ交易
### Author : YouZhe
### Time Limit : 600 ms
### Description
:::spoiler 提敘(右側三角形點開)
---
眾所皆知Tim Chen是個狂熱的ㄌㄌ愛好者，最近他從黑市中找到了一個攤販，願意以吸引人的價格賣給他最上等的白毛ㄌㄌ
這個攤販花了不少心血才弄到一隻難能一見的白毛ㄌㄌ，因此他對於他的訂價絲毫不肯退讓
並且為了讓他在黑市的生意不要曝光，攤販不願意找任何錢，畢竟錢上是有編號的，找錢相當於讓自己的資訊流出
正好Tim Chen又是一個寧願不吃午餐來省錢的台南血脈客家人(或者他只是想要存錢去吃女僕咖啡廳)。因此他不可能做出給更多錢的舉動
也就是說他們之間的交易**只可能在剛好等於定價時發生，且只能付剛好的錢(不找錢)**
今天正是Tim Chen要買下白毛ㄌㄌ的日子，但黑市攤販跟他說當他來到黑市後才願意釋出價格$C$
因此他無法準備確切數目的紙鈔，最後他在錢包裡**準備了$N$種面額的紙鈔各一張**
但是在路上時，或許是因為滿腦都是白毛ㄌㄌ，所以**有$M$張鈔票從他的錢包掉了出去**
現在**給出$Q$次詢問，每次詢問給出$M$個數字**
代表Tim Chen**丟掉的鈔票面額**。
試問每次詢問中，Tim Chen有**幾種方法**可以湊到購買白毛ㄌㄌ的價格
若沒有任何湊到白毛ㄌㄌ價格的方法，請用力嘲笑他:"Ha! What a poor guy!"
(答案請對10^9+7取模)
---
:::
### Input Description
:::spoiler 輸入說明(右側三角形點開)
---
第一行有兩個整數$N$、$C$，代表攜帶的紙鈔數量、要賣出的價格
第二行，有$N$個數字$a_i$代表紙鈔的面額。
接下來有一個整數$Q$詢問的次數
接下來有$Q$組數字:
第一行有一個整數$M$代表遺失的紙鈔數量
第二行，有$M$個數字$b_i$代表遺失紙鈔的面額。
$1 \leq N \leq 2000$
$1 \leq C \leq 2000$
$1 \leq Q \leq 2000$
$1 \leq M \leq 10$
$1 \leq a_i, b_i \leq 2000$
b集合在a集合之中
部份給分
50%$1 \leq N, C, Q, a_i ,b_i \leq 100$
50% 原測資
---
:::
### Output Description
:::spoiler 輸出說明(右側三角形點開)
---
請輸出湊到白毛ㄌㄌ價格的方法數，若為0，請輸出Ha! What a poor guy!
---
:::
### Sample
:::spoiler 輸出說明(右側三角形點開)
---
input 1:
```
5 8
1 4 3 6 8
2
1
6
3
6 8 1
```
output 1:
```
2
Ha! What a poor guy!
```
---
:::
### 題解
這題呢我預估解出來的人也是在3個以內，不過因為其他題目太邪惡了，所以她就被排到了第6題
至於要怎麼解這題呢?
如果還記得背包DP的最後一堂課，那就會發現這題長的就一臉找錢問題對吧。
只不過要把它從無限背包的架構，改成01背包的架構
的確，這題就是那題找錢問題的延伸。不過我猜大多數人根本沒聽懂就是了。
首先這一看，先套進找錢問題的模板就是我們的第一步了
接下來，因為我們可以知道的是，它會有Q次查詢改變原本的物品
所以這裡可以直接看出第一種作法
O(QNC)的做法，我們只要改變Q次物品，並且每次都對它做一次背包DP
每次背包DP的複雜度是O(NC)，乘在一起就變成O(QNC)了，這也是前50%的拿法
阿因為不是AC code，所以我就不放範例code了
現在知道了O(QNC)，很顯然這在完全測資裡是會爆掉的
所以我們希望能在每次修改之後，不需要都多做一次背包DP
那麼就先觀察掉一種面額的鈔票會導致甚麼結果
很顯然，在背包DP裡，就是透過這種面額加到的方法數會失效嘛
```cpp=
for(int i=1;i<=n;i++)
for(int j = c;j>=w[i];j--){
dp[j] = dp[j]+dp[j-w[i]];
}
```
那麼我們就反過來做，把他所得到的結果反過來扣掉
```cpp=
for(int j=lost;j<=c;j++) //lost代表掉的錢面額
ndp[j] = ndp[j]-ndp[j-lost];
}
```
至於為甚麼要從小到大順推過去，而不是按照01背包那樣，由大到小逆堆呢
因為我們如果不先把小容量的背包扣掉的話，大容量的背包就會扣掉使用lost這個面額達成的方法數，變成扣了兩次
舉個例
有 1 2 3 4 面額 要湊到價格6
-|1|2|3|4|5|6
-|-|-|-|-|-|-
for i=1|1|0|0|0|0|0
for i=2|1|1|1|0|0|0
for i=3|1|1|2|1|1|1
for i=4|1|1|2|2|2|2
現在扣掉3這個面額
如果逆著做
-|1|2|3|4|5|6
-|-|-|-|-|-|-
原本|1|1|2|2|2|2
後來|1|1|1|1|1|0
因為6先扣掉了3的2種方法，所以掛了，本來還有2+4這種，算出來卻變0種
3的兩種方法包刮[1+2],[3]，如果6先扣它，就相當於扣了一個0+3+3的情況
但這顯然是不成立的，所以我們要正著做它
變成這樣
-|1|2|3|4|5|6
-|-|-|-|-|-|-
原本|1|1|2|2|2|2
後來|1|1|1|1|1|1
答案就會正確是1
以下附上範例code
:::spoiler code
```cpp=
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int MAXN = 3000+50;
int dp[MAXN];
int w[MAXN];
signed main(){
int n,c;
cin>>n>>c;
for(int i=1;i<=n;i++){
cin>>w[i];
}
dp[0] = 1;
for(int i=1;i<=n;i++)
for(int j = c;j>=w[i];j--){
dp[j] = (dp[j]+dp[j-w[i]])%mod;
}
// 01背包架構的找錢
// O(NC)
int q;
cin>>q;
while(q--){
int ndp[MAXN]; //new dp
memcpy(ndp,dp,sizeof(dp));//O(NQ)
//這個memcpy()代表把dp陣列複製給ndp陣列
//你們也可以用for迴圈來做
int m;
cin>>m;
int lost;
for(int i=1;i<=m;i++){
cin>>lost;
for(int j=lost;j<=c;j++) // 順推 這樣才不會扣到已經用了lost來湊出的方法數，變成扣了兩次
ndp[j] = (ndp[j]-ndp[j-lost]+mod)%mod; //前面即取過模，只取一次
} //O(QMC)
if(ndp[c]==0)
cout<<"Ha! What a poor guy!"<<endl;
else
cout<<ndp[c]<<endl;
}
}
```
:::
Sign in with Wallet
Connect another wallet