APCS進階班第2次模擬考解答
===

10038
題目：http://luckycat.kshs.kh.edu.tw/homework/q10038.htm
觀念：bruteforce (DFS)
難度：luckycat ★

#include <bits/stdc++.h>
using namespace std; 
int N, input[3005];
bool used[3005];
int main(){

    while ( cin >> N ){

        bool isJolly = true;

        for ( int i = 0 ; i < N ; i++ ){
            used[i] = false;
            cin >> input[i];
        }
            
        for ( int i = 1 ; i < N ; i++ ){
            int offset = abs( input[i] - input[i-1] );
            if ( offset > 0 && offset < N ){
                // 如果該距離已存在，代表不符合jolly格式    
                if ( !used[offset] )
                    used[offset] = true;
                else{
                    isJolly = false;
                    break;    
                }    
            }
            else{
                isJolly = false;
                break;
            }
        }

        if ( isJolly )
            cout << "Jolly" << endl;
        else
            cout << "Not jolly" << endl;
    }
    return 0;        
}

---

11059 Maximum Product
題目：http://luckycat.kshs.kh.edu.tw/homework/q11059.htm
觀念：bruteforce (DFS)
難度：luckycat ★

#include <iostream>
#include <string.h>
using namespace std;
int N;
long long arr[20], answer ;
void DFS( int now , long long product ){
    if ( product > answer )
        answer = product;
    if ( now == N )
        return;    
    DFS( now+1 , product * arr[now] );

}
int main(){
    int c = 1;
    while ( cin >> N ){
        for ( int i = 0 ; i < N ; i++ )
            cin >> arr[i];    
        answer = 0;
        for ( int str = 0 ; str < N ; str++ )
            DFS( str+1 , arr[str] );

        cout << "Case #" << c++ << ": The maximum product is " << answer << "." << endl;
        cout << endl;
    }

    return 0;    
}

解題示意


---

## 11520 Fill the Square

題目：[http://luckycat.kshs.kh.edu.tw/homework/q11520.htm](http://luckycat.kshs.kh.edu.tw/homework/q11520.htm)
觀念：greedy
難度：luckycat ★★

參考解答：
[http://programming-study-notes.blogspot.tw/2014/01/uva-11520-fill-square.html](http://programming-study-notes.blogspot.tw/2014/01/uva-11520-fill-square.html)

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

char square[12][12];

void fillChar (int n,int i,int j){
    char filled = 'A';
    bool up,left,right,down;

    //嘗試A~Z之間的所有字母
    while (filled <= 'Z'){

        //此格的上下左右 '超過邊界' 或 '內容與此格不同'  
        if (i-1<0  || square[i-1][j]!=filled) up=1;   else up=0;
        if (i+1>=n || square[i+1][j]!=filled) down=1; else down=0;
        if (j-1<0  || square[i][j-1]!=filled) left=1; else left=0;
        if (j+1>=n || square[i][j+1]!=filled) right=1;else right=0;

        //四邊的格子都與本格不衝突的話，就可以使用所選的字母
        if (up && down && left && right){
            square[i][j] = filled;
            cout<<filled;
            break;
        }
        else filled += 1; //換成下一個字母，例如：A -> B
    }
}

int main()
{
    //t是測資數量，n是正方形的邊長
    int t,n,Case=1;
    cin>>t;
    while (t--)
    {
        cin>>n;
        gets(square[0]);
        for(int i=0;i<n;i++) gets(square[i]);

        cout<<"Case "<<Case++<<endl;

        //對每一個格子做greedy演算法
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if (square[i][j]!='.')
                {
                    //如果此格已經有字母則輸出
                    cout<<square[i][j];
                }                    
                else
                {
                    //還是空格子，決定該填上哪個字母
                    fillChar(n,i,j);
                }
            }
            cout<<endl;
        }
    }

    return 0;
}

---

12694 Meeting Room Arrangement
題目：http://luckycat.kshs.kh.edu.tw/homework/q12694.htm
觀念：Greedy
難度：luckycat ★★

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int T, N;
struct Meeting{
    int s, e;    
}meeting[25];

bool cmp( Meeting A, Meeting B ){
    return A.e < B.e;    
}

int main(){
    int s, e;
    int ts, te;

    cin >> T;
    while ( T-- ){
        N = 0;
        while ( cin >> ts >> te ){
            if ( ts == 0 && te == 0 ) break;
            meeting[N].s = ts;
            meeting[N].e = te;
            N++;
        }

        sort( meeting, meeting+N , cmp );

        int ans = 0, lastUsedTime = 0;

        for ( int i = 0 ; i < N ; i++ )
            if ( meeting[i].s >= lastUsedTime ){
                ans++;
                lastUsedTime = meeting[i].e;
            }

        cout << ans << endl;

    }

    return 0;
}

---

12694 Meeting Room Arrangement
題目：https://zerojudge.tw/ShowProblem?problemid=c463
觀念：Tree BFS

/*
由下到上的方式計算節點的高度，原圖葉節點高度為0，
取出葉節點後其雙親節點高度為原來雙親節點高度與葉節點高度加1的較大值，
接著葉節點的雙親節點小孩個數少1，當雙親節點的子節點個數為0時，可以視為新的葉節點，
取出該雙親節點以相同方式計算其雙親節點的高度。
最後一個節點就是root，累加所有節點高度就可以獲得高度總和。
*/
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
const int MAX = 100001;
using namespace std;

int parent[MAX];//parent[i]=j，表示i的雙親為j
int degree[MAX];//紀錄節點深度
int childrenCount[MAX];//紀錄節點的子節點個數，子節點計算過後就減1
deque<int> todo;//儲存葉節點

int main()
{
  int n,cnt,child;
  long long int sum;//1+2+3+...+100000，會超出int範圍
  while (cin>>n) {

    sum = 0; // 這是用來存H(T)的結果
    //初始化
    for(int i = 0; i<MAX; i++ ){
        degree[i] = -1;
        childrenCount[i] = 0;
    }

    // 輸入每個節點的children
    for (int i = 1; i<=n; i++) {
      cin>>cnt;
      if (cnt == 0){
        todo.push_back(i);//葉節點
        degree[i]=0;//葉節點深度為0
      }else{
        childrenCount[i]=cnt;
        for(int j=0;j<cnt;j++){
          cin>>child;
          parent[child] = i;//使用陣列parent紀錄c的parent為i
        }
      }
    }
    
    int node;
    while(!todo.empty()){
      node = todo.front();//取出葉節點
      todo.pop_front();

      //取自己的深度與從子節點加1的較大值
      degree[parent[node]]=max(degree[parent[node]],degree[node]+1);

      //從todo中取出後，該節點的parent節點個數減1
      childrenCount[parent[node]]--;

      if (childrenCount[parent[node]] == 0){//當所有子節點都走訪過時
         todo.push_back(parent[node]);//加入該節點到佇列
      }
    }
    for (int i = 1; i<=n; i++) {
      sum += degree[i];
    }
    cout << node << endl;//最後一個從t取出的就是root
    cout << sum << endl;
  }
}