# APCS 2016年10月題解
## 第一題 三角形辨別
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c294
### 解套
N/A
### 題目分析
本題分成兩個部分：決定大小順序和判斷三角形種類
因為只有三個數字，所以在大小方面最小的就對三邊取最小值、最大就對三邊取最大值、而中間的我是用三邊邊長總合減最大與最小來計算
判斷三型種類則是用簡單的if依序判斷就好
時間複雜度$O(1)$
### 解題流程
輸入$→$排序$→$判斷、輸出
### 解題過程
#### 變數宣告
```cpp=3
int a,b,c,d,e,f;
```
d,e,f吃輸入；a,b,c存排序後的邊長
#### 輸入
```cpp=5
cin>>d>>e>>f;
```
#### 排序
```cpp=6
a=min({d,e,f});
c=max({d,e,f});
b=d+e+f-a-c;
```
方法同前述
#### 輸出、判斷
```cpp=9
cout<<a<<" "<<b<<" "<<c<<"\n";
if(a+b<=c)cout<<"No";
else{
a*=a;b*=b;c*=c;
if(a+b<c)cout<<"Obtuse";
else if(a+b==c)cout<<"Right";
else cout<<"Acute";
}
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,f;
int main(){
cin>>d>>e>>f;
a=min({d,e,f});
c=max({d,e,f});
b=d+e+f-a-c;
cout<<a<<" "<<b<<" "<<c<<"\n";
if(a+b<=c)cout<<"No";
else{
a*=a;b*=b;c*=c;
if(a+b<c)cout<<"Obtuse";
else if(a+b==c)cout<<"Right";
else cout<<"Acute";
}
}
```
## 第二題 最大和
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c295
### 解套
N/A
### 題目分析
直接操作即可。
最直觀的作法會是用二維陣列存所有數字，不過我用稍微難一點的方法，就是對每組數字邊吃輸入更新最大值，並把最大值加到總和並存起來，最後一個一個判斷是否整除總和即可
另外因為要求結尾不能有空格，所以答案先全部存起來再輸出
時間複雜度$O(mn)$
### 解題流程
輸入、決定最大值$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,sum=0,inp;
vector<int>picked,last;
```
n,m同題述，sum存總和，inp是輸入用，picked存被選到的數字，last存能整除的
#### 輸入、更新
```cpp=6
cin>>n>>m;
picked.assign(n,0);
for(int i=0;i<n;i++){
int mx=INT_MIN;
for(int j=0;j<m;j++){
cin>>inp;
mx=max(mx,inp);
}
picked[i]=mx;
sum+=mx;
}
```
依照n決定picked的大小(第7行)
接著對每組數字，先設一個最大值，並邊輸入邊更新最大值，最後把它加進總和並放入picked
#### 輸出
``` cpp=17
cout<<sum<<"\n";
for(int i:picked)if(sum%i==0)last.push_back(i);
if(last.empty())cout<<-1;
else{
cout<<last[0];
for(int i=1;i<last.size();i++)cout<<" "<<last[i];
}
```
先輸出總和(第17行)
接著把能整除總和的放進last(第18行)
然後按題述輸出即可(注意沒有符合的要輸出-1，且結尾不能有空白)
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,sum=0,inp;
vector<int>picked,last;
int main(){
cin>>n>>m;
picked.assign(n,0);
for(int i=0;i<n;i++){
int mx=INT_MIN;
for(int j=0;j<m;j++){
cin>>inp;
mx=max(mx,inp);
}
picked[i]=mx;
sum+=mx;
}
cout<<sum<<"\n";
for(int i:picked)if(sum%i==0)last.push_back(i);
if(last.empty())cout<<-1;
else{
cout<<last[0];
for(int i=1;i<last.size();i++)cout<<" "<<last[i];
}
}
```
## 第三題 定時K彈
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c296
### 解套
約瑟夫問題
### 題目分析
基本上跟經典的[約瑟夫問題](https://oi-wiki.org/misc/josephus/)非常像，因此只需要對約瑟夫問題的$O(n)$解法做一些些微的調整就好
如果最後只剩一個人解法會長這樣：
```cpp
int josephus(int n,int m) {
int res=0;
for(int i=1;i<=n;i++)res=(res+m)%i;
return res;
}
```
其中n代表有幾個人，m代表一次屬幾個人
但這題只會去除k個人，而且第一個人編號是1，所我們稍微做一下改寫：
```cpp
int josephus(int n,int m) {
int res=0;
for(int i=n-k+1;i<=n;i++)res=(res+m)%i;
return res+1;
}
```
把i=1～n改成i=n-k+1讓我們只去除k個人，要注意的是不能改成i=1～k
(因為對i取模是在處理剩下人數)
最後加一是為了變回1-base
時間複雜度$O(k)$
### 解題流程
輸入$→$套公式$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int n,m,k;
```
變數名同題述
#### 輸入
```cpp=5
cin>>n>>m>>k;
```
#### 找答案、輸出
```cpp=6
int tmp=0;
for(int i=n-k+1;i<=n;i++)tmp=(tmp+m)%i;
cout<<tmp+1<<"\n";
```
跟前面一樣，只是不是用函式的形式呈現
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int main(){
cin>>n>>m>>k;
int tmp=0;
for(int i=n-k+1;i<=n;i++)tmp=(tmp+m)%i;
cout<<tmp+1<<"\n";
}
```
## 第四題 棒球遊戲
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=c297
### 解套
N/A
### 題目分析
這題到底是想考甚麼...?
早期的APCS都這樣嗎?
唯一比較要注意的是打擊順序是由上而下，由左而右的，所以不能直接吃輸入
我的作法是用9個vector存每個打者的狀況，再合併起來處理
其餘就直接照規則做就好
時間複雜度$O(1)$(最多只有45個數字)
### 解題流程
輸入$→$調整順序$→$按規則計算分數$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int a,b,cnt=0,pts=0,outs=0;
bool one=0,two=0,three=0;
vector<string>v[9],arr;
```
a,b輸入用，cnt紀錄有幾次打擊，pts紀錄分數，outs紀錄出局數，one,two,three紀錄一二三壘有沒有人，v存初始輸入，arr按順序存打擊狀態
#### 輸入
```cpp=7
for(int i=0;i<9;i++){
cin>>a;
cnt+=a;
v[i].assign(a,"");
for(int j=0;j<a;j++)cin>>v[i][j];
}
cin>>b;
```
#### 轉成按順序存
```cpp=14
for(int i=0;i<5&&cnt;i++){
for(int j=0;j<9&&cnt;j++){
arr.push_back(v[j][i]);
cnt--;
}
}
```
cnt確保不會多存導致記憶區間錯誤
#### 計算分數
```cpp=20
for(int i=0;i<arr.size()&&b>0;i++){
if(arr[i]=="1B"){
if(three){
pts++;
three=0;
}
if(two){
three=1;
two=0;
}
if(one){
two=1;
one=0;
}
one=1;
}
else if(arr[i]=="2B"){
if(three){
pts++;
three=0;
}
if(two){
pts++;
two=0;
}
if(one){
three=1;
one=0;
}
two=1;
}
else if(arr[i]=="3B"){
if(three){
pts++;
three=0;
}
if(two){
pts++;
two=0;
}
if(one){
pts++;
one=0;
}
three=1;
}
else if(arr[i]=="HR"){
if(three){
pts++;
three=0;
}
if(two){
pts++;
two=0;
}
if(one){
pts++;
one=0;
}
pts++;
}
else{
outs++;
b--;
if(outs%3==0)one=two=three=0;
}
}
```
比較直接的做法，只是按照規則寫而已
雖然題目的三種出局分別給不同的代號，但統一處理即可，所以統一放在else裡面
需要特別注意的是如果出局數達到三的倍數就要清空壘包(第84行)
#### 輸出
```cpp=87
cout<<pts;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int a,b,cnt=0,pts=0,outs=0;
bool one=0,two=0,three=0;
vector<string>v[9],arr;
int main(){
for(int i=0;i<9;i++){
cin>>a;
cnt+=a;
v[i].assign(a,"");
for(int j=0;j<a;j++)cin>>v[i][j];
}
cin>>b;
for(int i=0;i<5&&cnt;i++){
for(int j=0;j<9&&cnt;j++){
arr.push_back(v[j][i]);
cnt--;
}
}
for(int i=0;i<arr.size()&&b>0;i++){
if(arr[i]=="1B"){
if(three){
pts++;
three=0;
}
if(two){
three=1;
two=0;
}
if(one){
two=1;
one=0;
}
one=1;
}
else if(arr[i]=="2B"){
if(three){
pts++;
three=0;
}
if(two){
pts++;
two=0;
}
if(one){
three=1;
one=0;
}
two=1;
}
else if(arr[i]=="3B"){
if(three){
pts++;
three=0;
}
if(two){
pts++;
two=0;
}
if(one){
pts++;
one=0;
}
three=1;
}
else if(arr[i]=="HR"){
if(three){
pts++;
three=0;
}
if(two){
pts++;
two=0;
}
if(one){
pts++;
one=0;
}
pts++;
}
else{
outs++;
b--;
if(outs%3==0)one=two=three=0;
}
}
cout<<pts;
}
```
Sign in with Wallet
Connect another wallet