# 2022 資訊之芽算法班 第一階段
Edited by 廖竑羿 2022/3/5 - 2022/4/23

記錄一下每週上課內容以及部分練習題
## 第一週

- Data Structure
- 單調隊列
### 中國人排隊問題
[題目連結](https://neoj.sprout.tw/problem/20/)

這題一開始一直沒過，經過講師一系列debug之後終於過了：
1. unordered_map 速度過慢且會發生碰撞
2. 內部結構為 list 的 queue 速度較快
3. 沒被歸在任何團體內的成員需視為自己一個團體

#include<bits/stdc++.h>
using namespace std;
queue<int, list<int>> in[1000005];  //隊伍中團體內順序 
queue<int, list<int>> gq;           //隊伍中團體順序
int mp[1000005];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,p,t,x,c=0,member,m;
    cin>>t;
    while(t--){
        memset(mp,0,sizeof(mp));
        cin>>n;
        cout<<"Line #"<<++c<<'\n';
        for(int i=1;i<=n;i++){
            cin>>p;
            while(p--){
                cin>>member;
                mp[member]=i;
            }
        }
        while(!gq.empty()) gq.pop();
        int not_in_group=1001;
        string cmd;
        cin>>m;
        while(m--){
            cin>>cmd;
            if(cmd[0]=='E'){
                cin>>x;
                if(mp[x]==0){
                    gq.push(not_in_group);
                    in[not_in_group++].push(x);
                }else if(in[mp[x]].empty()){
                    gq.push(mp[x]);
                    in[mp[x]].push(x);
                }else in[mp[x]].push(x);
            }
            else{
                cout<<in[gq.front()].front()<<'\n';
                in[gq.front()].pop();
                if(in[gq.front()].empty()) gq.pop();
            }
        }
        for(int i=0;i<=not_in_group;i++) {
            while(!in[i].empty()) in[i].pop();
        }
    }
}

### 陸行鳥大賽車
[題目連結](https://neoj.sprout.tw/problem/21/)

一開始用vector寫，但查詢操作位子要O(n)，一直tle
用 linked list 時間複雜度可以了
注意邊界要處理好不然跑到 NULL 吃了很多 RE

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m,x,cmd;

struct p{
    int data;
    p *pre,*next;
    p(){
        next=NULL;
        pre=NULL;
    }
}*prr[maxn];
int main(){
    cin>>n>>m;
    for(int i=0;i<=n+2;i++){
        prr[i]=new p();
        prr[i]->data=i;
    }
    // 初始化
    for(int i=1;i<=n+2;i++){
        prr[i]->pre=prr[i-1];
        prr[i]->next=prr[i+1];
    }
    while(m--){
        cin>>cmd>>x;
        if(cmd==0){             //出局
            prr[x]->pre->next=prr[x]->next;
            prr[x]->next->pre=prr[x]->pre;
        }else{
            if(!prr[x]->pre->pre)continue;
            int pp,p,nx;         //前前。前。後
            pp=prr[x]->pre->pre->data;
            p=prr[x]->pre->data;
            nx=prr[x]->next->data;
            
            prr[x]->pre=prr[pp];
            prr[pp]->next=prr[x];
            prr[x]->next=prr[p];
            prr[p]->pre=prr[x];
            prr[p]->next=prr[nx];
            prr[nx]->pre=prr[p];
        }
    }
    stack<int> s;
        int ind = n+1;
        while(prr[ind]->pre!=NULL){
            if(ind!=n+1) s.push(prr[ind]->data);
            ind = prr[ind]->pre->data;
        }
        while(!s.empty()&&s.size()!=1){
            cout<<s.top()<<" ";
            s.pop();
        }
    cout<<s.top()<<'\n';
}

### 大善人老闆救濟東南亞兒童
[題目連結](https://neoj.sprout.tw/problem/19/)

用stack跟queue模擬火車進出站

#include<iostream>
#include<vector>
#include<deque>
int arr[20005];
using namespace std;
vector<int> vv;
deque<int> dq;
int main(){
    int n,t;cin>>t;
    while(t--){
        cin>>n;
        vv.clear();
        dq.clear();
        for(int i=1;i<=n;i++){
            int a; cin>>a;
            dq.push_back(a);
        }
        for(int i=1; i<=n ;i++){
            vv.push_back(i);
            while((!vv.empty() && !dq.empty()) && (vv.back()==dq.front())){
                vv.pop_back();
                dq.pop_front();
            }
        }
        if(vv.empty()) cout<<"Yes"<<'\n';
        else if(!vv.empty()) cout<<"No"<<'\n';
    }
    return 0;
}

### 超大螢幕設置
[題目連結](https://neoj.sprout.tw/problem/513/)

各從左右掃一遍，找每個index往左右看第一個比他矮的柱子
用單調列隊做 O(n)
注意記得開 long long ，int * int 出來會溢位

#include<bits/stdc++.h>
#define maxn 200005
#define ll long long
using namespace std;
ll arr[maxn];
ll l[maxn],r[maxn];
stack<int> s;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];

    s.push(0);
    for(int i=1;i<=n;i++){
        while(arr[i]<=arr[s.top()]) s.pop();
        l[i]=i-s.top();
        s.push(i);
    }
    while(!s.empty()) s.pop();
    s.push(n+1);
    for(int i=n;i>=1;i--){
        while(arr[i]<=arr[s.top()]) s.pop();
        r[i]=s.top()-i-1;
        s.push(i);
    }
    
    ll ans=-1;
    for(int i=1;i<=n;i++)ans=max(ans,arr[i]*(r[i]+l[i]));
    cout<<ans<<'\n
}

## 第二週

- Tree
- 複雜度計算
### It's my ____ in the box
[題目連結](https://neoj.sprout.tw/problem/49/)

將盒子a放入盒子b時，要將所有包含b盒子的盒子加上a盒子的盒子總數量

紀錄哪個盒子在哪個盒子內也可以開一個陣列做

#include<bits/stdc++.h>
#define maxn 100005
using namespace  std;
struct node{
    int data=1;
    node *in;
    node(){
        in=NULL;
    }
};
node *box[maxn];
int main(){
    int t,n,m,q,x,a,b;cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<=n+1;i++){
            box[i]=new node();
        }
        while(m--){
            cin>>a>>b;          //a <- b
            box[b]->in=box[a];
            box[a]->data+=box[b]->data;
            node *now=box[a];
            while(now->in!=NULL){
                now->in->data+=box[b]->data;
                now=now->in;
            }
            
        }
        cin>>q;
        while(q--){
            cin>>x;
            cout<<box[x]->data<<'\n';
        }
    }
}

