---
# System prepended metadata

title: APCS 衝刺班

---

# APCS 衝刺班

## 筆記
![](https://i.imgur.com/0McqKvc.png)

* 萬用表頭: `#include <bits/stdc++.h>`

* 加速運行:
    ```
    ios::sync_with_stdio(0);
    cin.tie(0); 
    ```
    * `cin` 和 `scanf` / `sscanf` 混用時不可寫上述兩行

* int to string: `to_string()`

* string to int: `stoi()`

* 類似py的`map()`的功能: `sscanf(str, "%d:%d:%d", &var1, &var2, &var3)`
    * 相關概念用法
    
    | 輸入用符號   | 含意     |
    | --------   | -------- |
    | `%d`       |十進位制有符號整數|
    | `%u`       |進位制無符號整數|
    | `%f`       |浮點數|
    | `%s`       |字串|
    | `%c`       |單個字元|
    | `%p`       |指標的值|
    | `%e`       |指數形式的浮點數|
    | `%x`,` %X` |無符號以十六進位制表示的整數 |
    | `%0`       |無符號以八進位制表示的整數|
    | `%g`       |自動選擇合適的表示法|
    | `%ld`      |表示輸出long int|
    | `%ld`      |表示輸出double|


* 取得整行
    ```
    string s;
    getline (cin, s);
    // type of s is string
    ```
    或
    ```
    char cs[256];
    cin.getline (cs, sizeof(cs));
    // type of cs is char[]
    ```
    
* 字串相關
    ```cpp=
    s.size()和s.length() 會傳回字串的長度
    s[0]指的是字串的第一個字元，s[s.size()-1]指的是字串的最後一個字元
    isalpha(字元x);  //判斷是不是a~z，A~Z，傳回true或false
    isdigit(字元x);  //判斷是不是0~9，傳回true或false
    isupper(字元x);  //判斷是不是大寫字母，傳回true或false
    islower(字元x);  //判斷是不是小寫字母，傳回true或false
    toupper(字元x);  //轉成大寫字母
    tolower(字元x);  //轉成小寫字母
    reverse(s.begin(), s.end()); //將字串s反轉
    s.find('a');  //傳回字元a在字串s中第1次被發現的位置(引索值從0開始)
    " "雙引號，括起來的是字串，可以是很多個字元，例如："abc123"
    ' ' 單引號，括起來的是字元，只能放1個，例如：'a'或'1'
    ```


## a096: 時間差計算
```cpp=
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    
    char str[10];
    int h, m, s;
    
    while( cin.getline(str,10) ){
        
        sscanf(str, "%d:%d:%d", &h, &m, &s);
        int t1 = h*3600 + m*60 + s;
        
        cin.getline(str,10);
        sscanf(str, "%d:%d:%d", &h, &m, &s);
        int t2 = h*3600 + m*60 + s;
        int dif = (86400 + t2 - t1) % 86400;
        
        string h = to_string(dif/3600);
        string m = to_string( (dif%3600)/60 );
        string s = to_string( (dif%3600)%60 );
        
        if( h.length() == 1 ){
            h = '0' + h;
        }
        if( m.length() == 1 ){
            m = '0' + m;
        }
        if( s.length() == 1 ){
            s = '0' + s;
        }
        
        cout<< h << ':' << m << ':' << s;
    }
    
    return 0;
}
```

## a064: 成績指標
```cpp=
#include <iostream>
#include <algorithm>
using namespace  std;

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

    if(arr[0] >= 60){               //best
        for(int i=0; i<times; i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;
        
        cout<<"best case"<<endl;
        cout<<arr[0]<<endl;

    }else if(arr[times-1] < 60){      //worst
        for(int i=0; i<times; i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;

        cout<<arr[times-1]<<endl;
        cout<<"worst case"<<endl;

    }else{
        for(int i=0; i<times; i++){
            cout<<arr[i]<<" ";
        }
        cout<<endl;

        for(int i=0; i<times; i++){
            if(arr[i] < 60 && arr[i+1] >= 60){
                cout<<arr[i]<<endl;
                cout<<arr[i+1]<<endl;
            }
        }
    }
}
```

## a104: 雪花片片
聽不懂 還沒寫

## a144: 找出最小的完全平方
```cpp=
#include <bits/stdc++.h>
using namespace std;

bool even( long long a ) {
    while( a > 0 ) {
        if( ( a % 10 ) % 2 == 1 ) return false;
        else a /= 10;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , k;
    cin >> n;
    while( n-- ) {
        cin >> k;
        int s = (int)sqrt( pow( 10 , k - 1 ) );
        int e = (int)sqrt( pow( 10 , k ) );
        for( int i = s ; i <= e ; i++ ) {
            long long a = i * i;
            if( even(a) ) {
                cout << a << endl;
                break;
            }
        }
    }
}
```

## a116: 一起回家的日子
```cpp=
#include <bits/stdc++.h>
using namespace std;

bool check_year(int year){
    if ( (year % 4 == 0) && (year % 100 != 0) || (year % 400 == 0) ) return true;
    return false;
}

int main() {
    int n, a;
    
    cin>>n;
    cin>>a;
    n--;
    
    while(n){
        int x; cin>>x;
        a = a * x / __gcd(a, x);
        n--;        // originally didn't write this line, resulting in CE
    }
    
    char date[12];
    int month_days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    scanf("%s", date);
    int y, m ,d;
    
    sscanf(date, "%d/%d/%d", &y, &m, &d);
    d += a;
    
    while( d > month_days[m] ){
        d -= month_days[m];
        if( m==12 ){
            y++; m=1;
            
        }else if( m<12 && m>0 ){
            if( check_year(y) && m==2 ) d--;
            m++;
        }
    }
    
    cout<<y <<"/";
    
    if( m<10 ) cout<<0;
    cout<<m <<"/";
    
    if(d<10) cout<<0;
    cout<<d;
}
```

## a157: 費波那契數列
```cpp=
#include <bits/stdc++.h>
using namespace std;

int fib( int d ) {
    if ( d == 0 ) return 0;  
    if ( d == 1 ) return 1;  
    return fib(d - 1) + fib(d - 2);  
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    while( cin >> n ) cout << fib(n) << endl;
}
```

## a117: 三色河內塔
WRONG 沒考慮三色
```cpp=
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;

void move_all(int n, char from, char to, char by){
    if(n <= 0) return;
    
    move_all(n-1, from, by, to);
    cout<< "ring " << n << " : " << from << " => " << to << '\n';
    cnt++;
    move_all(n-1, by, to, from);
    
}

void move(int n, char from, char to, char by){
    if(n <= 0) return;
    
    move_all(n-1, from, by, to);
    cout << "ring " << n << " : " << to << " => " << by << '\n';
    cnt++;
    
    move(n-2, by, from, to);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin>>n;
    
    move(n, 'A', 'C', 'B');
    cout<< "共需" << cnt << "個移動";
    return 0;
}

```


## a118: 指數2^k的四個自然數平方和之所有表示法
```cpp=
#include <bits/stdc++.h>
using namespace std;
int sq[65536] = {};
int solutions, num[4];

void solve(int remain, int id){
    if( id == 3 ){
        int n = sqrt(remain);
        if( sq[n] == remain ){
            solutions++;
            num[3] = n;
            cout<<num[0]<<' '<<num[1]<<' '<<num[2]<<' '<<num[3]<<"\n";
        }
        return;
    }
    int lbound;
    if( id > 0 ) lbound = num[id - 1];
    else lbound = 1;
    int ubound = sqrt( remain / ( 4 - id ) );
    for( int i = lbound ; i <= ubound ; i++ ) {
        num[id] = i;
        solve( remain - sq[i] , id + 1 );
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    for( int i = 1 ; i < 65536 ; i++ ) sq[i] = i * i;
    cin >> k;
    solutions = 0;
    solve( 1 << k , 0 );
    if( solutions == 0 ) cout << 0; 
}
```

## a147: 促銷活動
NA (97%)
```cpp=
#include <iostream>
using namespace std;

void discount(int p1, int p2){
    if( p1 == p2 ){
        p2 = p1 / 2;
    }
    
    cout << "Price after discount:" << endl;
    cout << p1 << " " << p2 << endl;
    return;
}


int main(){
    double p1, p2;
    cout << "Original price:" << endl;
    cin >> p1 >> p2;
    
    discount(p1, p2);
    
    return 0;
}
```


## a159: 錯誤更正
```cpp=
#include <bits/stdc++.h>
using namespace std;

int a[100][100];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while( cin >> n ) {
        if( n == 0 ) return 0;
        int rsum[100] = {0} , csum[100] = {0};
        for( int i = 0 ; i < n ; i++ ) {
            for( int j = 0 ; j < n ; j++ ) {
                cin >> a[i][j];
                rsum[i] += a[i][j];
                csum[j] += a[i][j];
            }
        }
        int rcnt = 0 , ccnt = 0;
        int ci = -1 , cj = -1;
        for( int i = 0 ; i < n ; i++ ) {
            if( rsum[i] % 2 ) {
                rcnt++;
                ci = i;
            }
            if( csum[i] % 2 ) {
                ccnt++;
                cj = i;
            }
        }
        if( ( rcnt == 0 ) && ( ccnt == 0 ) ) cout << "OK\n";
        else if( ( rcnt == 1 ) && ( ccnt == 1 ) ) cout << "Change bit (" << ci + 1 << ',' << cj + 1 << ')' << endl;
        else cout << "Corrupt" << endl;
    } 
}
```


## a105: 爺爺種樹
```cpp=
#include <bits/stdc++.h>
using namespace std;

int t[501][501];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , m , row;
    cin >> n >> m >> row;
    int r1 , c1 , r2 , c2;
    memset( t , 0 , sizeof(t) );
    for( int i = 0 ; i < row ; i++ ) {
        cin >> c1 >> r1 >> c2 >> r2;
        int dr = r2 - r1 , dc = c2 - c1;
        if( dr > 0 ) dr = 1;
        else if( dr < 0 ) dr = -1;
        if( dc > 0 ) dc = 1;
        else if( dc < 0 ) dc = -1;
        t[r2][c2] = 1;
        if( r1 == r2 ) {
            for( int c = c1 ; c != c2 ; c += dc ) t[r1][c] = 1;
        } else {
            for( int r = r1 , c = c1 ; r != r2 ; r += dr , c += dc ) {
                t[r][c] = 1;
            }
        }
    }
    int tsum = 0;
    for( int r = 1 ; r <= m ; r++ ) {
        for( int c = 1 ; c <= n ; c++ ) tsum += t[r][c];
    }
    cout << tsum;
}
```

## a106: 冰果遊戲
```cpp=
#include <bits/stdc++.h>
using namespace std;

int n;
char name[100] = {0} , line[100][10] = {0};
pair<int , int> mp[100][16];

bool check( int i , int p ) {
    int r = mp[i][p].first;
    int c = mp[i][p].second;
    line[i][r]++;
    if( line[i][r] == 4 ) return true;
    line[i][c + 4]++;
    if( line[i][c + 4] == 4 ) return true;
    if( ( r + c ) == 3 ) {
        line[i][8]++;
        if( line[i][8] == 4 ) return true;
    }
    if( r == c ) {
        line[i][9]++;
        if( line[i][9] == 4 ) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    char ch;
    int v;
    cin >> ch >> n;
    for( int i = 0 ; i < n ; i++ ) {
        cin >> name[i];
        for( int j = 0 ; j < 16 ; j++ ) {
            cin >> v;
            mp[i][v].first = j / 4;
            mp[i][v].second = j % 4;
        }
    }
    char cp;
    int p , cnt = 16;
    bool stop = false;
    cin >> cp;
    while( cnt-- ) {
        cin >> p;
        cout << p << " ";
        for( int i = 0 ; i < n ; i++ ) {
            if( check( i , p ) ) {
                cout << name[i] << " ";
                stop = true;
            }
        }
        if( stop ) return 0;
    }
}
```

## a107: 加密解密
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

string a = "abcdefghijklmnoprstuvwxyz";
string b = "EXAMPLBCDFGHIJKNORSTUVWYZ";

int main(){
    int n;
    string s;
    cin>>n;
    getline(cin, s);    // read enter
    getline(cin, s);
    reverse(s.begin(), s.end());
    
    for(int i=0; i<s.size(); i+=2){
        string f, t;
        if( s[0]>='a' && s[0]<='z' ){
            f = a; t = b;
        }else{
            f = b; t = a;
        }
        
        int p1 = f.find(s[i]);
        int p2 = f.find(s[i+1]);
        
        int i1 = p1 / 5;
        int j1 = p1 % 5;
        int i2 = p2 / 5;
        int j2 = p2 % 5;
        
        cout<<t[i1*5 + j2]<<t[i2*5 + j1];
    }
}
```

## a065: 秘密差
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    string x;
    while(cin>>x){
        int ans = 0, sign = 1;
        for(int i=0; i<x.size(); i++){
            ans += (x[i] - '0') * sign;
            sign *= -1;
            
        }

        cout<<abs(ans)<<'\n';
    }
}
```

## a067: ROT13
```cpp=
#include <iostream>
using namespace std;

int main(){
    string s;
    while(getline(cin, s)){
        for(auto c: s){ // get each char c from s
            if( isupper(c) ){
                cout<<(char)( (c-'A'+13) % 26 + 'A');
                
            }else if( islower(c) ){
                cout<<(char)( (c-'a'+13) % 26 + 'a');
               
            }else cout<<c;
        }
    }
}
```

## a109: 跑長編碼與資料壓縮
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    string s , binary[8] = { "000" , "001" , "010" , "011" , "100" , "101" , "110" , "111" };
    cin >> n;
    cin.ignore();
    while( n-- ) {
        getline( cin , s );
        string t = "";
        int ori = s.length();
        int after = 0;
        int times = 1;
        char ch = s[0];
        if( ch != '0' && ch != '1' ) {
            cout << "-1" << endl;
            continue;
        }
        for( int i = 1 ; i <= s.length() ; i++ ) {
            if( i != s.length() && s[i] != '0' && s[i] != '1' ) {
                after = -1;
                break;
            } 
            if( s[i] != ch ) {
                t += ch;
                t += binary[times];
                t += " ";
                times = 1;
                ch = s[i];
                after += 4;
            } else {
                times++;
                if( times == 7 ) {
                    t += ch;
                    t += binary[times];
                    t += " ";
                    times = 1;
                    after += 4;
                    ch = s[i + 1];
                    i++;
                }
            }
        }
    if( after == -1 ) cout << "-1" << endl;
    else cout << t << setprecision(0) << fixed << (double)after * 100 / ori << "%" << endl;    
    }
}
```

## a105 計算字串間隔距離
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    char ch;
    cin >> s >> ch;
    int a1;
    ch = toupper(ch);
    for( int i = 0 ; i < s.length() ; i++ ) {
        if( toupper(s[i]) == ch ) {
            a1 = i;
            break;
        }
    }
    int a2;
    for( int i = a1 + 1 ; i < s.length() ; i++ ) {
        if( toupper(s[i]) == ch ) {
            a2 = i;
            cout << a2 - a1 << ' ';
            a1 = a2;
        } 
    } 
}
```

