# APCS 2017年03月題解
## 第一題 秘密差
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c290
### 解套
N/A
### 題目分析
因為數字最長有1000位，所以用字串紀錄
直接讀入字串，開一個變數ans紀錄數字，並從頭到尾加/減即可
不過因為讀入的是字串，所以可以用「字元-'0'」來快速轉成數字
最後輸出ans的絕對值即可
時間複雜度$O(n)$
### 解題流程
輸入$→$計算$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
string x;
int ans=0;
```
#### 輸入
```cpp=6
cin>>x;
```
#### 計算
```cpp=7
for(int i=0;i<x.size();i++)ans+=(i%2==0?x[i]-'0':'0'-x[i]);
```
#### 輸出
```cpp=8
cout<<abs(ans);
```
記得加絕對值
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
string x;
int ans=0;
int main(){
cin>>x;
for(int i=0;i<x.size();i++)ans+=(i%2==0?x[i]-'0':'0'-x[i]);
cout<<abs(ans);
}
```
## 第二題 小群體
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c291
### 解套
求一無向圖的連通塊數
### 題目分析
用圖論的概念來看這題的話，就是把每個人看作節點，好友關係看做無向邊，就能把題目轉成求連通塊數量$～$只要跑dfs就解決了
如果沒有圖論的概念可以這樣想：
對於一群朋友來說，如果從A開始，不斷到A的朋友、A的朋友的朋友、...最後一定會回到A
(其實就跟提示講的一樣)
因此如果我們用一個陣列been紀錄一個人有沒有處理過，並且從頭開始處理，一遇到沒處理過的就把朋友圈數(ans)加一，接著處理他、他朋友、他朋友的朋友...直到遇到處理過的就代表處理完了，如此每個人都跑過一遍就能得到答案了(遇到處理過的就直接跳過以節約時間)
時間複雜度$O(n)$
### 解題流程
輸入$→$遍歷、dfs$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,friends[500000+10],ans=0;
bool been[500000+10]={};
```
n同題述，friends存每個人的朋友，其他同前述
#### dfs函式宣告
```cpp=5
void dfs(int id){
if(been[friends[id]]==1)return;
else{
been[friends[id]]=1;
dfs(friends[id]);
return;
}
}
```
若其朋友到過就終止遞迴(第6行)
不然不斷往下遍歷
#### 輸入優化
```cpp=14
ios::sync_with_stdio(0);
cin.tie(0);
```
不加也行
#### 輸入
```cpp=16
cin>>n;
for(int i=0;i<n;i++)cin>>friends[i];
```
#### 遍歷、dfs
```cpp=18
for(int i=0;i<n;i++){
if(been[i]==0){
ans++;
been[i]=1;
dfs(i);
}
}
```
遇到沒遇過的就把答案加一
#### 輸出
```cpp=25
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,friends[500000+10],ans=0;
bool been[500000+10]={};
void dfs(int id){
if(been[friends[id]]==1)return;
else{
been[friends[id]]=1;
dfs(friends[id]);
return;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++)cin>>friends[i];
for(int i=0;i<n;i++){
if(been[i]==0){
ans++;
been[i]=1;
dfs(i);
}
}
cout<<ans;
}
```
## 第三題 數字龍捲風
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c292
### 解套
N/A
### 題目分析
正如題目提示所說
> 本題有多種處理方式，其中之一是觀察每次轉向與走的步數。例如起始方向是向左時，前幾步的走法是：左1、上 1、右 2、下 2、左 3、上 3、…… 一直到出界為止。
應該不難發現就方向而言，是「左上右下」不斷循環；
就行進距離而言，則是11223344...
因此我們用兩個變數xcur、ycur紀錄當前位置，cnt紀錄還剩幾個數字沒造訪過
接下來就是不斷地按提示的規則造訪、輸出
需要注意的是若cnt歸零(造訪完了)就要停止，並注意不能超出邊界(下面有較詳細的解釋)
時間複雜度$O(n^2)$
### 解題流程
輸入$→$遍歷、輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,direc,arr[50][50];
```
direc存方向，存數字陣列
#### 輸入優化
```cpp=5
ios::sync_with_stdio(0);
cin.tie(0);
```
不加也會過
#### 輸入
```cpp=7
cin>>n>>direc;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)cin>>arr[i][j];
}
```
#### 造訪用變數
```cpp=11
int xcur=n/2,ycur=n/2,len=1,cnt=n*n;
bool add=0;
```
xcur,ycur存位置，len存要走的長度，cnt存為造訪的位置數量，add決定要不要改變長度，後面解釋
#### 造訪(遍歷)、輸出
```cpp=13
cout<<arr[xcur][ycur];
cnt--;
while(cnt){
if(direc==0){
for(int i=1;i<=len;i++){
if(ycur-1>=0){
cout<<arr[xcur][ycur-1];
ycur--;
cnt--;
}
else break;
}
}
else if(direc==2){
for(int i=1;i<=len;i++){
if(ycur+1<n){
cout<<arr[xcur][ycur+1];
ycur++;
cnt--;
}
else break;
}
}
else if(direc==1){
for(int i=1;i<=len;i++){
if(xcur-1>=0){
cout<<arr[xcur-1][ycur];
xcur--;
cnt--;
}
else break;
}
}
else if(direc==3){
for(int i=1;i<=len;i++){
if(xcur+1<n){
cout<<arr[xcur+1][ycur];
xcur++;
cnt--;
}
else break;
}
}
if(add)len++;
add=!add;
direc=(direc+1)%4;
}
```
先處理初始位置(第13-14行)
接著依照方向不同有不同操作，以向左為例：
往左輸出並移動len個數字，除非已經到達邊界，那就直接break
其他方向依此類推
移動完後要處理移動距離與方向(第56-58行)
因為len每兩次要加1，所以令len在add為true時才加一(第56行)，
而add則在true與false之間不斷互換(第57行)就能達到要的效果
而方向剛好是0變1，1變2，2變3，3變0，所以直接加一再對4取模就好
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,direc,arr[50][50];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>direc;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)cin>>arr[i][j];
}
int xcur=n/2,ycur=n/2,len=1,cnt=n*n;
bool add=0;
cout<<arr[xcur][ycur];
cnt--;
while(cnt){
if(direc==0){
for(int i=1;i<=len;i++){
if(ycur-1>=0){
cout<<arr[xcur][ycur-1];
ycur--;
cnt--;
}
else break;
}
}
else if(direc==2){
for(int i=1;i<=len;i++){
if(ycur+1<n){
cout<<arr[xcur][ycur+1];
ycur++;
cnt--;
}
else break;
}
}
else if(direc==1){
for(int i=1;i<=len;i++){
if(xcur-1>=0){
cout<<arr[xcur-1][ycur];
xcur--;
cnt--;
}
else break;
}
}
else if(direc==3){
for(int i=1;i<=len;i++){
if(xcur+1<n){
cout<<arr[xcur+1][ycur];
xcur++;
cnt--;
}
else break;
}
}
if(add)len++;
add=!add;
direc=(direc+1)%4;
}
}
```
## 第四題 基地台
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c575
### 解套
對答案二分搜
### 題目分析
首先我們先看一下題目數字的範圍，幫助我們分析會過的複雜度；會發現$n,k\leq50000$，但座標範圍$\leq10^9$，代表直徑最長也可以到$10^9$
因此很明顯地我們的演算法要嘛跟直徑無關(直接算出直徑)，或是跟直徑的$log$有關
但說實話我不認為有辦法直接算出直徑，所以只能想辦法把直徑的部分壓到$log$
最後的結論就是：我們要對直徑(答案)二分搜！~~by通靈~~
理由是我們可以發現如果要檢驗一個直徑能不能只架$\leq k$個基地台，只需要$O(n)$的時間
因此只要對直徑(答案)做二分搜，再用$O(n)$的線性搜判斷一直徑可不可行，就能得到答案
線性搜實作上我們先把所有座標從小到大排序，檢驗直徑時從頭開始掃，把基地台的最左界設在起始座標，接下來的座標如果超出最右界就在新放一個基地台並重置右界，就能得到需要的基地台數量，
最後再跟$k$比較決定方案可不可行
二分搜就是一般的二分搜，如果中點符合線性搜條件就把右界往下縮，不然把左界往上縮
最終複雜度$O(nlogl)$(設l為座標長度)
### 解題流程
輸入$→$二分搜(用線性搜決定往上或往下縮)$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,k,p[500000+10];
```
同題述
#### 線性搜檢驗函式
```cpp=4
bool check(int len){
int cnt=1,right=p[0]+len;
for(int i=1;i<n;i++){
if(p[i]<=right){
continue;
}
else{
cnt++;
right=p[i]+len;
}
}
return cnt<=k;
}
```
cnt紀錄需要的基地台數量，right紀錄當前能提供服務的最右界
如果新的座標還在服務範圍內就continue(第7-9行)
不然(第10行)就新設一個基地台(第11行)並更新右界(第12行)
最後回傳基地台數量合不合要求(第15行)
#### 輸入優化
```cpp=18
ios::sync_with_stdio(0);
cin.tie(0);
```
你懂的，不加也行
#### 輸入、排序
```cpp=20
cin>>n>>k;
for(int i=0;i<n;i++)cin>>p[i];
sort(p,p+n);
```
#### 二分搜
```cpp=23
int l=1,r=1e9;
while(l<=r){
if(l==r)break;
else if(r==l+1){
if(!check(l))l=r;
break;
}
else{
int m=(l+r)/2;
if(check(m))r=m;
else l=m+1;
}
}
```
用check當檢驗標準
因為希望最後的基地台直徑越小越好，所以只剩兩個可能數字時(第26-29行)，要用
```cpp
if(!check(l))l=r;
```
因為只有在比較小的數字不行時我們才會用大的數字
### 輸出
```cpp=36
cout<<l;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,k,p[500000+10];
bool check(int len){
int cnt=1,right=p[0]+len;
for(int i=1;i<n;i++){
if(p[i]<=right){
continue;
}
else{
cnt++;
right=p[i]+len;
}
}
return cnt<=k;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++)cin>>p[i];
sort(p,p+n);
int l=1,r=1e9;
while(l<=r){
if(l==r)break;
else if(r==l+1){
if(!check(l))l=r;
break;
}
else{
int m=(l+r)/2;
if(check(m))r=m;
else l=m+1;
}
}
cout<<l;
}
```
Sign in with Wallet
Connect another wallet