{%hackmd BJrTq20hE %}
本篇均為短解無注釋，在這裡你可以學到把code寫短寫美跟一些小技巧
通常AC了才來這裡看呦。有問題、建議、不懂可以在右上旁邊留言

[oj離線網址](https://nthuoj-archive.yikuo.dev)
:::spoiler 如何寫得更快更精簡
1. 數學運算用','隔開，善用'='

a = 1;
b = 0;
c = 0;
------寫成 ------
a = 1, b = c = 0;

2. define for 成你想要的名字(我是REP)

int n,m,z,x[10][10][10];
int main(void){
    scanf("%d%d%d",&n,&m,&z);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<z;k++)
                scanf("%d",&x[i][j][k]);
}
------寫成------
#define REP(i,j,k) for(int i=j;i<k;i++)
int n,m,z,x[10][10][10];
int main(void){
    scanf("%d%d%d",&n,&m,&z);
    REP(i,0,n) REP(j,0,m) REP(k,0,z) 
        scanf("%d",&x[i][j][k]);
}

:::
# Yang-109II
## Lab
### [lab0](https://acm.cs.nthu.edu.tw/contest/2266/)
-
:::spoiler 12604 - N-Queens M-Rooks Problem

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int n,m,ans,col[10],dia[20],ndia[20];                   //col直排，dia左上右下斜，ndia右上左下斜，有沒有被擺過
    void dfs(int nn,int mm){                                //擺了nn個Queens，mm個Rooks 
        if(nn==n && mm==m) ans++;
        else{                                               //現在擺nn+mm行，這樣保證橫排不會撞到 
            REP(i,0,n+m){                                      
                if(col[i] + dia[i-nn-mm+n+m] + ndia[i+nn+mm] == 0 && nn<n){          //擺Queen  
                    col[i] = dia[i-nn-mm+n+m] = ndia[i+nn+mm] = m+1;                 //用m+1代表那排有Queen   
                    dfs(nn+1,mm); 
                    col[i] = dia[i-nn-mm+n+m] = ndia[i+nn+mm] = 0;
                }
                if(col[i] == 0 && dia[i-nn-mm+n+m]<m && ndia[i+nn+mm]<m && mm<m){    //擺Rook 
                    col[i]++, dia[i-nn-mm+n+m]++, ndia[i+nn+mm]++;                   //++代表那排有幾個Rook
                    dfs(nn,mm+1);
                    col[i]--, dia[i-nn-mm+n+m]--, ndia[i+nn+mm]--;
                }
            }
        }
    }
    int main(){
        while(scanf("%d%d",&n,&m)!=EOF){
            ans = 0, dfs(0,0);
            printf("%d\n",ans);
        }
    }

:::
:::spoiler 12605 - Rebranding

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define swap(a,b) a^=b^=a^=b
    int n,m,c[26],ans[26];
    char s[200005],a,b;
    int main(){
        REP(i,0,26) c[i] = i;
        scanf("%d%d%s",&n,&m,s);
        REP(i,0,m) scanf("%s%s",&a,&b), (a!=b?swap(c[b-'a'],c[a-'a']):0);
        REP(i,0,26) ans[c[i]] = i;
        REP(i,0,n) printf("%c",'a'+ans[s[i]-'a']);
        printf("\n");
    }

:::
### [lab1](https://acm.cs.nthu.edu.tw/contest/2281/)
-
:::spoiler 13136 - Band Ya Rou Ze - Reverse

    #include<stdio.h>                                 //複雜度O(max{N,Q,len of all string}) 
    #include<stdlib.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    typedef struct _{
        char *c;
        struct _ *l, *r;                              //兩條邊的節點 
        int rev, vl, vr;                              //本身是否反轉，兩條邊的節點是否反轉輸出，是為1
    }Node; 
    Node *rh[100005],*re[100005],*tmp;              
    int n,a,b,c,t;            
    int main(){
        scanf("%d",&n);
        REP(i,1,n+1){
            scanf("%d",&a); rh[i] = re[i] = NULL;
            if(a){
                rh[i] = re[i] = (Node*)malloc(sizeof(Node));
                rh[i]->c = (char*)malloc(sizeof(char)*(a+1));             //注意+1，尾巴還有'\0' 
                scanf("%s",rh[i]->c), rh[i]->r = rh[i]->l = NULL, rh[i]->rev = rh[i]->vl = rh[i]->vr = 0;
            }
        }
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&c,&a);
            if(c!=4) scanf("%d",&b);
            if(c==1 && rh[a]){
                if(rh[b]==NULL) re[b] = re[a];                            
                else                                                      //先把l邊給r邊，再用l邊去連
                    re[a]->r = re[a]->l, re[a]->vr = re[a]->vl, re[a]->l = rh[b], re[a]->vl = rh[b]->rev,
                    rh[b]->r = rh[b]->l, rh[b]->vr = rh[b]->vl, rh[b]->l = re[a], rh[b]->vl = re[a]->rev^1;
                rh[b] = rh[a], rh[a] = re[a] = NULL;
            }
            if(c==2 && rh[a]){
                if(rh[b]==NULL) rh[b] = rh[a];
                else                                                      //先把l邊給r邊，再用l邊去連
                    re[b]->r = re[b]->l, re[b]->vr = re[b]->vl, re[b]->l = rh[a], re[b]->vl = rh[a]->rev,
                    rh[a]->r = rh[a]->l, rh[a]->vr = rh[a]->vl, rh[a]->l = re[b], rh[a]->vl = re[b]->rev^1;
                re[b] = re[a], rh[a] = re[a] = NULL;
            }
            if(c==3) tmp = rh[a], rh[a] = rh[b], rh[b] = tmp, tmp = re[a], re[a] = re[b], re[b] = tmp;
            if(c==4 && rh[a]){
                tmp = rh[a], rh[a] = re[a], re[a] = tmp, rh[a]->rev ^= 1; //頭尾交換並打上標記 
                if(rh[a] != re[a]) re[a]->rev ^= 1;                       //注意節點只有一個時別重複reverse 
            }
        }
        REP(i,1,n+1){
            if(rh[i]) a = rh[i]->rev, tmp = NULL;                         //a為1反向輸出，tmp上一個節點 
            while(rh[i]){
                if(a){
                    int sz = strlen(rh[i]->c);
                    REP(j,0,sz) printf("%c",rh[i]->c[sz-1-j]);
                }
                else printf("%s",rh[i]->c);
                if(rh[i]->l!=tmp) tmp = rh[i], a = rh[i]->vl, rh[i] = rh[i]->l;     
                else tmp = rh[i], a = rh[i]->vr, rh[i] = rh[i]->r;        //要的是另一個沒被拜訪的節點 
            } 
            printf("\n");
        }
    }

:::
:::spoiler 13135 - Got You! Suicune!

    #include "function.h"   
    void createLinkedList(Node **head, int N, int *arr){
        Node *now = (Node*)malloc(sizeof(Node));
        now->val = arr[1], *head = now;                 
        for(int i=2;i<=N;i++) now->next = (Node*)malloc(sizeof(Node)), now = now->next, now->val = arr[i];
        now->next = *head;
    }
    void swapTwoSegment(Node **head, int N, int a, int b, int len){
        if(a+len-1-b>=N || b+len-1-a>=N || a<=b && b<=a+len-1 || b<=a && a<=b+len-1) return;    //new                        
        Node *A = *head,*B = *head;          
        while(--a) A = A->next;                       
        while(--b) B = B->next;                   
        while(len--){
            int tmp = A->val;
            A->val = B->val, B->val = tmp, A = A->next, B = B->next;
        }
    }

:::
### [lab2](https://acm.cs.nthu.edu.tw/contest/2291/)
-
:::spoiler 13149 - Ternary Expression Evaluation

    #include<stdio.h>
    int l[3005],r[3005],t,o,b;                                     //l: true跳到哪, r: false跳到哪 
    char c,s[3005];
    int dfs(){
        int a;
        scanf("%d%c",&a,&c);                                       //c 有三種 '?' ':' '\n'  
        if(c=='?') l[a] = dfs(), r[a] = dfs();
        return a;
    }
    int main(){
        o = dfs();                                                 //原點 
        scanf("%d",&t);
        while(t--){
            scanf("%s",s+1), b = o;
            while(l[b]+r[b]) b = (s[b]=='1') ? l[b] : r[b];        //l+r!=0 還沒走到底 
            printf("%c\n",s[b]);
        }
    }