## a110: 棒球遊戲
```cpp=
#include <bits/stdc++.h>
using namespace std;
map < int , queue<string> > mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a , b;
    for( int i = 0 ; i < 9 ; i++ ) {
        cin >> a;
        string s;
        while( a-- ) {
            cin >> s;
            mp[i].push(s);
        }
    }
    cin >> b;
    int out = 0;
    int b1 = 0 , b2 = 0 , b3 = 0 , b4 = 0;
    int score = 0;
    int n = -1;
    while(1) {
        int t = 0;
        n = ( n + 1 ) % 9;
        string hit = mp[n].front();
        mp[n].pop();
        if( hit == "SO" || hit == "GO" || hit == "FO" ) {
            out++;
            if( out == b ) break;
            if( out % 3 == 0 ) {
                b1 = b2 = b3 = b4 = 0;
                continue;
            }
        } else if( hit == "HR" ) t = 4;
        else t = hit[0] - '0';
        for( int i = 1 ; i <= t ; i++ ) {
            b4 = b3;
            b3 = b2;
            b2 = b1;
            if( i == 1 ) b1 = 1;
            else b1 = 0;
            if( b4 == 1 ) score++;
        } 
    }
    cout << score;
}
```

## a180: 多邊形面積
```cpp=
#include <bits/stdc++.h>
using namespace std;

struct Coor{
    double x;
    double y;
};

int main(){
    int n;
    Coor coor[100];
    cin>>n;
    for(int i=0; i<n; i++){
        cin >> coor[i].x >> coor[i].y;
    }
    
    double area;
    for(int i=0; i<n; i++){
        if( i== n-1 ){
            area += (coor[i].x) * (coor[0].y) - (coor[0].x) * (coor[i].y);
    
        }else{
            area += (coor[i].x) * (coor[i+1].y) - (coor[i+1].x) * (coor[i].y);
        }
    }
    
    area = abs(0.5 * area);
    cout<< setprecision(2) << fixed << area;
    
}
```