### 二元搜尋樹
[題目連結](https://neoj.sprout.tw/problem/48/)

利用前序走訪和中序走訪可以推得整棵樹的原始樣貌

#include<iostream>
#include<algorithm>
using namespace std;

int arr[200005];
int sorted[200005];
int a,N;

struct node{
    node *left;
    node *right;
    int val;
};
node* binary_tree(int *pre,int *in, int lenth){
    if(lenth==0) return NULL;
    node *n = new node;
    int index=0;
    for(;index<N;index++)
        if(*pre==in[index]) break;
    n->val = in[index];
    n->left=binary_tree(pre+1,in,index);
    n->right=binary_tree(pre+index+1,in+index+1,lenth-index-1);
    cout<<n->val<<'\n';
    return n;
};

int main(){
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>arr[i];
        sorted[i]=arr[i];
    }
    sort(sorted,sorted+N);
    binary_tree(arr,sorted,N);
}

### 1d-kd-tree
[題目連結](https://neoj.sprout.tw/problem/47/)

用一個set（二元搜尋樹），每次詢問時比較第一個>=詢問數字，及他的前面一個。

在set裡加入最大及最小值比較方便確認查到的指標是不是在第一或最後一個，不然很容易RE

#include<bits/stdc++.h>
using namespace std;
int maxn=1e9+5;
set<int> s;
int main(){
    int t,x;cin>>t;
    s.insert(maxn);
    s.insert(-maxn);
    string op;
    while(t--){
        cin>>op>>x;
        if(op[0]=='i') s.insert(x);
        else if(op[0]=='d') s.erase(x);
        else{
            auto front=s.lower_bound(x);
            front--;
            auto next=s.lower_bound(x);
            int dis1=x-*front;
            int dis2=*next-x;
            
            if(*front==-maxn) cout<<*next<<'\n';
            else if(*next==maxn) cout<<*front<<'\n';
            else{
                if(dis1==dis2) cout<<*front<<' '<<*next<<'\n';
                else{
                    if(dis1<dis2) cout<<*front<<'\n';
                    else cout<<*next<<'\n';
                }
            }
        }
    }
}

### 樹重心
[題目連結](https://neoj.sprout.tw/problem/293/)

用一個sruct紀錄每個節點最大子樹的數量、子結點數量
dfs 遍歷每個節點後找「慘度」最小的節點編號

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
vector<int> vrr[maxn];
bool visit[maxn];
struct node{
    int sons,max_son;
}nrr[maxn];
int dfs(int x){
    visit[x]=1;
    for(auto i:vrr[x]){
        if(!visit[i]){
            int tmp=dfs(i);
            nrr[x].sons+=tmp;
            nrr[x].max_son=max(nrr[x].max_son,tmp);
        }
    }
    return nrr[x].sons+1;
}
int main(){
    int t,n,b,a;
    cin>>t;
    while(t--){
        cin>>n;
        // init
        memset(visit,0,sizeof(visit));
        for(int i=0;i<=n;i++){
            nrr[i].max_son=nrr[i].sons=0;
            vrr[i].clear();
        }
        for(int i=0;i<n-1;i++){
            cin>>a>>b;
            vrr[a].push_back(b);
            vrr[b].push_back(a);
        }
        dfs(0);
        int ans=0,minn=maxn;
        for(int i=0;i<n;i++){
            int cmp=max(nrr[i].max_son,n-nrr[i].sons-1);
            if(cmp<minn){
                ans=i;
                minn=cmp;
            }
        }
        cout<<ans<<'\n';
    }
}

## 第三週
- Heap
- Flood Fill
- Graph

### 庭院裡的水池
[題目連結](https://neoj.sprout.tw/problem/42/)

用dfs計算聯通塊數量

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int arr[maxn][maxn];
bool visit[maxn][maxn];
int mr[4]={1,0,-1,0};
int mc[4]={0,1,0,-1};
void dfs(int r,int c){
    visit[r][c]=1;
    for(int i=0;i<4;i++){
        if(!visit[r+mr[i]][c+mc[i]] && arr[r+mr[i]][c+mc[i]]==1)
            dfs(r+mr[i],c+mc[i]);
    }
}
int main(){
    int t,n,m;cin>>t;
    char x;
    while(t--){
        memset(arr,-1,sizeof(arr));
        memset(visit,0,sizeof(visit));
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>x;
                if(x=='.') arr[i][j]=1;
                else arr[i][j]=0;
            }
        }
        
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!visit[i][j] && arr[i][j]==1){
                    ans++;
                    dfs(i,j);
                }
            }
        }
        cout<<ans<<'\n';
    }
}