:::
:::spoiler 13150 - Binary Patrick Star 2

    #include"function.h"
    #include<stdlib.h>
    Node* buildBinaryTree(int n, int* l, int* r){
        Node *T = (Node*)malloc(sizeof(Node)*n);
        for(int i=0;i<n;i++)
            T[i].id = i, T[i].left = (l[i]!=-1)?&T[l[i]]:NULL, T[i].right = (r[i]!=-1)?&T[r[i]]:NULL;
        return T;
    }
    void Traversal(Node* o, int* sz){
        sz[o->id] = 1;
        if(o->left) Traversal(o->left, sz), sz[o->id] += sz[o->left->id];
        if(o->right){
            Traversal(o->right, sz);
            if(sz[o->id] < sz[o->right->id]+1) sz[o->id] = sz[o->right->id]+1;
        }
    }
    void freeBinaryTree(Node* o){
        free(o);
    }

:::
### [mid1](https://acm.cs.nthu.edu.tw/contest/2310/)
-
:::spoiler 11366 - Moving the books

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int n,a,b,table[30][30],book[30],top[30];   //table: 桌子上的書，book: 每本在哪張，top: 每桌高度 
    char s[5],t[5]; 
    void move(int a,int b){                     //move a to b, if b==0 mean go home
        int ok = 0, A = book[a], sz = top[A];   //ok: 在a上(包含a), A: a的桌子 
        REP(i,0,sz){
            if(table[A][i]==a) ok = 1;
            if(ok && (table[A][i]!=a || b)){
                int home = (b?book[b]:table[A][i]);
                table[home][top[home]] = table[A][i], book[table[A][i]] = home,
                top[home]++, top[A]--, table[A][i] = 0;
            }
        }
    }
    int main(){
        scanf("%d",&n);
        REP(i,1,n+1) table[i][0] = book[i] = i, top[i] = 1;
        while(scanf("%s",s) && s[0]!='e'){
            scanf("%d%s%d",&a,t,&b), a++, b++;
            if(book[a]!=book[b]) move(b,0), move(a,b);
        }
        REP(i,0,n){
            printf("%d:",i);
            REP(j,0,top[i+1]) printf(" %d",table[i+1][j]-1);
            printf("\n");
        }
    }

:::
:::spoiler 13156 - Guess Left or Right

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define MX 200005
    int n,a,b,no[MX],l[MX],r[MX],p[MX],root,ans;
    void dfs(int L, int R, int o){                                                 //L，R左右邊界(他能存在的範圍) 
        if(L<=p[o] && p[o]<=R) ans++;                                              //被拜訪過幾個合理的節點
        if(l[o]==0){                                                          
            if(r[o]) p[r[o]] < p[o] ? dfs(L,p[o]-1,r[o]) : dfs(p[o]+1,R,r[o]);     //只有一節點 
        }
        else dfs(L,p[o]-1,l[o]), dfs(p[o]+1,R,r[o]);                               //兩個節點 
    }
    int main(){
        while(~scanf("%d",&n)){
            ans = 0;
            REP(i,1,n+1) no[i] = 0;                                                //有沒有可能是root 
            REP(i,1,n+1) scanf("%d%d",&a,&b), l[i] = a, r[i] = b, no[a] = no[b] = 1;
            REP(i,1,n+1) if(!no[i]) root = i;                                      //root
            REP(i,1,n+1) scanf("%d",&a), p[a] = i;                                 //逆向存 
            REP(i,1,n+1) if(p[r[i]]<p[l[i]]) r[i]^=l[i]^=r[i]^=l[i];               //哪邊才是左右，0(空的)也優先在左
            dfs(1,n,root);
            printf("%s\n",ans==n?"YES":"NO");
        }
    }

:::
:::spoiler 13157 - Beef color vain

    #include<stdio.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define MX 1000005 
    int p,q,n,a[MX],b,c,ppow[MX]={1},ans,pq[MX],num,po,l;
    char s[MX];
    int main(){
        scanf("%d%d%d",&p,&q,&n);
        REP(i,1,n+1) scanf("%d",&a[i]);
        scanf("%s",s), l = strlen(s);
        REP(i,1,MX) ppow[i] = (long long)p*ppow[i-1]%q;      
        REP(i,0,l){	                             
            while('0'<=s[i] && s[i]<='9') num = num*10+s[i]-'0', i++;
            pq[num] = (pq[num]+(long long)ppow[po])%q, ans = (ans+(long long)ppow[po]*a[num])%q, num = 0;
            if(s[i]=='f') po++;                                  //po是幾次方 
            if(s[i]==',') po--;
        }
        scanf("%d",&n);
        while(n--){
            scanf("%d%d",&b,&c);                                 //pq 是 "係數" 
            ans = (ans+(long long)pq[b]*(c-a[b])%q+q)%q, a[b] = c;
            printf("%d\n",ans);
        }
    }

:::
### [mid1 Bonus](https://acm.cs.nthu.edu.tw/contest/2331/)
-
:::spoiler 13189 - Guess Left or Right and Where

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define MX 5005
    int n,a[MX],pa[MX],l[MX],r[MX],p[MX],root,ans,bk[7],t,ok,used[7];
    void dfs(int L, int R, int o){                                                 //L，R左右邊界(他能存在的範圍) 
        if(L<=p[o] && p[o]<=R) ans++;                                              //被拜訪過幾個合理的節點
        if(l[o]==0){                                                          
            if(r[o]) p[r[o]] < p[o] ? dfs(L,p[o]-1,r[o]) : dfs(p[o]+1,R,r[o]);     //只有一節點 
        }
        else dfs(L,p[o]-1,l[o]), dfs(p[o]+1,R,r[o]);                               //兩個節點 
    }
    void permutation(int _){
        if(_==n+1){
            REP(i,1,n+1) if(p[r[i]]<p[l[i]]) r[i]^=l[i]^=r[i]^=l[i];               //哪邊才是左右，0(空的)也優先在左
            ans = 0;
            dfs(1,n,root);
            if(ans==n) ok = 1;
            return;
        }
        if(a[_]==0){
            REP(i,0,t) if(used[i]==0){
                used[i] = 1, p[bk[i]] = _;
                permutation(_+1);
                used[i] = 0;
            }
        }
        else permutation(_+1);
    }
    int main(){
        while(~scanf("%d",&n)){
            t = ok = 0;                                                            //t:有幾個blank 
            REP(i,1,n+1) l[i] = r[i] = p[i] = 0;
            REP(i,1,n+1) scanf("%d",&pa[i]), r[pa[i]] = l[pa[i]], l[pa[i]] = i;    //pa:parent
            REP(i,1,n+1) if(pa[i]==0) root = i;                                    //root
            REP(i,1,n+1) scanf("%d",&a[i]), p[a[i]] = i;                           //p:這數字在哪 
            REP(i,1,n+1) if(p[i]==0) bk[t++] = i;
            p[0] = 0, permutation(1); 	                                         //p[0] = 0，讓14行:0(空的)也優先在左 
            printf("%s\n",ok?"YES":"NO");
        }
    }

:::
### [lab4](https://acm.cs.nthu.edu.tw/contest/2347/)
-
:::spoiler 10997 - Queue

    #include "function.h" 
    List_queue::List_queue(){ head = tail = nullptr; }
    List_queue::~List_queue(){}
    void List_queue::enqueue(const int &a){
        if(head) tail = tail->nextPtr = new ListNode(a);
        else head = tail = new ListNode(a);
    }
    void List_queue::dequeue(){
        if(head==nullptr) return;
        ListNode *o = head;
        head = head->nextPtr, delete o;
    }
    void List_queue::print(){
        ListNode *o = head;
        while(o){
            std::cout<<o->data, o = o->nextPtr;
            if(o) std::cout<<" ";
        }
    }

:::
:::spoiler 12286 - Matrix

    #include "function.h"
    #define REP(i,j,k) for(int i=j;i<k;i++)
    Matrix::Matrix(int s):size(s),buf(nullptr){
        matrix = new int* [size];
        REP(i,0,size) matrix[i] = new int [size];
    }
    std::istream &operator>>(std::istream &intput, Matrix &a){
        REP(i,0,a.size) REP(j,0,a.size) intput>>a.matrix[i][j];
        return intput;
    }
    std::ostream &operator<<(std::ostream &output, const Matrix &a){
        REP(i,0,a.size){
            REP(j,0,a.size){
                if(j) output<<" ";
                output<<a.matrix[i][j];
            }
            output<<endl;
        }
        return output;
    }

