遞迴

函數呼叫函數

重點

要定義清楚對於函數的定義，像是：
「f(x,y) 代表 x 的 y 次方」

習題

例題 P-1-1. 合成函數(1)

令 f(x)=2x-1, g(x,y)=x+2y-3。本題要計算一個合成函數的值，例如 f(g(f(1),3))=f(g(1,3))=f(4)=7。

Time limit: 1 秒

輸入格式：輸入一行，長度不超過 1000，它是一個 f 與 g 的合成函數，但所有的括弧與逗號都換成空白。輸入的整數絕對值皆不超過 1000。

輸出：輸出函數值。最後答案與運算過程不會超過正負 10 億的區間。

範例輸入： f g f 1 3

範例輸出： 7

利用遞迴式處理
1. 輸入
2. 取後面值

#include<bits/stdc++.h>
using namespace std;

#define N 10000
istream& ss=cin;
//stringstream ss("f g f 1 3");

int a(){
    char s[N];
    ss>>s;
    if(s[0]=='f'){
        return 2*a()-1;
    }
    else if(s[0]=='g'){
        return a()+2*a()-3;
    }
    else{
        return atoi(s);
    }
}
int main(){
    cout<<a();
}

習題 Q-1-2. 合成函數(2) (APCS201902)

令 f(x)=2x–3；g(x,y)=2x+y–7；h(x,y,z)=3x–2y+z。本題要計算一個合成函數的值，例如 h(f(5),g(3,4),3)=h(7,3,3)=18。

Time limit: 1 秒

輸入格式：輸入一行，長度不超過 1000，它是一個 f, g, 與 h 的合成函數，但所有的括弧與逗號都換成空白。輸入的整數絕對值皆不超過 1000。

輸出：輸出函數值。最後答案與運算過程不會超過正負 10 億的區間。

範例輸入： h f 5 g 3 4 3

範例輸出： 18

#include <bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 1001

istream & ss =cin;
//stringstream ss("h f 5 g 3 4 3");


int a(){
    char s[N];
    ss>>s;
    if(s[0]=='f'){
        return 2*a()-3;
    }
    if(s[0]=='g'){
        return 2*a()+a()-7;
    }
    if(s[0]=='h'){
        return 3*a()-2*a()+a();
    }
    return atoi(s);
}



int main(){
    cout<<a();
}

例題 P-1-3. 棍子中點切割

有一台切割棍子的機器，每次將一段棍子會送入此台機器時，機器會偵測棍子上標示的可切割點，然後計算出最接近中點的切割點，並於此切割點將棍子切割成兩段，切割後的每一段棍子都會被繼續送入機器進行切割，直到每一段棍子都沒有切割點為止。請注意，如果最接近中點的切割點有二，則會選擇座標較小的切割點。每一段棍子的切割成本是該段棍子的長度，輸入一根長度 L 的棍子上面 N 個切割點位置的座標，請計算出切割總成本。

Time limit: 1 秒

輸入格式：第一行有兩個正整數 N 與 L。第二行有 N 個正整數，依序代表由小到大的切割點座標 p[1]~p[N]，數字間以空白隔開，座標的標示的方式是以棍子左端為 0，而右端為 L。N  5e4，L< 1e9。

輸出：切割總成本點。

範例輸入：
4 10
1 2 4 6

範例輸出： 22

範例說明：第一次會切割在座標 4 的位置，切成兩段 [0, 4], [4, 10]，成本 10； [0, 4] 切成 [0, 2] 與 [2, 4]，成本 4； [4, 10] 切成 [4, 6] 與 [6, 10]，成本 6； [0, 2] 切成 [0, 1] 與 [1, 2]；成本 2；總成本 10+4+6+2 = 22

可以建一個陣列

v	v[0]	v[1]	v[2]	v[3]	v[4]	v[5]
value	0	1	2	4	6	10

線性搜尋

#include<bits/stdc++.h>
using namespace std;
#define N 50001
#define nn "\n"

istream& ss=cin;
//stringstream ss("4 10 \
1 2 4 6");

long long v[N];
long long cut(long long a,long long b){
    long long len=v[b]-v[a];
    long long m=(v[b]+v[a])/2;
    if(b-a<=1){
        return 0;
    }
    long long w=a;
    while(v[w]<m){
        w++;
    }
    if(v[w-1]-v[a]>=v[b]-v[w]){
        w--;
    }
    return len+cut(a,w)+cut(w,b);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n,m;
    ss>>n>>m;
    v[0]=0;
    v[n+1]=m;
    for(long long i=1;i<=n;i++){
        ss>>v[i];
    }
    cout<<cut(0,n+1);
}