### 喵喵抓老鼠
[題目連結](https://neoj.sprout.tw/problem/44/)

bfs算出最短路徑

要記得在丟進去queue時就要標記visit ！

#include<bits/stdc++.h>
#define maxn 105
#define pii pair<int,int>
using namespace std;
int mr[4]={1,0,-1,0};
int mc[4]={0,1,0,-1};
char arr[maxn][maxn];
bool visit[maxn][maxn];
queue<pair<int,pii>> q;       //step,position
int main(){
    int t,n,m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        memset(visit,0,sizeof(visit));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) {
                cin>>arr[i][j];
                if(arr[i][j]=='K')
                    q.push({0,{i,j}});
            }
        }
        int ans=-1;
        while(!q.empty()){
            int nr=q.front().second.first;
            int nc=q.front().second.second;
            int step=q.front().first;
            if(arr[nr][nc]=='@') {
                ans=step;
                break;
            }
            q.pop();
            for(int i=0;i<4;i++){
                if(arr[nr+mr[i]][nc+mc[i]]!='#' && !visit[nr+mr[i]][nc+mc[i]]){
                    q.push({step+1,{nr+mr[i],nc+mc[i]}});
                    visit[nr+mr[i]][nc+mc[i]]=1;
                }
            }
        }
        if(ans!=-1) cout<<ans<<'\n';
        else cout<<"= ="<<'"'<<'\n';
        while(!q.empty()) q.pop();
    }
}