:::
### [mid2](https://acm.cs.nthu.edu.tw/contest/2356/)
-
:::spoiler 11001 - Polynomial(operator overloading)

    #include "function.h"
    #define REP(i,j,k) for(int i=j;i<k;++i)
    Polynomial::Polynomial(const int &n, const int a[51]):greatestPower(n){
        REP(i,0,101) coefficients[i] = (i<=n) ? a[i] : 0;    
    }
    Polynomial Polynomial::operator + ( const Polynomial &a) const{
        Polynomial ans;
        ans.greatestPower = greatestPower > a.greatestPower ? greatestPower : a.greatestPower;
        REP(i,0,51) ans.coefficients[i] = coefficients[i] + a.coefficients[i];
        return ans;
    }
    Polynomial Polynomial::operator - ( const Polynomial &a) const{
        Polynomial ans;
        ans.greatestPower = greatestPower > a.greatestPower ? greatestPower : a.greatestPower;
        REP(i,0,51) ans.coefficients[i] = coefficients[i] - a.coefficients[i];
        return ans;
    }
    std::ostream &operator<<(std::ostream &os, const Polynomial &a){
        int n = a.greatestPower;
        while(n>=0){
            std::cout<<(a.coefficients[n]);
            if(n--) std::cout<<" ";
        }
        return os;
    }

:::
:::spoiler 11935 - double-end-queue

    #include "function.h"
    void _stack::push(const _node N){
        _node *o = new _node(N);
        o->prev = End->prev, End->prev->next = o;
        End->prev = o, o->next = End;
    }
    void _stack::pop(){
        if(Empty()==0) End = End->prev;
    }
    _node* _stack::get_data(){
        return Empty() ? NULL : End->prev;
    }
    void _queue::push(const _node N){
        _node *o = new _node(N);
        o->prev = End->prev, End->prev->next = o;
        End->prev = o, o->next = End;
    }
    void _queue::pop(){
        if(Empty()==0) Begin = Begin->next;
    }
    _node* _queue::get_data(){
        return Empty() ? NULL : Begin->next;
    }

:::
:::spoiler 13206 - Codec

    #include "function.h"
    using namespace std;
    class ReverseCodec : public BaseCodec{
    public:
        ReverseCodec(){}
        string encode(const string &s){ 
            string ans = "";
            for(int i=s.size()-1;i>=0;i--) ans += s[i];
            return ans;
        }
    };
    class CompressCodec : public BaseCodec{
    public:
        CompressCodec(){}
        string encode(const string &s){ 
            string ans = "";
            char la = ' ';
            int num = 0;
            for(int i=0;i<=s.size();i++){
                if(s[i]==la || num==0) num++;
                else if(num==1) ans += la, num = 1;
                else if(num==2) ans = ans + la + la, num = 1;
                else{
                    string a = "";
                    while(num) a = char('0'+num%10) + a, num/=10;
                    ans = ans + a + la, num = 1;
                }
                la = s[i];
            }
            return ans;
        }
    };
    class DelayCodec : public BaseCodec{
    public:
        DelayCodec():la(""){}
        string encode(const string &s){ 
            string ans = la=="" ? "None" : la;
            la = s;
            return ans;
        }
        string la;
    };
    BaseCodec* getCodec(const std::string& name){
        if(name=="Reverse") return new ReverseCodec;
        if(name=="Compress") return new CompressCodec;
        if(name=="Delay") return new DelayCodec;
    }

:::
:::spoiler 13207 - Happy Ball - Reverse

    #include "function.h"
    #include<iostream>
    using namespace std;
    void Array::move(int a){
        cur = max(1,min(size,cur + a * (rev ? -1 : 1)));
    }
    void Array::remove(){
        for(int i=cur;i<size;i++) mem[i] = mem[i+1];
        if(rev) cur--;
        size--, cur = max(1,min(cur,size));
    }
    void Array::reverse(){
        rev ^= 1;
    }
    void List::move(int a){
        if(a*(rev?-1:1)>0) while(a && cur->nxt) cur = cur->nxt , a -= (rev?-1:1);
        else while(a && cur->pre) cur = cur->pre, a += (rev?-1:1);
    }
    void List::remove(){
        cur = cur->remove(rev), size--;
    }
    void List::reverse(){
        rev ^= 1;
    }
    ContainerBase* create(int n, int *a, int op2, int op3){
        return (op2 > op3 ? (ContainerBase*)new Array(n,a) : (ContainerBase*)new List(n,a));
    }

:::
### [final](https://acm.cs.nthu.edu.tw/contest/2378/)
-
:::spoiler 12307 - anagram

    #include<bits/stdc++.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    using namespace std;
    int n;
    string s[1000005],t;
    map<string,int> m;
    int main(){
        cin>>n;
        REP(i,0,n){
            cin>>s[i], t = s[i];
            for(auto &u:t) if('A'<=u && u<='Z')	u = u-'A'+'a';
            sort(t.begin(),t.end());
            (m.find(t)!=m.end()) ? m[t]++ : m[t] = 1;
        }
        sort(s,s+n);
        REP(i,0,n){
            t = s[i];
            for(auto &u:t) if('A'<=u && u<='Z')	u = u-'A'+'a';
            sort(t.begin(),t.end());
            if(m[t]==1) cout<<s[i]<<"\n";
        }
    }

:::
## Homework
### [Winter](https://acm.cs.nthu.edu.tw/contest/2255/)
-
:::spoiler 10947 - delete linked list

    #include "function.h"

    void deleteNode(Node **nd, int data){
        Node *now = *nd, *last = NULL;
        while(now && --data) last = now, now = now->next;
        if(data==0 && now){
            if(last) last->next = now->next;                         //刪的不是頭 
            else *nd = (*nd)->next;                                  //如果刪的是頭 
            free(now);
        }
    }

    Node* createList(){
        Node *head = NULL, *now;
        int a;
        while(scanf("%d",&a) && a!=-1){
            if(head) now = now->next = (Node*)malloc(sizeof(Node));	 //不是頭 
            else now = head = (Node*)malloc(sizeof(Node));           //是頭 
            now->data = a, now->next = NULL;
        }
        return head;
    }

:::
:::spoiler 12602 - OuQ String

    #include<stdio.h>
    #define int long long                                                //注意溢位 
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define min(a,b) (a<b?a:b)
    #define max(a,b) (a>b?a:b)
    int k,l,r,len[55];
    void dfs(int level,int l,int r){
        if(level==0) return;                                                         
        if(l==0) printf("O"); 
        if(l<len[level]/2 && r>0) dfs(level-1,max(l-1,0),min(r,len[level-1])-1);     //注意r>0             
        if(l<=len[level]/2 && len[level]/2<=r) printf("u");
        if(len[level]/2<r && l<len[level]-1) dfs(level-1,max(l-len[level]/2-1,0),min(r-len[level]/2,len[level-1])-1);  //注意l<len[level]-1
        if(r==len[level]-1) printf("Q");
    }
    int main(){
        REP(i,1,51) len[i] = len[i-1]*2+3;
        while(scanf("%lld%lld%lld",&k,&l,&r)!=EOF){
            dfs(k,l,r);
            printf("\n");
        }
    }

:::
:::spoiler 12603 - Launch of Collider

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int n,ans=1e9,a[200005];
    char s[200005];
    int main(){
        scanf("%d%s",&n,s);
        REP(i,0,n){
            scanf("%d",&a[i]);
            if(i && s[i-1]=='R' && s[i]=='L' && (a[i]-a[i-1])/2<ans) ans = (a[i]-a[i-1])/2;
        }
        printf("%d\n",ans==1e9?-1:ans);
    }

:::
:::spoiler 12604 - N-Queens M-Rooks Problem

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int n,m,ans,col[10],dia[20],ndia[20];                   //col直排，dia左上右下斜，ndia右上左下斜，有沒有被擺過
    void dfs(int nn,int mm){                                //擺了nn個Queens，mm個Rooks 
        if(nn==n && mm==m) ans++;
        else{                                               //現在擺nn+mm行，這樣保證橫排不會撞到 
            REP(i,0,n+m){                                      
                if(col[i] + dia[i-nn-mm+n+m] + ndia[i+nn+mm] == 0 && nn<n){          //擺Queen  
                    col[i] = dia[i-nn-mm+n+m] = ndia[i+nn+mm] = m+1;                 //用m+1代表那排有Queen   
                    dfs(nn+1,mm); 
                    col[i] = dia[i-nn-mm+n+m] = ndia[i+nn+mm] = 0;
                }
                if(col[i] == 0 && dia[i-nn-mm+n+m]<m && ndia[i+nn+mm]<m && mm<m){    //擺Rook 
                    col[i]++, dia[i-nn-mm+n+m]++, ndia[i+nn+mm]++;                   //++代表那排有幾個Rook
                    dfs(nn,mm+1);
                    col[i]--, dia[i-nn-mm+n+m]--, ndia[i+nn+mm]--;
                }
            }
        }
    }
    int main(){
        while(scanf("%d%d",&n,&m)!=EOF){
            ans = 0, dfs(0,0);
            printf("%d\n",ans);
        }
    }