## a113: 99遊戲
```cpp=
#include <bits/stdc++.h>
using namespace std;

map < int , queue<string> > mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    for( int i = 0 ; i < 4 ; i++ ) {
        char x;
        cin >> x;
        for( int j = 0 ; j < 13 ; j++ ) {
            string s;
            cin >> s;
            mp[x - 'A'].push(s);
        }
    }
    int id = 0;
    int dir = 1;
    int sum = 0;
    while( sum <= 99 ) {
        string card = mp[id].front();
        if( card == "A" ) sum = 0;
        else if( card == "4" ) dir *= -1;
        else if( card == "5" ) ;
        else if( card == "10" ) {
            sum += 10;
            if( sum > 99 ) sum -= 20; 
        } else if( card == "J" ) ;
        else if( card == "Q" ) {
            sum += 20;
            if( sum > 99 ) sum -= 40; 
        }
        else if( card == "K" ) sum = 99;
        else {
            sum += card[0] - '0';
            if( sum > 99 ) {
                cout << char( 'A' + id ) << endl << mp[id].size() - 1 << endl;
                break;
            }
        }
        mp[id].pop();
        if( mp[id].empty() ) {
            cout << char( 'A' + id ) << endl << sum << endl;
            break;
        }
        id = ( id + dir + 4 ) % 4;
    }    
}
```