### 哪裡有卦，哪裡就有源
[題目連結](https://neoj.sprout.tw/problem/1101/)

判斷一張圖是否為二分圖
要注意不只有一個聯通塊

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int color[maxn];
bool visit[maxn];
vector<int> v[maxn];
bool dfs(int x,int paint){
    int ok=1;
    visit[x]=1;
    color[x]=paint;
    for(auto i : v[x]){
        if(!visit[i]) ok&=dfs(i,!paint);
        else if(color[i]==color[x]) return 0;
    }
    return ok;
}
int main(){
    int t,n,m,a,b;
    cin>>t;
    while(t--){
        memset(color,-1,sizeof(color));
        memset(visit,0,sizeof(visit));
        cin>>n>>m;
        for(int i=0;i<n;i++) v[i].clear();
        while(m--){
            cin>>a>>b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        bool ok=1;
        for(int i=0;i<n;i++){
            if(color[i]==-1) {
                if(!dfs(i,0)) {
                    ok=0;
                    break;
                }
            }
        }
        if(ok) cout<<"NORMAL."<<'\n';
        else cout<<"RAINBOW."<<'\n';
    }
}

### 染色遊戲

zerojudge [題目連結](zhttps://zerojudge.tw/ShowProblem?problemid=d537)
neoj [題目連結](https://neoj.sprout.tw/problem/46/)

在將新的節點推入queue的時候
順便紀錄哪種顏色變少哪種顏色變多變少
每個回合（步數）計算一次答案

- 注意 visit 需要分三種顏色紀錄
- 三原色的 visit 要先標為 true

除了n的範圍之外是一樣的題目
但在 zerojudge 上 AC 的 code 丟上 neoj 就 wa 了
目前還在debug

後記：講師說可能會有一開始三種顏色在同一個點的case
然後就過了

#include<bits/stdc++.h>
#define maxn 1002
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
bool visit[5][maxn][maxn];      // color,row,col
int arr[maxn][maxn];
int amount[8],ans[8];
int mr[8]={1,1,1,0,0,-1,-1,-1};
int mc[8]={1,0,-1,1,-1,1,0,-1};
queue<pair<pii,pii>> q;     //step,color, position
// R=1, Y=2, B=4 O=3, P=5, G=6, D=7;
int t,n,r,c;
bool check(int r,int c){            //check range
    return (r<n && c<n && r>=0 && c>=0);
}
int main(){
    cin>>t;
    char x;
    while(t--){
        memset(arr,0,sizeof(arr));
        memset(visit,0,sizeof(visit));
        memset(ans,0,sizeof(ans));
        memset(amount,0,sizeof(amount));
        while(!q.empty()) q.pop();
        
        cin>>n;
        for(int i=0;i<3;i++){
            cin>>x>>r>>c;
            if(x=='R') {arr[r][c]++;visit[1][r][c]=1; q.push({{0,1},{r,c}});}
            if(x=='Y') {arr[r][c]+=2;visit[2][r][c]=1; q.push({{0,2},{r,c}});}
            if(x=='B') {arr[r][c]+=4;visit[4][r][c]=1; q.push({{0,4},{r,c}});}
        }
        
        int now=-1;
        int chg[8]={0,0,0,0,0,0,0,0};
        for(int i=0;i<1002;i++)
            for(int j=0;j<1002;j++)
                if(arr[i][j]!=0) chg[arr[i][j]]++;
        while(!q.empty()){
            int cl=q.front().f.s;
            int time=q.front().f.f;
            if(time!=now) {
                now++;
                for(int i=0;i<8;i++) amount[i]+=chg[i];
                for(int i=0;i<8;i++) ans[i]=max(ans[i],amount[i]);
                memset(chg,0,sizeof(chg));
            }
            for(int i=0;i<8;i++){
                int nr=q.front().s.f+mr[i];
                int nc=q.front().s.s+mc[i];
                if(check(nr,nc) && !visit[cl][nr][nc]){
                    visit[cl][nr][nc]=1;
                    q.push({{time+1,cl},{nr,nc}});
                    chg[arr[nr][nc]]--;
                    arr[nr][nc]+=cl;
                    chg[arr[nr][nc]]++;
                }
            }
            q.pop();
        }
        //for(int i=0;i<8;i++) cout<<ans[i]<<' ';
        cin>>x;
        if(x=='R') cout<<ans[1]<<'\n';
        if(x=='Y') cout<<ans[2]<<'\n';
        if(x=='O') cout<<ans[3]<<'\n';
        if(x=='B') cout<<ans[4]<<'\n';
        if(x=='P') cout<<ans[5]<<'\n';
        if(x=='G') cout<<ans[6]<<'\n';
        if(x=='D') cout<<n*n<<'\n';
    }
}

## 第四週

- dfs 枚舉
- 二分搜、三分搜
### 數獨
[題目連結](https://neoj.sprout.tw/problem/62/)

用dfs遞迴，最後再檢查一遍是否合法。

#include<bits/stdc++.h>
using namespace std;
int arr[15][15];
bool ok=0;
void print(){
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++) cout<<arr[i][j];
    cout<<'\n';
}
int find_next(int r,int c){
    for(int i=r;i<9;i++)
        for(int j=0;j<9;j++)
            if(arr[i][j]==0) return i*9+j;
    return -1;
}
vector<int> put(int r,int c){
    bool ok[10]={1,1,1,1,1,1,1,1,1,1};
    for(int i=0;i<9;i++) if(arr[i][c]!=0) ok[arr[i][c]]=0;          //col
    for(int i=0;i<9;i++) if(arr[r][i]!=0) ok[arr[r][i]]=0;          //row
    
    int boxr=3*(r/3),boxc=3*(c/3);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(arr[boxr+i][boxc+j]!=0) ok[arr[boxr+i][boxc+j]]=0;
        
    vector<int> ans;
    for(int i=1;i<=9;i++) if(ok[i]) ans.push_back(i);
    return ans;
}
void dfs(int r,int c){
    int pos=find_next(r,c),nr,nc;
    if(pos==-1) {
        ok=1;
        return;
    }
    
    vector<int> v=put(r,c);
    
    for(int i=0;i<v.size();i++){
        arr[r][c]=v[i];
        pos=find_next(r,c);
        nr = pos/9; nc = pos%9;
        dfs(nr,nc);
        if(ok) return;
    }
    arr[r][c]=0;
}
void solve(){
    int pos=find_next(0,0);
    int r=pos/9,c=pos%9;
    dfs(r,c);
    
    bool legal=1;
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            vector<int> v=put(i,j);
            if(v.size()>0) legal=0;
        }
    }
    
    if(!legal || !ok) cout<<"No solution."<<'\n';
    else print();
}

int main(){
    int t;cin>>t;
    char x;
    while(t--){
        ok=0;
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                cin>>x;
                if(x=='.') arr[i][j]=0;
                else arr[i][j]=x-'0';
            }
        }
        solve();
    }
}

### Lotto
[題目連結](https://neoj.sprout.tw/problem/63/)

一樣用dfs枚舉每種情況

#include<bits/stdc++.h>
using namespace std;
int arr[105],ans[105];
int t,n;
void dfs(int ansid,int arrid){
    if(arrid>n) return;         // bug
    if(ansid==6){
        for(int i=0;i<5;i++)cout<<ans[i]<<' ';
        cout<<ans[5]<<'\n';
        return;
    }
    ans[ansid]=arr[arrid];
    dfs(ansid+1,arrid+1);
    dfs(ansid,arrid+1);
    
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++) cin>>arr[i];
        dfs(0,0);
    }
}

