# 簡介
# 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。
```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);//找出對應的序列
}
}
```
# zerojudge
Sign in with Wallet
Connect another wallet