## a111: 排隊
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int t[1000][3];
    int lineup = 0;
    int ans = 0;
    int now_service = 0;
    cin >> n >> t[0][0] >> t[0][1];
    t[0][2] = t[0][0] + t[0][1];
    for( int i = 1 ; i < n ; i++ ) {
        cin >> t[i][0] >> t[i][1];
        if( t[i][0] < t[i - 1][2] ) {
            t[i][2] = t[i - 1][2] + t[i][1];
        } else {
            t[i][2] = t[i][0] + t[i][1];
        }
        if( t[i][0] >= t[now_service][2] ) {
            ans = max( ans , lineup );
            while( t[i][0] >= t[now_service][2] ) {
                if( now_service == i ) break;
                lineup--;
                now_service++;
            }
        }
        if( t[i][0] < t[now_service][2] ) {
            lineup++;
        }
    }
    ans = max( ans , lineup );
    cout << ans;
}
```

## a112: 動物數量統計
```cpp=
#include <bits/stdc++.h>
using namespace std;
map < string , queue< pair< string , int > > > mp;

int main() {
    int n;
    vector <string> pcmp;
    cin >> n;
    while( n-- ) {
        string an , p;
        int qu , idx;
        cin >> an >> qu >> p;
        idx = find( pcmp.begin() , pcmp.end() , p ) - pcmp.begin();
        if( idx == pcmp.size() ) pcmp.push_back(p);
        mp[p].push( {an , qu} );
    } 
    for( auto i : pcmp ) {
        cout << i << ":";
        map < string , int > sta;
        vector <string> almp;
        while( !mp[i].empty() ) {
            string an = mp[i].front().first;
            int qu = mp[i].front().second;
            mp[i].pop();
            int idx = find( almp.begin() , almp.end() , an ) - almp.begin();
            if( idx == almp.size() ) almp.push_back(an);
            if( sta.count(an) == 0 ) sta[an] = qu;
            else sta[an] += qu; 
        }
        bool comma = false;
        for( auto j : almp ) {
            if( comma ) cout << ",";
            cout << j << " " << sta[j];
            comma = true;
        }
        cout << endl; 
    }
}
```

## a151: 後序式求值
```cpp=
#include <bits/stdc++.h>
using namespace std;
map < string , queue< pair< string , int > > > mp;

