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

1. [c290: 秘密差](#c290)
2. [c291: 小群體](#c291)
3. [c292: 數字龍捲風](#c292)
4. [c575: 基地台](#c575)

# <a id="c290">第 1 題 秘密差</a>

### 題意：
有一個數字，求奇數位的數字總和及偶數位的數字總和的差，例如13579就是|(1+5+9)-(3+7)|=5

### 解法：
數字用字串輸入，迴圈跑以%2為條件判斷是哪個位數，記得存和的時候要減掉'0'或48，最後用cmath裡面的abs計算絕對值和差並輸出。

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

int main()
{
    string str; //或是 char str[1001];
    int sum1, sum2;
    int str_len;

    while( cin >> str )//輸入字串，例：9872
    {
        sum1 = 0; //sum1 sum2 一個是奇數和，一個是偶數合
        sum2 = 0;
        str_len = str.length(); //輸入字串
        
        
        的長度，9872的長度為4
        // ↑ 如果原本宣告 char str[1001]的話則可以用 s_len = strlen(str);

        for (int i=0; i<str_len; i++)//將整個字串掃過一遍
        {
            if (i%2==1)//從左到右如果是第奇數個字元，像是 8 2，則把他們加起來
                sum1 += str[i]-'0'; //因為s是字元字串，不是數字，所以要減去'0'或是48，才會換算成正確數字
            else //從左到右如果是第偶數個字元，像是 9 7，則把他們加起來
                sum2 += str[i]-'0';
        }

        cout << abs(sum1-sum2) << endl; //算出絕對值差
    }
    return 0;
}

---

# <a id="c291">第 2 題 小群體</a>

### 題意：
有N個人，給你他們的朋友，要你求朋友圈數，保證每個人的朋友不重複，意思大概就是直到沒有共同好友為止算一個朋友圈這樣。

### 解法：
用一個bool陣列紀錄那個人是否被算進生活圈，然後從編號0開始，只要是沒算過生活圈的就ans++並dfs一下把所有共同好友紀錄為算進生活圈，走完一次迴圈再輸出ans就好了。

#include<iostream>
using namespace std;

int N, members[50005], i, now;
bool visited[50005];
int ans;

int main()
{
    while( cin >> N )
    {
        for( i=0 ; i<N ; i++ )
        {
            cin >> members[i]; //輸入每個人的最好朋友編號
            visited[i] = false; //還沒被算進小群體的人為false，預設都是false
        }

        ans = 0;//群體數量一開始為0
        for( i=0 ; i<N ; i++ ) //針對每個人檢查他的小群體
        {
            if( !visited[i] )//如果這個人還沒被算進小群體中
            {
                ans++;//建立新的小群體
                now = i;
                //開始一個一個人加進小群體
                while( !visited[now] )//還沒拜訪過的人則把他加入群體
                {
                    visited[now] = true;//設定為拜訪過
                    now = members[now];//繼續找下一個
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

---

# <a id="c292">第 3 題 數字龍捲風</a>

### 題意：
給你一個N*N的方陣和方向k，要從中間開始轉出去，輸出是旋轉的路徑，這一題步驟比較繁雜，但靠點耐心還是能解決

### 解法：
走x步換方向、走2次+每次步數，然後讓他轉...這題好抽象好難解釋，如果有人想看再留言，我再附上完整說明吧

#include<iostream>
#define MAP_SIZE 50
#define LEFT 0
#define UP 1
#define RIGHT 2
#define DOWN 3

using namespace std;

void walk(  int dir,  int *y,  int *x )
{
    if( dir == LEFT )
        *x=*x-1;
    else if( dir == UP )
        *y=*y-1;
    else if( dir == RIGHT )
        *x=*x+1;
    else if( dir == DOWN )
        *y=*y+1;
}

int main()
{
     //N是地圖的邊長，dir是方向
     int N, dir, x, y, i;
     int maze[MAP_SIZE][MAP_SIZE];
    /*
    level 1 round 1 -> level 1 round 2
    -> level 2 round 1 -> level 2 round 2
    -> level 3 round 1 -> level 3 round 2
    ...
    */
     int level;//往此方向該走幾步
     int round;//同個level該走幾回合

    while( cin >> N >> dir )
    {
        for( y=0 ; y<N ; y++  )
            for( x=0 ; x<N ; x++ )
                cin >> maze[y][x]; //輸入地圖資訊

        level = 1;
        round = 1;
        y = x = N/2; //正中心的座標，也就是起點
        while( level < N )
        {
            for( i=0 ; i<level ; i++ )
            {
                cout << maze[y][x];
                walk( dir, &y, &x );
            }

            //每走一round，就會往右轉90度
            //LEFT 左 -> UP 上 -> RIGHT 右 -> DOWN 下
            dir = (dir+1)%4;

            round++;
            if( round == 3 )//每 2 round，步數就要變多，所以level++
            {
                level++;
                round = 1;
            }
        }
        //last path，最後一round要個別處理
        for( i=1 ; i<level ; i++ ){
            cout << maze[y][x];
            walk( dir, &y, &x );
        }
        cout << maze[y][x] << endl;
    }

    return 0;
}

---

# <a id="c575">第 4 題 基地台</a>

### 題意：
有N個點要架設東西，你可以擺放K個基點台讓這N個點能收到訊號，求基地台訊號的直徑至少要多少

### 解法：
先把N個點sort，再來開一陣列儲存兩兩之間的差，最後以直徑對差之和做二分搜，結束。

#include <iostream>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
int N, K, arr[50005]; 
int main(){

       cin>>N>>K; //N 個服務點， K 個基地台

        for ( int i = 1 ; i <= N ; i++ )
            cin>>arr[i]; //輸入每個服務點的位置
        sort( arr+1, arr+N+1 );//要先排序，因為等等要做Greedy演算法

        int left = 0, right= (arr[N]-arr[1])/K; // right也可以直接使用很大的數字代替，像是1000000000;
        int ans = -1;

        //使用二元搜尋法，left是最小的直徑，R則是最大直徑，取中間值的直徑來測試
        while ( right >= left ){

            int mid = ( left + right ) /2;

            //cnt代表count，代表這次測試我們使用多少個基地台，rZone代表目前基地代所涵蓋的範圍
            int cnt = 1, rZone = arr[1] + mid;//假如說第一個服務點在2，所用的直徑是3，代表5之前都能被服務到，rZone=5

            //以此類推去檢查每個點能不能被服務到，不能就再安排一個基地台
            for ( int i = 2 ; i <= N ; i++ )
                if ( arr[i] > rZone ){
                    rZone = arr[i] + mid;    
                    if ( ++cnt > K ) break;
                }

            if ( cnt <= K ){ //如果所用到的基地台數量小於K，代表這個直徑可以用，但是還可以嘗試尋找更短的直徑
                ans = mid; //先將這個直徑當作最佳解答   
                right = mid-1;
            }
            else //代表不能用這個直徑，因為不能涵蓋所有的服務點
                left = mid+1;

        }

        cout<<ans<<endl;


    return 0;    
}