:::
:::spoiler 12605 - Rebranding

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define swap(a,b) a^=b^=a^=b
    int n,m,c[26],ans[26];
    char s[200005],a,b;
    int main(){
        REP(i,0,26) c[i] = i;
        scanf("%d%d%s",&n,&m,s);
        REP(i,0,m) scanf("%s%s",&a,&b), (a!=b?swap(c[b-'a'],c[a-'a']):0);
        REP(i,0,26) ans[c[i]] = i;
        REP(i,0,n) printf("%c",'a'+ans[s[i]-'a']);
        printf("\n");
    }

:::
:::spoiler 12606 - Happy New Year

    #include<stdio.h>
    int n,a,b,l,r;
    int main(){
        scanf("%d%d",&n,&a);
        while(n--){
            scanf("%d",&b);
            if(b-a>r) r = b-a;
            if(a-b>l) l = a-b;
        }
        printf("%d\n",l*2+r*2);
    }

:::
:::spoiler 12611 - The Same Calendar

    #include<stdio.h>
    int t,y,yy,num;
    int leap(int n){ return (n%400==0 ||(n%4==0 && n%100)); }
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d",&y), yy = y, num = 0;
            do{
                num += leap(yy) + 1, yy++;
            }while(num%7 || leap(yy)!=leap(y));
            printf("%d\n",yy);
        }
    }

:::
:::spoiler 12612 - Queries on a String

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int m,l,r,k;
    char s[10005],ss[10005];
    int main(){
        scanf("%s%d",&s,&m);
        while(m--){
            scanf("%d%d%d",&l,&r,&k), l--, r--;
            REP(i,l,r+1) ss[l+(i-l+k)%(r-l+1)] = s[i];
            REP(i,l,r+1) s[i] = ss[i];
        }
        printf("%s\n",s);
    }

:::
:::spoiler 12613 - Yet Another Meme Problem

    #include<stdio.h>
    int t,a,b,ans,num;
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&a,&b), ans = 0, num = 9;
            for(ans=0;num<=b;ans++) num = num*10+9;
            printf("%lld\n",(long long)a*ans);
        }
    }

:::
:::spoiler 12614 - Game Shopping

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int n,m,a[1005],b[1005],p;
    int main(){
        scanf("%d%d",&n,&m);
        REP(i,0,n) scanf("%d",&a[i]);
        REP(i,0,m) scanf("%d",&b[i]);
        REP(i,0,n) if(p<m && b[p]>=a[i]) p++;
        printf("%d\n",p);
    }

:::
:::spoiler 12615 - Knight Search

    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int n,dx[8]={2,1,-1,-2,-2,-1,1,2},dy[8]={-1,-2,-2,-1,1,2,2,1};
    char s[105][105],c[11]="ICPCASIASG";
    int dfs(int x,int y,int p){
        if(p==10) return 1;
        REP(i,0,8){
            int nx = dx[i]+x, ny = dy[i]+y;
            if(0<=nx && nx<n && 0<=ny && ny<n && s[nx][ny]==c[p]) 
                if(dfs(nx,ny,p+1)) return 1;
        }
        return 0;
    }
    int main(){
        scanf("%d\n",&n);
        REP(i,0,n) REP(j,0,n) scanf("%c",&s[i][j]);
        REP(i,0,n) REP(j,0,n) if(s[i][j]=='I'){
            if(dfs(i,j,1)){
                printf("YES\n");
                return 0;
            }
        }
        printf("NO\n");
    }

:::
### [HW1](https://acm.cs.nthu.edu.tw/contest/2267/)
-
:::spoiler 12680 - Card Magic

    #include "function.h"
    #include<stdlib.h>
    Node* ReadOneList(){
        Node *a = (Node*)malloc(sizeof(Node));
        scanf("%d:",&a->size);
        a->data = (int*)malloc(sizeof(int)*a->size);
        for(int i=0;i<a->size;i++) scanf("%d",&a->data[i]);
        a->next = NULL;
        return a;
    };
    void PrintList(Node* now){
        while(now->next){
            now = now->next;
            for(int i=0;i<now->size;i++) printf("%d%c",now->data[i],i==now->size-1?'\n':' ');
        }
    }
    void Merge(Node* head, int pa, int pb){
        int cnt = 0;
        Node *a,*b,*last = head;          //last 是a的前一個
        while(head){
            head = head->next, cnt++;
            if(cnt==pa) a = head;         //找a
            if(cnt<pa) last = head;       //找a的前一個
            if(cnt==pb) b = head;         //找b
        }
        int *bdata = b->data;                     //先複製b的data
        b->data = (int*)malloc(sizeof(int)*(a->size+b->size));     //將b開大
        for(int i=0;i<b->size;i++) b->data[i] = bdata[i];
        for(int i=0;i<a->size;i++) b->data[i+b->size] = a->data[i];
        last->next = a->next, b->size += a->size, free(a->data), free(a), free(bdata);      //將a的前面街上後面
    }
    void Cut(Node* head, int pa, int x){
        while(pa--) head = head->next;     
        Node *a = (Node*)malloc(sizeof(Node));
        a->size = head->size-x, a->data = (int*)malloc(sizeof(int)*a->size);
        for(int i=0;i<a->size;i++) a->data[i] = head->data[x+i];
        head->size = x, a->next = head->next, head->next = a; 
    }

:::
:::spoiler 12668 - Text Editor - Linked List Version

    #include<stdio.h>
    #include<stdlib.h>
    int t,n;
    char s[1000005];
    typedef struct _Node{
        char c;
        struct _Node *l, *r;
    }Node;
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%s",&n,s);
            Node *head = (Node*)malloc(sizeof(Node)), *now = head, *tmp;
            head->l = head->r = NULL;
            for(int i=0;i<n;i++){
                if(s[i]=='L') now = now->l;
                else if(s[i]=='R') now = now->r;
                else if(s[i]=='B'){
                    tmp = now, now->l->r = now->r;
                    if(now->r) now->r->l = now->l;                //now->r有可能為空 
                    now = now->l;
                    free(tmp);
                }
                else{
                    Node *N = (Node*)malloc(sizeof(Node));
                    if(now->r!=NULL) now->r->l = N;                     //now->r有可能為空 
                    N->c = s[i], N->l = now, N->r = now->r, now->r = N, now = now->r;
                }
            }
            while(head->r) head = head->r, printf("%c",head->c), free(head->l);
            printf("\n");
        }
    }

    #include<stdio.h>              //陣列寫法
    #define MX 1000005
    int t,n,l[MX],r[MX],now;
    char s[MX];
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%s",&n,s), now = 0;
            for(int i=0;i<MX;i++) l[i] = r[i] = 0;
            for(int i=0;i<n;i++){
                if(s[i]=='L') now = l[now];
                else if(s[i]=='R') now = r[now];
                else if(s[i]=='B') r[l[now]] = r[now], l[r[now]] = l[now], now = l[now];
                else l[r[now]] = i+1, l[i+1] = now, r[i+1] = r[now], r[now] = i+1, now = r[now];
            }
            now = 0;
            while(r[now]) now = r[now], printf("%c",s[now-1]);
            printf("\n");
        }
    }

:::
:::spoiler 13133 - Got You! JerryFish!

    #include "function.h"                                  //複雜度O(N*Q)           
    void createLinkedList(Node **head, int N, int *arr){
        Node *now = (Node*)malloc(sizeof(Node));
        now->val = arr[1], *head = now;                    //注意main裡arr下標從1開始 
        for(int i=2;i<=N;i++) now->next = (Node*)malloc(sizeof(Node)), now = now->next, now->val = arr[i];
        now->next = *head;
    }
    void swapTwoSegment(Node **head, int a, int b, int len){
        Node *A = *head,*B = *head;          
        while(--a) A = A->next;                       
        while(--b) B = B->next;                   
        while(len--){
            int tmp = A->val;
            A->val = B->val, B->val = tmp, A = A->next, B = B->next;
        }
    }

