# APCS 2020年10月題解
## 第一題 人力分配
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f312
### 解套
N/A
### 題目分析
直接嘗試每一種組合，找到最大可能收益
時間複雜度$O(n)$
### 解題流程
輸入$→$枚舉$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int a1,b1,c1,a2,b2,c2,n;
```
變數名與題述相同
```cpp=6
int ans=INT_MIN;
```
一開始設答案為極小值
#### 輸入
```cpp=5
cin>>a1>>b1>>c1>>a2>>b2>>c2>>n;
```
#### 暴力枚舉
```cpp=7
for(int x1=0;x1<=n;x1++){
int x2=n-x1;
ans=max(ans,a1*x1*x1+b1*x1+c1+a2*x2*x2+b2*x2+c2);
}
```
枚舉所有x1與x2的可能，並更新答案
#### 輸出
```cpp=11
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a1,b1,c1,a2,b2,c2,n;
int main(){
cin>>a1>>b1>>c1>>a2>>b2>>c2>>n;
int ans=INT_MIN;
for(int x1=0;x1<=n;x1++){
int x2=n-x1;
ans=max(ans,a1*x1*x1+b1*x1+c1+a2*x2*x2+b2*x2+c2);
}
cout<<ans;
}
```
## 第二題 人口遷移
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f313
### 解套
N/A
### 題目分析
直接按照題目說的規則處理即可，不過需要注意的是因為遷移是同步的，但我們的處理只能依序做，
所以遷移到其他地區的量先開另一個陣列math紀錄，所有地區都處理完後再加上去
(如果直接把遷移的量加上去會造成後處理的地區出錯)
另外因為題目保證$k\geq4$，所以不論如何人數都不會是負的，不用特別處理
處理遷移$m$次後再遍歷一次找最小值與最大值
時間複雜度$O(mrc)$
### 解題流程
輸入$→$模擬$→$遍歷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int r,c,k,m;
int arr[50][50],math[50][50];
```
r,c,k,m與題述相同，arr存總人數，math存每次遷移暫時增加的人數
```cpp=42
int minans=INT_MAX,maxans=0;
```
初始化最小值與最大值
#### 輸入
```cpp=6
cin>>r>>c>>k>>m;
for(int i=0;i<r;i++)for(int j=0;j<c;j++)cin>>arr[i][j];
```
#### 處理遷移m次
```cpp=8
for(int l=0;l<m;l++){
for(int i=0;i<r;i++)for(int j=0;j<c;j++)math[i][j]=0;
for(int i=0;i<r;i++)for(int j=0;j<c;j++){
if(arr[i][j]==-1)continue;
int num=arr[i][j]/k;
int cnt=0;
if(i!=0){
if(arr[i-1][j]!=-1){
math[i-1][j]+=num;
cnt++;
}
}
if(j!=0){
if(arr[i][j-1]!=-1){
math[i][j-1]+=num;
cnt++;
}
}
if(i!=r-1){
if(arr[i+1][j]!=-1){
math[i+1][j]+=num;
cnt++;
}
}
if(j!=c-1){
if(arr[i][j+1]!=-1){
math[i][j+1]+=num;
cnt++;
}
}
arr[i][j]-=num*cnt;
}
for(int i=0;i<r;i++)for(int j=0;j<c;j++)if(arr[i][j]!=-1)arr[i][j]+=math[i][j];
}
```
一開始(第9行)先歸零math
接著遍歷所有位置(第10-39行)
如果該位置不是城市(值是$-1$)就跳過(第11行)
不然開兩個變數num與cnt紀錄要遷移的人數與共要遷移到幾個相鄰區域(第12、13行)
接著看上下左右四個相鄰區域是不是城市，如果是就把人移過去(math加num，cnt加1)(第14-37行)
四個都處理完後一次性減掉人數(第38行)
每次處理完所有位置再用math更新arr(第40行)
#### 找答案
```cpp=43
for(int i=0;i<r;i++)for(int j=0;j<c;j++){
if(arr[i][j]!=-1)minans=min(minans,arr[i][j]);
maxans=max(maxans,arr[i][j]);
}
```
遍歷所有區域更新答案
其中因為代表不是都市的-1會影響取最小值的操作，所以要額外判斷(第44行)
當然也可以一開始遇到-1就直接continue~~只是這樣會多一行~~
#### 輸出
```cpp=47
cout<<minans<<"\n"<<maxans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int r,c,k,m;
int arr[50][50],math[50][50];
int main(){
cin>>r>>c>>k>>m;
for(int i=0;i<r;i++)for(int j=0;j<c;j++)cin>>arr[i][j];
for(int l=0;l<m;l++){
for(int i=0;i<r;i++)for(int j=0;j<c;j++)math[i][j]=0;
for(int i=0;i<r;i++)for(int j=0;j<c;j++){
if(arr[i][j]==-1)continue;
int num=arr[i][j]/k;
int cnt=0;
if(i!=0){
if(arr[i-1][j]!=-1){
math[i-1][j]+=num;
cnt++;
}
}
if(j!=0){
if(arr[i][j-1]!=-1){
math[i][j-1]+=num;
cnt++;
}
}
if(i!=r-1){
if(arr[i+1][j]!=-1){
math[i+1][j]+=num;
cnt++;
}
}
if(j!=c-1){
if(arr[i][j+1]!=-1){
math[i][j+1]+=num;
cnt++;
}
}
arr[i][j]-=num*cnt;
}
for(int i=0;i<r;i++)for(int j=0;j<c;j++)if(arr[i][j]!=-1)arr[i][j]+=math[i][j];
}
int minans=INT_MAX,maxans=0;
for(int i=0;i<r;i++)for(int j=0;j<c;j++){
if(arr[i][j]!=-1)minans=min(minans,arr[i][j]);
maxans=max(maxans,arr[i][j]);
}
cout<<minans<<"\n"<<maxans;
}
```
## 第三題 勇者修煉
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f314
### 解套
N/A
### 題目分析
(為方便討論，設$arr[i][j]$為原本的值，$dp[i][j]$為考慮到第$i$行$j$列的情形)
(如果沒有dp基礎可以先去看[這裡](https://oi-wiki.org/dp/))
先把題目~~大幅~~簡化一下
假設從左上角開始，而且只能往右下方走，那要怎麼寫？
那就是常見的dp題目嘛，轉移式$dp[i][j]=max(dp[i-1][j],dp[i][j-1])+arr[i][j]$
那如果加上可從最上層任意位置開始要怎麼做？
只要在處理最上層時增加只考慮自己的可能就好了 $dp[0][j]=max(dp[0][j-1],0)+arr[0][j]$
最後處理完整的題目，即加上左右都能走的條件
因為由右往左跟由左往右可能會有不一樣的結果，取用上也不能互相通用
| 1 | 2 | 3 | 4 |
| - | - | - | - |
| 5 | 6 | 7 | 8 |
(假設要從7走到6，因為不能重複走所以只能考慮3→7→6和8→7→6而不能考慮6→7→6)
所以往右跟往左的dp要分開存
因此我們把dp的定義改成$dp[i][j][k]$，$k=0$代表從左邊走過來，$k=1$代表從右邊走過來
dp轉移式就變成$dp[i][j][0]=max({dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1]})+arr[i][j]$
以及$dp[i][j][1]=max({dp[i][j+1][1],dp[i-1][j][0],dp[i-1][j][1]})+arr[i][j]$
初始化的部分則是$dp[0][0][0]=arr[0][0],dp[0][n-1][1]=arr[0][n-1]$，
最上面一列取max時不用考慮上面但要加上直接從自己開始的可能性，
且每一列最左和最右會缺少從右邊來和從左邊來的可能性
dp跑完後再掃最後一列，看最大值是多少並輸出
時間複雜度$O(mn)$
### 解題流程
輸入$→$動態規劃$→$遍歷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int m,n,arr[50][10000],dp[50][10000][2]={};
```
變數名與前述、題述相同
```cpp=21
int ans=INT_MIN;
```
一開始設答案為極小值
#### 輸入
```cpp=5
cin>>m>>n;
for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>arr[i][j];
```
#### 動態規劃
```cpp=7
dp[0][0][0]=arr[0][0];
dp[0][n-1][1]=arr[0][n-1];
for(int i=0;i<m;i++){
if(i==0){
for(int j=1;j<n;j++)dp[i][j][0]=max(dp[i][j-1][0],0)+arr[i][j];
for(int j=n-2;j>=0;j--)dp[i][j][1]=max(dp[i][j+1][1],0)+arr[i][j];
}
else{
dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][0][1])+arr[i][0];
dp[i][n-1][1]=max(dp[i-1][n-1][1],dp[i-1][n-1][0])+arr[i][n-1];
for(int j=1;j<n;j++)dp[i][j][0]=max({dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1]})+arr[i][j];
for(int j=n-2;j>=0;j--)dp[i][j][1]=max({dp[i][j+1][1],dp[i-1][j][0],dp[i-1][j][1]})+arr[i][j];
}
}
```
第7、8行初始化左上角與右上角
第10-13行初始化最上面一列
第15、16行計算每一列最左與最右一格
第17、18行計算剩下的格子
#### 找答案
```cpp=21
int ans=INT_MIN;
for(int i=0;i<n;i++)ans=max({ans,dp[m-1][i][0],dp[m-1][i][1]});
```
遍歷最後一列並更新答案
#### 輸出
```cpp=23
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int m,n,arr[50][10000],dp[50][10000][2]={};
int main(){
cin>>m>>n;
for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>arr[i][j];
dp[0][0][0]=arr[0][0];
dp[0][n-1][1]=arr[0][n-1];
for(int i=0;i<m;i++){
if(i==0){
for(int j=1;j<n;j++)dp[i][j][0]=max(dp[i][j-1][0],0)+arr[i][j];
for(int j=n-2;j>=0;j--)dp[i][j][1]=max(dp[i][j+1][1],0)+arr[i][j];
}
else{
dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][0][1])+arr[i][0];
dp[i][n-1][1]=max(dp[i-1][n-1][1],dp[i-1][n-1][0])+arr[i][n-1];
for(int j=1;j<n;j++)dp[i][j][0]=max({dp[i][j-1][0],dp[i-1][j][0],dp[i-1][j][1]})+arr[i][j];
for(int j=n-2;j>=0;j--)dp[i][j][1]=max({dp[i][j+1][1],dp[i-1][j][0],dp[i-1][j][1]})+arr[i][j];
}
}
int ans=INT_MIN;
for(int i=0;i<n;i++)ans=max({ans,dp[m-1][i][0],dp[m-1][i][1]});
cout<<ans;
}
```
## 第四題 低地距離
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=f315
### 解套
題目寫得好清楚喔怎麼辦
定義$i$的低窪值為一陣列裡兩個數值為$i$的位置中間有幾個小於$i$的是數字，求所有低窪值總和
### 題目分析
首先這題如果暴力做的話時間複雜度會是$O(n^2)$，要執行$10^{10}$次運算，會超時
那究竟要怎麼做呢？
因為題目要的是兩相同數值間比他們小的，而因為從小到大具有規律性，
所以我們可以把題目稍微做一下轉換
如果我們把數字從小到大掃，並開一個新的陣列，每掃到一個數字就在他出現的兩個位置標記，就能動態紀錄比某數字小的數字出現位置
以題目的$[3,1,2,1,3,2]$為例
1. 掃到1
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 |
| -- | - | - | - | - | - | - |
| 標記 | 0 | 1 | 0 | 1 | 0 | 0 |
2. 掃到2
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 |
| -- | - | - | - | - | - | - |
| 標記 | 0 | 1 | 1 | 1 | 0 | 1 |
3. 掃到3
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 |
| -- | - | - | - | - | - | - |
| 標記 | 1 | 1 | 1 | 1 | 1 | 1 |
就會發現一個數字的低窪值就是掃到他之前，他兩個位置之間的區間和！
例如數值3的位置是$1,5$，而掃完2後$[1,5]$的區間和是3，也就是數值3的低窪值
但是要怎麼做到動態更新數值與求區間和呢？答案是用**BIT**(樹狀數組)
他支持在$O(n)$時間初始化，$O(logn)$時間單點加值與求前綴和
BIT的詳細介紹在[這裡](https://oi-wiki.org/ds/fenwick/)(也可以用線段樹，但BIT寫起來比較簡潔)
於是就得到解法：先掃過一遍原始陣列得到各數值的出現位置，接著數字從小到大處理，先把答案加上出現位置之間的區間和再用出現位置更新BIT，最後輸出答案即可
時間複雜度$O(nlogn)$
### 解題流程
輸入$→$用BIT更新答案、操作區間$→$輸出
### 解題過程
#### define
```cpp=2
#define F first
#define S second
```
懶得打字
#### 變數宣告
```cpp=5
int n,a;
long long int ans=0;
pair<int,int>arr[100000+10];
```
a是輸入用的變數，ans是答案(題目說要long long)，arr存個數值出現位置
#### BIT
```cpp=8
struct BIT{
int sz;
vector<int>dat;
void init(int n){
sz=n;
dat.assign(n+1,0);
return;
}
void upd(int id,int x){
for(int i=id;i<=sz;i+=i&-i)dat[i]+=x;
return;
}
int sum(int id){
int ans=0;
for(int i=id;i>0;i-=i&-i)ans+=dat[i];
return ans;
}
}bit;
```
#### 輸入、存位置
```cpp=27
cin>>n;
for(int i=1;i<=2*n;i++){
cin>>a;
if(arr[a].F==0)arr[a].F=i;
else arr[a].S=i;
}
```
第30、31行存數值出現的第一和第二個位置
#### 初始化BIT
```cpp=33
bit.init(2*n);
```
要記得大小是$2n$
#### 操作
```cpp=34
for(int i=1;i<=n;i++){
ans+=bit.sum(arr[i].S-1)-bit.sum(arr[i].F);
bit.upd(arr[i].F,1);
bit.upd(arr[i].S,1);
}
```
更新答案、BIT
#### 輸出
```cpp=39
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n,a;
long long int ans=0;
pair<int,int>arr[100000+10];
struct BIT{
int sz;
vector<int>dat;
void init(int n){
sz=n;
dat.assign(n+1,0);
return;
}
void upd(int id,int x){
for(int i=id;i<=sz;i+=i&-i)dat[i]+=x;
return;
}
int sum(int id){
int ans=0;
for(int i=id;i>0;i-=i&-i)ans+=dat[i];
return ans;
}
}bit;
int main(){
cin>>n;
for(int i=1;i<=2*n;i++){
cin>>a;
if(arr[a].F==0)arr[a].F=i;
else arr[a].S=i;
}
bit.init(2*n);
for(int i=1;i<=n;i++){
ans+=bit.sum(arr[i].S-1)-bit.sum(arr[i].F);
bit.upd(arr[i].F,1);
bit.upd(arr[i].S,1);
}
cout<<ans;
}
```
Sign in with Wallet
Connect another wallet