跳躍二分搜

#include<bits/stdc++.h>
using namespace std;
#define N 50001
#define nn "\n"

istream& ss=cin;
//stringstream ss("4 10 \
1 2 4 6");

long long v[N];
long long cut(long long a,long long b){
    if(b-a<=1){
        return 0;
    }
    long long m=(v[b]+v[a])/2;
    long long w=a;

    //jump-----------------------------------------------
    for (int jump=(b-a)/2;jump>0; jump>>=1) {
        while (w+jump<b && v[w+jump]<m){
            w+=jump;
        }
    }
    if (v[w]-v[a] < v[b]-v[w+1]){
        w++;
    }
    //jump-----------------------------------------------
    

    return v[b]-v[a] +cut(a,w)+cut(w,b);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n,m;
    ss>>n>>m;
    v[0]=0;
    v[n+1]=m;
    for(long long i=1;i<=n;i++){
        ss>>v[i];
    }
    cout<<cut(0,n+1);
}

lower_bound

#include<bits/stdc++.h>
using namespace std;
#define N 50001
#define nn "\n"

istream& ss=cin;
//stringstream ss("4 10 \
1 2 4 6");

long long v[N];


long long cut(long long a,long long b){
    long long len=v[b]-v[a];
    long long k=(v[b]+v[a])/2;
    if(b-a<=1){
        return 0;
    }

    //lower_bound---------------------------------------
    long long m=lower_bound(v+a, v+b,k)-v;
    if(v[m-1]-v[a]>=v[b]-v[m]){
        m--;
    }
    //lower_bound---------------------------------------

    return len+cut(a,m)+cut(m,b);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n,m;
    ss>>n>>m;
    v[0]=0;
    v[n+1]=m;
    for(long long i=1;i<=n;i++){
        ss>>v[i];
    }
    cout<<cut(0,n+1);
}

習題Q-1-4. 支點切割 (APCS201802) (@@)

輸入一個大小為 N 的一維整數陣列 p[]，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個：子陣列範圍小於 3 或切到給定的層級 K 就不再切割。而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，但不可以是兩端點，也就是說，若區段的範圍是[s,t]，則要找出切點 m屬於[s+1,t-1]，使得 \(\left| \sum_{i=s}^{t} p[i] \times (i - m) \right|\) 越小越好，如果有兩個最佳切點，則選擇編號較小的。所謂切割層級的限制，第一次切以第一層計算。

Time limit: 1 秒

輸入格式：第一行有兩個正整數 N 與 K。第二行有 N 個正整數，代表陣列內容 p[1] ~ p[N]，數字間以空白隔開，總和不超過 109。N <= 50000，切割層級限制 K<30。

輸出：所有切點的 p[ ]值總和。

範例一輸入：
7 3
2 4 1 3 7 6 9

範例一輸出：
11

範例二輸入：
5 1
1 2 3 4 100

範例二輸出：
4

範例一說明：第一層切在 7，切成第二層的[2,4,1,3]與[6,9]。左邊[2,4,1,3] 切在 4 與 1 都是最佳，選擇 4 來切，切成[2]與[1,3]，右邊[6,9]不到 3 個就不切了。第三層都不到 3 個，所以終止。總計切兩個位置 7+4=11。範例二說明：

第一層切在 4(注意切點不可在端點)，切出[1,2,3]與[100]，因為 K=1，所以不再切。提示：與 P_1_3 類似，只是找切割點的定義不同，終端條件多了一個切割層級。

暴力解，TLE

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 50000
istream & ss=cin;
//stringstream ss("7 3 \
2 4 1 3 7 6 9");


long long v[N];
long long n,k;

