# SCIST S4 演算法課程_遞迴

:::info
時間：03/17 9:00 ~ 18:00
主題：遞迴
直播連結：https://www.youtube.com/watch?v=3LS6TaUL63M
:::

## 課程內容
- 遞迴
- 尋找相似子結構
- Top-down
- 快速冪
- 講義連結：https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FrJpY0i7PS
- 簡報連結：https://slides.com/sa072686/scist240303_basicdatastructure/fullscreen

# 題解

[TOC]

## [UVa 10696](http://domen111.github.io/UVa-Easy-Viewer/?10696)

撰寫者：fishhh

遞迴的入門題，根據題目的意思以遞迴的方式呈現。

:::spoiler

#include<iostream>
using namespace std;
int f(int n){
	if(n>=101){
		return n-10;
	}
	else{
		return f(f(n+11));
	}
}
int main(){
	int n;
	while(cin>>n){
		if(n==0){
			return 0;
		}
		printf("f91(%d) = %d\n",n,f(n));
	}
}

:::

## [AtCoder typical90_bq](https://hackmd.io/@sa072686/AtCoder_typical90_bq)

撰寫者：Eason

題目可以理解為：相鄰一格或兩格皆不可同色，求塗滿 $n$ 格方塊的方法數。

~~根據大家應該都學過的排列組合~~，我們將排好的方塊由左而右上色，第一格有 $k$ 種選擇，第二格因為要扣除第一格用過的顏色，所以剩下 $k-1$ 種選擇，第三格要扣除前面兩格用過的顏色，所以剩下 $k-2$ 種選擇，而後每一格都跟第三格一樣，所以都是 $k-2$ 種選擇，根據乘法原理，我們要把所有的選擇數相乘，總方法數就是：
$$
k \times (k-1) \times (k-2)^{n-2}
$$
因為這題的 $n$ 超大，所以次方的部分要用快速冪來求。

:::spoiler code

$$
solve(n)=
\begin{cases}
1 & n=0\\
k-2 & n=1\\
(solve({\frac{n}{2}}))^2 \times (k-2) & \text{n is odd}\\
(solve({\frac{n}{2}}))^2 & \text{n is even}
\end{cases}
$$

#include<bits/stdc++.h>
#define ll long long
#define weakson ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

ll n, k;
ll ans;
const ll MOD = 1e9+7;

ll solve(ll x){
    if (x == 0) return 1;
    else if (x == 1) return k - 2;
    else{
        ll tmp = solve (x / 2);
        tmp *= tmp;
        tmp %= MOD;
        if (x & 1){
            tmp *= k - 2;
            tmp %= MOD;
            return tmp;
        }
        else{
            return tmp;
        }
    }
}

int main(){
    weakson;

    cin >> n >> k;

    if (n == 1) ans = k;
    else ans = (((solve (n - 2) * k) % MOD) * (k - 1)) % MOD;

    cout << ans << '\n';

    return 0;
}

:::

## [ZJ f638](https://zerojudge.tw/ShowProblem?problemid=f638)

撰寫者：小麥

**超級細節請小心**
要處理的第一個點是切點左右兩邊的相差值的計算，這點應該要可以想到兩次前綴合這件事，簡單來說就是對一個前綴合再做一次前綴合，就可以算出題目要求的乘積，之後再邊相差。

之後就遞迴，按題意實作

:::spoiler 花了一天的程式碼

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio; cin.tie(0); cout.tie(0);
#define int long long

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef vector<string> vs;
typedef vector<vs> v2s;
typedef vector<pii> vp;
typedef vector<vp> v2p;
typedef vector<bool> vb;
typedef vector<vb> v2b;

int n, m;
vi arr;

int f(int l, int r, int depth) {
    if (depth == m) {
        return 0;
    }
    if (r - l < 3) {
        return 0;
    }

    vi prefix(r - l + 5, 0);
    vi suffix(r - l + 5, 0);
    for (int i = 1; i <= r - l; i++) {
        prefix[i] = prefix[i - 1] + arr[i + l - 1];        
    }
    for (int i = r - l - 1; i >= 0; i--) {
        suffix[i] = suffix[i + 1] + arr[i + l];        
    }

    vi prefix2(r - l + 1, 0);
    vi suffix2(r - l + 1, 0);
    for (int i = 1; i <= r - l; i++) {
        prefix2[i] = prefix2[i - 1] + prefix[i];        
    }
    for (int i = r - l - 1; i >= 0; i--) {
        suffix2[i] = suffix2[i + 1] + suffix[i + 1];        
    }
    
    int index = 0;
    int minimum = 1e18;
    for (int i = l + 1; i < r - 1; i++) {
        int diff = abs(prefix2[i - l] - suffix2[i - l]);
        if (minimum > diff) {
            minimum = diff;
            index = i;
        }
    }
    
    return arr[index] + f(l, index, depth + 1) + f(index + 1, r, depth + 1);
}

void solve() {
    while (cin >> n >> m) {
        
        arr.resize(n + 5);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        cout << f(0, n, 0) << '\n';
    }
}

signed main() {
    fastio;
    solve();
    return 0;
}

:::

## [Kattis sylvester](https://open.kattis.com/problems/sylvester)

撰寫者：fishhh

文字說明待補

:::spoiler 參考程式