### 田忌賽馬
[題目連結](https://neoj.sprout.tw/problem/69/)

對天數二分搜，且用自己最強的 k 隻馬與敵方最弱的 k 隻馬比
debug 很久的部分
1. long long 記得開
2. ans 的初始值
3. 不用成長就已經了了的情況

#include<bits/stdc++.h>
#define maxn 10005
#define MAXN 10000000001
#define int long long
using namespace std;
int arr[maxn],enemy[maxn],grow[maxn];
int crr[maxn];           //grown horses
int t,k,n;
bool check(int day){
    for(int i=0;i<n;i++) crr[i]=arr[i]+grow[i]*day;
    sort(crr,crr+n);
    for(int i=0;i<k;i++)
        if(enemy[i]>=crr[n-k+i]) return 0;
    return 1;
}
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=0;i<n;i++) cin>>arr[i]>>grow[i];
        for(int i=0;i<n;i++) cin>>enemy[i];
        sort(enemy,enemy+n);
        int l=0,r=MAXN,ans=MAXN;
        
        if(!check(r)) cout<<-1<<'\n';
        else if(check(0)) cout<<0<<'\n';
        else {
            while(r>l){
                int mid=(r+l)/2;
                if(check(mid)){
                    ans=min(ans,mid);
                    r=mid;
                }else l=mid+1;
            }
            cout<<ans<<'\n';
        }
    }
}

### Happiness Function
[題目連結](https://neoj.sprout.tw/problem/72/)

三分搜

#include<bits/stdc++.h>
#define d long double
using namespace std;
d a[15],b[15],c[15];
int t,n;
d check(double x){
    d ans=-1;
    for(int i=0;i<n;i++) ans=max(ans,a[i]*((x-b[i])*(x-b[i]))+c[i]);
    return ans;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];
        d l=0.000000,r=300.0000000;
        int cnt=10007;
        while(cnt--){
            d ml=(l*2+r)/3, mr=(l+r*2)/3;
            if(check(mr)>check(ml)) r=mr;
            else l=ml;
        }
        printf("%LF\n",check((l+r)/2));
    }
}

### 東方古墓古文
[題目連結](https://neoj.sprout.tw/problem/73/)

對答案做二分搜
小心一開始的 r 值不能開太小，答案乘起來可能會超過 int 範圍

#include<bits/stdc++.h>
#define int long long
#define maxn 100005
using namespace std;
int arr[maxn];
int t,n,m;

bool check(int w){
    int id=0,cnt=0;
    for(int i=0;i<n;i++){
        
        while(cnt+arr[i]>w && id<m) {
            cnt=0;
            id++;
        }
        if(id>=m) return 0;

        cnt+=arr[i];
    }
    return 1;
}
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>arr[i];
        int l=0,r=10000000005,ans=10000000005;
        while(l<r){
            int mid=(l+r)/2;
            if(check(mid)){
                r=mid;
                ans=min(ans,mid);
            }else l=mid+1;
        }
        cout<<ans<<'\n';
    }
}

## 第五週
- Greedy

### Add all
[題目連結](https://neoj.sprout.tw/problem/70/)

每次取最小的兩個數相加

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t,n,x;cin>>t;
    priority_queue<int> q;
    while(t--){
        cin>>n;
        int cnt=0;
        while(n--){
            cin>>x;
            q.push(-x);
        }
        while(q.size()!=1){
            int a=q.top();
            q.pop();
            int b=q.top();
            q.pop();
            cnt-=(a+b);
            q.push(a+b);
        }
        q.pop();
        cout<<cnt<<'\n';
    }
}

### 円円攻略黃河
[題目連結](https://neoj.sprout.tw/problem/74/)

如果下一塊石頭要找比自己高的，但石頭比自己低時則取較低的石頭
如果下一塊石頭要找比自己低的，但石頭比自己高時則取較高的石頭

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int t,n,x;cin>>t;
    while(t--){
        cin>>n;
        int ans=0,now=0;
        bool tall=1;
        while(n--){
            cin>>x;
            if(tall && x>now) ans++,tall=!tall;
            else if(!tall && x<now) ans++,tall=!tall;
            now=x;
        }
        if(tall) cout<<ans-1<<'\n';
        else cout<<ans<<'\n';
    }
}

### 包裝禮物
[題目連結](https://neoj.sprout.tw/problem/78/)

從大的開始放入，有多的空位則放入小的

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int t;cin>>t;
    while(t--){
        int arr[7]={0};
        int ok=0,ans=0;
        for(int i=1;i<=6;i++) cin>>arr[i];
        for(int i=1;i<=6;i++) if(arr[i]) ok=1;
        if(!ok) break;
        
        ans+=arr[6];                         //6
        
        ans+=arr[5];                         //5
        arr[1]-=arr[5]*11;
                
        ans+=arr[4];                         //4
        int blank4=arr[4]*20;
        while(arr[2] && blank4>0) arr[2]--,blank4-=4;
        if(arr[1]>0 && blank4>0) arr[1]-=blank4;

        ans+=arr[3]/4 + bool(arr[3]%4);       //3
        int blank3=36-9*(arr[3]%4);
        int cnt=0;
        while(arr[2]>0 && cnt<(4-arr[3]%4)*2-1 && arr[3]%4 )
            arr[2]--,cnt++,blank3-=4;
        if(arr[1]>0 && (arr[3]%4) && blank3>0) arr[1]-=blank3;
        
        ans+=arr[2]/9 + bool(arr[2]%9);        //2
        if(arr[1]>0 && arr[2]>0 && arr[2]%9) arr[1]-=(36-arr[2]%9*4);

        if(arr[1]>0) ans+=arr[1]/36+bool(arr[1]%36); //1
        
        cout<<ans<<'\n';
        
    }
}