long long cut(long long x,long long y,long long z){
      
    //cout<<v[x]<<" "<<v[y]<<" "<<z<<nn;
    long long len=y-x;

    if(y-x<=1){
        return 0;
    }
  
    if(len<3){
        return 0;
    }
    if(k==z){
        return 0;
    }

    long long sum=100000000000;
    long long sub_value=-1;

    for(long long m=x+1;m<=y-1;m++){
        //cout<<"m:"<<m<<nn;
        long long sub_sum=0;
        for(long long i=x;i<=y;i++){
            sub_sum+=abs(v[i]*(i-m));
        }
        if(sub_sum<sum){
            //cout<<"m:"<<m<<" sub_sum:"<<sub_sum<<nn;
            sum=sub_sum;
            sub_value=m;
            //cout<<"M:"<<m<<nn;
        }
    }

    //cout<<nn<<sub_value<<nn;


    return v[sub_value] + cut(x,sub_value-1,z+1) + cut(sub_value+1,y,z+1);
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);


    
    ss>>n>>k;

    for(long long i=0;i<n;i++){
        ss>>v[i];
    }

    cout<<cut(0,n-1,0);

}

習題 Q-1-5. 二維黑白影像編碼 (APCS201810)

ZJ網址(題目較詳細)

假設 n 是 2 的冪次，也就是存在某個非負整數 k 使得 n = 2k 。將一個 n*n 的黑白影像以下列遞迴方式編碼：如果每一格像素都是白色，我們用 0 來表示；如果每一格像素都是黑色，我們用 1 來表示；否則，並非每一格像素都同色，先將影像均等劃分為四個邊長為 n/2 的小正方形後，然後表示如下：先寫下 2，之後依續接上左上、右上、左下、右下四塊的編碼。輸入編碼字串 S 以及影像尺寸 n，請計算原始影像中有多少個像素是 1。

Time limit: 1 秒

輸入格式：第一行是影像的編碼 S，字串長度小於 1,100,000。第二行為正整數 n， 1 <= n <= 1024，中 n 必為 2 的冪次。

輸出格式：輸出有多少個像素是 1。

範例輸入：
2020020100010
8

範例輸出：
17

這題想法和例題 P-1-1. 合成函數(1)差不多，直接一個字一個字處裡，找到2就往後找4個數字

#include<bits/stdc++.h>
using namespace std;
#define N 11000000

istream & ss=cin;
//stringstream ss("2020020100010 \
//8");
//stringstream ss("2200101020110 \
//4");

char s[N];
int n,ans;
int i=-1;

int a(int len){
    i++;
    if(s[i]=='2'){
        return a(len/2) + a(len/2) + a(len/2) + a(len/2);
    }
    if(s[i]=='1'){
        return len*len;
    }
    return 0;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ss>>s;
    ss>>n;
    cout<<a(n);
}

以遞迴窮舉暴搜

例題 P-2-11. 最接近的區間和 (*)

假設陣列 A[1..n]中存放著某些整數，另外給了一個整數 K，請計算哪一個連續區段的和最接近 K 而不超過 K。 (這個問題有更有效率的解，在此我們先說明窮舉的解法。)

範例輸入 1
5 10
5 -5 8 -3 4

範例輸出 1
9

範例輸入 2
1 1
-1

範例輸出 2
0

暴力解「NA (score:12%)」

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 100001
#define int  long long
int v[N];
signed main(){
    int n,m,ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            int sum=0;
            for(int k=i;k<=j;k++){
                sum+=v[k];
            }
            if(sum>ans && sum<=m){
                ans=sum;
            }
        }
    }
    cout<<ans;
}

暴力解 + 前綴「NA (score:37%)

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 100001
int v[N];
int main(){
    int n,m,ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }

    //前綴和-------------------------------
    for(int i=1;i<n;i++){
        v[i]=v[i-1]+v[i];
    }
    //前綴和-------------------------------

    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            int sum=v[j]-v[i];
            if(sum>ans && sum<=m){
                ans=sum;
            }
        }
    }
    cout<<ans;
}

前綴和、二分搜 AC

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 100011
#define int  long long
//---------------------------



//---------------------------main
#undef int
int main(){
#define int long long
    ios::sync_with_stdio(0);
    cin.tie(0);
//---------------------------main

    //istringstream cin("5 10 \
5 -5 8 -3 4");

    set<int>s{0};
    int n,k,ans=LONG_LONG_MIN;
    cin>>n>>k;
    int p=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        p+=x;
        auto it=s.lower_bound(p-k);
        if(it!=s.end()){
            ans=max(ans,p-*it);
        }
        s.insert(p);
    }
    cout<<ans;
}

例題 P-1-7. 子集合乘積 -

輸入 n 個正整數，請計算其中有多少組合的相乘積除以 P 的餘數為 1，每個數字可以選取或不選取但不可重複選，輸入的數字可能重複。P=10009，0