:::
:::spoiler 13134 - Band Ya Rou Ze

    #include<stdio.h>
    #include<stdlib.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    typedef struct _{
        char *c;
        struct _ *r;
    }Node; 
    Node *rh[100005],*re[100005],*tmp;              //rh紀錄每行開頭，re結尾，沒東西為NULL
    int n,a,b,c,t;            
    int main(){
        scanf("%d",&n);
        REP(i,1,n+1){
            scanf("%d",&a); rh[i] = re[i] = NULL;
            if(a){
                rh[i] = re[i] = (Node*)malloc(sizeof(Node));
                rh[i]->c = (char*)malloc(sizeof(char)*(a+1));      //注意
                scanf("%s",rh[i]->c), rh[i]->r = NULL;
            }
        }
        scanf("%d",&t);
        while(t--){
            scanf("%d%d%d",&c,&a,&b);
            if(c==1 && re[a]){
                if(rh[b]==NULL) re[b] = re[a];                            //注意
                re[a]->r = rh[b], rh[b] = rh[a], rh[a] = re[a] = NULL;
            }
            if(c==2 && re[a]){
                if(rh[b]==NULL) rh[b] = rh[a], re[b] = re[a], rh[a] = re[a] = NULL;
                else re[b]->r = rh[a], re[b] = re[a], rh[a] = re[a] = NULL;
            }
            if(c==3) tmp = rh[a], rh[a] = rh[b], rh[b] = tmp, tmp = re[a], re[a] = re[b], re[b] = tmp;
        }
        REP(i,1,n+1){
            while(rh[i]!=NULL) printf("%s",rh[i]->c), rh[i] = rh[i]->r;
            printf("\n");
        }
    }

    #include<stdio.h>                                     //陣列寫法 
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define MX 2000005
    #define swap(a,b) a^=b^=a^=b
    int n,a,b,c,rh[100005],re[100005],r[MX],p;            //rh紀錄每行開頭，re結尾，沒東西為0 
    char s[MX];
    int main(){
        scanf("%d",&n);
        REP(i,1,n+1){
            scanf(" %d ",&a), rh[i] = (a?p+1:0), re[i] = (a?p+a:0);         //p為字串s下標 
            REP(i,0,a) scanf("%c",&s[++p]), i?r[p-1] = p:0;
        }  
        scanf("%d",&p);                                                     //重複利用p變數 
        while(p--){
            scanf("%d%d%d",&c,&a,&b);
            if(c==1 && re[a]){
                if(rh[b]==0) re[b] = re[a];                                 //注意 
                r[re[a]] = rh[b], rh[b] = rh[a], rh[a] = re[a] = 0;
            }
            if(c==2 && re[a]){
                if(rh[b]==0) rh[b] = rh[a], re[b] = re[a], rh[a] = re[a] = 0;
                else r[re[b]] = rh[a], re[b] = re[a], rh[a] = re[a] = 0;
            }
            if(c==3) swap(rh[a],rh[b]), swap(re[a],re[b]);
        }
        REP(i,1,n+1){
            while(rh[i]) printf("%c",s[rh[i]]), rh[i] = r[rh[i]];
            printf("\n");
        }
    }

:::
### [HW2](https://acm.cs.nthu.edu.tw/contest/2283/)
-
:::spoiler 10966 - Infix to syntax tree

    #include "function.h"
    #include <stdlib.h>
    BTNode* FACTOR();                             //因為EXPR()呼叫的時候還沒定義
    BTNode* makeNode(char c){
        BTNode *head = (BTNode*)malloc(sizeof(BTNode));
        for(int i=0;i<6;i++) if(sym[i]==c) head->data = (TokenSet)i;
        head->left = head->right = NULL;
        return head;
    }
    BTNode* EXPR(){
        BTNode *r = FACTOR(); pos--;
        if(pos==-1 || expr[pos]=='(') return r;
        BTNode *head = makeNode(expr[pos]); pos--;
        head->right = r, head->left = EXPR();
        return head;
    } 
    BTNode* FACTOR(){
        if(expr[pos]==')'){ pos--; return EXPR();}
        return makeNode(expr[pos]);
    }

:::
:::spoiler 10968 - Prefix to infix

    #include "function.h"
    void printInfix(Node *root){
        if(root->left) printInfix(root->left);
        printf("%c",root->data);
        if(root->right)
            if(root->right->data=='|' || root->right->data=='&')
                printf("("), printInfix(root->right), printf(")");
            else printInfix(root->right);
    }

:::
:::spoiler 10972 - Remove unnecessary parentheses

    #include<bits/stdc++.h>                     //c++ 括號匹配寫法
    using namespace std;
    stack<int> r;                               //右括號的位置stack   
    string s; 
    int main(){
        cin>>s;
        for(int i=s.size()-1;i>=0;i--)
            if(s[i]=='('){                      //第一個括號or連續的左括號or只括一字 可以刪
                if(i==0 || s[i-1]=='(' || i+2==r.top()) s[i] = s[r.top()] = 'K';
                r.pop();
            }
            else if(s[i]==')') r.push(i);
        for(int i=0;i<s.size();i++) if(s[i]!='K') cout<<s[i];
    }

:::
:::spoiler 11847 - Prefix Boolean expression

    #include<stdio.h>
    int n,num;
    char s[35];
    int f(){
        int a,b;
        if(s[n]=='&')      n++, a = f(), n++, b = f(), a &= b;
        else if(s[n]=='|') n++, a = f(), n++, b = f(), a |= b;
        else a = (num>>(3-s[n]+'A')) & 1;
        return a;
    }
    int main(){
        scanf("%s",&s);
        for(num=0;num<16;num++) printf("%d %d %d %d %d\n",(num>>3)&1,(num>>2)&1,(num>>1)&1,num&1,f()), n = 0;
    }
    :::
    :::spoiler 13139 - Binary Patrick Star   

#include"function.h"
#include<stdlib.h>
Node* buildBinaryTree(int n, int* l, int* r){
Node *T = (Node*)malloc(sizeof(Node)*n);
for(int i=0;i<n;i++)
T[i].id = i, T[i].left = (l[i]!=-1)?&T[l[i]]:NULL, T[i].right = (r[i]!=-1)?&T[r[i]]:NULL;
return T;
}
void Traversal(Node* o, int* sz){
sz[o->id] = 1;
if(o->left) Traversal(o->left, sz), sz[o->id] += sz[o->left->id];
if(o->right) Traversal(o->right, sz), sz[o->id] += sz[o->right->id];
}
void freeBinaryTree(Node* o){
free(o);
}

    :::
    :::spoiler 13140 - Wubalubadubdub   

#include<stdio.h>
int a[200005],n;
void dfs(int l,int r){
if(l>r) return;
printf("%s%d",(r!=n-2?" ":""),a[r]);
int ll = l, rr = r, mid;
while(ll<rr){ //二分搜
mid = (ll+rr)/2;
if(a[mid]<a[r]) ll = mid+1;
else rr = mid;
}
dfs(l,ll-1), dfs(ll,r-1);
}
int main(){
while(~scanf("%d",&a[n++]));
dfs(0,n-2);
printf("\n");
}

    :::
### [mid1](https://acm.cs.nthu.edu.tw/contest/2293/)
-
    :::spoiler 11840 - Moving books   

#include<stdio.h>
#define REP(i,j,k) for(int i=j;i<k;i++)
int n,a,b,table[30][30],book[30],top[30]; //table: 桌子上的書，book: 每本在哪張，top: 每桌高度
char s[5],t[5];
void move(int a,int b){ //move a to b, if b==0 mean go home
int ok = 0, A = book[a], sz = top[A]; //ok: 在a上(包含a), A: a的桌子
REP(i,0,sz){
if(table[A][i]==a) ok = 1;
if(ok && (table[A][i]!=a || b)){
int home = (b?book[b]:table[A][i]);
table[home][top[home]] = table[A][i], book[table[A][i]] = home,
top[home]++, top[A]--, table[A][i] = 0;
}
}
}
int main(){
scanf("%d",&n);
REP(i,1,n+1) table[i][0] = book[i] = i, top[i] = 1;
while(scanf("%s",s) && s[0]!='e'){
scanf("%d%s%d",&a,t,&b), a++, b++;
if(book[a]==book[b]) continue;
if(s[0]=='m') move(a,0);
if(t[1]=='n') move(b,0);
move(a,b);
}
REP(i,0,n){
printf("%d:",i);
REP(j,0,top[i+1]) printf(" %d",table[i+1][j]-1);
printf("\n");
}
}

    :::
    :::spoiler 11891 - Postfix to Syntax Tree   

#include "function.h"
void constructTree(Node** head){
Node *o = (Node*)malloc(sizeof(Node));
o->data = s2[idx++], o->right = o->left = NULL, *head = o;
if(o->data=='|' || o->data=='&') constructTree(&o->right), constructTree(&o->left);
}

    :::
    :::spoiler 12720 - Binary search trees II: pruning   

#include<stdio.h>
#define REP(i,j,k) for(int i=j;i<k;i++)
#define MX 100005
int n,a,o,val[MX],L[MX],R[MX];
char c[3];
int dfs(int o, int no, int l, int r){ //現在節點，壞掉，合理上下界
if(val[o]<=l || r<=val[o]) no = 1;
int lvl = 0, lvr = 0; //左右子樹的level
if(L[o]) lvl = dfs(L[o], no, l, val[o]);
if(R[o]) lvr = dfs(R[o], no, val[o], r);
lvl = (lvl>lvr?lvl:lvr) + 1;
if(no) val[o] = -lvl;
return lvl;
}
int main(){
scanf("%d",&n);
REP(i,1,n+1) scanf("%d",&val[i]);
REP(i,1,n+1){
scanf("%d",&a);
if(!a) o = i;
else scanf("%s",c), c[0]=='L' ? (L[a] = i) : (R[a] = i);
}
dfs(o,0,-1e9-5,1e9+5);
REP(i,1,n+1) printf("%d%c",val[i],(i==n?'\n':' '));
}

    :::
    :::spoiler 12725 - Minimum Spinning Tree   