int main() {
    string s;
    while( getline(cin, s) ){
        stack<int> st;
        int ans = 0;
        
        for(int i=0; i<s.size(); i++){
            if( isdigit(s[i]) ){
                st.push( s[i] - '0' );
            }else {
                int a = st.top();
                st.pop();
                int b = st.top();
                st.pop();
                if( s[i] == '+' ) st.push( b + a );
                else if( s[i] == '-' ) st.push( b - a );
                else if( s[i] == '*' ) st.push( b * a );
                else if( s[i] == '/' ) st.push( b / a );
                else if( s[i] == '%' ) st.push( b % a );
            }
        }
        cout << st.top() << endl;
    }
}
```

## a120: 中置式轉後置式
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    map < char , int > mp = { {'+' , 1} , { '+' , 1 } };
    mp['+'] = 1;
    mp['-'] = 1;
    mp['*'] = 2; 
    mp['/'] = 2;
    string s;
    cin >> s;
    stack <char> st;
    for( int i = 0 ; i < s.size() ; i++ ) {
        if( s[i] == '(' ) st.push( '(' );
        else if( s[i] == ')' ) {
            while( st.top() != '(' ) {
                cout << st.top();
                st.pop();
            }
            st.pop();
        } else if( s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
            while( !st.empty() && mp[st.top()] >= mp[s[i]] ) {
                cout << st.top();
                st.pop();
            } 
            st.push(s[i]);
        } else {
            cout << s[i];
        }
    }
    while(!st.empty()) {
        cout << st.top();
        st.pop();
    } 
}
```

