# APCS 2017/3 題解
## ==秘密差==
### 題目
[秘密差](https://zerojudge.tw/ShowProblem?problemid=c290)
### 核心
字元處理
### 思路

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin>>str;
    int A=0,B=0;
    for(int i=1;i<=str.size();i++)
    {
        if(i&1) A+=(str[str.size()-i]-'0');
        else B+=(str[str.size()-i]-'0');
    }
    printf("%d\n",abs(A-B));
}

## ==小群體==
### 題目
[小群體](https://zerojudge.tw/ShowProblem?problemid=c291)
### 核心
DFS
### 思路

#include<bits/stdc++.h>
using namespace std;
#define N 50005
int friends[N];
bool visit[N]={false};
int ans=0;
int main()
{
    int n,num;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",friends+i);
    for(int i=0;i<n;i++)
    {
        if(visit[i]) continue;
        ans++;
        num=i;
        while(!visit[num])
        {
            visit[num]=true;
            num=friends[num];
        }
    }
    printf("%d\n",ans);
}

## ==數字龍捲風==
### 題目
[數字龍捲風](https://zerojudge.tw/ShowProblem?problemid=c292)
### 核心
找規律
### 思路
[參考解法](https://moon-jam.me/zerojudge_c292/)

#include <bits/stdc++.h>
using namespace std;
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int n,dir;
    int arr[55][55];
    vector<int> records;
    cin>>n>>dir;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>arr[j][i];
    int dx[5]={-1,0,1,0}, dy[5]={0,-1,0,1};
    int curx=n/2,cury=n/2,pace=10;
    records.push_back(arr[curx][cury]);
    while(curx>=0&&curx<n&&cury>=0&&cury<n)
    {
        for(int i=0, curp=pace/10; i<curp; i++)
        {
            curx+=dx[dir],cury+=dy[dir];
            if(curx>=0&&curx<n&&cury>=0&&cury<n) records.push_back(arr[curx][cury]);
        }
        dir=(dir+1)%4, pace+=5;
    }
    for(int i : records) cout<<i;
    cout<<'\n';
}

## ==基地台==
### 題目
[基地台](https://zerojudge.tw/ShowProblem?problemid=c575)
### 核心
二分搜、貪心
### 思路
找出最小滿足直徑。

#include<bits/stdc++.h>
using namespace std;
#define N 50005
int n,k;
int locate[N];
bool judgeR(int r)
{
    int to=-1,num=k;
    for(int i=0;i<n;i++)
    {
        if(locate[i]>to) num--,to=locate[i]+r;
        if(num<0) return false;
    }
    return true;
}
int findR()
{
    int l=1,r=INT_MAX,mid;
    while(l<r)
    {
        mid=l-(l-r)/2;
        bool can=judgeR(mid);
        if(can) r=mid;
        else l=mid+1;
    }
    return r;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",locate+i);
    sort(locate,locate+n);
    printf("%d\n",findR());
}