#include<stdio.h>
#define MX 300005
int ans=1e9,l[MX],r[MX],num[MX],p=1,L,R;
char s[MX];
void calc(int now){
if(s[now]=='+') num[now] = num[l[now]] + num[r[now]];
if(s[now]=='-') num[now] = num[l[now]] - num[r[now]];
if(s[now]=='*') num[now] = num[l[now]] * num[r[now]];
}
int dfs(){ //p:字串s下標
int now = p;
if(s[now]<'0') p++, l[now] = dfs(), p++, r[now] = dfs(), calc(now);
else num[now] = s[now]-'0';
return now;
}
int main(){
scanf("%d%s",&p,s+1), p = 1; //p:字串s下標
dfs(), ans = num[1], p = 1; //p:現在為頭
while(l[p] && s[l[p]]<'0'){ //往左走到底
L = l[p], l[p] = r[L], calc(p); //L:左邊新頭
r[L] = p, calc(L), p = L;
if(num[p]<ans) ans = num[p];
}
while(r[p] &&s[r[p]]<'0'){ //往右走到底
R = r[p], r[p] = l[R], calc(p); //R:右邊新頭
l[R] = p, calc(R), p = R;
if(num[p]<ans) ans = num[p];
}
printf("%d\n",ans);
}

    :::
    :::spoiler 13154 - Bee cover rain   

#include<stdio.h>
#define MX 5000005
int p,q,pos;
char s[MX];
int dfs(){
int x,y,num=0;
if(s[pos]=='f') pos += 2, x = dfs(), pos++, y = dfs(), pos++, num = ((long long)p*x+y)%q;
else while('0'<=s[pos] && s[pos]<='9') num = num*10+s[pos]-'0', pos++;
return num;
}
int main(){
scanf("%lld%lld%s",&p,&q,s);
printf("%lld\n",dfs());
}

    :::
    :::spoiler 13155 - Maxmax tree operation   

#include"function.h"
#include<stdlib.h>
struct Graph* createGraph(int n){
struct Graph *G = (struct Graph*)malloc(sizeof(struct Graph));
G->adjLists = (struct Node**)malloc(sizeof(struct Node*)*n);
for(int i=0;i<n;i++) G->adjLists[i] = NULL;
G->vertices_num = n;
return G;
}
void addEdge(struct Graph* G, int a, int b){
struct Node *it = G->adjLists[a];
G->adjLists[a] = (struct Node*)malloc(sizeof(struct Node));
G->adjLists[a]->id = b, G->adjLists[a]->next = it;
it = G->adjLists[b];
G->adjLists[b] = (struct Node*)malloc(sizeof(struct Node));
G->adjLists[b]->id = a, G->adjLists[b]->next = it;
}
int findMax(struct Graph* G, int now, int pre){
int ans = now, a;
for(struct Node *it=G->adjLists[now];it;it=it->next) if(it->id!=pre)
a = findMax(G,it->id,now), a>ans ? ans=a : 0;
return ans;
}
void freeGraph(struct Graph* G){
for(int i=0;i<G->vertices_num;i++)
for(struct Node *it=G->adjLists[i];it;){
struct Node *nt = it->next;
free(it), it = nt;
}
free(G->adjLists);
free(G);
}

    :::
### [HW3](https://acm.cs.nthu.edu.tw/contest/2313/)
-
    :::spoiler 10993 - Polynomial class   

#include "function.h"
#define REP(i,j,k) for(int i=j;i<k;++i)
Polynomial::Polynomial(){
REP(i,0,101) coefficients[i] = 0;
};
Polynomial::Polynomial(const int n, const int a[51]):greatestPower(n){
REP(i,0,101) coefficients[i] = (i<=n) ? a[i] : 0;
}
Polynomial Polynomial::add(const Polynomial a) const{
Polynomial ans;
ans.greatestPower = greatestPower > a.greatestPower ? greatestPower : a.greatestPower;
REP(i,0,51) ans.coefficients[i] = coefficients[i] + a.coefficients[i];
return ans;
}
Polynomial Polynomial::subtract( const Polynomial a) const{
Polynomial ans;
ans.greatestPower = greatestPower > a.greatestPower ? greatestPower : a.greatestPower;
REP(i,0,51) ans.coefficients[i] = coefficients[i] - a.coefficients[i];
return ans;
}
Polynomial Polynomial::multiplication( const Polynomial a) const{
Polynomial ans;
ans.greatestPower = greatestPower + a.greatestPower;
REP(i,0,51) REP(j,0,51) ans.coefficients[i+j] += coefficients[i] * a.coefficients[j];
return ans;
}
void Polynomial::output() const{
int n = greatestPower;
while(n>=0){
std::cout<<(coefficients[n]);
if(n--) std::cout<<" ";
}
}

    :::
    :::spoiler 10998 - Stack   

#include "function.h"
List_stack::List_stack():head(NULL),tail(NULL){}
List_stack::~List_stack(){};
void List_stack::push(const int &a){
ListNode *o = new ListNode(a);
o->prevPtr = tail, tail = o;
}
void List_stack::pop(){
if(tail==NULL) return;
ListNode *o = tail;
tail = tail->prevPtr;
delete o;
}
void List_stack::print(){
ListNode *o = tail;
while(o){
std::cout<<(o->data);
o = o->prevPtr;
if(o) std::cout<<" ";
}
}

    :::
    :::spoiler 13178 - Band Ya Rou Ze - Reverse Classtarburst   

#include<iostream>
#include"function.h"
Node::~Node(){
Node *ne = neighbors[(neighbors[0] == nullptr ? 1 : 0)];
if(ne) ne->unLink(this), delete ne;
}
void List::init(std::string s){
if(s=="") head = tail = nullptr;
else{
head = tail = new Node(s[0]);
for(int i=1;i<s.size();i++){
Node *o = new Node(s[i]);
o->link(tail), tail->link(o), tail = o;
}
}
}
void List::merge(List &front, List &back){
if(front.tail==nullptr) head = back.head, tail = back.tail;
else if(back.tail==nullptr) head = front.head, tail = front.tail;
else
front.tail->link(back.head), back.head->link(front.tail),
head = front.head, tail = back.tail;
}
void List::swap(List &swapList){
std::swap(head, swapList.head), std::swap(tail, swapList.tail);
}
void List::reverse(){
std::swap(head, tail);
}
List::~List(){
delete head;
}

    :::
### [HW4](https://acm.cs.nthu.edu.tw/contest/2337/)
-
    :::spoiler 11417 - String Operation   

#include "function.h"
Str::Str(char *s){
head = tail = new Char(s[0]);
for(int i=1;s[i]!='\0';i++) tail = tail->next = new Char(s[i]);
}
Str::Str(const Str &s){
head = tail = new Char(s.head->text);
Char *o = s.head->next;
while(o) tail = tail->next = new Char(o->text), o = o->next;
}
Str& Str::strInsert(const Str &s){
Str *ss = new Str(s);
tail->next = ss->head, tail = ss->tail;
return *this;
}

    :::
    :::spoiler 12753 - Go on mission   

#include "function.h"
#include<string.h>
BigInt::BigInt():sign(1){ //sign 1為正
for(int i=0;i<N;i++) bigInt[i] = 0;
}
BigInt::BigInt(char *s):sign(1){
for(int i=0;i<N;i++) bigInt[i] = 0;
int len = strlen(s), n = 0;
for(int i = len-1; i >= 0 ;i -= WIDTH, n++) //逆著存
for(int j = WIDTH-1; j >= 0; j--)
if(i-j>=0) bigInt[n] = bigInt[n]*10+s[i-j]-'0';
}
BigInt::BigInt(const BigInt &a){
*this = a;
}
BigInt& BigInt::operator = (const BigInt &a){
sign = a.sign;
for(int i=0;i<N;i++) bigInt[i] = a.bigInt[i];
return *this;
}
bool BigInt::operator < (BigInt a){ //注意正負
if(sign != a.sign) return sign < a.sign;
for(int i=N-1;i>=0;i--)
if(bigInt[i] < a.bigInt[i]) return sign;
else if(bigInt[i] > a.bigInt[i]) return 1^sign;
return 0;
}
bool BigInt::operator == (BigInt a){
return !(*this < a) && !(a < *this);
}
bool BigInt::operator >= (BigInt a){
return a < *this || a == *this;
}
BigInt BigInt::operator + (BigInt a){ //用來處理負+負 ***我把+當做+=用***
for(int i=0;i<N-1;i++)
bigInt[i] += a.bigInt[i], bigInt[i+1] += bigInt[i]/BASE, bigInt[i] %= BASE;
return *this;
}
BigInt BigInt::operator - (BigInt a){ //輸入保證a為正 ***我把-當做-=用***
if(sign)
if(*this < a) *this = a - *this, sign = 0;
else
for(int i=0;i<N;i++){
bigInt[i] -= a.bigInt[i];
if(bigInt[i] < 0) bigInt[i] += BASE, bigInt[i+1] -= 1;
}
else *this + a;
return *this;
}
istream& operator >> (istream &input, BigInt &a){
char s[BigInt::N * BigInt::WIDTH + 5];
input >> s, a = BigInt(s);
return input;
}
ostream& operator << (ostream &ouput, BigInt &a){
if(a.sign==0) ouput<<"-";
int n = BigInt::N-1, first = 1;
while(n && a.bigInt[n]==0) n--;
while(n>=0)
if(first) printf("%d",a.bigInt[n--]), first = 0;
else printf("%08d",a.bigInt[n--]);
return ouput;
}