int rec(int now_scale,int x,int y){
    if(now_scale==-1)return 1;
    int res = 1;
    if(x>(1<<now_scale)&&y>(1<<now_scale)){
        res = -1;
    }
    if(x>(1<<now_scale))x-=(1<<now_scale);
    if(y>(1<<now_scale))y-=(1<<now_scale);
    
    return rec(now_scale-1,x,y)*res;
}
void solve(){
    int n,x,y,h,w;
    cin>>n>>x>>y>>h>>w;
    int nn = n;
    int cnt = 0;
    while(nn){
        nn>>=1;
        cnt++;
    }
    // cout<<cnt<<"!\n";
    x++,y++;
    for(int i=0;i<w;i++){
        for(int j=0;j<h;j++){
            cout<<rec(cnt-2,y+i,x+j)<<" "; // 枚舉 wxh 裡面的每一個點的座標
        }
        cout<<"\n";
    }
    cout<<"\n";
}

:::

## [ZJ f637](https://zerojudge.tw/ShowProblem?problemid=f637)

## [ZJ f640](https://zerojudge.tw/ShowProblem?problemid=f640)

## [Kattis batmanacci](https://open.kattis.com/problems/batmanacci)

撰寫者：高睿哥哥 (本人：??

題目的作法其實跟遞迴算費波那契數列很像，$S_n$的長度會合$fib_n$相同。
這樣的複雜度聽起來會很糟，因為剛上課說過費波那契數值差不多是$2^n$級別。但其實題目只要求判斷某個字元是什麼。
因為每個$S_n$，其左邊是$S_{n-2}$，右邊是$S_{n-1}$，所以對於$S_n$的第$k$個字元，我們只需判斷它是從$S_{n-1}$或$S_{n-2}$來，非來源的那一邊就不需要計算。
但要如何判斷來源呢? 方法其實就是去看$S_{n-2}$的長度，這樣對於一個詢問$Q(n,k)$，我們就能從$Q(n-2)$和$Q(k-len(S_{n-2}))$中找出其來源。
另外一個要注意的陷阱是，由於費波那契數的值(等同$S_n$的長度)為$2^n$級別，所以$len(S_{n-2})$，要特別判斷會不會超過當前k值(或者不要這麼麻煩，可以向下方code一樣給一個顯然的上界)，假設發現會大於該上界，就可以直接預設其來源為$S_{n-2}的部分$

:::spoiler

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

#define int long long

const int mx = 1e18,MAX_N=1e5+5;
vector<int> fb;

char f(int n,int k){
    if(n==1) return 'N';
    if(n==2) return 'A';
    if(n-2>=fb.size()) return f(n-2,k);
    int x=fb[n-2];
    if(x!=0&&k>x) return f(n-1,k-x);          //右半了
    return f(n-2,k);       //左半
}

void solve(){
    int n,k;
    cin >> n >> k;
    fb.push_back(0);
    fb.push_back(1);
    for(int i=1;;i++){
        int x=fb[i]+fb[i-1];
        if(x>mx) break;
        fb.push_back(x);
    }
    cout << f(n,k);
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int t=1;
    // cin >> t;
    while(t--){
        solve();
    }
}

:::

## [UVa 271](http://domen111.github.io/UVa-Easy-Viewer/?271)

## [Kattis hypercube](https://open.kattis.com/problems/hypercube)

## [CSES 2165](https://cses.fi/problemset/task/2165/)

撰寫者：Paul

~~相信大家都知道河內塔~~，簡單來說就是有 $n$ 個圓盤和三根桿子，一開始$n$個圓盤由大到小，由下到上放在第一根桿子。目標是將所有圓盤由大到小，由下到上放在第三根桿子，但是一次只能動一個在桿子最上方圓盤，而且每次移動都要保持由大到小，由下到上排放。
可以先假設三根桿子分別為目前所在的桿子、目標桿子和空的桿子，如果 $n = 1$ 就直接移過去較好了。其他的情形可以想成:先將 $n - 1$ 個圓盤從目前位置移到空桿，將第 $n$ 個圓盤從目前位置移到目標桿，最後再將 $n - 1$ 個圓盤從空桿移到目標桿，就可以完成目標。
至於移動的次數，假設有 $n$ 個圓盤時的總移動次數為 $f(n)$ ，則: $f(1) = 1$， $f(n) = 2*f(n-1) + 1$ 。可以證明 $f(n) = 2^n - 1$。

:::spoiler

#include<bits/stdc++.h>
using namespace std;
void f(int num, int now, int goal, int empty)
{
    if(num==1) cout<<now<<' '<<goal<<endl;
    else
    {
        f(num-1, now, empty, goal);
        cout<<now<<' '<<goal<<endl;
        f(num-1, empty, goal, now);
    }
}
int main()
{
    int n, ans=1;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       ans*=2; 
    }
    cout<<ans-1<<endl;
    f(n, 1, 3, 2);
}

:::

## [ZJ c296](https://zerojudge.tw/ShowProblem?problemid=c296)

----

## 預處理

## [AtCoder typical90_d](https://hackmd.io/@sa072686/AtCoder_typical90_d)

## [AtCoder typical90_at](https://hackmd.io/@sa072686/AtCoder_typical90_at)

## [TOJ 120](https://toj.tfcis.org/oj/pro/120/)

撰寫：fishhh

前綴和裸題。

:::spoiler 參考程式

#include<iostream>
using namespace std;
int main(){
    long long t,tree[300000],n,a,b;
    cin>>t;
    tree[0]=0;
    for(int i=1;i<=t;i++)cin>>tree[i],tree[i]+=tree[i-1];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        if(a>b)swap(a,b);
        cout<<tree[b]-tree[a-1]<<"\n";
    }
}

:::

## [AtCoder abc048_b](https://atcoder.jp/contests/abc048/tasks/abc048_b)

## [CSES 1662](https://cses.fi/problemset/task/1662/)

## [Kattis commercials](https://open.kattis.com/problems/commercials)