# 簡介
# APCS
# AP325
## AP325各項連結
### https://jmj.cmgsh.tp.edu.tw/files/AP325_v1.3.pdf 講義連結
### https://hackmd.io/@cube/H1Q4zMJmt#AP325-%E7%B7%B4%E7%BF%92%E9%A1%8C%E5%96%AE 題目連結
### https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m 測資連結(題目的測資)
## 遞迴
### 合成函式(1)(d001
###### `遞迴` `recursion`
令 f(x)=2x−1, g(x,y)=x+2y−3。本題要計算一個合成函數的值
輸入 : 輸入一行，長度不超過 1000，它是一個 f 與 g 的合成函數，但所有的括弧與逗號都換成空白。輸入的整數絕對值皆不超過 1000。
輸出 : 輸出函數值。最後答案與運算過程不會超過正負 10 億的區間。
範例: 輸入 f g f 1 3/輸出 7 (f(g(f(1),3))=f(g(1,3))=f(4)=7 )
```c++=
#include<bits/stdc++.h>
using namespace std;
int eval(){//合成函式
int x,y;
char c[7];
scanf("%s",&c);
if (c[0] == 'f'){
x = eval();
return 2*x-1;
}
else if (c[0] == 'g'){
x = eval();
y = eval();
return x+2*y-3;
}
else return atoi(c);//atoi是將字串轉為數字的函式
}
int main()
{
printf("%d",eval());
}
```
### 合成函式(2)(d002
###### `遞迴` `recursion`
令 f(x)=2x–3;g(x,y)=2x+y–7;h(x,y,z)=3x–2y+z。本題要計算一個合成函數的值
輸入 : 輸入一行，長度不超過 1000，它是一個 f, g 與 h 的合成函數，但所有的括弧與逗號都換成空白。輸入的整數絕對值皆不超過 1000。
輸出 : 輸出函數值。最後答案與運算過程不會超過正負 10 億的區間。
範例: 輸入 h f 5 g 3 4 3/輸出 18 (h(f(5),g(3,4),3)=h(7,3,3)=18 )
```c++=
#include<bits/stdc++.h>
using namespace std;
int eval(){//合成函式
int x,y,z;
char c[7];
scanf("%s",&c);
if (c[0] == 'f'){
x = eval();
return 2*x-3;
}
else if (c[0] == 'g'){
x = eval();
y = eval();
return 2*x+y-7;
}
else if (c[0] == 'h'){
x = eval();
y = eval();
z = eval();
return 3*x-2*y+z;
}
else return atoi(c);//atoi是將字串轉為數字的函式
}
int main()
{
printf("%d",eval());
}
```
### 棍子中點切割(d003
###### `遞迴` `recursion` `二分搜` `binary search` `lower_bound`
有一台切割棍子的機器，每次將一段棍子會送入此台機器時，機器會偵測棍子上標示 的可切割點，然後計算出最接近中點的切割點，並於此切割點將棍子切割成兩段，切割後的每一段棍子都會被繼續送入機器進行切割，直到每一段棍子都沒有切割點為止。請注意，如果最接近中點的切割點有二，則會選擇座標較小的切割點。每一段棍子的切割成本是該段棍子的長度
輸入 : 第一行有兩個正整數 N 與 L。第二行有 N 個正整數，依序代表由小到大的切割點座標 p[1]~p[N]，數字間以空白隔開，座標的標示的方式是以棍子左端為 0， 而右端為L。N≤5∗104，L<109。
輸出 : 切割總成本點
範例 :
輸入
4 10
1 2 4 6
輸出
22
:::success
基本寫法
:::
```c++=
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;//定義LL為long long
LL p[50010];
LL cut(int left,int right){//分割從left到right最小成本
if (right - left <= 1) return 0;//如果中間無切割點就回傳0
int k = (p[right] + p[left]) / 2;//找中點
int m = left;
while(p[m] < k) m++;//找最接近中點的切割點
if (p[right]-p[m] <= p[m-1]-p[left]) m--;//確認m-1是否更接近
return (p[right] - p[left]) + cut (left,m) + cut(m,right);
}
int main()
{
int n,l;
scanf("%d%d",&n,&l);
p[0] = 0, p[n+1] = l;//設最左為0，最右為總長
for (int i = 1; i <= n; i++)scanf("%d",&p[i]);
printf("%lld\n",cut(0,n+1));
}
```
:::success
二分搜版本
:::
```c++=11
for (int i = (right + left)/2; i > 0; i /= 2){//二分搜找最接近中點的切割點
while (m + i < right && p[m+i] < k){
m += i;
}
}
if (p[m] - p[left] < p[right] - p[m+1])m ++;//m+1是否更接近中點
```
:::success
lower_bound版本
:::
```c++=11
int m = lower_bound(p+left,p+right,k)-p;//lower_bound找最接近中點的切割點
if (p[m-1] - p[left] >= p[right] - p[m])m --;//m-1是否更接近中點
```
### 支點切割(d004
###### `AP325` `前綴和` `prefix` `遞迴` `recursion`
輸入一個大小為 N 的一維整數陣列 p[]，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個:子陣列範圍小於 3 或切到給定的層級 K 就不再切割。
而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，也就是說，若區段的範圍是[s,t]，則要找出切點 m∈[s+1,t−1]，使得 |∑ti=sp[i]×(i−m)| 越小越好，如果有兩個最佳切點，則選擇編號較小的。
輸入 : 第一行有兩個正整數 N 與 K。
第二行有 N 個正整數，代表陣列內容 p[1] ~ p[N]，
數字間以空白隔開，總和不超過109,N≤50000，切割層級限制 K<30。
輸出 : 所有切點的 p[]值總和。
:::info
這題可以用力矩的想法，最佳支點就是左右兩邊力矩和最相近的時候
找支點時要用到前綴和，當支點往右移時左邊力矩要先加上支點以前的前綴和，右邊則要減掉支點以後的前綴和
:::
```c++=
#include <bits/stdc++.h>
using namespace std;
#define N 50010
typedef long long LL;//定義LL為long long
LL p[N];
LL cut(int left,int right,int deg){//分割從left到right最小成本
if (right - left < 3 || deg <= 0) return 0;//如果中間無切割點就回傳0
int m = left+1;//暫時支點
LL Lsum = p[left],Rsum = 0;//左右力矩
for (int i = left+2; i < right; i++) Rsum+=p[i]*(i-m);//當支點為m+1時的右邊力矩和
LL prefix = p[left],suffix = 0;//前綴和
for (int i = left+2; i < right; i++) suffix += p[i];
LL flag = abs(Rsum - Lsum),tem;//左右力矩差
while(m < right-1){
//找出最佳支點也就是左右力矩最相近的(左右力矩差開始變小時
prefix += p[m];//更新支點前的前綴和
Lsum += prefix;//更新左力矩
m++;//支點右移
Rsum -= suffix;//更新右力矩
suffix -= p[m];//更新支點後的前綴和
tem = abs(Rsum-Lsum);
if (tem >= flag) break;//力矩差變小時代表找到支點
flag = tem;
}
m--;
return p[m]+ cut(left,m,deg-1) + cut(m+1,right,deg-1);
}
int main()
{
int n,d;
scanf("%d%d",&n,&d);
for (int i = 0; i < n; i++)scanf("%d",&p[i]);
printf("%lld\n",cut(0,n,d));
}
```
### 二維黑白影像編碼(d005
###### `AP325` `遞迴` `recursion`
假設 n 是 2 的冪次，也就是存在某個非負整數 k 使得 n=2k。將一個 n∗n 的黑白影像以下列遞迴方式編碼：
如果每一格像素都是白色，我們用 0 來表示；
如果每一格像素都是黑色，我們用 1 來表示；
否則，並非每一格像素都同色，先將影像均等劃分為四個邊長為 n2 的小正方形後，然後表示如下：先寫下 2，之後依續接上左上、右上、左下、右下四塊的編碼。
輸入 : 第一行是影像的編碼 S，字串長度小於 106。
第二行為正整數 n， 1≤n≤1024，其中 n 必為2的冪次。
輸出 : 輸出有多少個像素是 1。
:::success
範例 :
輸入
2020020100010
8
輸出
17
示意圖:
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int idx = -1,n;
char s[1000010];
int rec(int d){
idx++;
if (s[idx] == '1') return d*d;//黑色 回傳此塊大小
else if (s[idx] == '0') return 0;//白色 回傳0
else{
int total = 0;
for (int i = 0; i < 4; i++){//分割四塊 分別遞迴並加總回傳
total += rec(d/2);
}
return total;
}
}
int main()
{
scanf("%s%d",&s,&n);
printf("%d",rec(n));
}
```
## 遞迴窮舉
### 子集合乘積(d006
###### `遞迴` `recursion` `窮舉`
輸入 n 個正整數，請計算其中有多少組合的相乘積除以 P 的餘數為 1，每個數字可以選取或不選取但不可重複選，輸入的數字可能重複。
P=10009
輸入 : 第一行是 n，0<n<26
第二行是 n 個以空白間隔的正整數 ai，ai≤104
輸出 : 有多少種組合。
若輸入為1,1,2，則有三種組合，選第一個 1，選第二個 1，以及選兩個 1。
```c++=
#include<bits/stdc++.h>
using namespace std;
int n,ans = 0;
long long p = 10009,a[26];
void func(int i , int res){
if (i >= n){
if (res == 1)ans++;//餘1時總數加一
return;
}
func(i+1,(res * a[i])%p);//選i
func(i+1,res);//不選i
return;
}
int main()
{
scanf("%d",&n);
for (int i = 0; i < n ; i++) scanf("%d",&a[i]);
func(0,1);
printf("%d",ans-1);
}
```
### 子集合的和(d007
###### `遞迴` `recursion` `窮舉`
輸入 n 個正整數，請計算各種組合中，其和最接近 P 但不超過 P 的和是多少。
每個元素可以選取或不選取但不可重複選，輸入的數字可能重複。
P≤1000000009，0<n<26。
輸入 : 第一行是 n 與 P，
第二行 n 個整數是 A[i]，
同行數字以空白間隔。
輸出 : 最接近 P 但不超過 P 的和。
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[30],ans = 0,n,p;
void func(int idx,int total){
if (idx >= n){
if (total <= p) ans = max(ans,total);
return;
}
func(idx+1,total+a[idx]);//選idx
func(idx+1,total);//不選idx
return;
}
int main()
{
scanf("%d%d",&n,&p);
for (int i = 0; i < n; i++) scanf("%d",&a[i]);
func(0,0);
printf("%d",ans);
}
```
### 最多得分的皇后(d008
###### `遞迴` `recursion` `皇后問題` `窮舉`
在一個 n∗n 的方格棋盤上每一個格子都有一個整數的得分，如果將一個皇后放在某格子上就可以得到該格子的分數，請問在放置的皇后不可以互相攻擊的條件下，最多可以得到幾分，皇后的個數不限制。0<n<14。每格 |分數| 不超過 100。
輸入 : 第一行是 n，接下來 n 行是格子分數，由上而下，由左而右，同行數字以空白間隔。
輸出 : 輸出最大得分
```c++=
#include<bits/stdc++.h>
using namespace std;
int n,board[15][15],ans = 0;
void func(int row,int pre[],int total){//行,列,之前放置的皇后在的行數
bool vis[15] = {false};//紀錄是否走訪過
ans = max(ans,total);
if (row >= n) return;
for (int i = 0; i < row; i++){
if (pre[i] == -1) continue;//未放皇后
vis[pre[i]] = true;//已放皇后
int j = row-i+pre[i];//此皇后的右邊斜線的格子(不能放再放
if (j<n) vis[j] = true;
j = pre[i]-(row-i);//此皇后的左邊斜線的格子(不能放再放
if (j >= 0) vis[j] = true;
}
pre[row] = -1;
func(row+1,pre,total);//此列不放皇后的狀況
for (int i = 0; i < n; i++){//此列放皇后的全部狀況
if (!vis[i]){
pre[row] = i;
func(row+1,pre,total+board[row][i]);
}
}
return;
}
int main()
{
scanf("%d",&n);
int pre[15] = {0};
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
scanf("%d",&board[i][j]);
}
}
func(0,pre,0);
printf("%d",ans);
}
```
## 排序
### 不同的數—排序(d010
假設有 N 個整數要被讀到一個陣列中，我們想要將這些數字排序並去除重複的數字，例如輸入的整數序列是 (5,3,9,3,15,9,8,9)，這些數如從小到大排是 (3,3,5,8,9,9,9,15)，去除重複者後為(3,5,8,9,15)。寫一個函數，傳回有多少不同的數字並且將結果放在陣列中回傳。
輸入 : 輸入兩行，第一行是正整數 N 不超過 10 萬，第二行是 N 個整數，大小不超過 109，以空白間隔。
輸出 : 第一行輸出有多少相異整數，第二行輸出這些相異整數，相鄰數字之間以一個空白間隔。
:::info
這題可以用sort來寫 但我是用set寫 set的特性會將數字由大排到小並且直接刪除重複的元素
一開始將所有數字insert到set裡 然後直接列印set的大小(及相異整數數量)並透過迴圈列印set內的數字(由小到大的數字排序)
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,tem;
set<int> s;
scanf("%d",&n);
for (int i = 0; i < n; i++) {
scanf("%d",&tem);
s.insert(tem);
}
printf("%d\n",s.size());//s裡有幾個元素
for (auto num:s) printf("%d ",num);//列印s裡的所有數值
}
```
### 離散化 – sort(d011
###### `lower_bound` `sort` `二分搜` `排序`
假設有 N 個整數要被讀到一個陣列中，我們想要將這些整數置換成從 0 開始依序排列的整數並且維持它們原來的大小關係，例如輸入的整數序列是 (5,3,9,3,15,9,8,9)，這些數如從小到大排是 (3,3,5,8,9,9,9,15)，去 除重複者後為 (3,5,8,9,15)，所以我們要替換的是:
3 ==> 0
5 ==> 1
8 ==> 2
9 ==> 3
15 => 4
所以原先的序列就會變成 (1,0,3,0,4,3,2,3)。
輸入 : 輸入兩行，第一行是正整數 N 不超過 10 萬，
第二行是 N 個整數，大小不超過 109，以空白間隔。
輸出 : 輸出置換後的序列，兩數之間以一個空白間隔。
```c++=
#include<bits/stdc++.h>
using namespace std;
int from[100010],to[100010];
int func(int n){
if (n < 1) return 0;
vector<int> v (from,from+n);//將原數據複製到新的陣列
sort(v.begin(),v.end());//排序新陣列
to[0] = v[0];
int num = 1;
for (int i = 1; i < n; i++){
if (v[i] != v[i-1]){//已經小到大排序 將相異數分別放入to陣列
to[num++] = v[i];
}
}
return num;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++) scanf("%d",&from[i]);
int idx = func(n);
for (int i = 0; i < n; i++){
printf("%d ",lower_bound(to,to+idx,from[i])- to);//找出對應的序列
}
}
```
## 快速冪
### 快速冪(d012
###### `快速冪` `二分搜` `模逆元` `模運算`
輸入正整數 x, y 與 p，計算 x^y mod(取餘數) p。x, y, p 皆不超過 109+9。例如 x=2,y=5,p=11，則答案是10。
輸入 : 輸入 x, y 與 p 在同一行，以空白間隔，行尾可能有空格。
輸出 : 輸出計算結果。
:::info
這題會使用模逆元的概念 這是一個數學的運算方式 有興趣的人可以去查
這題會使用到的技巧是 (n*m) % x = n * (m%x) = (n%x) * m
運用這個性質就可以在每次先mod來避免數字過大無法運算
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL func(LL x, LL y,LL p){
if (y == 0) return 1;
if (y % 2) return (func(x,y-1,p)*x)%p;//y為奇數
LL tem = func(x,y/2,p);//y為偶數
return (tem*tem) %p;
}
int main()
{
int x,y,p;
scanf("%d%d%d",&x,&y,&p);
printf("%d",func(x,y,p));
}
```
以下為類似習題 只是數字需要用字串做處理
### 快速冪--200 位整數(d013
輸入正整數 x, y 與 p，計算 xymodp
y, p 皆不超過 109+9，但 x 的範圍是不超過 200 位的正整數
```c++=
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL func(LL x,LL y,LL p){
if (y == 0) return 1;
if (y & 1) return (func(x,y-1,p)*x) %p;
LL tem = func(x,y/2,p);
return (tem*tem) % p;
}
int main()
{
string x;
LL y,p;
while(cin >> x >> y >> p){
LL ans = 0;
for (int i = 0; i < x.size(); i++){
if (i < x.size()-1)ans = (ans+x[i]-'0')% p * 10;
else ans = (ans+x[i]-'0') % p;
}
cout << func(ans,y,p) << "\n";
}
}
```
## Greedy
### 少林寺的代幣(d042
###### `greedy` `貪心法`
令狐沖去少林寺觀光，少林寺有四種代幣，面額分別是[1, 5, 10, 50]，令狐沖拿了 n 元去換代幣，
請問以這四種代幣湊成 n 元，最少要多少枚代幣？
輸入 : 第一行是一個正整數 m，代表有幾筆測資，
以下有 m 行，每行是一筆測資， 每筆測資是一個正整數 n，n<1000。
輸出 : 依序每一行輸出每一筆測資的最少的代幣數量。
:::info
這題的貪心法就是由面額最大的硬幣開始換就可以使用最少代幣 (在其他題目不一定適用 面額必須都是倍數才行
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int coin[] = {1,5,10,50};
int n,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int num = 0;
for (int i = 3;i >= 0 && n > 0; i--){//由最大面額開始找
* num += n/coin[i];//看最多可以換幾個
n %= coin[i];
}
printf("%d\n",num);
}
}
```
### 笑傲江湖之三戰(d043
###### `greedy` `貪心法` `priority_queue`
少林寺與五嶽劍派等正教派出 n 位高手，而你方也有 n 位高手，每個人都有一個戰力值。雙方要進行一對一的對戰，每個人不管輸或贏都只能比一場，假設兩人對戰時，戰力值高的獲勝。對於對方的每一位高手，你可以指定派哪一位與其對戰，你希望贏越多場越好， 平手則沒有幫助。
請計算出最多能贏多少場。
輸入 :
第一行是一個正整數 n ，
第二行有 n 個非負整數是對方的戰力，
第三行有 n 個非負整數是我方的戰力，
同行數字間以空白間格。 n 與戰力值不超過 1e5 。
輸出 : 輸出最多可能的勝場數。
:::info
證明:
(a為我方最小戰力,b為敵方最小戰力)
當a<=b時，a對誰都沒用
當a>b，且另y>=a時
可以由上圖發現
a對b，x對y會有最佳的結果
結論:將雙方戰力排序並依序比較戰力可以得到最佳結果(也就是說每次贏都贏和我方戰力最近的(a>b，且b最接近a))
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int num;
priority_queue<int> q1,q2;
//priority_queue會先將數字由小到大排序 //(語法和queue一樣)
for (int i = 0; i < n; i++){
scanf("%d",&num);
q1.push(num);
}
for (int i = 0; i < n; i++){
scanf("%d",&num);
q2.push(num);
}
int ans = 0;
while(!q2.empty()&&!q1.empty()){//拿我方最小戰力去比較直到贏才換下一個人
int me = q2.top(),other = q1.top();
q1.pop();
if (me > other){
ans++;
q2.pop();
}
}
printf("%d",ans);
}
```
### 十年磨一劍 (最少完成時間)(d044
###### `greedy` `貪心法` `前綴和` `prefix` `sort`
華山磨劍坊目前有 n 筆訂單，每筆訂單要磨一把劍，每把劍所需的時間不盡相同。磨劍師傅每次只能磨一把劍，現在希望每一筆訂單的完成時間之總和能夠最小，希望能找出最好的磨劍順序。
舉例來說，如果有四把劍，磨劍需要的時間分別是 (3,1,3,4) ，如果以 (3,1,3,4) 的順序來磨，第一把的完成時間是 3 ，第二把完成 時間是 3+1=4 ，第三把是 3+1+3=7 ，第四把是 3+1+3+4=11 ，總和是 3+4+7+11=25 。 如果把順序改成 (1,3,3,4) ，那麼完成時間分別是 (1,4,7,11) ，總和是 23 ，這是這一題最好的解。
輸入 : 第一行是一個正整數 n ，
第二行有 n 個正整數是每一把劍需要的時間，同行數字間以空白間格。
n 與每把劍的時間都不超過 1e5 。
輸出 : 輸出最小的完成時間總和。
:::info
*#a[]是每把劍需要的時間*
這題很直覺就小排到大，因為計算第i筆訂單時就是(n-i)*a[i]，越大的數字越後面就會花費越少時間
這題也可以使用priority_queue來寫
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++)scanf("%d",&a[i]);
sort(a,a+n);//排序
long long ans = 0;
long long tem = 0;
for (int i = 0; i < n; i++){
tem += a[i];//運用前綴和計算本次花費才不會變成O^2
ans += tem;
}
printf("%lld\n",ans);
}
```
### 幾場華山論劍(d045
###### `greedy` `貪心法` `sort` `pair`
華山派決定每年都舉辦非常多場的華山論劍，每一場都有自己的開始時間與結束時間，參加者必須全程在場，所以不能在同一時間參加兩場。
令狐沖拿到了今年所有場次的資料，希望能參加越多場越好，以便盡速累積經驗值，請你幫忙計算最多可以參加幾場。
請注意，前一場的結束時間必須小於下一場的開始時間。
輸入 : 第一行是一個正整數 n，代表一共舉辦了 n 場華山論劍，
接下來 n 行，每 行兩個非負整數 s 與 t，代表這場活動的時間區間是 [s,t]，兩數字間以空白間格。
n 不超過 1e5，s<t<1e9。
輸出 : 最多參加幾場活動。
:::info
這題證明會使用的是反證法
先把每場比賽都是為數線上的一個區間
令[x,y]為右端最小值(也就是結束時間最小的)
令[a,b]為最佳解中右端最小值(也就是最佳解中結束時間最小的)
由此設定得知y<=b
從上圖可以看出選擇[x,y]一定不會比選擇[a,b]差
所以可以得知每次選擇結束間最早的會有最佳解
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> a1,pair<int,int> a2){
return a1.second > a2.second;
}
int main()
{
int n;
scanf("%d",&n);
vector<pair<int,int>> v;
v.clear();
int s,t;
for (int i = 0; i < n; i++){
scanf("%d%d",&s,&t);
v.push_back({s,t});
}
sort(v.begin(),v.end(),cmp);
int ans = 0;
s = -1,t = -1;
while(!v.empty()){
s = v.back().first;
if (s > t){//如果開始時間大於上次的結束時間才可以計算
ans ++;
t = v.back().second;
}
v.pop_back();
}
printf("%d",ans);
}
```
### 嵩山磨劍坊的問題 (加權最小完成時間)(d046
###### `greedy` `貪心法` `sort` `struct`
嵩山磨劍坊接了 n 筆磨劍工作，磨劍師傅每次只能磨一把劍。除了每把劍各有所需的時間之外，每件工作的重要性也不同。
假設第 i 筆訂單需要的時間是 t[i]，而重要性是 w[i]。
磨劍坊的計價方式是：每件工作都已經先收了一筆款項，假設第 i 筆訂單在時間 f 時完成，則需要扣款 f∗w[i]，現在希望將 n 筆磨劍工作安排最好的順序，使得扣款總額越小越好。
舉例來說，如果有四把劍，磨劍需要的時間分別是 t=(1,4,5,6)，而重要性依序是 w=(1,3,4,7)。
依照訂單編號順序 (4,1,3,2) 來磨,則 t 與 w 重新排列後分別是 t=(6,1,5,4)，w=(7,1,4,3)。完工時間是 (6,7,12,16)，扣款總額是 6∗7+7∗1+12∗4+16∗3=145。
輸入 : 第一行工作數 N，N<1e5。
第二行有 N 個正整數，依序是各訂單所需時間 t[1]、t[2]、…、t[N]。
第三行有 N 個非負整數，依序是各訂單的重要性 w[1]、w[2]、…、w[N]，時間與重要性皆不超過 1000，相鄰以空白間隔。
輸出 : 輸出最小的扣款總額。答案不超過 1e18。
:::info
證明 :
$$
假設\frac{t[i]}{w[i]}>\frac{t[i+1]}{w[i+1]}可整理成w[i+1]*t[i]>w[i]*t[i+1]
$$
若交換i和i+1的順序時並不會引想其他的訂單而i延後i+1提早所以變化量是
$$
w[i]*t[i+1]-w[i+1]*t[i]<0(結合上述算式) (下圖為輔助說明)
$$
------------------------------>
$$
所以結論是當\frac{t[i]}{w[i]}>\frac{t[i+1]}{w[i+1]}時交換兩者順序會有最佳解
$$
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
struct thing{
int t,w;
};
thing a[100010];
bool cmp(thing f,thing s){
return (double)f.t/f.w < (double)s.t/s.w;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++)scanf("%d",&a[i].t);
for (int i = 0; i < n; i++)scanf("%d",&a[i].w);
sort(a,a+n,cmp);
int time = 0;
long long ans = 0;
for (int i = 0; i < n; i++){
time += a[i].t;
ans += a[i].w*time;
}
printf("%lld",ans);
}
```
### 少林寺的自動寄物櫃 (APCS201710)(d047
###### `greedy` `貪心法` `sort` `struct` `APCS` `preifx` `前綴和`
少林寺的自動寄物櫃系統存放物品時，是將 N 個物品堆在一個垂直的貨架上，每個物品各佔一層。
系統運作的方式如下：每次只會取用一個物品，取用時必須先將在其上方的物品貨架升高，取用後必須將該物品放回，然後將剛才升起的貨架降回原始位置，之後才會進行下一個物品的取用。每一次升高貨架所需要消耗的能量是以這些物品的總重來計算。
現在有 N 個物品，第 i 個物品的重量是 w(i) 而需要取用的次數為 f(i)，我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。
輸入 : 輸入的第一行是物品件數 N，N<1e5。
第二行有 N 個正整數，依序是各物品的重量 w(1)、w(2)、…、w(N)。
第三行有 N 個正整數，依序是各物品的取用次數 f(1)、f(2)、…、f(N)，
重量與次數皆不超過 1000，相鄰以空白間隔。
輸出 : 輸出最小能量消耗值。答案不超過 1e18。
:::info
這題的證明和上題是一樣的，不一樣的部分是，因為從最上面的開始拿所以排序要相反並且重量要前綴和
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
struct item{
int w,f;
};
item a[100010];
bool cmp(item i,item j){//排序和上題相反
return (double)i.f/i.w > (double)j.f/j.w;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++) scanf("%d",&a[i].w);
for (int i = 0; i < n; i++) scanf("%d",&a[i].f);
sort(a,a+n,cmp);
long long weight = 0,ans = 0;
for (int i = 0; i < n; i++){
ans += weight * a[i].f;
weight += a[i].w;//前綴和重量
}
printf("%lld",ans);
}
```
### 先到先服務(d053
###### `greedy` `貪心法` `priority_queue`
有 n 個客人要分配到 m 個櫃台來服務，客人依編號順序到達，第 i 個客人需要 t(i) 的時間來完成(無論分配到哪一個櫃台)，而且每個客人的需求必須在同一個櫃台完成。因為公平的因素，先到客人不可以比晚到客人更晚開始服務。
現在希望安排每個客人的服務櫃檯，以便可以在最短的時間內完成所有客人的需求。
輸入 : 輸入兩行，第一行是正整數 n 與 m ，
第二行是 n 個正整數 t(1),t(2),…,t(n) ，
同行數字間以空白間格。 n 與 m 不超過 2e5，t(i) 不超過 1e4 。
輸出 : 最早可能服務完所有客人的時間。
:::info
這題的想法是每一客人都去它最早可以被服務的櫃檯
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
priority_queue<long long> pq;//每次放入數值都會由大排到小
int num;
for (int i = 0; i < n; i++){
scanf("%d",&num);
if (pq.size() < m) pq.push(-num);//還有空櫃檯的時候
//push負數可以變成由小排到大
else{//沒有空櫃台所以選最早可以被服務的櫃台
long long tem = pq.top();
pq.pop();
tem -= num;
pq.push(tem);
}
}
long long ma = 0;
while(!pq.empty()){//找最後服務完的櫃台
ma = max(-pq.top(),ma);
pq.pop();
}
printf("%lld",ma);
}
```
### 基地台 (APCS201703)(d049
###### `greedy` `貪心法` `二分搜` `APCS`
直線上有 N 個要服務的點，每架設一座基地台可以涵蓋直徑 R 範圍以內的服務點。
輸入服務點的座標位置以及一個正整數 K，請問：在架設 K 座基地台以及每個基地台的直徑皆相同的條件下，基地台最小直徑 R 為多少？
輸入 : 輸入有兩行。第一行是兩個正整數 N 與 K，以一個空白間格。
第二行 N 個非負整數 P[0]，P[1]，….，P[N−1] 表示服務點的點座標，相鄰數字以空白間隔。
座標範圍不超過 1e9，1≤K<N≤5e4 。
輸出 : 最小的基地台直徑。
:::info
這題的二分搜是在檢查在長度len時是否可以用k個服務點覆蓋所有的基地台，如果可以那麼就可以嘗試用更短的len，如果不行就檢查更長的len。
而Greedy的地方是在檢查是否可以覆蓋時，我們可以從最左端開始並且忽略以被覆蓋的點，如圖
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[50010];
int n,k;
bool check(int len){
int flag = -1,idx = k;
for (int i = 0; i < n; i++){
if (a[i] > flag){//是最左端
idx--;
flag = a[i]+len;
}
if (idx < 0) return false;//超過k個，不合
}
return true;
}
int main()
{
scanf("%d%d",&n,&k);
for (int i = 0; i < n; i++) scanf("%d",&a[i]);
sort(a,a+n);
int r = 0,l = a[n-1]-a[0],mid = (r+l)/2;
while(l-1 > r){//二分搜
mid = (r+l)/2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d\n",l);
}
```
### 恢復能量的白雲熊膽丸(d054
###### `greedy` `貪心法` `二分搜`
令狐沖闖黑木崖要依序通過 n 個關卡，第 i 個關卡要消耗 p[i] 的能量，如果能量不足就會闖關失敗。不管當時的能量剩下多少，吃下一顆恆山派的「白雲熊膽丸」就會讓令狐沖的能量值恢復到滿額的 F 。
假設在開始時能量是 F ，闖關過程中最多只能服用 m 次，
輸入 p[] 與 m ，請問令狐沖的能量額 F 至少必須是多少才能闖關成功。
請注意，連吃兩顆是沒用的，能量還是 F 。
輸入 : 第一行是正整數 n 與非負整數 m ，
第二行有 n 個正整數 p[1] , p[2] ,…, p[n] 。
p[i] 不超過 1e5，0≤m<n≤1e5
輸出 : 輸出 F 的最小值。
:::info
這題和上一題幾乎一樣，就不再說明
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100010];
bool check(int f){
int flag = m,now = f;
for (int i = 0; i < n; i++){
if (now - a[i] < 0){//如果能量不足時就吃藥丸
flag--;
now = f;
}
if (flag < 0 || a[i] > f) return false;
now -= a[i];
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
int r = 0,l = 0;
for (int i = 0; i < n; i++){
scanf("%d",&a[i]);
l += a[i];
}
int mid;
while(l-1 > r){//二分搜
mid = (l+r)/2;
if (check(mid))l = mid;
else r = mid;
}
printf("%d",l);
}
```
### 線段聯集 (APCS 201603)(d050
###### `greedy` `貪心法` `線性掃描法` `sweep-line` `APCS`
輸入數線上的 N 個線段，計算線段聯集的總長度。
輸入 : 第一行是一個正整數 N ，
接著的 N 行每一行兩個非負整數，代表一根線段的左端點與右端點，左端點座標值小於等於結束端點座標值，兩者之間以一個空格區隔。
N 不超過 1e5 ，座標絕對值皆不超過 1e8
輸出 : 線段聯集總長度。
```c++=
#include<bits/stdc++.h>
using namespace std;
pair<int,int> p[100010];
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++){
scanf("%d%d",&p[i].first,&p[i].second);
}
sort(p,p+n);//排序左端也就是排序p[i].first
int s = -1,e = -1;
int ans = 0;
for (int i = 0; i < n; i++){
if (p[i].first > e){//如果和前者沒有交集
ans += e-s;
s = p[i].first;
e = p[i].second;
}
else{//如果有交集右端選擇最大的
e = max(e,p[i].second);
}
}
ans += e-s;
printf("%d",ans);
}
```
### 一次買賣(d051
###### `greedy` `貪心法` `線性掃描法` `sweep-line`
某商品在某個時期每一天的價格是 p(1),p(2),…,p(n) 。
假設只能先買後賣，
請計算買賣一次的最大獲利價差，允許當天買賣，也就是一次都不買 (獲利 0)。
輸入 : 第一行是正整數 n ，
第二行有 n 個正整數 p[1],p[2],…,p[n] 。
n 不超過 1e5 ，價格皆不超過 1e9。
輸出 : 買賣一次的最大獲利。
:::info
第i天的最大獲利一定是買第i天前的最小值，所以我們只須要維護一個值mi為最小值，並且每次讀入資料時都更新最小值擊最大獲利即可
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int mi = 1e9,ans = 0;
for (int i = 0; i < n; i++){
int num;
scanf("%d",&num);
mi = min(mi,num);//第i天前的最小值
ans = max(ans,num-mi);//最大獲利
}
printf("%d\n",ans);
}
```
### 最大連續子陣列(d052
###### `greedy` `貪心法` `線性掃描法` `sweep-line`
輸入一個整數陣列 A[1:n] ，
請計算 A 的連續子陣列的最大可能總和，空陣列的和以 0 計算。
輸入 : 第一行是正整數 n ，
第二行有 n 整數 A[1] , A[2] , … , A[n] 。
n 不超過 105 ，陣列內容絕對值不超過 109 。
輸出 : 最大可能總和。
:::info
這題的想法就是當前面累積的小於0時就0開始在繼續累加(因為負的對後面沒有幫助所以就直接重新計算)並且每次讀入資料都重新更新最大總和
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
long long num,pre = 0,ma = 0;
for (int i = 0; i < n; i++){
scanf("%lld",&num);
pre = max((long long)0,pre+num);
ma = max(ma,pre);
}
printf("%lld",ma);
}
```
### 控制點 (2D-max)(d055
平面上有 N 個點，第 i 點的座標為 (x[i] , y[i]) 。若 x[i]≤x[j] 且 y[i]≤y[j] ，則我們說第 j 點可以控制第 i 點。我們希望能在輸入的點中，選取最少的點做為控制點，使得每一個輸入的點都至少被一個控制點所控制。
輸入 N 個點的座標，請計算出最少要選取多少個控制點。
輸入 : 每筆測試資料的第一行為一個正整數 N，N <= 1e5 。
第二行有 N 個非負整數，依序是這些點的 X 座標，
第三行有 N 個非負整數，依序是這些點的 Y 座標，
座標值不超過 1e9 。
輸出 : 輸出最少的控制點數量。
:::info
首先將點的x座標由大排到小這樣就只需要比較y座標是否已被控制。
判斷方式是維護一個陣列最前面存放的就是現在y座標的最大值，只要現在的y座標小於這個值那麼就代表已經被控制了，如果y座標比目前最大的還大代表此點必須為控制點，如圖
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int pos;
vector<pair<int,int>> s;
stack<int> v;
for (int i = 0; i < n; i++){
scanf("%d",&pos);
s.push_back({-pos,0});
}
for (int i = 0; i < n; i++){
scanf("%d",&s[i].second);
}
sort(s.begin(),s.end());
v.push(-1);
for (auto p:s){
if (p.second > v.top()){
v.push(p.second);
}
}
printf("%d",v.size()-1);
}
```
### 賺錢與罰款(d057
###### `greedy` `貪心法` `struct` `sort` `排序`
泰山派的磨劍坊接了 n 筆訂單，每一筆訂單有需要的工時 t[i] 以及完工要求時間 d[i] ，如果在時間 x 的時後交貨就可以賺 d[i]−x 的錢，也就是說越早完成賺越多，超過時間完成的話，越晚賠越多。
磨劍坊每次只能做一件工作，所以要把這 n 筆訂單做一個排程，希望利潤最大，也就是賺最多錢，如果不可能賺錢就要賠最少。
輸入 : 輸入的第一行是工作數 N 。
第二行有 N 個正整數，依序是各訂單所需時間 t[1] 、 t[2] 、…、 t[N] 。
第三行有 N 個非負整數，依序是各訂單的完工要求 d[1] 、 d[2] 、…、 d[N] ，相鄰以空白間隔。
N<1e5 ，時間不超過 1000 ，完工要求不超過 1e8 。
輸出 : 最大利益。
:::info
有兩個工作分別為t[i],d[i]和t[i+1],d[i+1]且訂單從時間T開始製作
假設t[i]>t[i+1]
原本的利益P = d[i]-(T+t[i])+d[i+1]-(T+t[i]+t[i+1])
若將兩個工作調換
調換後的利益P' = d[i+1]-(T+t[i+1])+d[i]-(T+t[i+1]+t[i])
整裡後發現P'-P = -t[i+1]+t[i] 而t[i]>t[i+1]所以得到P'>P所以依照製作時間排序可以得到最佳解
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
struct item{
int t,d;
};
item a[100010];
bool cmp(item f,item s){
if (f.t == s.t) return f.d < s.d;
return f.t<s.t;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++){
scanf("%d",&a[i].t);
}
for (int i = 0; i < n; i++){
scanf("%d",&a[i].d);
}
sort(a,a+n,cmp);
long long time = 0,ans = 0;
for (int i = 0; i < n; i++){
time += a[i].t;
ans += a[i].d - time;
}
printf("%lld",ans);
}
```
### 死線高手(d058
###### `greedy` `貪心法` `struct` `sort` `排序`
令狐沖現在有 n 個作業，每個作業需要花的時間是 t[i] 而死線是 d[i] ，此外，每次只能進行一個作業，不可能一次做兩個作業，
請問他是否可能安排作業的順序，讓每個作業的完成時間都不會超過死線。
輸入 : 輸入包括多筆測資，第一行是測資筆數 T，T<20 ，以下是 T 筆測資的資料。每筆測資的第一行是作業數 n 。
第二行有 n 個正整數，依序是各作業所需時間 t[1] 、 t[2] 、…、 t[N] 。
第三行有 n 個正整數，依序是各作業的死線 d[1] 、 d[2] 、…、 d[N] ，相鄰以空白間隔。
n<1e5 ，時間不超過 1000 ，死線不超過 1e8 。
輸出 : 依序輸出每筆測資是否所有作業都可以在死線前完成，是則輸出 yes，否則輸出 no。
:::info
和上題類似也是依照工作時間排序
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
pair<int,int> p[100010];
bool cmp (pair<int,int> a, pair<int,int> b){
return a.second < b.second;
}
int main()
{
int n,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for (int i = 0; i < n; i++) scanf("%d",&p[i].first);
for (int i = 0; i < n; i++) scanf("%d",&p[i].second);
sort(p,p+n,cmp);
int time = 0;
bool flag = true;
for (int i = 0; i < n; i++){
if (time + p[i].first > p[i].second){
flag = false;
break;
}
else{
time += p[i].first;
}
}
if (flag) printf("yes\n");
else printf("no\n");
}
}
```
### 少林寺的櫃姐(d059
###### `greedy` `貪心法` `二分搜`
少林寺是觀光勝地，每天要接待很多客人，根據數據分析，方丈決定即使在尖峰時期也必須在時間 D 內完成 n 個客人的服務，現在的問題是不知道要開設多少個服務櫃台。
假設客人依編號順序到達，第 i 個客人需要 t(i) 的時間來完成他的需求(無論分配到哪一個櫃台)，而且每個客人的需求必須在同一個櫃台完成。因為公平的因素，先到客人的服務開始時間不可以大於晚到客人的服務開始時間。
因為每開設一個櫃台就要請一位櫃姐，為了節省人事成本，請計算出最少要開設多少櫃台才能讓這 n 個客人的服務都在時間 D 內完成。
輸入 : 輸入兩行，第一行是正整數 n 與 D ，
第二行是 n 個正整數 t(1) , t(2) ,…, t(n) ，同行數字間以空白間格。
n 不超過 1e5，t(i) 不超過 1e4，D 不超過 1e9 也不小於 1e4 ，所以一定有解。
輸出 : 最少的櫃檯數。
:::info
二分搜櫃台數量，看最少可以用幾個櫃台(可以參考基地台那題)
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[100010],n,d;
bool check(int idx){
int time = 0;
priority_queue<int> q;
for (int i = 0; i < n; i++){
if (time > d) return false;
if (i >= idx){
int tem = q.top();
q.pop();
q.push(tem-a[i]);
time = max(time,-tem+a[i]);
}
else{
q.push(-a[i]);
time = max(time,a[i]);
}
}
return true;
}
int main()
{
scanf("%d%d",&n,&d);
for (int i = 0; i < n; i++) scanf("%d",&a[i]);
int r = 1, l = n,mid;
while(l-1 > r){
mid = (l+r)/2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%d",l);
}
```
### 監看華山練功場(d061
華山派有 n 個弟子，每個弟子的練功時間都不盡相同，第 i 個弟子到練功場所練功的時間是區間 [s(i),t(i)] 。最近華山頗不平靜，掌門岳不群要求令狐沖找一些弟子練功時順便監看練功場，對於想要監看的時間區間 [x,y] ，
請問他最少只要找幾位弟子，這些弟子的練功時間就可以涵蓋整個 [x,y]
輸入 : 第一行是個正整數 n ，
第二行是兩個整數 x 與 y ，
接著的 n 行每一行有兩個整數 s(i) 與 t(i) ，同行相鄰兩數之間空白區隔。
n 不超過 1e5，0≤x<y≤1e9 ,且對所有 i，0≤s(i)<t(i)≤1e9 。
輸出 : 練功時間可以涵蓋 [x,y] 的最少的弟子數。如果無解輸出 −1
```c++=
#include<bits/stdc++.h>
using namespace std;
struct item{
int s,t;
};
item a[100010];
bool cmp(item a,item b){
return a.s < b.s;
}
int main()
{
int n,x,y;
scanf("%d%d%d",&n,&x,&y);
for (int i = 0; i < n; i++)scanf("%d%d",&a[i].s,&a[i].t);
sort(a,a+n,cmp);
int idx = 0;
for (int i = 0; i < n; i++){
if (a[i].s < y && a[i].t > x){
idx = i;
break;
}
}
int ans = 0;
int i = idx;
while(i < n && x < y){
int r = -1;
while(a[i].s <= x && i < n){
r = max(r,a[i].t);
i++;
}
if (r == -1){
ans = -1;
break;
}
x = r;
ans++;
}
printf("%d",ans);
}
```
## 霍夫曼編碼(Huffman code)
### 用途是什麼?
Huffman code是使用Greedy來編碼的，目的是將資料進行壓縮
---
舉例來說，有一個字串 CCBCAB 而我們要將這串字串用0和1進行編碼
若一般直覺的編碼方式，如右圖 
會得出10 10 01 10 00 01，共佔12個bites
若用huffman code依據字元出現頻率進行編碼，如右圖 
則會得到0 0 1 0 01 1，只佔了7個bites
---
在小資料運算雖看不出很大差異但未來運算大量資料時就會有顯著的差異，而Huffman除了壓縮資料也可以讓運算時速度加快。
### 如何編碼?
1.先將各字元視為一顆單節點的樹，初始權重為字母出現的頻率
2.接著將權重最小的兩棵樹合併產生新的樹，新樹的權重就是原先兩棵樹的總和
3.將新的樹合併回原本的森林(森林就是一堆樹組成的樹)，重複以上動作直到只剩下一顆樹(也就是只有一個跟節點)
---
以下是範例
首先會有各個字母的頻率(也就步驟1)，如圖
接著開始合併(重複步驟2,3)如下圖
1.-->2.-->3.-->
4.-->5.-->6.
ps:編碼的方式就是往左是0往右則是1，每增加一層就會多一個字元
最終的最優編碼如圖 
### 為何是最優?
#### 四個特性
在證明這樣的編碼方式是最優之前，需要先了解用Huffman code編的這棵最優編碼樹(以下簡稱為樹，是***最優編碼的***喔)的四個特性
特性一:
在這棵樹中除了葉節點外，所有節點都有兩個葉節點。
:::info
證明:
若有一個父節點只有一個子節點，那麼可以直接被子節點取代，如圖
依據編碼性質父節點的權重是葉節點相加，那麼當只有一個葉節點時，父(藍)及子(紅)節點的權重會相同，取代後的編碼會比原先更佳(最佳狀況才是最優編碼樹)
:::
特性二:
頻率高的字元深度越淺(樹的深度，也就是編碼後佔的位元比較少)
:::info
證明:
這個很容易理解出現越多次的字元就使用越小的代碼編碼就可以節省空間。
以下是圖像的說明(圓圈內分別代表兩個點的頻率，旁邊的0 1則是編碼(有幾個字就佔幾個bites))
透過計算發現頻率高的越淺會得到較佳的答案(要最佳才是最優編碼樹喔)
:::
特性三:
頻率最低的兩個字元的葉節點一定是兄弟(也就是同個父節點)
:::info
證明:
透過性質一我們知道父節點一定有兩個葉節點，再透過性質二可以知道頻率最低的一定會在最下層，所以頻率最低的葉節點一定會在同一層
只要在同一層父節點是誰都是一樣的(因為深度決定佔的空間)如圖
:::
特性四:(這個特性有點難懂，但後面證明主要就是透過這個性質證明)
若有一顆最優編碼樹T0，將其中以x節點形成的樹替換為結點並形成新樹T，而新樹T也會是最優編碼樹，如圖(T0和T都是最優編碼樹)
:::info
證明:
使用反證法
假設T0為最優編碼樹，x為其中一個子樹(圖1)
將子樹x換為節點fs(x)，形成新樹T(圖2)
若T不是最優編碼樹，那麼假設T'為最佳編碼樹(圖3)
將T'展開後得到新樹T0'發現T0'比T0還要好(圖4)
但T0是最優編碼樹所以T0'不存在導致T'也不存在所以T也是最優編碼樹
1.2.
3.4.
反之若縮點後為最佳編碼樹則佔開也是最佳編碼樹(可以用上述方法證明，這邊就不再寫一次了)
:::
#### 遞迴證明法
那要證明Huffman code的Greedy(也就是每次將頻率最小的兩個點結合)是正確的，那麼要使用遞迴證明法
1.首先定義問題Pn為n種字元時的最佳解
2.而當n=1時最佳解就是自己本身
3.假設Pn包含了Pn-1，透過性質三發現將頻率最低的兩個點結合一定是在最佳解中(因為頻率最低的兩個點互為兄弟一定可以合併)
ps:步驟3是證明貪心法是正確的
4.接著根據性質四，將Pn-1縮點合併成Pn後Pn也會是最佳編碼樹
ps:步驟4是證明Pn一定包含Pn-1
### 例題
#### 岳不群的併派問題(Two-way merge)(d048
江湖上門派林立，華山派掌門岳不群認為要消除門派的衝突就是要合併各門派，但不能操之過急，必須每次挑兩個門派合併，如此逐步合併，最後將所有門派合併成一派。
合併門派需要一些成本，每個門派都有他的成員數，第 i 個門派的成員數是 m(i)，合併兩派的成本就是雙方成員數之和，而兩派合併後，雙方成員就會歸到新合併的門派。
岳不群不希望耗費太多成本，輸入各派人數，請幫他計算最少的合併總成本。
輸入 : 第一行是一個正整數 n，代表初始的門派數量，
第二行有 n 個正整數是每派的成員數，同行數字間以空白間格。
n 不超過 2∗105，每個門派初始人數都不超過 105。
輸出 : 第一行輸出總人數，
第二行輸出最小的合併總成本。
ps :
1.如果不理解程式碼可以試著用前面的例子自己跑跑看程式碼
2.priority_queue在每次加入新元素時都會是排序好的，也就是說我每次的top都一定是最大的數字，這部分就是Greedy
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
long long num,total = 0;
priority_queue<long long> pq;
for (int i = 0; i < n; i++){
scanf("%lld",&num);
total += num;
pq.push(-num);
//priority_queue是由大排到小，但我要將它由小排到大所以加上負號
}
long long m = 0,cnt = 0;
for (int i = 0; i < n-1; i++){
//每次都合併最小的兩個數字直到只剩一個數字
m = pq.top();
pq.pop();
m += pq.top();
pq.pop();
pq.push(m);
cnt += m;
}
printf ("%lld\n%lld\n",total,-cnt);
}
```
## 分治 divide-and-conquer
### 反序數量 (APCS201806)(d064
###### `分治` `divide-and-conquer` `APCS`
考慮一個數列 A[1:n]。如果 A 中兩個數字 A[i] 和 A[j] 滿足 i<j AND A[j]<A[i]，也就是在前面的比較大，則我們說 (A[i],A[j]) 是一個反序對 (inversion)。
定義 W(A)為數列 A 中反序對數量。例如，在數列 A=(3,1,9,8,9,2) 中，一共有 (3,1)、(3,2)、(9,8)、(9,2)、(8,2)、(9,2) 一共 6 個反序對，所以 W(A)=6。
請注意到序列中有兩個 9 都在 2 之前，因此有兩個 (9,2) 反序對，也就是說，不同位置的反序對都要計算，不管兩對的內容是否一樣。
請撰寫一個程式，計算一個數列 A 的反序數量 W(A)。
輸入 : 第一行是一個正整數 n ，代表數列長度，
第二行有 n 個非負整數，是依序數列內容，數字間以空白隔開。
n 不超過 1e5
數列內容不超過 1e6 。
輸出 : 輸出反序對數量。
:::info
這題的分治是要計算A的反序數對，那麼我可以先切一半分別計算兩邊的反序數列(第9行)再加上跨兩邊的反序數列(第12~14行)
所以其實我只要會處理跨兩邊就可以
假設我l ~ m為前半，m ~ r為後半，而兩邊都分別由小到大排序好
那麼我就可以知道前半的每個數字可以和後半形成多少反序數列
並在計算完後將l ~ r排序，以下是範例(可以排序是因為在分割後排序不會影響之後的結果，不理解的可以去看看合併排序法跟這部分是一樣的)
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[100010];
long long func(int l,int r){
if (l+1 >= r) return 0;
int m = (l+r)/2;
long long LaR = func(l,m)+func(m,r);//左右分別的反序數對
long long LR = 0;
int j = m;
for (int i = l; i <m; i++){//跨左右區的反序數對
while(j < r && a[j] < a[i])j++;
//因以排序所以找a[j]最大且小於a[i]的數字
LR += j-m;
}
sort(a+l,a+r);
return LaR+LR;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++) scanf("%d",&a[i]);
long long ans = func(0,n);
printf("%lld\n",ans);
}
```
### 最靠近的一對 (closest pair)(d056
###### `分治` `divide-and-conquer`
平面兩點的 L1 距離為兩點的 X 差值與 Y 差值的和，也就說，如果兩點座標是 (a,b) 與 (c,d)，則 L1 距離是 |a−c|+|b−d|。
輸入 n 個點的座標，請計算出 L1 距離最近兩點的 L1 距離。
輸入 : 第一行為一個正整數 n，
接下來 n 行，每行兩個整數 x 與 y 代表一點的座標。
n 不超過 1e5，座標值絕對值不超過 1e8。
輸出 : 最近兩點的 L1距離。
:::info
這題也可以用Greedy但這邊就先用分治法
首先先將點的x座標排序這樣我們就只需要處理y座標就好了
那分治的方法和上面一樣，將座標切一半分辨看左右邊的最小距離再看跨兩區的點的最小距離(所以處理跨兩區的就好了)
假設我已知目前最小距離為mi那可以先用上題的方法將左右兩區x座標距離小於mi的座標用新陣列先記錄(這裡我使用tem這個陣列佔存)接著再計算這個陣列內座標的與前半座標的真正距離(這個部分是function con，這部分會看到我只檢查8個點，這是因為8個點外就不會再更小了，那其實有個證明的原因但有點複雜有興趣可以查closet pair)，以下範例
-> -> 
->-> 
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
pair<int,int> pos[100010];
bool cmp(pair<int,int> a,pair<int,int> b){
return a.second < b.second;
}
long long dis(pair<int,int> a, pair<int,int> b){
return abs(a.first-b.first) + abs(a.second-b.second);
}//算距離
long long con(pair<int,int> p[],int r){
long long d = 1e9;
for (int i = 0; i < r; i++){
for (int j = i+1; j < r && j <= i+7;j++){
d = min(d,dis(p[i],p[j]));
}
}
return d;
}//計算tem陣列內各點距離
long long func(int l,int r){
if (l+1 >= r){//左右各一點直接計算兩者距離
long long mi = 1e9;
mi = min(mi,dis(pos[l],pos[r]));
return mi;
}
int m = (l+r)/2;
long long mi = min(func(l,m),func(m,r));//左右兩邊最短距離
pair<int,int> tem[r-l];
int k = 0;
for (int i = l; i < r; i++){
if (abs(pos[i].first - pos[m].first) < mi){
tem[k++] = pos[i];//x座標差小於mi則放入tem等等檢查
}
}
sort(tem,tem+k,cmp);
mi = min(mi,con(tem,k));//計算tem內的最短距離
return mi;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++) scanf("%d%d",&pos[i].first,&pos[i].second);
sort(pos,pos+n);
long long ans = func(0,n);
printf("%lld",ans);
}
```
### 線性函數(d038
###### `分治` `divide-and-conquer`
有 N 線性函數 fi(x)=aix+bi，1≤i≤n。
定義 F(x)=max fi(x)。
輸入 c[i],1≤i≤m，
請計算 ∑F(C[i])。
輸入 : 第一行是 N 與 m。
接下來有 N 行，依序每行兩個整數 ai 與 bi，
最後一行有m個整數c[1],c[2],⋯,c[m]。
每一行的相鄰數字間以空白隔開。
N≤105， m≤5∗104，輸入整數絕對值不超過 107，答案不超過 1015。
輸出 : 計算結果。
:::info
這題要先知道一個性質就是當x越大時斜率越大y值就會越大，如圖
所以先寫一個比較函式將斜率由小排到大，接著分治，假設在有一個x=c最大值在f(i)那麼斜率比i小的函式的x就會小於c，反之比i大的函式的x就會比c大
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
pair<int,int> p[100010];
int c[100010];
bool cmp(pair<int,int> a,pair<int,int> b){
if (a.first == b.first) return a.second < b.second;
else return a.first < b.first;
}
long long dc(int pl,int pr,int cl,int cr){
if (cl >= cr) return 0;
int m = (cl+cr)/2;
long long maxy = -1e20,who;
for (int i = pl; i < pr; i++){//找出c[m]在甚麼時候有最大值
long long y = (long long)c[m]*p[i].first+p[i].second;
if (maxy < y){
maxy = y;
who = i;
}
}
return maxy + dc(pl,who+1,cl,m) + dc(who,pr,m+1,cr);
//分治比i小的斜率和比i大的斜率
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0; i < n; i++) scanf("%d%d",&p[i].first,&p[i].second);
for (int i = 0; i < m; i++) scanf("%d",&c[i]);
sort(p,p+n,cmp);
sort(c,c+m);
long long ans = dc(0,n,0,m);
printf("%lld",ans);
}
```
### 完美彩帶 (APCS201906)(d036
###### `分治` `divide-and-conquer` `APCS`
有一條細長的彩帶，總共有 m 種不同的顏色，彩帶區分成 n 格，每一格的長度都是 1，每一格都有一個顏色，相鄰可能同色。
長度為 m 的連續區段且各種顏色都各出現一次，則稱為「完美彩帶」。
請找出總共有多少段可能的完美彩帶。請注意，兩段完美彩帶之間可能重疊。
輸入 : 第一行為整數 m 和 n，滿足 2≤m≤n≤2∗105；
第二行有 n 個以空白間隔的數字，依序代表彩帶從左到右每一格的顏色編號，
顏色編號是不超過 109 的非負整數，每一筆測試資料的顏色數量必定恰好為 m。
輸出 : 有多少段完美彩帶。
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main()
{
int n,m;
scanf("%d%d",&m,&n);
for (int i = 0; i < n; i++) scanf("%d",&a[i]);
map<int,int> check;
check.clear();
int total = 0,ans = 0;
for (int i = 0; i < m ; i++){
check[a[i]]++;
if (check[a[i]] == 1) total++;
if (total == m){
ans++;
}
}
for (int left = 0,right = m;right < n; left++,right++){
check[a[right]]++;
if (check[a[right]] == 1) total++;
check[a[left]]--;
if (check[a[left]] == 0) total--;
if (total == m){
ans ++;
}
}
printf("%d\n",ans);
}
```
## 動態規劃(DP dynamic programing)
### 小朋友上樓梯最小成本(d066
###### `DP` `動態規劃` `1D0D`
小朋友玩上樓梯遊戲，每一步可以往上走一階或兩階，開始位置在第 0 階，從第一階開始每階都有一個數字，踩在第 i 階，分數就要扣第 i 階的數字，
請問走到第 n 階的最少的扣分是多少。
輸入 : 第一行是正整數 n 。
第二行有 n 個正整數，依序代表第 1 階開始的數字，
數字間以空白隔開。 n≤1e5 ，每階的數字不超過 1e4 。
輸出 : 走到第 n 階的最小總扣分。
:::info
假設c[i]是第i階的最佳答案,cost[i]第i階的分數
那麼DP的轉移式是c[i] = cost[i] + min(c[i-1],c[i-2])
從轉移式可以發現只需要用到前兩隔，所以我分別用兩個變數p和pp來紀錄就不需要再使用陣列
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int cost = 0, p = 0, pp = 0;
for (int i = 0; i < n; i++){
scanf("%d",&cost);
cost += min(p,pp);
pp = p;//c[i-2]
p = cost;//c[i-1]
}
printf ("%d\n",cost);
}
```
### 不連續的表演酬勞(d067
###### `DP` `動態規劃` `1D0D`
楊鐵心帶著義女穆念慈當街頭的武術表演者，他接到許多的邀約，每天均有一場。每一場表演都可以得到某些金額的報酬，但是武術表演很辛苦，無法連續兩天都進行表演，
請你寫一支程式協助他決定應該接受那些表演以得到最大的報酬。
輸入 : 第一行是正整數 n。
第二行有 n 個非負整數，依序代表第 1 天開始每天邀約報酬，數字間以空白隔開。
n≤1e5 ，每天酬勞不超過 10000 。
輸出 : 最大可能獲得的總酬勞。
:::info
這題和上一題是一樣的只是轉移式中的min改為max
也就是c[i] = cost[i] + max(c[i-1],c[i-2]);
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int pay = 0,p = 0,pp = 0;
for (int i = 0; i < n; i++){
scanf("%d",&pay);
pay = max(pay+pp,p);
pp = p;
p = pay;
}
printf("%d",pay);
}
```
### 最小監控鄰居的成本(d068
###### `DP` `動態規劃` `1D0D`
有一條長長的大街被劃分成 n 個區段，編號依序為 1 ~ n。在第 i 個區段設置監控設備的話，需要成本 c[i] ，而可以監控第 i−1 到第 i+1 的區段(超出範圍可忽略)。
現在要選一些區段裝設監控設備，以便每一個區段都可以被監控到，請計算最少的總成本。
輸入 : 第一行是正整數 n 。
第二行有 n 個非負整數，依序代表第 i 個區段裝設監控設備的成本，數字間以空白隔開。
n≤1e5 ，每處成本不超過 1e4。
輸出 : 最小監控總成本。
:::info
a[i]為在i區段內裝設的最小成本
本題轉移式a[i] = a[i] + min(a[i-3],a[i-2],a[i-1])
但要注意最後最小值可能出現在n-1或n-2(因為n-2也可以涵蓋n-1)
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++) scanf("%d",&a[i]);
a[2] += min(a[1],a[0]);
for (int i = 3; i < n; i++){
a[i] += min(a[i-3],min(a[i-2],a[i-1]));//轉移式
}
if (n > 1)printf("%d",min(a[n-1],a[n-2]));
else printf("%d",a[0]);
}
```
### 闖關二選一(d072
###### `DP` `動態規劃` `1D0D`
某個遊戲要依序闖過 n 個關卡，初始的時候有一個幸運數字，每個關卡有兩個關卡數字，你必須把自己的幸運數字調整為兩個關卡數字之一，才能通過此關卡，調整的成本是你的幸運數字與關卡數字的差值(絕對值)。
請計算出最低闖關總成本。
輸入 : 第一行有兩個正整數 n 與 t，代表關卡數以及初始幸運號碼。
接下來有 n行，每行兩個整數，依序代表每一關的過關數字。
n≤105，過關數字的絕對值皆不超過 109。
輸出: 最小過關成本。
:::info
dp[i][0]是i關選擇在數字一的最佳解，dp[i][1]則是停留在數字二
a[i][0]是i關的數字一，a[i][1]則是數字二
這題的轉移式看起來有點長但其實很簡單
如果停留在數字一也就是
dp[i][0] = min(上關選數字一+次關選數字一,上關選數字二+此關選數字一)
反之dp[i][1] = min(上關選數字二+此關選數字二,上關選數字一+此關選數字二)
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[100010][2];
int dp[100010][2];
int main()
{
int n,t;
scanf("%d%d",&n,&t);
for (int i = 0; i < n; i++) scanf("%d%d",&a[i][0],&a[i][1]);
dp[0][0] = abs(a[0][0] - t);
dp[0][1] = abs(a[0][1] - t);
for (int i = 1; i < n; i++){
dp[i][0] = min(abs(a[i-1][0]-a[i][0])+dp[i-1][0],abs(a[i-1][1]-a[i][0])+dp[i-1][1]);
dp[i][1] = min(abs(a[i-1][0]-a[i][1])+dp[i-1][0],abs(a[i-1][1]-a[i][1])+dp[i-1][1]);
}
printf("%d",min(dp[n-1][0],dp[n-1][1]));
}
```
### 二維最大子矩陣(d073
###### `DP` `動態規劃` `1D0D` `前綴和`
輸入一個 m∗n 的二維整數矩陣 A[1:m][1:n] ，要找一塊總和最大的連續子矩陣，輸出其總和。
以下圖為例，挑選 A[1:3][2:3] 可以獲得最大總和 13 。
2 -2 3 3
-6 5 2 -8
3 7 -2 4
輸入 : 第一行有兩個正整數 m 與 n 。
接下來 m 行每行 n 個整數，代表矩陣由上而下由左而右的內容。
m 與 n 皆不超過 200 ，矩陣內的數字絕對值皆不超過 1e4 。
輸出: 子矩陣的最大可能總和，子矩陣邊長可為 0。
:::info
一開始先將每航以前綴和紀錄這樣計算時就不需要再用迴圈計算
轉移式有點難寫所以直接看程式碼搭配下圖作為例子，計算過程的i,j是在計算第i到j行的各種組合，以題目反例為例子假設i=2,j=3時
->
->->
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int dp[250][250];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
scanf("%d",&dp[i][j]);
dp[i][j] += dp[i-1][j];
}
}
int ma = 0;
for (int i = 1; i <= n; i++){
for (int j = i; j <= n; j++){
int tem = 0;
for (int k = 1; k <= m; k++){
tem = max(tem,0)+dp[j][k]-dp[i-1][k];
ma = max(tem,ma);
}
}
}
printf("%d",ma);
}
```
### 方格棋盤路線(d069
###### `DP` `動態規劃` `2D0D`
在一個 m∗n 方格棋盤上，每個格子都有一個分數(可正可負)，現在要從左上角的格子走到右下角，每次只能從當時位置移動到右方或下方的格子，
請計算出經過路線上的數字的最大可能總和。
輸入 : 第一行有兩個正整數 m 與 n 。
接下來 m 行，每行 n 個整數，代表方格由上而下，由左而右的內容。
m 與 n 皆不超過 200 ，矩陣內的數字絕對值皆不超過 1e4 。
輸出 : 最大總和。
:::info
假設dp[i][j]是到地[i][j]最大總和，a[i]是當前格子的分數
那轉移式dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i] (以表格來講就是用到上方和左方的格子，因為格的前一格就是上方和左方)
如圖假設i=2，j=2此格就會被左邊和上方的格子影響
那我的作法是不用用到二維陣列的，因為只需要用到左邊和上方那麼右邊其實就不需要紀錄了，可以直接看程式碼的註解
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int dp[250];
int main()
{
int n,m;
long long tem;
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
for (int i = 1; i <= m; i ++){
scanf("%d",&dp[i]);
dp[i] += dp[i-1];//第一行只能從左邊來所以直接用加的
}
for (int i = 2; i <= n; i++){
for (int j = 1; j <= m; j++){
scanf("%d",&tem);
if (j == 1)dp[j] +=tem;//在第一列只能從上方來
else dp[j] = max(dp[j],dp[j-1]) + tem;
//其他格子看上方和左方(j是上方，j-1是左方)
}
}
printf("%lld",dp[m]);
}
```
### LCS(d070
###### `DP` `動態規劃` `2D0D` `LCS` `最長共同子序列`
輸入兩字串，
計算其 LCS 的長度。
輸入 : 第一行與第二行個有一個字串，
字串均只含小寫字母，長度不超過 500
輸出 : LCS 長度。
:::info
LCS是最常共同子序列，假設有兩字串ABCDHEE、ACHDEE，那它們的LCS就是ACHEE或ACDEE
那其實跟上題一樣可以用填表格的(但不能用一維陣列喔)
轉移式如下(有字串A和B，填A[i]和B[j]的LCS長度用dp[n][n]紀錄)
當A[i]=B[j]時
dp[i][j] = dp[i-1][j-1]+1(也就是LCS包含這兩個字元)
否則A[i]!=B[j]時
dp[i][j] = max(dp[i-1][j]，dp[i][j-1])(不包含此字元目前最長的LCS)
下圖是範例箭頭就是此格的填表來源，紅底代表兩字元相同
那我的想法是用滾動陣列就是兩個陣列輪流紀錄，因為從上圖可以發現只會用到上方左方或是斜上方，那麼兩個陣列，一個就是紀錄上方的一列，另一個紀錄現在在的這一列
p.s:如果不懂可以參考https://web.ntnu.edu.tw/~algo/Subsequence2.html
我覺得蠻清楚的
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
char s1[510],s2[510];
scanf("%s%s",&s1,&s2);
int n = strlen(s1), m = strlen(s2);
int lcs[2][510],from = 0,to = 1;
//to跟from分別就是前一行陣列以及現在所在的陣列
memset(lcs,0,sizeof(lcs));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (s1[i] == s2[j]) lcs[to][j] = lcs[from][j-1]+1;
else lcs[to][j] = max(lcs[from][j],lcs[to][j-1]);
}
swap(from,to);
}
printf("%d",lcs[from][m]);
}
```
### Local alignment(d074
###### `DP` `動態規劃` `2D0D`
Alignment 是生物序列（如 DNA 與蛋白質）分析的重要問題，輸入兩個字元序列，我們要將兩序列的字母依照原順序做一個對應，過程中可以將任一序列的某些位置加入空白，
以輸入"CTTAACT"與"CGGATCAT"為例，以下是一個可能的 alignment（以-表示空白）：
CTTAAC−T
CGGATCAT
以下也是一個 alignment：
C−−−TTAACT
CGGATCA−−T
alignment 的目的是要評估兩序列有多相似，我們會有一個評分機制，以下是一個例子：兩字母相同得 8 分，相異 −5 分，字母與空白對應 −3 分。
給定評分機制，輸入兩序列，要計算最大的 alignment 分數。
Alignment 可分為 global alignment 與 local alignment，前者是輸入的序列整個要納入 alignment，而後者是兩序列各選取連續的一段（長度可為 0 ）來做 alignment。
輸入兩字串，計算 local alignment 的最大分數。
輸入 : 第一行與第二行個有一個字串，
字串均只由 ATCG 四個字母組成，
長度不超過 500。
輸出 : Local alignment 的最大分數。
:::info
跟上題很類似
轉移式變成這樣
當A[i]=B[j]時
dp[i][j] = dp[i-1][j-1]+8(包含這兩個字元)
否則A[i]!=B[j]時
dp[i][j] = max(dp[i-1][j]-3，dp[i][j-1]-3,dp[i-1][j-1]-5)(不包含此字元目前最大分數)(dp[i-1][j]和dp[i][j-1]可以填入空白所以-3，dp[i-1][j-1]則是兩個相異字母所以-5)
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
char s1[510],s2[510];
int track[510][510];
int main()
{
scanf("%s%s",&s1,&s2);
memset(track,0,sizeof(track));
int len1 = strlen(s1),len2 = strlen(s2);
int ma = 0;
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
if (s1[i-1] == s2[j-1]){
track[i][j] = track[i-1][j-1] +8;
}
else{
track[i][j] = max(0,max(track[i-1][j]-3,max(track[i][j-1]-3,track[i-1][j-1]-5)));
}
ma = max(ma,track[i][j]);
}
}
printf("%d",ma);
}
```
### 大賣場免費大搬家(d071
###### `DP` `動態規劃` `2D0D` `0/1背包問題`
你抽中了大賣場的周年慶的抽獎活動，在不超過總重量 W 的限制下，你可任意挑選商品免費帶走。
現場一共 n 項商品，每項商品有它的重量與價值，每項商品只可以選或不選，不可以拆開只拿一部份。
請計算可以獲得的最大價值總和。
輸入 : 第一行有兩個正整數 n 與 W
第二行有 n 個正整數，依序代表商品的重量
第三行有 n 個正整數，依序代表對應 n 項商品的價值
同一行數字間以空白隔開
n≤100
W 與各商品重量及價值皆不超過 105
輸出 : 最大價值總和。
:::info
這題當然是裝越重越好，所以轉移式(dp[i][j]紀錄第i樣物品不超過j重時最高價值是多少，w[i]為i物重，p[i]為i價值)
dp[i][j] = max(d[i − 1][j], p[i] + d[i − 1][j − w[i]])
一樣可以改成一為陣列，但要注意填表格時比須從右填到左，因為使用的格子是上一列的左方的格子(也就是在沒有拿物品i時的價值)，如果從左到右填就會變成拿完i又再拿i。
這邊的轉移式就會變成dp[j] = max(dp[j],dp[j-w[i]]+p[i]);
p.s:i或j為0時dp[i][j]會是0喔，也就是初始值是0
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int price[110],weigh[110];
int dp[100010];
int main()
{
int n,w;
scanf("%d%d",&n,&w);
dp[0] = 0;
int ma = 0;
for (int i = 1; i <= n; i++) scanf("%d",&weigh[i]);
for (int i = 1; i <= n; i++) scanf("%d",&price[i]);
for (int i = 1; i <= n; i++){
for (int j = w; j >= weigh[i]; j--){
dp[j] = max(dp[j],dp[j-weigh[i]]+price[i]);
ma = max(ma,dp[j]);
}
}
printf("%d",ma);
}
```
### 置物櫃出租 (APCS201810)(d075
###### `DP` `動態規劃` `2D0D` `0/1背包問題` `APCS`
王老先生有一個置物櫃，共有 M 個相同大小的格子，置物櫃目前已經租給 n 個客戶，第 i 位客戶所租的大小為 f(i) 個格子 (1≤i≤n) 。
目前的承租量總和不超過 M ，但是現在王老先生自己需要使用 S 個格子的置物櫃，如果剩下的容量不夠，就必須退掉某些客戶的租約。假設每個客戶所租容量只能全退或全不退，而退租第 i 個客戶損失的利益與其所租容量 f(i) 相同，
請寫一支程式計算王老先生最小的損失利益，如果不須退租，則損失為 0 。
輸入 : 測試資料有兩行，第一行有三個正整數，依序是 n 、 M 與 S ，其中 S<=M ，
第二行是 n 個正整數 f(1) , f(2) , f(3) , ... , f(n) ，同一行的數字間以空白隔開，此行的最後有一個空格
1≤n≤100，M≤2e5。
輸出 : 輸出王老先生最小的損失利益。
:::info
這題和上題是一樣的(a[i]是第i位客戶的租容量及收益，dp[j]是在出租j個容量時的最大收益)
轉移式是dp[j] = max(dp[j-a[i]] + a[i],dp[j]);
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int a[110];
int dp[1000010];
int main()
{
int n,m,s,total = 0;
scanf("%d%d%d",&n,&m,&s);
memset(dp,0,sizeof(dp));
for (int i = 1; i <= n; i++){
scanf("%d",&a[i]);
total += a[i];
}
int save = m-s;
for (int i = 1; i <= n; i++){
for (int j = save; j >= a[i]; j--){
dp[j] = max(dp[j-a[i]]+a[i],dp[j]);
}
}
printf("%d",total-dp[save]);
}
```
### Catalan number(d076
#### `DP` `動態規劃` `1D1D`
令 f[0]=0, f[1]=1,
f[n]=f[n−1]+f[n−2],∀n>1。
輸入非負整數 n，請輸出 f[n] 除以 p 的餘數。
p=1000000007,n<231。
輸入:輸入一個非負整數 n，n<100。
輸出:Cn除以 P 的餘數。
:::info
1D1D的問題是n個子問題中的每個子問題都還是需要n個字問題的計算，所以這種問題必須要記錄過程才不回太過耗時
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
#define P 1000000009
long long memo[110];
long long cat(int a){
if (memo[a] >= 0) return memo[a];
long long tem = 0;
for (int i = 0; i < a; i++){
long long t = cat(i)*cat(a-1-i)%P;
tem = (tem+t)%P;
}
return memo[a] = tem;
}
int main()
{
int n;
scanf("%d",&n);
memset(memo,-1,sizeof(memo));
memo[0] = 1;
printf("%lld\n",cat(n));
}
```
### 楊鐵心做 1 休 K(d048
#### `DP` `動態規劃` `1D1D`
每天均有一場。每一場表演都可以得到某些金額的報酬，但是每次表演完至少要休息 K 天，
請你協助他決定應該接受那些表演以得到最大的報酬。
輸入 : 第一行有兩個正整數 n 與 K 。
第二行有 n 個正整數，依序代表第 1 天開始每天邀約報酬，數字間以空白隔開。
K<n≤1e5 ，每天酬勞不超過 10000 。
輸出 : 最大可能獲得的總酬勞。
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,now;
scanf("%d%d",&n,&k);
vector<int> dp(n+1);
fill(dp.begin(),dp.end(),0);
for (int i = 1; i <= n; i++){
scanf("%d",&now);
if (i-k-1 >= 0)dp[i] = max(dp[i-1],dp[i-k-1]+now);
else dp[i] = max(dp[i-1],now);
}
printf("%d\n",dp[n]);
}
```
### 周伯通的基地台(d077
#### `DP` `動態規劃` `1D1D` `deque` `滑動視窗`
周伯通標下了一個政府標案，要在一條長長的大街架設基地台，長街被劃分成 n 個區段，編號依序為 1~n。在第 i 個區段架設基地台的話，需要成本 c[i]，而可以服務第 i−k 到第 i+k 的區段(超出範圍可忽略)。
現在輸入 k，要選一些區段架設基地台，以便每一個區段都可以被服務到，請計算最少的總成本。
輸入 : 第一行有兩個正整數 n 與 k。
第二行有 n 個正整數，依序代表 c[1],c[2],…,c[n]，數字間以空白隔開。
k<n≤2e5，每處成本不超過 1000。
輸出 : 最小總成本。
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
scanf("%d%d",&n,&k);
vector<int> c(n+1),p(n+1);//p是紀錄p[i]以前都被覆蓋的最小花費
int head = 0,tail = 0,ans = 0;
for (int i = 1; i <= n; i++) scanf("%d",&c[i]);
deque<int> minq;
p[1] = c[1];
minq.push_back(1);
for (int i = 2; i <= n; i++){
if (i <= k+1) p[i] = c[i];
else{
if (minq.front()<i-2*k-1) minq.pop_front();
//如果最前面的已經超出範圍則要移除
p[i] = p[minq.front()]+c[i];
}
while(!minq.empty() && p[minq.back()] >= p[i])minq.pop_back();
//如果花費比現在花費貴則換成現在花費才會是最小的
minq.push_back(i);
}
printf("%d\n",*min_element(p.begin()+n-k,p.begin()+n+1));
}
```
### K 次買賣 (106 高中全國賽 subtask)(d085
#### `DP` `動態規劃` `1D1D`
某商品在某個時期每一天的價格是 p[1], p[2],…,p[n]。假設只能先買後賣，且賣了之後才能再買，
請計算買賣 K 次的最大獲利總價差，允許當天買賣，也就是不超過 K 次的買賣。
輸入 : 第一行是正整數 n 與 K，
第二行有 n 個正整數 p[1], p[2],…,p[n]。
n 不超過 1e5，K<100，商品價格皆不超過 1e7。
輸出 : 買賣不超過 K 次的最大總價差。
```c=
#include<bits/stdc++.h>
using namespace std;
int buy[110][2],sell[110][2],p[100010];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
memset(sell,0,sizeof(sell));
for (int i = 1; i <= n; i++){
scanf("%d",&p[i]);
if (i <= k) buy[i][1] = -p[1];
}
int now = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k; j++){
buy[j][now] = max(buy[j][1-now],sell[j-1][1-now]-p[i]);
sell[j][now] = max(sell[j][1-now],buy[j][1-now]+p[i]);
}
now = 1-now;
}
printf("%d\n",sell[k][1-now]);
}
```
### 一覽衆山小(d078
#### `DP` `動態規劃` `1D1D` `LIS`
現在已知所有人物的戰力與出場順序，想要找出依照出場順序而且戰力逐步上升的人物序列，請你計算滿足這樣要求的序列的最大可能長度。
輸入 : 第一行有一個正整數 n 代表出場的人物數。
第二行有 n 個非負整數，是依出場順序的每一位人物的戰力，數字間以空白隔開。
n ≤ 2e5，戰力值不超過 1e8。
輸出 : 出場順序與戰力皆遞增的序列的最大可能長度。
:::info
LIS為最常遞增子序列
定義一序列S , lis(lis[i]是i以前的LIS) , v為目前的LIS
lis[i]=max{lis[j]+1 (for j<i and S[j]<S[i]) }。
當j<i但 S[i] < S[j] 且 v[i]>v[j] 就可以將S[j]移除並替換成S[i](可以接在S[j]後的一定可以接在S[i]後
要記得維持v為遞增序列
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
vector<int> v;
int num;
for (int i = 0; i < n; i++){
scanf("%d",&num);
auto it = lower_bound(v.begin(),v.end(),num);
if (it == v.end()) v.push_back(num);
else *it = num;
}
printf("%d",v.size());
}
```
### 山寨華山論劍(d118
#### `DP` `動態規劃` `1D1D` `二分搜` `LIS`
自從華山論劍聲名大噪之後，很多人都想參加，但 20 年辦一次實在太久了，五輪奧運都跑 5 趟了，於是各地都紛紛舉辦華山論劍，往往同一天就有很多場。每一場都有自己的開始時間與結束時間，參加者必須全程在場，所以兩場的時間如果有重疊就不能同時參加。
令狐沖本來想參加最多場來盡速累積經驗值，但後來他發現有很多場次能獲得的經驗值很少，參加了反而浪費時間，
現在要請你幫忙計算最多可以得到的經驗值總和。
輸入 : 第一行是一個正整數 n，代表一共舉辦了 n 場華山論劍，
接下來 n行，每行有三個非負整數 s、t 與 e，代表這場活動時間區間是[s,t]，而可以得到的經驗值是 e，兩數字間以空白間格。
n≤105,s<t<109，答案不超過 109。
輸出 : 最大可能經驗值總和。
```c++=
#include<bits/stdc++.h>
using namespace std;
struct race{
int l,r,w;
};
bool cmp(race a,race b){return a.r<b.r;}
int main()
{
int n;
scanf("%d",&n);
vector<race> s(n+1);
for (int i = 1; i <= n; i++){
scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].w);
}
sort(s.begin(),s.end(),cmp);
s[0].r = -1;
vector<int> dp(n+1);
dp[0] = 0;
for (int i = 1; i <= n; i++){
int j = 0;
for(int jump = i/2; jump > 0; jump >>= 1){
while(j+jump < i && s[j+jump].r < s[i].l) j+= jump;
}
dp[i] = max((dp[j]+s[i].w),dp[i-1]);
}
printf("%d",dp[n]);
}
```
### 切棍子(d079
#### `DP` `動態規劃` `2D1D` `遞迴`
有一台切割棍子的機器，每次將一段棍子會送入此台機器時，我們可以選擇棍子上的切割位置，機器會將此棍子在指定位置切斷，而切割成本是該段棍子的長度。現在有一根長度 L 的棍子，上面標有 n 個需要切割的位置座標，因為不同的切割順序會影響切割總成本，請計算出最小的切割總成本。
輸入 : 第一行有兩個正整數 n 與 L。
第二行有 n 個正整數，依序代表由小到大的切割點座標 p[1]~p[N]，數字間以空白隔開，座標的標示的方式是以棍子左端為 0，而右端為 L。
N <= 200，L <= 1e6。
:::info
計算切割i到j的最小成本，也就是將i到j之間的每個點都當成切點試試看找最小的，最後再加上切i到j的成本就是答案
:::
輸出 : 最小的切割總成本。
```c++=
#include<bits/stdc++.h>
using namespace std;
int p[210],memo[210][210];
int cut(int i,int j){
if (memo[i][j] >= 0) return memo[i][j];
int mi = 1e9;
for (int k = i+1; k < j; k++){
mi = min(mi,cut(i,k)+cut(k,j));
}
mi += p[j]-p[i];
return memo[i][j] = mi;
}
int main()
{
int n,L;
scanf("%d%d",&n,&L);
for (int i = 1; i <= n; i++) scanf("%d",&p[i]);
p[0] = 0,p[n+1] = L;
memset(memo,-1,sizeof(memo));
for (int i = 0; i < n+1; i++)memo[i][i+1] = 0;
printf("%d\n",cut(0,n+1));
}
```
### 階梯數字(d080
#### `DP` `動態規劃` `2D1D`
一個正整數如果從高位數往低位數看過去，每一位數字只會相等或變大，則我們稱它為階梯數字，例如：9、234、777、11222233。
給定一正整數 N，請計算不大於 N的階梯數字總共有幾個，請注意本題只算正整數，所以 0 不算階梯數字，而且階梯數字不會以 0 開始。
輸入 : 輸入一個正數字 N。
N <= 1e18。
輸出 : 不大於 N 的階梯數字個數。
:::info
dp[i][j]為以j開頭i位數有幾個階梯數字
轉移式:dp[i][j] = dp[i-1][k](k = 0~j)
-> dp[i][j] = dp[i][j+1]+dp[i-1][j]
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
char c[100];
scanf("%s",c);
long long dp[20][10];
int i,j,len = strlen(c);
memset(dp,0,sizeof(dp));
for (i = 0; i < len; i++) c[i] -= '0';
for (i = 1; i < 10; i++) dp[1][i] = 1;
dp[1][0] = 0;
for (i = 2; i <= len; i++){
dp[i][9] = dp[i-1][9];
for (j = 8; j >= 0; j--){
dp[i][j] = dp[i][j+1]+dp[i-1][j];
}
}
long long ans = 0;
for (i = 0; i < c[0]; i++) ans += dp[len][i];
for (i = 1; i < len; i++){
if (c[i] < c[i-1]) break;
for (j = c[i-1]; j < c[i]; j++)ans += dp[len-i][j];
}
if (len == i) ans ++;
printf("%lld\n",ans);
}
```
### Hyper-cube path(d081
#### `DP` `動態規劃` `2D1D`
一個維度為 n 的 hypercube 是由2n個節點組成的網路，每個節點被賦予唯一一個0~2n−1的編號，對於任兩個節點 i 與 j，他們之間會有邊相連若且惟若 i 與 j 的二進位編碼恰好相差一個位元，我們對於每個節點 i 給予一個正整數的權重 w(i)，
請找出編號 0 到編號2n−1的一條最短路徑，使得該路徑所經過的點權重總合(包含起點與終點)為最大。
輸入 : 第一行是正整數 n，
第二行則是這2n個節點的正整數權重 w(0),w(1),…,w(2n−1)數字之間以一個空白間隔，
其中 n<20 而每個權重值為非負整數不超過 100。
輸出 : 最大權重總和。
:::info
檢查一數字n每個位元，如果此為原為1則可更換成0形成路徑，在從所有路徑中找最短的(使用遞迴)
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int n,memo[1000000],w[1000000];
int dp(int now){
if (memo[now] > 0) return memo[now];
int ma = 0;
for (int i = 0; i < n; i++){
if (now & (1<<i)){//當now的i位元是1時可替換成0做連結並計算
int tem = dp(now ^ (1<<i));//^是XOR運算
ma = max(ma,tem);
}
}
return memo[now] = w[now]+ma;
}
int main()
{
scanf("%d",&n);
for (int i = 0; i < (1<<n); i++) scanf("%d",&w[i]);//1<<n是2的n次方
memset(memo,-1,sizeof(memo));
memo[0] = w[0];
printf("%d",dp((1<<n)-1));
}
```
## 圖論(BFS&DFS)
### 探索距離(d090
#### `BFS` `queue`
輸入一個有向圖 G 與一個起點 s ，
請計算由 s 出發可以到達的點數(不包含 s ) ，並且計算這些可以到達的點與 s 的距離和，假設每個邊的長度均為 1 。
兩點之間可能有多個邊，邊的起點與終點未必不同。
輸入 : 第一行是兩個正整數 n 與 m ，代表圖的點數與邊數，圖的點是以 0 ~ n−1 編號，
第二行是 s 的編號，接下來有 m 行，
每一行兩個整數 a 與 b 代表一個邊 (a,b) 。n 不超過 100，m 不超過 4000 。
輸出 : 第一行輸出可以到達的點數，
第二行輸出與 s 的距離總和。
:::info
這題是BFS，解BFS有幾項標準的流程，以下:
1.要有一個陣列path紀錄可走的路徑
2.一個紀錄距離的陣列dis
3.一個紀錄是否走訪過的陣列visit(這題我直接用dis做為紀錄依據)
4.一個queue紀錄現在需要走訪的點
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int path[110][110],dis[110];
int main()
{
int point,edge,s;
scanf("%d%d%d",&point,&edge,&s);
memset(path,0,sizeof(path));
for (int i = 0; i < edge; i++){
int from,to;
scanf("%d%d",&from,&to);
path[from][to] = 1;
}
int total = 0,sum = 0;
memset(dis,-1,sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = 0;
while(!q.empty()){
int now = q.front();
q.pop();
for (int i = 0; i < point; i++){
if (path[now][i] == 1 && dis[i] == -1){
dis[i] = dis[now]+1;
q.push(i);
total++;
sum += dis[i];
}
}
}
printf("%d\n%d\n",total,sum);;
}
```
### 開車蒐集寶物(d091
#### `DFS`
你拿到一個地圖，地圖上有 n 個藏寶點，每個藏寶點有若干價值的寶物，從地圖上看得到一共有 m 條道路，每條道路連接兩個藏寶點，而且每條道路都是雙向可以通行的。
在遊戲的一開始，你可以要求直升機將你的團隊運送到某個藏寶點，但是直升機的載送只有一次，所以你必須決定要從哪裡開始才可以獲得最多的寶藏總價值。
輸入 : 第一行是兩個正整數 n 與 m ，代表藏寶地點數與道路數，地點是以 0 ~ n−1 編號，
第二行 n 個非負整數，依序是每一個地點的寶藏價值，每個地點的寶藏價值不超過 100 。
接下來有 m 行，每一行兩個整數 a 與 b 代表一個道路連接的兩個地點編號。
n 不超過 5×104，m 不超過 5×105 。
兩點之間可能有多條道路，有些道路的兩端點可能是同一地點。
輸出 : 最大可以獲得的寶藏總價值。
:::info
這題是DFS，解DFS有幾項標準的流程，以下:
1.要有一個陣列path紀錄可走的路徑
2.一個紀錄每個點的值的陣列value
3.一個紀錄是否走訪過的陣列visit
4.最後是一個遞迴函式找出每個點最大的值
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int value[50010];
vector<int>path[50010];
bool visit[50010];
int dfs(int s,int n){
visit[s] = 1;
int tem = value[s];
for (auto i: path[s]){
if(!visit[i]){
tem+=dfs(i,n);
}
}
return tem;
}
int main()
{
int spot,road;
scanf("%d%d",&spot,&road);
memset(visit,0,sizeof(visit));
for (int i = 0; i < spot; i++){scanf("%d",&value[i]);}
for (int i = 0; i < road; i++){
int s,t;
scanf("%d%d",&s,&t);
path[s].push_back(t);
path[t].push_back(s);
}
int ma = 0;
for (int i = 0; i < spot; i++){
if (!visit[i]){
ma = max(dfs(i,spot),ma);
}
}
printf("%d",ma);
}
```
### 機器人走棋盤(d092
#### `topological sort` `DAG`
有一個方格棋盤的每一個格子裡都標示了一個不同的整數，有一個機器人在此方格棋盤上行動，每一次只會移動到目前位置的上下左右四個相鄰格子其中之一。起點是數字最小的格子，每次移動則在可以移動位置中挑選數字最小的格子，但是走過的格子就不會再走，當無路可走的時候，機器人就會停下來。輸入方格棋盤中每個格子的數字，請模擬機器人走過的路徑，並輸出機器人走過的格子的數字總和。
輸入 : 輸入的第一行是兩個不超過 100 的正整數 m 與 n，代表是一個 m*n 的方格棋盤，
接下來有 m 行，每行 n 個數字，分別是方格棋盤由上而下，由左而右的數字。
方格內的數字皆為不超過 1e5 的非負整數，同一行數字之間以空白間隔。
輸出 : 機器人走過的格子中數字的總和。
```c++=
#include<bits/stdc++.h>
using namespace std;
int path[101][101];
int n,m,si,sj,mi;
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
int main()
{
scanf("%d%d",&n,&m);
mi = 100010;
memset(path,-1,sizeof(path));
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
scanf("%d",&path[i][j]);
if (path[i][j] < mi){
si = i,sj = j;
mi = path[i][j];
}
}
}
int total = 0;
while(1){
total += path[si][sj];
path[si][sj] = -1;
mi = 100010;
int ti = si,tj = sj;
for (int i = 0; i < 4; i++){
if (path[ti+dx[i]][tj+dy[i]] > 0 && path[ti+dx[i]][tj+dy[i]] < mi){
si = ti+dx[i],sj = tj+dy[i];
mi = path[si][sj];
}
}
if (mi > 100000) break;
}
printf("%d",total);
}
```
# zerojudge
## 圖論
### BFS
#### 最短距離(d453
輸入 : 輸入檔中有多筆測試資料。每筆測試資料第一行有一個正整數 N, （1 ≦ N ≦ 100），代表有N筆測試資料。
接下來，有N筆測試資料，每筆代表一個二維平面在此二維平面，請找出起點至終點最短路徑，輸入檔說明：每筆測試資料的第一行為6個整數 分別表示此二維平面的列數n 行數m (1≤n,m≤100) 起點(列和行)座標 終點(列和行)座標 第二行開始是一n*m二維陣列 其中"0"代表可以走的道路 "1"代表牆
輸出 : 對於每筆測資，輸出一行此筆資料的最短路徑，若無法到，則該行輸出1個字: 0。
```c++=
#include<bits/stdc++.h>
using namespace std;
int visit[110][110];
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(visit,-1,sizeof(visit));
int sx,sy,ex,ey,n,m;
scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&ex,&ey);
for (int i = 1; i <= n; i++){
char s[m];
scanf("%s",s);
for (int j = 1; j <= m; j++){
if (s[j-1] == '0') visit[i][j] = 0;
}
}
queue<pair<int,int>> q;
q.push({sx,sy});
visit[sx][sy] = 1;
while(!q.empty()){
int x,y;
x = q.front().first,y = q.front().second;
if (x == ex && y == ey) break;
q.pop();
for (int i = 0; i < 4; i++){
int nx = x+dx[i],ny = y+dy[i];
if (visit[nx][ny] == 0){
visit[nx][ny] = visit[x][y]+1;
q.push({nx,ny});
}
}
}
if (visit[ex][ey] == -1) printf("%d\n",0);
else printf("%d\n",visit[ex][ey]);
}
}
```
# TOI營隊
## DAY1
### sorting
stable_sort(排序如初線一樣元素則按原先排序)
insertion sort(插入排序:幫每個元素找到第一個大於或小於它的位置)
quick sort(最大和最小的交換以此類推)
#### APCS 2017-0304-4基地台
zerojudege:https://zerojudge.tw/ShowProblem?problemid=c575
```c++=
#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int> a;
bool check(int len){
int now = a[0]+len;
int t = k-1;
for (int i = 1; i < n; i++){
if (a[i] > now){
t--;
now = a[i]+len;
}
if (t < 0) return false;
}
return true;
}
bool cmp(int a,int b){return a < b;}
int main()
{
scanf("%d%d",&n,&k);
a.clear();
for (int i = 0; i < n; i++){
int num;
scanf("%d",&num);
a.push_back(num);
}
sort(a.begin(),a.end(),cmp);
int R = 0,L = a[n-1]-a[0];
while(L-1 > R){
int mid = (L+R)/2;
if (check(mid)) L = mid;
else R = mid;
}
printf("%d\n",L);
}
```
#### 線段覆蓋長度
zerojudge:https://zerojudge.tw/ShowProblem?problemid=b966
```c++=
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> x,pair<int,int> y){
if (x.first == y.first) return x.second<y.second;
else return x.first<y.first;
}
int main()
{
int n,s,t;
scanf("%d",&n);
vector<pair<int,int>> a(n);
for (int i = 0; i < n; i++){
scanf("%d%d",&s,&t);
a[i] = {s,t};
}
sort(a.begin(),a.end(),cmp);//按照線段開頭大小排序(小排到大)
s = a[0].first,t = a[0].second;
long long total = 0;
for (int i = 1; i < n; i++){計算線段覆蓋長
if (a[i].first > t){
total += t-s;
s = a[i].first,t = a[i].second;
}
else{
t = max(t,a[i].second);
}
}
total += t-s;
printf("%lld\n",total);
}
```
#### UVa-Where is the marble
zerojudge:https://zerojudge.tw/ShowProblem?problemid=e541
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1415
```c++=
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){return a<b;}
int main()
{
int n,q,CASE = 0;
while(scanf("%d%d",&n,&q)&&n!=0&&q!=0){
CASE++;
vector<int> a(n);
for (int i = 0; i < n; i++) scanf("%d",&a[i]);
sort(a.begin(),a.end(),cmp);
printf("CASE# %d:\n",CASE);
for (int i = 0; i < q; i++){
int tem;
scanf("%d",&tem);
auto it = lower_bound(a.begin(),a.end(),tem)-a.begin();
if (a[it] == tem) printf("%d found at %d\n",tem,it+1);
else printf("%d not found\n",tem);
}
}
}
```
#### UVa630-Anagrams (II)
zerojudge:https://zerojudge.tw/ShowProblem?problemid=e608
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=571
```c++=
#include<bits/stdc++.h>
using namespace std;
struct word{
string sor_s,or_s;
};
int main()
{
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<word> words(n);
string s,tem;
for (int i = 0; i < n; i++){
cin >> s;
tem = s;
sort(tem.begin(),tem.end());//將字串排序
words[i].sor_s = tem,words[i].or_s = s;
}
while(cin >> s && s!="END"){
cout << "Anagrams for: " << s << "\n";
int idx = 0;
tem = s;
sort(tem.begin(),tem.end());
for (int i = 0; i < n; i++){//檢查字串排序後是否相同
if (tem == words[i].sor_s){
idx ++;
cout << setw(3) << idx << ") " << words[i].or_s << "\n";
}
}
if (idx == 0) cout << "No anagrams for: " << s << "\n";
}
//if (t) cout << "\n";傳UVa要加這行
}
}
```
#### UVa10905-Children's Game
zerojudge:https://zerojudge.tw/ShowProblem?problemid=d385
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1846
```c++=
#include<bits/stdc++.h>
using namespace std;
bool cmp(string a ,string b){return a+b>b+a;}
int main()
{
int n;
while(cin >> n && n){
vector<string> s(n);
for (int i = 0; i < n; i++) cin >> s[i];
sort(s.begin(),s.end(),cmp);
for (int i = 0; i < n; i++) cout << s[i];
cout << "\n";
}
}
```
### stack
#### rails
zerojudge:https://zerojudge.tw/ShowProblem?problemid=c123
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(cin >> n && n){
while(1){
int idx = 1,now;
bool flag = true;
stack<int> train;
while(!train.empty()) train.pop();
int i;
for (i = 0; i < n; i++){
cin >> now;
if (now == 0) break;
if (!train.empty()&&train.top() == now){
train.pop();
}
else if (now >= idx){
while(idx < now) train.push(idx++);
idx ++;
}
else{
flag = false;
}
}
if (now == 0) break;
if (flag) cout << "Yes\n";
else cout << "No\n";
}
cout << "\n";
}
}
```
#### 四則運算
zerojudge:https://zerojudge.tw/ShowProblem?problemid=a664
:::info
運用運算子的優先順序
:::
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--){
string s;
cin >> s;
int idx = 0;
stack<long long> ans;
stack<char> oper;
for (int i = 0; i < s.size(); i++){
char c = s[i];
if (c == '(' || c == '/' || c == '+' || c == '-' || c == '*'){
oper.push(c);
idx = 0;
}
else if (c == ')'){
long long a = ans.top();
ans.pop();
long long b = ans.top();
ans.pop();
char op = oper.top();
oper.pop();
oper.pop();
if (op == '/') ans.push(b/a);
//一定要後項除前項因為stack是先進後出所以被除數會是第二個數字
if (op == '+') ans.push(b+a);
if (op == '-') ans.push(b-a);
if (op == '*') ans.push(b*a);
idx = 0;
}
else {//紀錄數字用
if (idx == 0){
ans.push(c-'0');
idx++;
}
else{//如果連續出現兩個字元為數字那麼就要重新處理
long long a = ans.top();
ans.pop();
a*=10;
a+= c-'0';
idx++;
ans.push(a);
}
}
}
cout << ans.top() << "\n";
ans.pop();
}
}
```
#### Parentheses Balance
zerojudge:https://zerojudge.tw/ShowProblem?problemid=b304
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=614&mosmsg=Submission+received+with+ID+29202897
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
cin.ignore();
while(t--){
string s;
getline(cin,s);
//一定要用getline因為有空字串，如果用一般的讀入空字串會被忽略
stack<char> stk;
bool flag = true;
while(!stk.empty()) stk.pop();
for (int i = 0; i < s.size(); i++){
if (s[i] == '(' || s[i] == '[') stk.push(s[i]);
else if (s[i] == ')'){
if (!stk.empty() && stk.top() == '(')stk.pop();
else{
flag = false;
break;
}
}
else if (s[i] == ']'){
if (!stk.empty() && stk.top() == '[')stk.pop();
else{
flag = false;
break;
}
}
}
if (flag && stk.empty()) cout << "Yes\n";
else cout << "No\n";
}
}
```
#### apcs 物品堆疊 (Stacking)
zerojudge:https://zerojudge.tw/ShowProblem?problemid=c471
```c++=
#include<bits/stdc++.h>
using namespace std;
struct item{
int w,f;
};
item a[100010];
bool cmp(item i,item j){
return (double)i.f/i.w > (double)j.f/j.w;
}
int main()
{
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++) scanf("%d",&a[i].w);
for (int i = 0; i < n; i++) scanf("%d",&a[i].f);
sort(a,a+n,cmp);
long long weight = 0,ans = 0;
for (int i = 0; i < n; i++){
ans += weight * a[i].f;
weight += a[i].w;
}
printf("%lld",ans);
}
```
### queue
#### UVa540-Team Queue
zerojudge:https://zerojudge.tw/ShowProblem?problemid=e564
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=481
```c=
#include<bits/stdc++.h>
using namespace std;
int id[1000000];//紀錄元素所在的q的編碼
int main()
{
int t,CASE = 0;
while(scanf("%d",&t)&&t){
CASE++;
memset(id,-1,sizeof(id));
for (int i = 0; i<= t; i++){
while(!q[i].empty()) q[i].pop();
}
for (int i = 0; i < t; i++){
int n,tem;
scanf("%d",&n);
for (int j = 0; j < n; j++){
scanf("%d",&tem);
id[tem] = i;
}
}
queue<int> q[t+1];//紀錄每個queue的元素
queue<int> team;//紀錄每個queue在team的順序
char s[7];
printf("Scenario #%d\n",CASE);
while(scanf("%s",s)&&s[0]!='S'){
if (s[0] == 'E'){//ENQUEUE
int x;
scanf("%d",&x);
if (id[x]==-1)id[x] = t;
if (q[id[x]].empty())team.push(id[x]);
q[id[x]].push(x);
}
else if (s[0] == 'D'){//DEQUEUE
int now = team.front();
printf("%d\n",q[now].front());
q[now].pop();
if(q[now].empty())team.pop();
}
}
//printf("\n")送UVa記得加這行
}
}
```
### Greedy
#### UVa10954-add all
zerojudge:https://zerojudge.tw/ShowProblem?problemid=d221
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1895
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n) && n){
priority_queue<int> pq;
while(!pq.empty()) pq.pop();
for (int i = 0; i < n; i++){
int num;
scanf("%d",&num);
pq.push(-num);
}
long long total = 0;
for (int i = 1; i < n; i++){
int a = pq.top();
pq.pop();
int b = pq.top();
pq.pop();
total += (a+b);
pq.push(a+b);
}
printf("%lld\n",-total);
}
}
```
### data structure
#### UVa353-Pesky Palindromes
zerojudge:https://zerojudge.tw/ShowProblem?problemid=e619
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=289
```c++=
#include<bits/stdc++.h>
using namespace std;
string s;
bool check(int L,int R){
for (; R > L; R--,L++){
if (s[R]!=s[L])return false;
}
return true;
}
int main()
{
while(cin >> s){
set<string> ans;
ans.clear();
for (int i = 0; i < s.size(); i++){//窮舉檢查有多少回文
for (int j = i; j < s.size(); j++){
if(check(i,j)){
string tem = s.substr(i,j-i+1);
ans.insert(tem);//避免有重複地所以用set紀錄(set會自動過濾重複單字)
}
}
}
cout << "The string '" << s << "' contains " << ans.size() << " palindromes.\n";
}
}
```
#### UVa136-Ugly Number
zerojudge:https://zerojudge.tw/ShowProblem?problemid=d129
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
priority_queue<long long,vector<long long>,greater<long long>> pq;
pq.push(1);
long long x;
for (int i = 0; i < 1500; i++){
//所有的醜數都是任意醜數的2,3,5倍，所以每次取最小的醜數乘上2,3,5也會是醜數
x = pq.top();
while(!pq.empty() && pq.top() == x) pq.pop();
pq.push(x*2);
pq.push(x*3);
pq.push(x*5);
}
cout << "The 1500'th ugly number is " << x << ".\n";
}
```
#### UVa1203-Argus
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3644
```c++=
#include<bits/stdc++.h>
using namespace std;
struct query{
int Q_num,period;
long long time;
};
bool operator < (query a,query b){
if (a.time == b.time) return a.Q_num>b.Q_num;
return a.time>b.time;
}
int main()
{
string s;
priority_queue<query> pq;
while(cin >> s && s== "Register"){
int a,b;
cin >> a >> b;
query n;
n.Q_num = a,n.period = n.time = b;
pq.push(n);
}
int n;
cin >> n;
for (int i = 0; i < n; i++){
query tem = pq.top();
pq.pop();
cout << tem.Q_num << "\n";
tem.time += tem.period;
pq.push(tem);
}
}
```
#### UVa230-Borrower
zerojudge:https://zerojudge.tw/ShowProblem?problemid=e862
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=166
```c++=
#include<bits/stdc++.h>
using namespace std;
struct item{
string title,author;
int statu = 0;//0架上/1借走/2還回未排序
};
bool cmp(item a,item b){
if(a.author == b.author) return a.title<b.title;
return a.author<b.author;
}
int main()
{
vector<item> books;
char c;
string a,b;
while(cin >> c && c=='"'){
getline(cin,a,'"');
cin >> b;
cin.ignore();
getline(cin,b);
item tem;
tem.title = a,tem.author = b;
books.push_back(tem);
}
cin >> a;
sort(books.begin(),books.end(),cmp);
map<string,int> m;
for (int i = 0; i < books.size(); i++){
m[books[i].title] = i;
}
while(cin >> a && a!="END"){
if (a == "BORROW"){
cin >> c;
getline(cin,b,'"');
books[m[b]].statu = 1;
}
if (a == "RETURN"){
cin >> c;
getline(cin,b,'"');
books[m[b]].statu = 2;
}
if (a == "SHELVE"){
int prev = -1;
for (int i = 0; i < books.size(); i++){
if (books[i].statu == 0) prev = i;
if (books[i].statu == 2){
cout << "Put \"" << books[i].title << "\" ";
if (prev == -1) cout << "first\n";
else cout << "after \"" << books[prev].title << "\"\n";
prev = i;
books[i].statu = 0;
}
}
cout << "END\n";
}
}
}
```
#### UVa441-Lotto
zerojudge:https://zerojudge.tw/ShowProblem?problemid=c074
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=382&mosmsg=Submission+received+with+ID+29223903
```c++=
#include<bits/stdc++.h>
using namespace std;
int A[12], s[6], n;
void dfs(int now, int dep) {
s[dep-1]=A[now];
if(dep==6) {
for(int i = 0; i < 6; i++) {
cout << s[i] << " \n"[i==5];
}
}
else {
for (int i = now+1; i < n;i++)dfs(i,dep+1);
}
}
int main() {
bool flag = 0;
while(cin >> n) {
if(flag && n != 0)cout << '\n';
else flag = 1;
for(int i = 0; i < n; i++)cin >> A[i];
for (int i = 0; i <= n-6; i++)dfs(i,1);
}
}
```
### Union and Find
#### UVa793-Network Connections
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=734&mosmsg=Submission+received+with+ID+29224681
```c=
#include<bits/stdc++.h>
using namespace std;
int root[1000];
int FIND(int a){
if (root[a]<0) return a;
return root[a] = FIND(root[a]);
}
void UNION(int a,int b){
int ro_a = FIND(a),ro_b = FIND(b);
int tem = root[ro_a]+root[ro_b];
if (ro_a == ro_b) return;
if (ro_a < ro_b){
root[ro_b] = ro_a;
root[ro_a] = tem;
}
else{
root[ro_a] = ro_b;
root[ro_b] = tem;
}
}
int main()
{
int t;
cin >> t;
cin.ignore();
while(t--){
int n,a,b,pass = 0,fail = 0;
cin >> n;
cin.ignore();
string s;
char c;
memset(root,-1,sizeof(root));
while(getline(cin,s)){
if (s == "") break;
sscanf(s.c_str(),"%c %d %d",&c,&a,&b);
if (c == 'c'){
UNION(a,b);
}
else{
if (FIND(a) == FIND(b)) pass++;
else fail++;
}
}
cout << pass << "," << fail << "\n";
if (t) cout << "\n";
}
}
```
#### UVa10583 - Ubiquitous Religions
zerojudge:https://zerojudge.tw/ShowProblem?problemid=d813
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=1524&mosmsg=Submission+received+with+ID+29236011
```c=
#include<bits/stdc++.h>
using namespace std;
int FIND(vector<int> &a,int idx){
if (a[idx] < 0) return idx;
return a[idx] = FIND(a,a[idx]);
}
void UNION(vector<int> &a,int b,int c){
int ro_b = FIND(a,b),ro_c = FIND(a,c);
if (ro_b == ro_c)return;
int tem = a[ro_b] + a[ro_c];
if (a[ro_b] > a[ro_c]){
a[ro_b] = ro_c;
a[ro_c] = tem;
}
else{
a[ro_c] = ro_b;
a[ro_b] = tem;
}
return;
}
int main()
{
int n,m,t = 0;
while(cin >> n >> m && n && m){
t++;
vector<int> root(n+1);
fill(root.begin(),root.end(),-1);
for (int i = 0; i < m; i++){
int a,b;
cin >> a >> b;
UNION(root,a,b);
}
int total = 0;
for (int i = 1; i <= n; i++){
if (root[i] < 0) total ++;
}
cout << "Case " << t << ": " << total << "\n";
}
}
```
### DFS&BFS
#### UVa722-Lakers
zerojudge:https://zerojudge.tw/ShowProblem?problemid=e550
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=663&mosmsg=Submission+received+with+ID+29226517
```c++=
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {1,0,-1,0},dy[4] = {0,-1,0,1};
struct pos{
int x,y;
};
int main()
{
int t,x,y;
cin >> t;
while(t--){
cin >> x >> y;
x--,y--;
cin.ignore();
string s;
vector<string> v;
v.clear();
int n,m;
while(getline(cin,s) && s !=""){
v.push_back(s);
n = s.size();
}
m = v.size();
queue<pos> q;
pos tem;
tem.x = x,tem.y = y;
q.push(tem);
int total = 0;
while(!q.empty()){
tem = q.front();
x = tem.x,y = tem.y;
q.pop();
if (v[x][y] == '1')continue;
total ++;
v[x][y] = '1';
for (int i = 0; i < 4; i++){
if (x+dx[i] < 0 || x+dx[i] >= m || y+dy[i] < 0 || y+dy[i] >= n) continue;
if (v[x+dx[i]][y+dy[i]] == '0'){
tem.x = x+dx[i],tem.y = y+dy[i];
q.push(tem);
}
}
}
cout << total << "\n";
if (t) cout << "\n";
}
}
```
#### UVa10959-The Party, Part1
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=1900&mosmsg=Submission+received+with+ID+29233411
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,p,t;
cin >> t;
while(t--){
cin >> n >> p;
vector<int> deg(n);
fill(deg.begin(),deg.begin()+n,0x3f3f3f);
vector<int> path[n+1];
for (int i = 0; i < p; i++){
int a,b;
cin >> a >> b;
path[a].push_back(b);
path[b].push_back(a);
}
deg[0] = 0;
vector<int> visit(n);
fill(visit.begin(),visit.begin()+n,0);
queue<int> q;
q.push(0);
while(!q.empty()){
int now = q.front();
q.pop();
if (visit[now])continue;
visit[now] = 1;
for (auto i:path[now]){
if (!visit[i]){
q.push(i);
}
deg[i] = min(deg[i],deg[now]+1);
}
}
for (int i = 1; i < n; i++) cout << deg[i] << "\n";
if (t) cout << "\n";
}
}
```
### Topological sort
### Tree
#### apcs 樹狀圖分析 (Tree Analyses)
zerojudge:https://zerojudge.tw/ShowProblem?problemid=c463
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,child;
cin >> n;
vector<int> deg(n+1),p(n+1),h(n+1);
queue<int> q;
fill(h.begin(),h.end(),0);
fill(p.begin(),p.end(),0);
for (int i = 1; i <= n; i++){
cin >> deg[i];
if (deg[i] == 0) q.push(i);
else{
for (int j = 0; j < deg[i]; j++){
cin >> child;
p[child] = i;
}
}
}
long long ans = 0;
int root,parent;
while(!q.empty()){
child = q.front();
q.pop();
ans += h[child];
parent = p[child];
if (parent == 0){
root = child;
break;
}
h[parent] = max(h[parent],h[child]+1);
deg[parent]--;
if (deg[parent] == 0) q.push(parent);
}
cout << root << "\n" << ans << "\n";
}
```
### DP
#### UVa10405-Longest Common Subsequence
zerojudge:https://zerojudge.tw/ShowProblem?problemid=c001
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=1346&mosmsg=Submission+received+with+ID+29242093
```c=
#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
int main()
{
string s1,s2;
while(getline(cin,s1)){
getline(cin,s2);
memset(dp,0,sizeof(dp));
for (int i = 0; i < s1.size(); i++){
for (int j = 0; j < s2.size(); j++){
if (s1[i] == s2[j]) dp[i+1][j+1] = dp[i][j]+1;
else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
}
}
cout << dp[s1.size()][s2.size()] << "\n";
}
}
```
#### UVa357-Let Me Count The Ways
zerojudge:https://zerojudge.tw/ShowProblem?problemid=d133
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=293&mosmsg=Submission+received+with+ID+29243981
```c++=
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long coin[5] = {1,5,10,25,50};
long long dp[30010];
memset(dp,0,sizeof(dp));
dp[0] = 1;
for (int i = 0; i < 5; i++){
for (int j = coin[i]; j < 30001; j++){
dp[j] += dp[j-coin[i]];
}
}
int n;
while(scanf("%d",&n) != EOF){
if (dp[n] == 1) printf("There is only 1 way to produce %d cents change.\n",n);
else printf("There are %lld ways to produce %d cents change.\n",dp[n],n);
}
}
```
#### UVa10130 - SuperSale
zerojudge:https://zerojudge.tw/ShowProblem?problemid=f440
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=1071&mosmsg=Submission+received+with+ID+29252128
```c++=
#include<bits/stdc++.h>
using namespace std;
struct thing{
int p,w;
};
int main()
{
int t,n,price,weight,g;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
vector<thing> item(n);
for (int i = 0; i < n; i++){
scanf("%d%d",&price,&weight);
item[i].p = price,item[i].w = weight;
}
scanf("%d",&g);
int task;
vector<int> dp(31);
fill(dp.begin(),dp.end(),0);
for (int i = 0; i < n; i++){
for (int j = 30; j >= item[i].w; j--){
dp[j] = max(dp[j],dp[j-item[i].w]+item[i].p);
}
}
int total = 0;
for (int i = 0; i < g; i++){
scanf("%d",&task);
total += dp[task];
}
printf("%d\n",total);
}
}
```
#### UVa469-Combinations
zerojudge:https://zerojudge.tw/ShowProblem?problemid=d134
UVa:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=305&mosmsg=Submission+received+with+ID+29254721
```c++=
#include<bits/stdc++.h>
using namespace std;
unsigned long long dp[110][110];
int main()
{
memset(dp,0,sizeof(dp));
for (int i = 0; i <= 100; i++){
for (int j = 0; j <= i; j++){
if (i == j-1 || j == 0) dp[i][j] = 1;
else dp[i][j] = dp[i-1][j]+dp[i-1][j-1];
}
}
int m,n;
while(cin>> n >> m){
if (!n & !m) break;
cout << n<< " things taken "<< m <<" at a time is "<<dp[n][m]<<" exactly.\n";
}
}
```
Sign in with Wallet
Connect another wallet