## a164: 團體佇列
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t , c = 0;
    while( cin >> t ) {
        if( t == 0 ) break;
        map < int , int > mp;
        for( int i = 0 , n , x ; i < t ; i++ ) {
            cin >> n;
            while( n-- ) {
                cin >> x;
                mp[x] = i;
            }
        }
        queue <int> Q;
        queue <int> t[1000];
        int in[1000] = {0};
        string cmd;
        cout << "Scenario #" << ++c << endl;
        while( cin >> cmd ) {
            int x;
            if( cmd[0] == 'E' ) {
                cin >> x;
                if( in[mp[x]] == 0 ) Q.push( mp[x] );
                t[mp[x]].push(x);
                in[mp[x]]++;
            } else if( cmd[0] == 'D' ) {
                int team = Q.front();
                cout << t[team].front() << endl;
                t[team].pop();
                in[team]--;
                if( in[team] == 0 ) Q.pop();
            } else if( cmd[0] == 'S' ) {
                cout << endl;
                break;
            }
        }
    }
}
```

## a076: 二元搜尋樹高度
```cpp=
#include <bits/stdc++.h>
using namespace std;

bool tree[2049];
int D;

int drop( int v ) {
    if( v >= 1 << ( D - 1 ) ) return v;
    tree[v] = !tree[v];
    if( tree[v] ) return drop( 2 * v );
    else return drop( 2 * v + 1 );
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t , I;
    cin >> t;
    while( t-- ) {
        memset( tree , 0 , sizeof(tree) );
        cin >> D >> I;
        int ans;
        for( int i = 0 ; i < I ; i++ ) ans = drop(1);
        cout << ans << endl;
    }
}
```

## a122: 血緣關係

solution 1
```cpp=
#include <bits/stdc++.h>
using namespace std;

map <int , vector<int>> G;
int d[100005];