範例輸入 #1
3
1 1 2

範例輸出 #1
3

位元窮舉「NA (score:80%)(TLE)」

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 100001
#define P 10009

int v[N];

int main(){
    int n,ans=0;
    cin>>n;

    for(int i=0;i<n;i++){
        cin>>v[i];
    }

    for(int i=1;i<(1<<n);i++){
        int pow=1;
        for(int j=0;j<n;j++){
            if(i & 1<<j){
                pow*=v[j];
                pow%=P;
            }
        }
        if(pow==1){
            ans++;
        }
    }
    cout<<ans;
}

寫遞迴的話就是直接想像樹狀圖，每一個數字有兩個選擇：選、不選
所以是：

前一個數字
|
|------------選下一個數字(加入計算)
|
|
|------------不選下一個數字(不加入計算)

遞迴「AC (1/10 s, 304KB)」

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 100001
#define P 10009

int v[N],ans=0;
int n;


int a(int i,int p){
    if(i>=n){//跑完全部
        if(p==1){
            ans++;
        }
        return 0;
    }
    a(i+1,(v[i]*p)%P);
    a(i+1,p);
    return 0;
}


int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    a(0,1);
    cout<<ans-1;//減去空字串
}

習題 Q-1-8. 子集合的和 (APCS201810, subtask)

輸入 n 個正整數，請計算各種組合中，其和最接近 P 但不超過 P 的和是多少。每個元素可以選取或不選取但不可重複選，輸入的數字可能重複。P<=1000000009，0 < n < 26。

Time limit: 1 秒

輸入格式：第一行是 n 與 P，第二行是 n 個可挑選的正整數，大小不會超過 P，同行數字以空白間隔。

輸出格式：最接近 P 但不超過 P 的和。

範例輸入：
5 17
5 5 8 3 10

範例輸出：
16

dp(MLE (64MB))

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
//#define int long long


//#undef int
int main(){
//#define int long long


    //istringstream cin("5 17 \
5 5 8 3 10");
    int n,k,ans=0;
    cin>>n>>k;


    int v[30];
    for(int i=0;i<n;i++){
        cin>>v[i];
    }

    //int dp[100000100]={0};//總大小為i的方法數

    unordered_map<int,int>mp;

    for(int i=0;i<n;i++){//商品數v[i]為商品價錢
        for(int j=k;j>=0;j--){//17~0
            if(j-v[i]>=0){
                mp[j]=max(mp[j],mp[j-v[i]]+v[i]);
            }
        }
    }
    cout<<mp[k];
}

bit解 O(2^n\*m\) WA(60%)

#include <bits/stdc++.h>
using namespace std;

#define N 100

int v[N];

int main(){
    int n,m,ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }



    for(int i=0;i<(1<<n);i++){
        int sum=0;
        for(int j=0;j<n;j++){
            if(i & (1<<j)){
                sum+=v[j];
            }
            if(sum>ans && sum<=m){
                ans=sum;
            }
        }
    }
    
    cout<<ans;
}

遞迴解 O(2^n) AC

#include <bits/stdc++.h>
using namespace std;

#define N 100

int v[N];

int n,m,ans=0;

int a(int i,int sum){
    if(i>=n){
        if(sum>ans && sum<m){
            ans=sum;
        }
        return 0;
    }
    a(i+1,sum+v[i]);
    a(i+1,sum);

    return 0;
}



int main(){

    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    a(0,0);
    cout<<ans;
}

n皇后問題

遞迴

#include<bits/stdc++.h>
using namespace std;


int col, uldr, dlur; // 將 int 用二進位的角度去維護直線、斜線上有沒有皇后
int queen(int r, int n)
{
    if(r == 0) return 1;
    int sum = 0;
    for(int c = 1; c <= n; c++)
    {
        if((col>>c)&1 || (uldr>>(r+c))&1 || (dlur>>(r-c+n))&1) continue;
        col |= (1<<c), uldr |= (1<<(r+c)), dlur |= (1<<(r-c+n));
        sum += queen(r-1, n);
        col &= ~(1<<c), uldr &= ~(1<<(r+c)), dlur &= ~(1<<(r-c+n));
    }
    return sum;
}

int main(){


    stringstream cin("5");



    int n; cin >> n;
    col = uldr = dlur = 0;
    cout << queen(n, n) << endl;
}