# APCS 2017年10月題解
## 第一題 邏輯運算子
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c461
### 解套
N/A
### 題目分析
首先因為AND操作、OR操作和XOR操作都有對應的位運算符號，所以輸入a,b後把非0數字都轉成1會比較方便，這樣就能直接用內建的位元運算得到答案
逐一判斷，如果符合就輸出對應的字串，最後如果都不合就輸出"IMPOSSIBLE"
時間複雜度$O(1)$
### 解題流程
輸入$→$轉換$→$判斷、輸出
### 解題過程
#### 變數宣告
```cpp=3
int a,b;
bool c;
```
變數名同題目
#### 輸入、轉換
```cpp=6
cin>>a>>b>>c;
a=(a!=0?1:0),b=(b!=0?1:0);
```
#### 判斷、輸出
```cpp=8
bool cmp=0;
if((a&&b)==c){
cmp=1;
cout<<"AND\n";
}
if((a||b)==c){
cmp=1;
cout<<"OR\n";
}
if((a^b)==c){
cmp=1;
cout<<"XOR\n";
}
if(cmp==0)cout<<"IMPOSSIBLE";
```
cmp紀錄有沒有符合的
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a,b;
bool c;
int main(){
cin>>a>>b>>c;
a=(a!=0?1:0),b=(b!=0?1:0);
bool cmp=0;
if((a&&b)==c){
cmp=1;
cout<<"AND\n";
}
if((a||b)==c){
cmp=1;
cout<<"OR\n";
}
if((a^b)==c){
cmp=1;
cout<<"XOR\n";
}
if(cmp==0)cout<<"IMPOSSIBLE";
}
```
## 第二題 交錯字串
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c462
### 解套
N/A
### 題目分析
首先因為題目關心的是「連續大(小)寫的交錯」，所以我們只需要知道連續大(小)寫區間的長度就好
一開始先$O(n)$掃過字串，把連續的大(小)寫子字串長度存進陣列segments
接著就是遍歷segments以獲得答案(以ans紀錄)
我的作法是開一個變數$tmp$紀錄第一個遇到長度為k的子字串的位置，
然後持續遍歷直到遇到長度不是$k$的子字串
假設該位置是$i$，代表總共有$i-tmp$個子字串，不過這時還要考慮前一個$(tmp-1)$以及後一個$(i)$子字串長度是否大於k，因為這樣也能對答案有貢獻
(例：$k=1$,$s=aa B a BB$，答案會是$aBaB$而非$Ba$)
再和ans取較大值即可
需要注意的是每處理完一段就要把$tmp$變回-1，避免重複計算
最後輸出$ans×k$，因為ans紀錄的是子字串數量
時間複雜度$O(n)$
### 解題流程
輸入$→$生成segments$→$計算答案$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int k,ans=0;
string s;
vector<int>segments;
```
變數名同題述、前述
#### 輸入優化
```cpp=7
ios::sync_with_stdio(0);
cin.tie(0);
```
不加也會過
#### 輸入
```cpp=9
cin>>k>>s;
```
#### 產生segments
```cpp=10
int tmp=1;
for(int i=1;i<s.size();i++){
if(isupper(s[i])==isupper(s[i-1]))tmp++;
else{
segments.push_back(tmp);
tmp=1;
}
}
if(tmp)segments.push_back(tmp);
```
tmp存當前子字串長度
#### 更新答案
```cpp=19
tmp=-1;
for(int i=0;i<segments.size();i++){
if(segments[i]==k){
if(tmp==-1)tmp=i;
else continue;
}
else{
if(tmp==-1)continue;
else{
int num=i-tmp;
if(segments[i]>k)num++;
if(tmp!=0&&segments[tmp-1]>k)num++;
ans=max(ans,num);
tmp=-1;
}
}
}
if(tmp!=-1){
int num=segments.size()-tmp;
if(tmp!=0&&segments[tmp-1]>k)num++;
ans=max(ans,num);
}
```
處理方法同前述，只是最後要再確認一遍(這邊因為沒有「後一個」所以不用判斷)
#### 輸出
```cpp=41
cout<<ans*k;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int k,ans=0;
string s;
vector<int>segments;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>k>>s;
int tmp=1;
for(int i=1;i<s.size();i++){
if(isupper(s[i])==isupper(s[i-1]))tmp++;
else{
segments.push_back(tmp);
tmp=1;
}
}
if(tmp)segments.push_back(tmp);
tmp=-1;
for(int i=0;i<segments.size();i++){
if(segments[i]==k){
if(tmp==-1)tmp=i;
else continue;
}
else{
if(tmp==-1)continue;
else{
int num=i-tmp;
if(segments[i]>k)num++;
if(tmp!=0&&segments[tmp-1]>k)num++;
ans=max(ans,num);
tmp=-1;
}
}
}
if(tmp!=-1){
int num=segments.size()-tmp;
if(tmp!=0&&segments[tmp-1]>k)num++;
ans=max(ans,num);
}
cout<<ans*k;
}
```
## 第三題 樹狀圖分析
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c463
### 解套
dfs
### 題目分析
這明顯是一題dfs/bfs的題目，只是題目沒有給根節點，需要自己找，然後他求的答案有點神奇，是「某節點和最遠子節點的距離」的總和
(我是用dfs，然後存圖是用鄰接串列)
根節點的部分我是用unordered_set來求，一開始先把從1到n的數字都放進去，在存圖時遇到是別人子節點的就把他從unordered_set裡拿掉，最後剩下來的就是根節點
dfs部分在函式裡我用了兩個參數id和dep，紀錄處理的節點編號與深度，另外再開一個far陣列紀錄每個節點「最遠子節點的深度」，而實際在dfs時分成兩種狀況：
1. 葉節點(用子節點陣列大小是0判斷)：這時為了方便就把葉節點視為自己，所以他的far值就是深度
2. 非葉節點：往下遍歷，並在遍歷過程中不斷更新far的值(自己和葉節點的far值取max)
最後把答案加上「far值檢調自己的深度」，全部跑完後就會是答案
喔對然後答案會爆int$(10^{10}>2^{31})$
時間複雜度$O(n)$
### 解題流程
輸入、存圖$→$dfs$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,a,b;
long long ans=0;
vector<vector<int>>v;
unordered_set<int>st;
vector<int>far;
```
n同題述，a,b只是輸入用，其他同前述
#### dfs函式
```cpp=8
void dfs(int id,int dep){
if(v[id].size()==0){
far[id]=dep;
return;
}
for(int i:v[id]){
dfs(i,dep+1);
far[id]=max(far[id],far[i]);
}
ans+=far[id]-dep;
return;
}
```
原理同前述
#### 輸入優化
```cpp=21
ios::sync_with_stdio(0);
cin.tie(0);
```
不加也行
#### 輸入、初始化、存圖
```cpp=23
cin>>n;
v.assign(n+1,{});
far.assign(n+1,0);
for(int i=1;i<=n;i++)st.insert(i);
for(int i=1;i<=n;i++){
cin>>a;
for(a;a>0;a--){
cin>>b;
v[i].push_back(b);
st.erase(b);
}
}
```
輸入n後決定v,far的大小，並初始化st
接著照順序存子節點，並更新st
#### dfs
```cpp=35
dfs(*st.begin(),0);
```
從根節點開始遍歷，深度設為0
#### 輸出
```cpp=36
cout<<*st.begin()<<"\n"<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,a,b;
long long ans=0;
vector<vector<int>>v;
unordered_set<int>st;
vector<int>far;
void dfs(int id,int dep){
if(v[id].size()==0){
far[id]=dep;
return;
}
for(int i:v[id]){
dfs(i,dep+1);
far[id]=max(far[id],far[i]);
}
ans+=far[id]-dep;
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
v.assign(n+1,{});
far.assign(n+1,0);
for(int i=1;i<=n;i++)st.insert(i);
for(int i=1;i<=n;i++){
cin>>a;
for(a;a>0;a--){
cin>>b;
v[i].push_back(b);
st.erase(b);
}
}
dfs(*st.begin(),0);
cout<<*st.begin()<<"\n"<<ans;
}
```
## 第四題 物品堆疊
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c471
### 解套
依照貪心法則排序
### 題目分析
這是一題貪心題，~~但如果看不出來好像也沒辦法？~~
我想到比較有邏輯的方式(不是通靈/靠經驗)是用複雜度分析；因為題目的$n$最大到$10^5$，時限1秒，
所以$O(n^2)$會超時，大概只能$O(nlogn)$或$O(n)$，但要$O(n)$著實有些困難(至少我想不到)，
而如果要$O(nlogn)$第一個想到的大概就是排序吧？
不過這題不能單純要內建排序，需要自己寫自定義排序的比較規則。
因為自定義排序韓式只需要寫兩個東西的比較，所以我們只需要思考針對兩個物品怎麼排序就好
假設有A,B兩個物品，若A放上面，那要拿B時就會花w(A)×f(B)的能量，同理如果B放上面，那要拿A時就會花w(B)×f(A)的能量，而題目希望最小化消耗的能量，所以讓比較小的排上面(要拿較多次)
排序完後從頭遍歷一邊累計搬運次數，一邊將答案加上重量乘次數，就能得到最後答案
另外這一題會爆int(如果有100000個物品每個都重1000要拿1000次...)，所以要開long long
時間複雜度$O(nlogn)$
### 解題流程
輸入$→$排序$→$計算$→$輸出
### 解題過程
#### define
```cpp=2
#define int long long
#define w first
#define f second
```
方便起見，另外pair前面存重量、後面存次數
#### 變數宣告
```cpp=6
int n,ans=0;
pair<int,int>arr[100000+10];
```
n同題述，ans存答案，arr存物品
#### 自定義排序
```cpp=8
bool cmp(pair<int,int> a,pair<int,int> b){
return a.w*b.f<b.w*a.f;
}
```
邏輯同前述
#### 輸入優化
```cpp=12
ios::sync_with_stdio(0);
cin.tie(0);
```
不加也會過
#### 輸入
```cpp=14
cin>>n;
for(int i=0;i<n;i++)cin>>arr[i].w;
for(int i=0;i<n;i++)cin>>arr[i].f;
```
#### 排序
```cpp=17
sort(arr,arr+n,cmp);
```
cmp要記得打
#### 計算答案
```cpp=18
int cnt=arr[0].w;
for(int i=1;i<n;i++){
ans+=arr[i].f*cnt;
cnt+=arr[i].w;
}
```
cnt紀錄累積的重量，因為最上面的不需要消耗能量，所以cnt預設為第0個物品的重量，而計算答案從第1個物品開始
#### 輸出
```cpp=23
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define int long long
#define w first
#define f second
using namespace std;
int n,ans=0;
pair<int,int>arr[100000+10];
bool cmp(pair<int,int> a,pair<int,int> b){
return a.w*b.f<b.w*a.f;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++)cin>>arr[i].w;
for(int i=0;i<n;i++)cin>>arr[i].f;
sort(arr,arr+n,cmp);
int cnt=arr[0].w;
for(int i=1;i<n;i++){
ans+=arr[i].f*cnt;
cnt+=arr[i].w;
}
cout<<ans;
}
```
Sign in with Wallet
Connect another wallet