void dfs( int x , int fa ) {
    for( auto i : G[x] ) {
        if( i != fa ) {
            d[i] = d[x] + 1;
            dfs( i , x );
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int a , b;
    for( int i = 1 ; i <= n - 1 ; i++ ) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    d[0] = 0;
    dfs( 0 , 0 );
    int u = 0;
    for( int i = 1 ; i < n ; i++ ) u = ( d[i] > d[u] ) ? i : u;
    d[u] = 0;
    dfs( u , u );
    int v = u;
    for( int i = 0 ; i < n ; i++ ) v = ( d[i] > d[v] ) ? i : v; 
    cout << d[v];
}
```

solution 2
```cpp=
#include <bits/stdc++.h>
using namespace std;
map <int , vector<int>> T;
int ans = 0;

int dfs( int x , int px ) {
    int h1 = 0 , h2 = 0;
    for( auto i : T[x] ) {
        int h = dfs( i , x ) + 1;
        if( h > h1 ) {
            h2 = h1;
            h1 = h;
        } else if( h > h2 ) h2 = h; 
    }
    ans = max( ans , h1 + h2 );
    return h1;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , a , b;
    cin >> n;
    vector <int> fa( n , -1 );
    for( int i = 1 ; i <= n - 1 ; i++ ) {
        cin >> a >> b;
        T[a].push_back(b);
        fa[b] = a;
    }
    int root = 0;
    while(fa[root] != -1 ) root++;
    dfs( root , root );
    cout << ans;
}
```

## a123 樹狀圖分析
```cpp=
#include <bits/stdc++.h>
using namespace std;

map <int , vector<int>> T;
vector <int> fa( 100005 , -1 );
int h[100005];

void dfs( int x ) {
    int mx = 0;
    for( auto p : T[x] ) {
        dfs(p);
        mx = max( mx , h[p] + 1 );
    }
    h[x] = mx;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , k , v;
    cin >> n;
    for( int i = 1 ; i <= n ; i++ ) {
        cin >> k;
        for( int j = 0 ; j < k ; j++ ) {
            cin >> v;
            T[i].push_back(v);
            fa[v] = i;
        }
    }
    int root = 1;
    while( fa[root] != -1 ) root++;
    dfs(root);
    int ans = 0;
    for( int i = 1 ; i <= n ; i++ ) ans += h[i];
    cout << root << endl << ans;
}
```

## a051: 城市旅遊
```cpp=
#include <bits/stdc++.h>
using namespace std;

char G[801][10001];
int n;

bool dfs( int from , int to ) {
    if( G[from][to] == '1' ) return true;
    for( int i = 1 ; i <= n ; i++ ) {
        if( G[from][i] == '1' ) {
            G[from][i] = -1; 
            return dfs( i , to );
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m , x , y , a , b;
    cin >> n >> m;
    memset( G , 0 , sizeof(G) );
    for( int i = 0 ; i < m ; i++ ) {
        cin >> x >> y;
        G[x][y] = '1';
    }
    cin >> a >> b;
    if( dfs( a , b ) ) cout << "Yes";
    else cout << "No";
}
```

## a103: 小群體
```cpp=
#include <bits/stdc++.h>
using namespace std;

int a[50001] = {0};
bool visited[50001] = {0};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for( int i = 0 ; i < n ; i++ ) cin >> a[i];
    int next , ans = 0;
    for( int i = 0 ; i < n ; i++ ) {
        if( !visited[i] ) ans++;
        while( !visited[i] ) {
            next = a[i];
            visited[i] = true;
            i = next;
        }
    }
    cout << ans;
}
```

## a124: 二分圖
```cpp=
#include <bits/stdc++.h>
using namespace std;

vector <int> G[100001];
int color[100001] , cnt[2];

bool dfs( int x , int c ) {
    color[x] = c;
    cnt[c]++;
    bool result = true;
    for( int i : G[x] ) {
        if( color[i] == color[x] ) return false;
        else if( color[i] == -1 ) result &= dfs( i , !c );
    } 
    return result;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , m , ans = 0;
    cin >> n >> m;
    memset( color , -1 , sizeof(color) );
    for( int i = 0 , a , b ; i < m ; i++ ) {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    } 
    for( int i = 0 ; i < n ; i++ ) {
        if( color[i] == -1 ) {
            cnt[0] = cnt[1] = 0;
            if( !dfs( i , 0 ) ) {
                cout << 0;
                return 0;
            } 
            ans += min( cnt[0] , cnt[1] );
        }
    }
    cout << ans;
}
```

## a126: 馬步問題
```cpp=
#include <bits/stdc++.h>
using namespace std;
int n;
bool visit[3][10] , found;
int answer[30];
int temp[30];

bool smaller() {
    for( int i = 0 ; i < 3 * n ; i++ ) {
        if( temp[i] < answer[i] ) return true;
        else if( temp[i] > answer[i] ) return false;
    }
    return false;
}

bool inrange( int x , int y ) {
     return x >= 0 && x < 3 && y >= 0 && y < n;
}

void dfs( int row , int col , int step ) {
    int dir[8][2] = { {-2 , 1} , {-2 , -1} , {2 , 1} , {2 , -1} , {1 , 2} , {1 , -2} , {-1 , 2} , {-1 , -2} };
    temp[row * n + col] = step;
    visit[row][col] = true;
    if( step == 3 * n ) {
        if( !found || smaller() ) {
            for( int i = 0 ; i < 3 * n ; i++ ) answer[i] = temp[i];
        }
        found = true;
        return;
    }
    for( int i = 0 ; i < 8 ; i++ ) {
        int x = row + dir[i][0];
        int y = col + dir[i][1];
        if( inrange( x , y ) && !visit[x][y] ) {
            dfs( x , y , step + 1 );
            visit[x][y] = false;
        }
    } 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    found = false;
    dfs( 0 , 0 , 1 );
    if( !found ) cout << 0;
    else {
        for( int i = 0 ; i < 3 * n ; i++ ) cout << answer[i] << ' ';
    }
}
```

## a127: 連號或不連號 
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while( cin>>n ){
        set <int> st;
        for( int i=0, x; i<n; i++ ){
            cin>>x;
            st.insert(x);
            
        }
        
        int mn = *st.begin();
        int mx = *(--st.end()); //st.end()是st結束的位置 所以最大值是st.end()的前一個位置
        
        if( st.size() == mx - mn + 1) cout<<mn<<' '<<mx<<' '<<"yes";
        else cout<< mn<<' '<<mx<<' '<<"no";
    }
}
```

## 字元頻率

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

bool cmp( pair<int , int> x , pair<int , int> y ) {
	if( x.second == y.second ) return ( x.first > y.first );
	else return ( x.second < y.second );
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    while( getline( cin , s ) ) {
    	map <int , int> mp;
    	vector <pair <int , int>> vec;
		for( auto c : s ) mp[c]++;
		for( auto x : mp ) vec.push_back(x);
		sort( vec.begin() , vec.end() , cmp );
		for( auto v : vec ) cout << v.first << ' ' << v.second << endl; 
	}
}
```cpp=
#include <bits/stdc++.h>
using namespace std;

int f[10001];
map <int , set<int>> mp;

void eat( int win , int lose ) {
	for( auto i : mp[lose] ) mp[win].insert(i);
	mp[lose].clear();
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , m;
	cin >> n >> m;
	fill( f , f + n + 1 , 10 );
	for( int i = 1 ; i <= n ; i++ ) mp[i].insert(i);
	int x = 0;
	while(m--) {
		int a , b , win , lose;
		cin >> a >> b;
		win = ( f[a] >= f[b] ) ? a : b;
		lose = ( f[a] >= f[b] ) ? b : a;
		f[win] += f[lose];
		f[lose] = 0;
		if( f[win] > f[x] ) x = win;
		eat( win , lose );
	} 
	cout << x << endl;
	for( auto i : mp[x] ) cout << i << ' ';
}
```

## a129: 飛天桑妮
```cpp=
#include <bits/stdc++.h>
using namespace std;

vector <pair<int , int>> tree;

bool cmp( pair<int , int> a , pair<int , int> b )  {
	if( a.first == b.first ) return ( a.second > b.second );
	else return ( a.first < b.first );
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , x , y , h;
    cin >> n;
    for( int i = 0 ; i < n ; i++ ) {
    	cin >> x >> y >> h;
    	tree.push_back({ x * x + y * y , h });
	}
	sort( tree.begin() , tree.end() , cmp );
	int ans = 0 , maxh = 0;
	for( int i = 0 ;  i < n ; i++ ) {
		maxh = max( maxh , tree[i].second );
		ans = max( ans , maxh - tree[i].second ); 
	}
	cout << ans;
}
```