void solution(BigInt &tanjiro, BigInt &zenitsu, BigInt &inosuke, int n){
while(n--){
BigInt a;
cin>>a;
if(inosuke >= tanjiro && inosuke >= zenitsu) inosuke - a;
else if(tanjiro >= zenitsu) tanjiro - a;
else zenitsu - a;
}
}

    :::
    :::spoiler 13199 - Vector Implementation   

#include"function.h"
using namespace oj;
Vector::~Vector(){ clear(), delete [] arr_; }

Vector::Vector():size_(0),cap_(0),arr_(nullptr){}

Vector::Vector(const Vector &rhs):size_(0),arr_(nullptr){ *this = rhs; }

Vector& Vector::operator = (const Vector &rhs){
clear(), delete [] arr_;
size_ = rhs.size_, cap_ = rhs.cap_, arr_ = new value_type*[cap_];
for(int i=0;i<size_;i++) arr_[i] = new value_type(rhs.arr_[i][0]);
return *this;
}
reference Vector::front(){ return arr_[0][0]; }

reference Vector::back(){ return arr_[size_-1][0]; }

reference Vector::operator[](size_type pos){ return arr_[pos][0]; }

const_reference Vector::operator[](size_type pos) const{ return arr_[pos][0]; }

size_type Vector::capacity() const{ return cap_; }

size_type Vector::size() const{ return size_; }

void Vector::clear(){
for(int i=0;i<size_;i++) delete arr_[i];
size_ = 0;
}
bool Vector::empty() const{ return size_==0; }

void Vector::erase(size_type pos){
delete arr_[pos], size_--;
for(int i=pos;i<size_;i++) arr_[i] = arr_[i+1];
}
void Vector::insert(size_type pos, size_type cnt, const_reference val){
size_type c = (cap_==0 ? 1 : cap_);
while(c<size_+cnt) c*=2;
reserve(c), size_ += cnt;
for(int i=size_-1;i>=pos+cnt;i--) arr_[i] = arr_[i-cnt];
for(int i=0;i<cnt;i++) arr_[pos+i] = new value_type(val);
}
void Vector::pop_back(){ erase(size_-1); }

void Vector::pop_front(){ erase(0); }

void Vector::push_back(const_reference val){ insert(size_, 1, val); }

void Vector::push_front(const_reference val){ insert(0, 1, val); }

void Vector::reserve(size_type new_capacity){
if(cap_ >= new_capacity) return;
value_type **tmp = new value_type*[cap_ = new_capacity];
for(int i=0;i<size_;i++) tmp[i] = arr_[i];
delete [] arr_, arr_ = tmp;
}
void Vector::shrink_to_fit(){ cap_ = 0, reserve(size_); }

    :::
### [mid2](https://acm.cs.nthu.edu.tw/contest/2342/)
-
    :::spoiler 11021 - Encoding and decoding   

#include "function.h"
void RleCodec::encode(){
std::string s = "";
char c = ' '; //c 同樣的字
int num = 0;
code_str += ' '; //要處理最後一組
for(char u:code_str)
if(u==c || num==0) num++, c = u; //num < 'A' 處理最開始
else{
while(num>=26) s = s + "QZ" + c, num -= 26;
if(num) s = s + 'Q' + char('A'+num-1) + c;
num = 1, c = u;
}
code_str = s, encoded = true;
}
void RleCodec::decode()
{
std::string s = "";
int num = 0, ok = 0;
for(char u:code_str)
if(!ok) ok = 1;
else if(num){
while(num) s += u, num--;
ok = 0;
}
else num = u-'A'+1;
code_str = s, encoded = false;
}

    :::
    :::spoiler 12224 - Doubly Linked List   

#include "function.h"
void List::InsertHead(int data){
if(head){
head->prev = new ListNode(data);
head->prev->next = head;
head = head->prev;
cnt++;
if(cnt%2) middle = middle->prev;
}
else head = tail = middle = new ListNode(data), cnt++;
}
int List::RemoveHead(){
if(head){
ListNode *o = head;
int a = head->data;
head = head->next;
if(head) head->prev = nullptr;
else tail = nullptr;
delete o;
cnt--;
if(cnt%2==0) middle = middle->next;
return a;
}
else throw std::out_of_range("\n");
}
void List::InsertTail(int data){
if(head){
tail->next = new ListNode(data);;
tail->next->prev = tail;
tail = tail->next;
cnt++;
if(cnt%2==0) middle = middle->next;
}
else head = tail = middle = new ListNode(data), cnt++;
}
int List::RemoveTail(){
if(head){
ListNode *o = tail;
int a = tail->data;
tail = tail->prev;
if(tail) tail->next = nullptr;
else head = middle = nullptr;
delete o;
cnt--;
if(cnt%2) middle = middle->prev;
return a;
}
else throw std::out_of_range("\n");
}
void List::Swap(){
if(cnt<=1) return;
head->prev = tail, tail->next = head, tail = middle->prev;
std::swap(head, middle);
if(cnt%2) middle = middle->prev;
head->prev = tail->next = nullptr;
}
:::
:::spoiler 12257 - Only children make choice!

    #include "function.h"
    Animal::Animal(Zoo *zoo, string name):belong(zoo),species(name){ 
        belong->born(species);
    }
    Dog::Dog(Zoo *zoo):Animal(zoo, "Dog"){}
    Dog::~Dog(){}
    Cat::Cat(Zoo *zoo):Animal(zoo, "Cat"){}
    Cat::~Cat(){}
    Caog::Caog(Zoo *zoo):Dog(zoo),Cat(zoo),Animal(zoo, "Caog"){}
    void Caog::barking(){ cout << "woof!woof!meow!\n";}
    void Caog :: carton(){ cout << "it looks so happy!\n";}
    void Caog ::throwBall(){ cout << "it looks happy!\n";}
    Caog::~Caog(){}

:::
:::spoiler 13205 - Happy Ball

    #include "function.h"
    #include<iostream>
    using namespace std;
    void Array::move(int a){
        cur = max(1,min(size,cur+a));
    }
    void Array::remove(){
        for(int i=cur;i<size;i++) mem[i] = mem[i+1];
        size--, cur = min(cur,size);
    }
    void List::move(int a){
        if(a>0) while(a-- && cur->getNxt()) cur = cur->getNxt();
        else if(a<0) while(a++ && cur->getPre()) cur = cur->getPre();
    }
    void List::remove(){
        cur = cur->remove(), size--;            //size要--destruct會用到
    }
    ContainerBase* create(int n, int *a, int q, Operation *op){
        int op2 = 0, op3 = 0;
        for(int i=1;i<=q;i++)
            if(op[i].type == 2) op2++;
            else if(op[i].type == 3) op3++;
        return (op2 > op3 ? (ContainerBase*)new Array(n,a) : (ContainerBase*)new List(n,a));
    }

    #include "function.h"
    #include <iostream>
    #include <ext/rope>
    using namespace std;
    using namespace __gnu_cxx;
    void Array::move(int a){}
    void Array::remove(){}
    void List::move(int a){}
    void List::remove(){} 
    ContainerBase* create(int n, int *a, int q, Operation *op){
        rope<int> R;
        for(int i=1;i<=n;i++) R.push_back(a[i]);
        int p = 1, ma = n;
        for(int i=1;i<=q;i++){
            if(op[i].type == 1) cout<<R[p-1]<<"\n", op[i].type = 24;
            else if(op[i].type == 2) p += op[i].d, p = max(min(p,ma),1);
            else R.erase(p-1,1), ma--, p = min(p,ma);
        }
        return new Array(n,a);
    }

