# APCS 2019年06月題解
## 第一題 籃球比賽
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=e286
### 解套
N/A
### 題目分析
用兩個變數計算主隊和客隊的分數，再另外開一個變數紀錄主隊贏了幾次，最後按題目要求輸出即可
時間複雜度$O(1)$
### 解題流程
輸入$→$判斷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int a=0,b=0,cnt=0,inp;
```
a存主隊分數，b存客隊分數，cnt存主隊贏了幾次，inp是輸入用
#### 輸入、計算分數
```cpp=5
for(int i=0;i<4;i++){
cin>>inp;
a+=inp;
}
for(int i=0;i<4;i++){
cin>>inp;
b+=inp;
}
cout<<a<<":"<<b<<"\n";
if(a>b)cnt++;
a=b=0;
for(int i=0;i<4;i++){
cin>>inp;
a+=inp;
}
for(int i=0;i<4;i++){
cin>>inp;
b+=inp;
}
cout<<a<<":"<<b<<"\n";
if(a>b)cnt++;
```
輸入主客隊分數後先輸出分數比，再看cnt要不要加；a,b歸零後再重複一遍
#### 輸出勝負
```cpp=26
cout<<(cnt==2?"Win":(cnt==1?"Tie":"Lose"));
```
三元運算子，不習慣可以換成
```cpp
if(cnt==2)cout<<"Win";
else if(cnt==1)cout<<"Tie";
else cout<<"Lose";
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a=0,b=0,cnt=0,inp;
int main(){
for(int i=0;i<4;i++){
cin>>inp;
a+=inp;
}
for(int i=0;i<4;i++){
cin>>inp;
b+=inp;
}
cout<<a<<":"<<b<<"\n";
if(a>b)cnt++;
a=b=0;
for(int i=0;i<4;i++){
cin>>inp;
a+=inp;
}
for(int i=0;i<4;i++){
cin>>inp;
b+=inp;
}
cout<<a<<":"<<b<<"\n";
if(a>b)cnt++;
cout<<(cnt==2?"Win":(cnt==1?"Tie":"Lose"));
}
```
## 第二題 機器人的路徑
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=e287
### 解套
dfs裸題
### 題目分析
如果學過一點圖論會發現這題就是dfs，如果沒學過可以這樣想：
因為題目說
> 不斷走向周圍的格子中數值最低且沒被走過的格子
所以會需要兩個二維陣列，分別存格子的數值(int)以及那個格子有沒有走過(bool)，
我是分別取名叫做arr和been
另外因為機器人會到處跑，所以該兩個變數x,y紀錄它當前的座標
初始化的時候先輸入arr的值(期間順便找到數值最小的格子設定x,y)，然後been全部設為0
接著就是直接模擬器人走的路徑，
一開始把初始位置的been設為1，並把答案加上初始位置的arr值
然後重複以下步驟：
1. 依序判斷上、下、左、右有沒有辦法走(如果到邊界/已經走過就不能走)，如果可以且下一格式目前遇到最小值的話，就先設定往那個方向
2. 都判斷完後如果都沒辦法走就跳出迴圈，代表能走的都走完了
3. 不然就按照決定方向移動，把新位置的been設為1，並把答案加上新位置的arr值
迴圈遍歷完後輸出答案即可
時間複雜度$O(mn)$
### 解題流程
輸入$→$模擬、遍歷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,arr[100+5][100+5],mn=INT_MAX,x,y,ans=0;
bool been[100+5][100+5]={};
```
n,m同題述，arr,been如前述，mn存最小值，x,y存機器人位置，ans存答案
#### 輸入、存值、找初始位置
```cpp=6
cin>>n>>m;
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
cin>>arr[i][j];
if(arr[i][j]<mn){
mn=arr[i][j];
x=i;
y=j;
}
}
```
第9-13行更新初始位置(數值最小的位置)
#### 依初始位置更新狀態
```cpp=15
been[x][y]=1;
ans+=arr[x][y];
```
#### 模擬、遍歷
```cpp=17
int drc;//udlr 0123
while(1){
bool cmp=0;
mn=INT_MAX;
if(x!=0&&been[x-1][y]==0&&arr[x-1][y]<mn){
mn=arr[x-1][y];
drc=0;
cmp=1;
}
if(x!=n-1&&been[x+1][y]==0&&arr[x+1][y]<mn){
mn=arr[x+1][y];
drc=1;
cmp=1;
}
if(y!=0&&been[x][y-1]==0&&arr[x][y-1]<mn){
mn=arr[x][y-1];
drc=2;
cmp=1;
}
if(y!=m-1&&been[x][y+1]==0&&arr[x][y+1]<mn){
mn=arr[x][y+1];
drc=3;
cmp=1;
}
if(!cmp)break;
drc==0?x--:(drc==1?x++:(drc==2?y--:y++));
ans+=arr[x][y];
been[x][y]=1;
}
```
先開一個變數drc存方向(上下左右分別是0123)(第17行)
還有一個bool變數cmp判斷有沒有辦法走，最後mn先設成最大值(第19-20行)
接著判斷上下左右要走哪個方向(第21-40行)
以向上為例
if由前到後判斷
1. 是不是在最上面(如果是就不能往上走)
2. 上面一格是不是沒走過(有走過就不行)
3. 上面一格的值是不是小於目前找到的最小值(如果比較大就不行)
如果都符合標準就更新mn、drc與cmp
方向判斷完後如果都不能走就跳出迴圈(第41行)
不然就依照方向改變位置(第42行)(一樣是三元運算子)
並更新been與答案
#### 輸出
```cpp=46
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,arr[100+5][100+5],mn=INT_MAX,x,y,ans=0;
bool been[100+5][100+5]={};
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
cin>>arr[i][j];
if(arr[i][j]<mn){
mn=arr[i][j];
x=i;
y=j;
}
}
been[x][y]=1;
ans+=arr[x][y];
int drc;//udlr 0123
while(1){
bool cmp=0;
mn=INT_MAX;
if(x!=0&&been[x-1][y]==0&&arr[x-1][y]<mn){
mn=arr[x-1][y];
drc=0;
cmp=1;
}
if(x!=n-1&&been[x+1][y]==0&&arr[x+1][y]<mn){
mn=arr[x+1][y];
drc=1;
cmp=1;
}
if(y!=0&&been[x][y-1]==0&&arr[x][y-1]<mn){
mn=arr[x][y-1];
drc=2;
cmp=1;
}
if(y!=m-1&&been[x][y+1]==0&&arr[x][y+1]<mn){
mn=arr[x][y+1];
drc=3;
cmp=1;
}
if(!cmp)break;
drc==0?x--:(drc==1?x++:(drc==2?y--:y++));
ans+=arr[x][y];
been[x][y]=1;
}
cout<<ans;
}
```
## 第三題 互補CP
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=e288
### 解套
給定一些字串，求有幾組(一組兩個)字串沒有重複字元且涵蓋所有字元
### 題目分析
這題最重要的關鍵是如何有效率地把有重複字母的字串變成沒有重複的，並快速地找到「互補CP」
一開始可能會想要把字串排序、再去除重複元素(C++確實有內建的相關函式)，或是用set之類的，但這樣的缺點是光花在排序的時間就有點長(可以略估一下複雜度)，而且更重要的是沒有辦法有效地找到互補CP(用unordered_set能避免排序但還是無法有效找到互補CP)
這時候就輪到~~通靈~~位運算登場了！(位運算一開始可能有點難想到但會用就真的很方便)
我們會發現如果把數字轉成二進位，那每個位元都是0或1，剛好可以代表有沒有某個字母
因為只有38個所以最多只會用到$2^{38}$，還在long long的範圍內
我們只要把A-Z轉成第0-25位，a-l轉成第26-37位，再利用位元的或運算就能把字串轉成數字了！
而互補的部分則要利用XOR運算
假設一個二進位數字一開始全部都是1，跟另一個數字XOR的話會把0變1，1變0，剛好就是我們要的，於是我們就有快速找到互補的方式了
(位運算較詳細解釋在後面配合程式碼)
於是就得到解法：
先遍歷每個字串把它轉成long long數字後存到unordered_map裡
接著遍歷unordered_map，對每個數字找到他的互補數字，並把答案加上兩者的出現次數的乘積
最後輸出答案即可，不過因為每種組合會算到兩遍(A×B和B×A)，所以答案要除以二
時間複雜度$O(nl)$，其中l是字串長度
### 解題流程
輸入、轉換成數字$→$遍歷、找互補、算答案$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int m,n;
long long ans=0;
string s;
unordered_map<long long,long long>mp;
```
m,n同題述，存答案，s是輸入用字串，mp存各數字出現次數
#### 轉換函式
```cpp=7
int cvt(char c){
return c<='Z'?c-'A':c-'a'+26;
}
```
方便把字母轉成數字
#### 輸入優化
```cpp=11
ios::sync_with_stdio(0);
cin.tie(0);
```
不加會TLE(或改用scanf、printf)
#### 輸入，存進mp
```cpp=13
cin>>m>>n;
for(int i=0;i<n;i++){
cin>>s;
long long tmp=0;
for(char c:s)tmp|=(long long)1<<(cvt(c));
mp[tmp]++;
}
```
先輸入m,n，接著讀入每個字串，並用位元或運算產生對應數字
以ABAC為例：
ABAC經過cvt函式後變成0 1 0 2
而tmp原本為$000$，與$001$作或運算變$001$，再與$010$作或運算變$011$，
再與$001$作或運算變$011$，最後與$100$作或運算變$111$，就是最後的目標字串
用或而不是用加是為了避免有重複的出現
另外需要注意把數字強制轉long long該數字一定要緊接在long long後面，即
```cpp
((long long)num)
```
我一開始寫成
```cpp
(long long)(num)
```
結果一直錯
另外1<<n是在二進位觀點下把1左移幾格，如1<<3是$(1000)_2$，也就是8
運算上比pow(2,n)快許多
#### 遍歷
```cpp=20
auto it=mp.begin();
while(it!=mp.end()){
long long tmp=(((long long)1<<m)-1)^(it->first);
if(mp.find(tmp)!=mp.end())ans+=(it->second)*mp[tmp];
it++;
}
```
生成互補數字的方式是用XOR的方式，說明如下：
假設m為5，要求$11010$的互補數字，就先設tmp是$11111$，
與$11010$做XOR後就會變成$00101$也較是互補字串
這是因為我們要把0變1、1變0，而對1做XOR剛好能達到這個效果
一樣注意long long的處理方式
#### 輸出
```cpp=26
cout<<ans/2;
```
記得除2
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int m,n;
long long ans=0;
string s;
unordered_map<long long,long long>mp;
int cvt(char c){
return c<='Z'?c-'A':c-'a'+26;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>m>>n;
for(int i=0;i<n;i++){
cin>>s;
long long tmp=0;
for(char c:s)tmp|=(long long)1<<(cvt(c));
mp[tmp]++;
}
auto it=mp.begin();
while(it!=mp.end()){
long long tmp=(((long long)1<<m)-1)^(it->first);
if(mp.find(tmp)!=mp.end())ans+=(it->second)*mp[tmp];
it++;
}
cout<<ans/2;
}
```
## 第四題 美麗的彩帶
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=e289
### 解套
求一數列所擁有的長度為$m$且有$m$種顏色的子區間數量
### 題目分析
第一個要注意的是數字大小最大可以到$10^{150}$，明顯超出long long範圍，所以要用字串存
接著就是處理題目的要求
比較直觀的作法是固定區間長度為$m$，由左往右掃，每次移一格
但要怎麼看區間裡是否剛好有$m$個不重複的數字？
最暴力的想法可能是用unordered_map紀錄每個數字出現幾次，每次直接掃一遍看符不符合，
但這樣的時間複雜度會是$O(mn)$，明顯超時
但仔細想想，每次移動其實只是把第一個數字去掉並加入最後一個數字而已，
所以或許我們可以只專注在這兩個數字？
一開始可能會不知道怎麼處理，不過可以這樣想：
我們還是需要一個unordered_map紀錄每個數字出現幾次，
但只有在某個數字出現次數「由0變1」時區間的數字種類才會增加，
同理只有在某個數字出現次數「由1變0」時區間的數字種類才會減少
所以我們可以額外維護一個變數cnt紀錄區間裡有幾種數字，從左到右掃過並依前述規則改變cnt的值，當cnt等於$m$時代表有一個區間剛好有m種數字，就把答案加1
時間複雜度$O(n)$
### 解題流程
輸入$→$由左往右遍歷$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int m,n,ans=0;
string s[200000+10];
unordered_map<string,int>mp;
```
m,n同題述，ans存答案，s存字串，mp存個數字出現次數
#### 輸入優化
```cpp=7
ios::sync_with_stdio(0);
cin.tie(0);
```
不加會TLE(或改用scanf、printf)
#### 輸入
```cpp=9
cin>>m>>n;
for(int i=0;i<n;i++)cin>>s[i];
```
#### 處理第一個區間
```cpp=11
int cnt=0;
for(int i=0;i<m;i++){
if(mp[s[i]]==0){
cnt++;
mp[s[i]]++;
}
else mp[s[i]]++;
}
if(cnt==m)ans++;
```
先開變數cnt存有幾種數字(第11行)
接著處理前m個數字(要注意這裡只有加數字的操作)，若原本不存在這個數字(第13行)就讓cnt加一，然後更新mp裡的數字
最後若cnt等於m答案加一
#### 遍歷
```cpp=20
for(int i=m;i<n;i++){
mp[s[i-m]]--;
if(mp[s[i-m]]==0)cnt--;
if(mp[s[i]]==0){
cnt++;
mp[s[i]]++;
}
else mp[s[i]]++;
if(cnt==m)ans++;
}
```
與前面幾乎相同，只是多了把最左邊的數字除掉的操作(第21行)，並看是否影響數字種類(第22行)
#### 輸出
```cpp=30
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int m,n,ans=0;
string s[200000+10];
unordered_map<string,int>mp;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>m>>n;
for(int i=0;i<n;i++)cin>>s[i];
int cnt=0;
for(int i=0;i<m;i++){
if(mp[s[i]]==0){
cnt++;
mp[s[i]]++;
}
else mp[s[i]]++;
}
if(cnt==m)ans++;
for(int i=m;i<n;i++){
mp[s[i-m]]--;
if(mp[s[i-m]]==0)cnt--;
if(mp[s[i]]==0){
cnt++;
mp[s[i]]++;
}
else mp[s[i]]++;
if(cnt==m)ans++;
}
cout<<ans;
}
```
Sign in with Wallet
Connect another wallet