### 誰先晚餐
[題目連結](https://neoj.sprout.tw/problem/78/)

吃最久的人先吃

#include<bits/stdc++.h>
#define pii pair<int,int>
#define s second
#define f first
using namespace std;
pii p[10005];           //eat,cook
bool cmp(pii a, pii b){
    return a.f>b.f;
}
int main(){
    int n,t;cin>>t;
    while(t--){
        memset(p,0,sizeof(p));
        cin>>n;
        for(int i=0;i<n;i++)cin>>p[i].s>>p[i].f;
        sort(p,p+n,cmp);
        
        int ans=0,cook=0;
        for(int i=0;i<n;i++){
            cook+=p[i].s;
            ans=max(ans,cook+p[i].f);
        }
        cout<<ans<<'\n';
    }
}

### 調校高棕櫚！
[題目連結](https://neoj.sprout.tw/problem/91/)

數字由 9 到 2 除，並計算除了幾次

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long t,n;cin>>t;
    while(t--){
        int arr[10]={};
        cin>>n;
        if(n==0 || n==1){
            cout<<n<<'\n';
            continue;
        }
        for(int i=9;i>=2;i--){
            while(n%i==0) {
                arr[i]++;
                n/=i;
            }
        }
        if(n!=1) cout<<-1<<'\n';
        else{
            for(int i=2;i<=9;i++)
                for(int j=0;j<arr[i];j++) cout<<i;
            cout<<'\n';
        }
        
    }
}

### 2014算法班認證考_pE
[題目連結](https://neoj.sprout.tw/problem/60/)

這題寫了非常久，去年看了題有一些想法但還是做不出來，今年好像就想通了

由於成熟度 m 之間皆為倍數，所以總共成熟度可以壓到 log2 m種，不會超過40。

1.將箱子及水果排序，使箱子內放入水果之總成熟度最大
2.從取的水果裡面成熟度最大的開始一個一個往下換，如果能換成較多顆就換
3.若一種成熟度沒有全部換完要記得加回去（ line 53 ）

#include<bits/stdc++.h>
#define maxn 100005
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
int box[maxn],arr[maxn];
pii p[51];          // value,amount
int use[50];
int main(){
    int t,m,n;cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>box[i];
        for(int i=0;i<m;i++) cin>>arr[i];
        sort(box,box+n,greater<int>());
        sort(arr,arr+m);
        for(int i=0;i<50;i++) p[i].f=p[i].s=use[i]=0;
        
        int id=0,ans=0;
        p[id].f=arr[0];
        p[id].s++;
        for(int i=1;i<m;i++){
            if(arr[i]!=arr[i-1]) id++;
            p[id].f=arr[i];p[id].s++;
        }
        // 使箱子內放入之總成熟度最大
        for(int i=0;i<n;i++){
            int cap=box[i],ind=id;
            while(cap>0 && ind>=0){
                int take=cap/p[ind].f;
                if(take>p[ind].s) take=p[ind].s;
                cap-=take*p[ind].f;
                p[ind].s-=take;
                use[ind]+=take;
                ans+=take;
                while(p[ind].s==0 || cap<p[ind].f) ind--;
            }
        }
        // 從在箱子內成熟度最大的水果開始一一往下替換
        for(int i=id;i>=0;i--){
            int cap=use[i]*p[i].f,ind=i-1;
            int orians=ans;
            while(cap>0 && ind>=0){
                int take=cap/p[ind].f;
                if(take>p[ind].s) take=p[ind].s;
                cap-=take*p[ind].f;
                p[ind].s-=take;
                use[ind]+=take;
                ans+=take;
                while(p[ind].s==0 || cap<p[ind].f) ind--;
            }
            if(orians<ans) ans-=(use[i]-(cap/p[i].f));
        }
        cout<<ans<<'\n';
    }
}

## 第六週

- 分治

### 王老先生
[題目連結](https://neoj.sprout.tw/problem/124/)

將正方形切成四塊每次上色點所在的另外三個正方形上一 L 色塊。

#include <bits/stdc++.h>
using namespace std;
int arr[1026][1026];

void land(int n,int st_r,int st_c){
    if(n<=1) return;

    int dot_r,dot_c,rx1,rx2,rx3,ry1,ry2,ry3;
    for(int i=st_r;i<st_r+n;i++){
        for(int j=st_c;j<st_c+n;j++){
            if(arr[i][j]==1) {
                dot_r=i,dot_c=j;
                break;
            }
        }
    }


    if(dot_r < st_r+n/2  && dot_c < st_c+n/2){           //1
        rx1=st_r+n/2-1; ry1=st_c+n/2;
        rx2=st_r+n/2;   ry2=st_c+n/2;
        rx3=st_r+n/2;   ry3=st_c+n/2-1;
    }
    if(dot_r < st_r+n/2  && dot_c >= st_c+n/2){           //2
        rx1=st_r+n/2-1; ry1=st_c+n/2-1;
        rx2=st_r+n/2;   ry2=st_c+n/2-1;
        rx3=st_r+n/2;   ry3=st_c+n/2;
    }
    if(dot_r >= st_r+n/2  && dot_c >= st_c+n/2){           //4
        rx1=st_r+n/2;   ry1=st_c+n/2-1;
        rx2=st_r+n/2-1; ry2=st_c+n/2;
        rx3=st_r+n/2-1; ry3=st_c+n/2-1;
    }
    if(dot_r >= st_r+n/2  && dot_c < st_c+n/2){           //3
        rx1=st_r+n/2-1; ry1=st_c+n/2-1;
        rx2=st_r+n/2-1; ry2=st_c+n/2;
        rx3=st_r+n/2;   ry3=st_c+n/2;
    }
    //printf("n:%d st_r:%d st_c:%d\n",n,st_r,st_c);
    Report(rx1,ry1,rx2,ry2,rx3,ry3);
    arr[rx1][ry1]=1;arr[rx2][ry2]=1;arr[rx3][ry3]=1;
    
    land(n/2,st_r,st_c);
    land(n/2,st_r+n/2,st_c);
    land(n/2,st_r,st_c+n/2);
    land(n/2,st_r+n/2,st_c+n/2);

}

void solve(int n,int r,int c){
    memset(arr,0,sizeof(arr));
    arr[r][c]=1;
    land(n,1,1);
}

### 逆序數對

[題目連結](https://neoj.sprout.tw/problem/125/)

做一次 merge sort ，合併時紀錄逆序數對和。

#include<bits/stdc++.h>
#define maxn 1000005
#define mod %10000019
#define int long long
using namespace std;
int arr[maxn],brr[maxn];
int ans=0;
void merge_sort(int l,int r){
    if(l==r-1) return;
    merge_sort(l,(l+r)/2);
    merge_sort((l+r)/2,r);
    int mid=(l+r)/2;
    int id=l,idl=l,idr=mid;
    //cout<<"merge_sort: "<<l<<' '<<r<<'\n';
    while(idr<r || idl<mid){
        if(idl<mid && (arr[idl]<=arr[idr] || idr>=r)) {
            ans+=(arr[idl]*(idr-mid))mod;
            brr[id++]=arr[idl++];
        }else{
            ans+=(arr[idr]*(mid-idl))mod;
            brr[id++]=arr[idr++];
        }
        ans=ans mod;
    }
    for(int i=l;i<r;i++) arr[i]=brr[i];
}
signed main(){
    int n;cin>>n;
    for(int i=0;i<n;i++) cin>>arr[i];
    merge_sort(0,n);
    cout<<ans<<'\n';
}

### 好的序列
[題目連結](https://neoj.sprout.tw/problem/789/)

長度為3時則為 1 3 2 ，大於 3 時：
每次合併時左半 *2-1 ，右半 *2 ，保證不會出現等差數列

一開始 wa 很久，沒辦法使 1-N 在序列中都出現，
後來講師提示：按造我的分法哪邊長度會是奇數？

經過思考的結論：一開始 mid 取 (l+r)/2 ，在奇數長度序列裡右邊會比左邊多一個，所以會沒辦法使 1-N 剛好出現在序列中。

#include<bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int arr[maxn];
void f(int l,int r){
    //cout<<l<<' '<<r<<'\n';
    if(l==r-3){
        arr[l]=1;
        arr[l+1]=3;
        arr[l+2]=2;
        return;
    }else if(l==r-2){
        arr[l]=1;
        arr[l+1]=2;
        return;
    }else if(l==r-1){
        arr[l]=1;
        return;
    }
    int mid=(l+r)/2+bool((l+r)%2==1);
    f(l,mid);
    f(mid,r);
    for(int i=mid;i<r;i++) arr[i]=arr[i]*2;
    for(int i=l;i<mid;i++) arr[i]=arr[i]*2-1;
}
signed main(){
    int n;cin>>n;
    f(0,n);
    for(int i=0;i<n;i++)cout<<arr[i]<<' ';
}

### 最近點對
[題目連結](https://neoj.sprout.tw/problem/795/)

分治經典題目，但 debug 非常久

- INF 一開始設成 7e18
但由於 x , y 值域為 +- 1e9，所以最糟情況會到 8e18
- ans 為平方後的值
一開始直接拿來跟 y 座標距離相減比，取到太多點會 tle

#include<bits/stdc++.h>
#define maxn 200005
#define int long long
#define pii pair<long long,long long>
#define f first
#define s second
#define INF 9e18
using namespace std;
pii p[maxn],temp[maxn];
bool cmp(pii a,pii b){
    return a.s<b.s;
}
int dis(pii a,pii b){
    return (a.f-b.f)*(a.f-b.f) + (a.s-b.s)*(a.s-b.s);
}
int solve(int l,int r){
    if(l==r-1) return INF;
    int mid=(l+r)/2,midx=p[mid].f;
    int ans=min(solve(l,mid),solve(mid,r));
    
    merge(          //std::merge 合併
        p+l,p+mid,
        p+mid,p+r,
        temp,cmp
    );
    for(int i=l;i<r;i++) p[i]=temp[i-l];
    vector<pii>v;
    for(int i=l;i<r;i++)
        if((p[i].f-midx) * (p[i].f-midx) <= ans) v.push_back(p[i]);
    
    int len=v.size();
    for(int i=0;i<len;i++){
        for(int j=i+1;j<len;j++){
            ans=min(ans,dis(v[i],v[j]));
            if((v[i].s-v[j].s)*(v[i].s-v[j].s)>ans) break;
        }
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=0;i<n;i++) cin>>p[i].f>>p[i].s;
    sort(p,p+n);
    int ans=solve(0,n);
    cout<<ans<<'\n';
}

## 第七週

- dp

### 円円數磁磚
[題目連結](https://neoj.sprout.tw/problem/138/)

轉移式一開始沒想出來，後來問了同學才知道要用推的

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int dp[maxn];
/*
 f(n)=3*f(n-2)+2*(f(n-4)+f(n-6)+……)
 f(n-2)=3*f(n-4)+2*(f(n-6)+f(n-8)+……)
 f(n-2)-f(n-4)=2*(f(n-4)+f(n-6)+f(n-8)+…)
 f(n)=4*f(n-2)-f(n-4)
 */
int main(){
    int t,n;cin>>t;
    dp[2]=3;
    dp[4]=11;
    for(int i=6;i<100002;i+=2)
    dp[i]=(dp[i-2]*4-dp[i-4]+1000007)%1000007;
    while(t--){
        cin>>n;
        cout<<dp[n]<<'\n';
    }
}

### 円円送禮物
[題目連結](https://neoj.sprout.tw/problem/140/)

用長度、頭尾顏色作為狀態

#include<bits/stdc++.h>
#define maxn 100005
#define mod 1000007
using namespace std;
int dp[maxn][3][3];        // lenth,start,end color (r,g,b)
int main(){
    int t,n;cin>>t;
    dp[3][0][0]=3;
    dp[3][0][1]=dp[3][0][2]=dp[3][1][0]=dp[3][1][1]=dp[3][2][0]=dp[3][2][2]=2;
    dp[3][2][1]=dp[3][1][2]=1;
    for(int i=4;i<maxn-2;i++){
        for(int j=0;j<3;j++){
            dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%mod;
            dp[i][j][1]=(dp[i-1][j][0]+dp[i-1][j][1])%mod;
            dp[i][j][2]=(dp[i-1][j][0]+dp[i-1][j][2])%mod;
        }
    }
    
    while(t--){
        cin>>n;
        if(n==1)cout<<3<<'\n';
        else if(n==2) cout<<7<<'\n';
        else cout<<(dp[n][0][0]+dp[n][0][1]+dp[n][0][2]+dp[n][1][0]+dp[n][1][1]+dp[n][2][0]+dp[n][2][2])%mod<<'\n';
    }
}

### 取數字1
[題目連結](https://neoj.sprout.tw/problem/141/)

每個位置，取或不取

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int arr[maxn],dp[maxn][2];      //lenth, take

int main(){
    int t,n;cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>arr[i];
        dp[1][0]=0,dp[1][1]=arr[1];
        for(int i=2;i<=n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=dp[i-1][0]+arr[i];
        }
        cout<<max(dp[n][0],dp[n][1])<<'\n';
    }
}

### 取數字2
[題目連結](https://neoj.sprout.tw/problem/142/)

要取時改成取第前面 k 個。

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int arr[maxn],dp[maxn][2];      //lenth, take

int main(){
    int t,n,k;cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>arr[i];
        
        for(int i=1;i<=n;i++){
            if(k>i)dp[i][1]=arr[i];
            else dp[i][1]=max(dp[i-k][0],dp[i-k][1])+arr[i];
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            
        }
        cout<<max(dp[n][0],dp[n][1])<<'\n';
    }
}

### 合成円円
合併一區間 [l,r] 時考慮用 [l,k],[k+1,r] 合併會最小，l<=k<=r。
[題目連結](https://neoj.sprout.tw/problem/143/)

#include<bits/stdc++.h>
#define maxn 105
using namespace std;
int sum[maxn][maxn];
int arr[maxn],dp[maxn][maxn];      //lenth, take

int main(){
    int t,n;cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>arr[i];
        for(int i=1;i<=n;i++) sum[i][i]=arr[i];
        
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)sum[i][j]=sum[i][j-1]+arr[j];
        
        for(int i=1;i<=n;i++){
            for(int j=i-1;j>=1;j--){
                int step=100000007;
                for(int k=j;k<i;k++)
                    step=min(step,dp[j][k]+dp[k+1][i]+sum[j][i]);
                dp[j][i]=step;
            }
        }
        
        cout<<dp[1][n]<<'\n';
    }
}