:::
### [HW5](https://acm.cs.nthu.edu.tw/contest/2359/)
-
:::spoiler 11447 - Use std::map

    #include "function.h"
    #include <iostream>
    #include <set>
    namespace oj{
        void insert(std::map<int,String> &ma, int key, const std::string &str){
            std::string s = str;
            if(ma.find(key)!=ma.end()) s = str + ma.find(key)->second.str, ma.erase(key);
            ma.insert(std::pair<int,String>(key,String(s)));

        void output(const std::map<int,String> &ma,int begin,int end){
            for(auto i:ma) if(begin<=i.first && i.first<=end) std::cout<<i.second<<' ';
        }
        void erase(std::map<int,String> &ma,int begin,int end){
            std::set<int> de;
            for(auto i:ma) if(begin<=i.first && i.first<=end) de.insert(i.first);
            for(auto i:de) ma.erase(i);
        }
        std::ostream& operator<<(std::ostream &o,const std::map<int,String> &ma){
            for(auto i:ma) o<<i.second<<' '; return o;
        }
    }

:::
:::spoiler 11485 - Use std::set

    #include<bits/stdc++.h>
    using namespace std;
    int a,num,num2;
    string s;
    map<int,vector<int>> m;
    main(){
        while(cin>>s){
            if(s=="insert"){
                vector<int> v;		
                while(cin>>a && a) v.push_back(a);
                num = 0;
                for(int i=0;i<v.size();i++) num += (v.size()-i)*v[i];
                if(m.find(num)!=m.end()){
                    cout<<"exist\n";
                    m.erase(num);
                    reverse(v.begin(),v.end());
                    num = 0;
                    for(int i=0;i<v.size();i++) num += (v.size()-i)*v[i];
                }
                m[num] = v;
            }
            if(s=="range_out"){
                vector<int> v,v2;		
                while(cin>>a && a) v.push_back(a);
                while(cin>>a && a) v2.push_back(a);
                num = num2 = 0;
                for(int i=0;i<v.size();i++) num += (v.size()-i)*v[i];
                for(int i=0;i<v2.size();i++) num2 += (v2.size()-i)*v2[i];
                for(auto u:m) if(num<=u.first && u.first<=num2){
                    for(auto uu:u.second) cout<<uu<<" ";
                    cout<<"\n"; 
                }
            }
            if(s=="output"){
                for(auto u:m){
                    for(auto uu:u.second) cout<<uu<<" ";
                    cout<<"\n"; 
                }
            }
        }
    }

:::
:::spoiler 13218 - BBPoints

    #include<bits/stdc++.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    #define ll long long
    #define P pair<ll,ll>
    #define F first
    #define S second
    using namespace std;
    ll n,q,t,ans[100005],a,b,c; 
    int main(){
        cin>>n>>q;
        set<P> s;             				 //first: y, second: x
        REP(i,1,n+1) s.insert(P(0,i)); 
        while(q--){
            cin>>t>>a>>b;		
            if(t==1) s.erase(P(ans[a],a)), ans[a] += b, s.insert(P(ans[a],a));
            else{
                cin>>c;
                auto p = s.lower_bound(P(b,a));
                if(p!=s.end() && (*p).F==b && (*p).S<=a+c) 
                    ans[(*p).S] -= (*p).S-a, s.erase(p), s.insert(P(ans[(*p).S],(*p).S));
            }
        }
        REP(i,1,n+1){
            cout<<ans[i];
            if(i!=n) cout<<" ";
        }
        cout<<"\n";
    }

:::
:::spoiler 13219 - BFS - Practice

    #include<bits/stdc++.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    #define P pair<int,int>
    using namespace std;
    int n,m,dx[4]={0,0,-1,1},dy[4]={1,-1,0,0},x,y,ex,ey; 
    queue<P> q;
    int main(){
        cin>>n>>m;
        vector<vector<int>> d(n+2,vector<int>(m+2,100005));       //d: 從起點到每點最短距離 
        vector<vector<char>> c(n+2,vector<char>(m+2)); 
        REP(i,1,n+1) REP(j,1,m+1) cin>>c[i][j];
        cin>>x>>y>>ex>>ey, d[x][y] = 0, q.push(P(x,y));
        while(q.size()){
            x = q.front().first, y = q.front().second; q.pop();
            for(int i=0;i<4;i++){
                int nx = x+dx[i], ny = y+dy[i];
                if(d[x][y]+1 < d[nx][ny] && 0<nx && nx<=n && 0<ny && ny<=m && c[nx][ny]=='0') 
                    d[nx][ny] = d[x][y]+1, q.push(P(nx,ny));
            }
        }
        cout<<(d[ex][ey]==100005?-1:d[ex][ey])<<"\n";	
    }

:::
### [final](https://acm.cs.nthu.edu.tw/contest/2371/)
-
:::spoiler 12264 - NPK-easy

    #include<bits/stdc++.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    using namespace std;
    int n,a,in[3];                     //in: i國家在x對列嗎 
    queue<int> x,y[3];                 //x: 所有的，y: 各國的 
    string s;
    int main(){
        cin>>n;
        while(n--){
            cin>>s;
            if(s=="ENQUEUE"){
                cin>>a, y[a%3].push(a);
                if(in[a%3]==0) x.push(a%3), in[a%3] = 1;
            }
            else{
                cout<<y[x.front()].front()<<"\n", y[x.front()].pop();
                if(y[x.front()].size()==0) in[x.front()] = 0, x.pop();
            }
        } 
    }

:::
:::spoiler 12306 - beat the monster

    #include<bits/stdc++.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    using namespace std;
    int l,hp,mhp,mdmg,dmg[20],hl[20],s[20][305][405];
    struct node{
        int l,hp,mhp,cnt;                           //cnt: 經過幾回合 
    };
    queue<node> q;
    int main(){
        cin>>l>>hp>>mhp>>mdmg;
        REP(i,0,l) cin>>dmg[i]>>hl[i];
        q.push(node{0,hp,mhp,0});
        while(q.size()){
            node o = q.front(); q.pop();
            if(o.mhp==0) return cout<<o.cnt<<"\n",0;
            if((o.hp-mdmg>0 || o.mhp-dmg[o.l]<=0) && s[o.l][max(0,o.hp-mdmg)][max(0,o.mhp-dmg[o.l])]==0){
                q.push(node{o.l, o.hp-mdmg, max(0,o.mhp-dmg[o.l]), o.cnt+1});         //攻擊
                s[o.l][max(0,o.hp-mdmg)][max(0,o.mhp-dmg[o.l])]++;
            }
            if(min(hp,o.hp+hl[o.l])-mdmg>0 && s[o.l][min(hp,o.hp+hl[o.l])-mdmg][o.mhp]==0){
                q.push(node{o.l, min(hp,o.hp+hl[o.l])-mdmg, o.mhp, o.cnt+1});         //回血
                s[o.l][min(hp,o.hp+hl[o.l])-mdmg][o.mhp]++;
            }
            if(o.hp-mdmg>0 && o.l+1<l && s[o.l+1][o.hp-mdmg][o.mhp]==0){
                q.push(node{o.l+1, o.hp-mdmg, o.mhp, o.cnt+1});                       //升級 
                s[o.l+1][o.hp-mdmg][o.mhp]++;
            }
        }
        cout<<-1<<"\n";
    }

:::
:::spoiler 12819 - 15 Puzzle

:::
:::spoiler 13239 - Co-Board

    #include<bits/stdc++.h>
    #define P pair<vector<int>,int>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    using namespace std;
    int t,cnt;
    int main(){
        cin>>t;
        while(t--){
            vector<int> a(8),b(8),c(8),cc(8);
            queue<P> q;
            set<vector<int>> s;                              //看有沒有重複 狀態最多8! 
            cin>>a[0]>>a[1]>>a[2]>>a[7]>>a[3]>>a[6]>>a[5]>>a[4];
            cin>>b[0]>>b[1]>>b[2]>>b[7]>>b[3]>>b[6]>>b[5]>>b[4];
            q.push(P(a,0));
            while(q.size()){
                c = q.front().first, cnt = q.front().second;
                if(c==b) break;
                q.pop();
                REP(i,0,8) cc[i] = c[(i+7)%8];               //1
                if(s.find(cc)==s.end()){
                    s.insert(cc);
                    q.push(P(cc,cnt+1));
                }
                REP(i,0,8){                                  //2
                    REP(j,0,8) cc[j] = c[j];
                    swap(cc[i],cc[(i+1)%8]);
                    if(s.find(cc)==s.end()){
                        s.insert(cc);
                        q.push(P(cc,cnt+1));
                    }
                }
                REP(i,0,4){                                  //3
                    REP(j,0,8) cc[j] = c[j];
                    swap(cc[i],cc[i+4]);
                    if(s.find(cc)==s.end()){
                        s.insert(cc);
                        q.push(P(cc,cnt+1));
                    }
                }
            }
            cout<<(c==b?cnt:-1)<<"\n";
        }
    }

:::