# 南部四校聯合 2020 9 月初學者程式設計線上練習賽 題解
## 前言
感謝各位參加了這次的比賽 希望大家都有好的收穫 為了讓我們
更好 請大家撥空填寫以下表單 給我們一點回饋 我們會在下一個
月辦出更好的比賽給大家的 ! 希望大家都有享受的 Coding 的
樂趣喔 !
表單連結 : https://docs.google.com/forms/d/e/1FAIpQLScNJdObAbIKk6g-7YhRGvgup8AgiGhEZnNlRSoA8OoBr7nmow/viewform
## 記分板(Standing)
https://codeforces.com/group/H0qY3QmnOW/contest/294260/standings/groupmates/true
## 題解
### Problem A - 四校聯合茶會
**Idea : 俊安 Colten**
這題要注意的地方只有 10 分的題目限制 可能含有空白的字元
如果沒注意到這點的話可能就只會拿到 90 分
:::spoiler 官方解(C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
string S;
getline(cin,S);
cout << "Welcome! " << S << "\n";
return 0;
}
```
:::
### Problem B - 負不得正 但負負得正
**Idea 俊安 Colten**
題目要求判斷整數 $N$ 是否為負數 這題要注意的地方在於範圍
如果在最不好的情況下可能只會得到 80 分
最保險的解法為 **字串解** 輸入一個字串 S 去判斷 S[0] 是否 == '-' 即可
:::spoiler 官方解(C++)
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
string S;
cin >> S;
cout << ( S[0]=='-' ? "Yes\n" : "No\n");
return 0;
}
```
:::
### Problem C - 資訊社入社考的邂逅
**Idea : 俊安 Colten**
從題目可以得知題目想要求 $a_i >= b$ 的人數
我們可以先設一個變數 $d$ 來記錄能夠加入資訊社的人數
每當輸入一個 $a_i$ 就去判斷是否 $>=b$ 如果是 就把 $d + 1$
:::spoiler 官方解(C++)
```cpp=
#include <iostream>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int a,b,c,d=0,i,input;
cin >> a >> b;
for(i=0;i!=a;i++)
{
cin >> input;
if(input>=b)
{
d++;
}
}
cout << d << "\n";
}
```
:::
### Problem D - 北門路上的數學謎題
**Idea : 俊安 Colten**
題目會輸入一個 $N$ 想要找符合以下式子的 $a,b,c$
$GCD(a,b) + LCM(a,b,c) + GCD(b,c) = N$
這題的解法其實有很多種 任何一種都會給對 這邊提供其中一種
換個方向想 只要讓 $GCD(a,b),GCD(b,c) = 1$ 以及
$LCM(a,b,c) = N-2$ 就可以達成題目條件了 !
所以你可以使 $a=1,b=1,c=N-2$ 就符合題目要求了
$GCD(1,1)=1,LCM(1,1,N-2)=N-2,GCD(1,N-2)=1$
$1+N-2+1=N$
:::spoiler 官方解(C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int q,n,i,k;
cin >> q;
while(q--)
{
cin >> n;
cout << 1 << " " << 1 << " " << n - 2 << "\n";
}
return 0;
}
```
:::
### Problem E - 色違拉姆的數列
**Idea : 煜傑 Fysty**
首先要先提醒一件重要的事：
除了極少數的題目以外，不要用int，只用long long，這可以幫你省掉很多WA。
首先從題意可推出$b_i=\sum_{j=0}^{i}a_j-a_{i-1}$。
換句話說，$a_i=b_i-\sum_{j=0}^{i-2}a_j,\forall i\ge2$
特別地，$a_1=b_1$。
如果我們算的順序是$a_1,a_2,...,a_n$，
則在計算$a_i$的時候，已經知道$a_{i-1},a_{i-2},...,a_1,a_0$了。
所以可以每次要算$a_i$的時候，
將$a_0$到$a_{i-2}$通通加起來$=sum_{i-2}$，就能輕易算出$a_i=b_i-sum_{i-2}$了。
但是這樣複雜度是$O(n^2)$，也就是說會TLE。
那該怎麼辦呢？
注意到$sum_{i}=sum_{i-1}+a_{i}$。
所以我們其實每次算$sum_i$的時候，
只需要拿上次用的$sum_{i-1}$就可以在$O(1)$的時間內算出$sum_i$了。
總時間複雜度$O(n)$。
:::spoiler 官方解(C++)
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n,sum=0,tmp;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>tmp;
if(i<=2) a[i]=tmp;
else a[i]=tmp-sum;
if(i>=2) sum+=a[i-1];
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
```
:::
這裡順便為幾件事道個歉：
(1)數列$<b_n>$的出現太突然
(2)$a_0$的意義沒有講得很清楚
(3)子題組的限制漏寫
### Problem F - 放大吧 ! 風原飛鏢隊的電子標靶
**Idea : 俊安 Colten**
解題關鍵 : 使用點到點的距離公式去求 距離是否 $\le R$
每輸入一個點 $(x,y)$ 就與 $(x_o,y_o)$ 去求距離
如果距離 $\le R$ 就代表這個點在圓內或圓上 就把分數 $+2$
點到點距離公式 : $\sqrt{(x_1-x2)^2+(y_1-y_2)^2}$
:::spoiler 官方解1(C++)
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int q,n,i,k,T;
cin >> T;
int x0,y0;
cin >> x0 >> y0;
int ans = 0,R;
cin >> R;
while(T--)
{
int x,y;
cin >> x >> y;
double d = sqrt((x-x0)*(x-x0) + (y-y0)*(y-y0));
if( d <= R )
{
ans += 2;
}
}
cout << ans << "\n";
return 0;
}
```
:::
::: spoiler 官方解2(C++)使用struct
```cpp=
#include<bits/stdc++.h> //finished,auther J.T.
using namespace std;
int main(){
int n;
while(cin>>n){
int x0,y0,r,cnt=0;
cin>>x0>>y0>>r;
r=pow(r,2);
struct d{
int x,y,dist;
};
d z[n+5];
for(int i=1;i<=n;i++){
cin>>z[i].x>>z[i].y;
z[i].x=pow((z[i].x-x0),2);
z[i].y=pow((z[i].y-y0),2);
z[i].dist=z[i].x+z[i].y;
if(z[i].dist<=r){
cnt+=2;
}
}
cout<<cnt<<endl;
}
}
:::
### Problem G - 平衡兔子序列
**Idea: Xuan**
此題的重點是中位數
中位數是一個由高到低排列的數列中位居正中間的值
e.g. 數列1、2、5 ，2即為此數列的中位數
如果覺得把M放在中間，其他兩個隨便放就錯了
因為中位數只能遞增或遞減
假若題目要求中位數是5，而你給出8、5、9的數列
那實際上中位數會是8而非5
:::spoiler 官方解(C++) O(NlogN)
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
ll a[100005];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(ll i=2;i<n;i++)
{
if(a[i]==m)
{
cout<<"Yes"<<endl;
cout<<a[i-1]<<" "<<a[i]<<" "<<a[i+1];
break;
}else if(i==n-1)
cout<<"No";
}
}
```
:::
### Problem H - 菜月昴與回文
**Idea : 煜傑 Fysty**
(比賽結束後才發現)參考題目來源：NPSC 2019 高中決賽 pD
首先注意到任一個回文中
若某種字母在出現的次數是奇數次，則回文的長度必為奇數且最中間的字母就是它。
原理很簡單，因為除了正中間的字母以外，其他都會兩兩成對出現在回文的左右。
所以我們可以獲得以下推論：
若回文的長度為偶數，則因為不存在最中間，所以所有字母皆會倆倆出現。
若回文的長度為奇數，則因為恰有一個最中間，所以除了某一種字母以外，所有字母皆會倆倆出現。
統整一下，我們可以發現以下性質：
要構造出一個回文，原字串至多只能有一種字母出現奇數次。
因此我們可以紀錄$a$到$z$分別出現幾次，並統計為奇數的有$cnt$個。
若$cnt>1$，
則答案為$-1$。
接下來要解決字典序的問題。
注意到當我們決定完前半的順序，後半的順序就完全定死了(因為要跟前半完全相反)，
因此只需要考慮前半要如何放就好
而因為前後半同個字母出現的次數相同，所以我們先把每個字母的個數先減半。
字典序最小時，還有$a$就一定排最前面，再來是$b$，然後是$c$，如此一般到$z$。
形成字串$S$。
後半的求法就相反，形成字串$S'$。
那麼答案就是$S$和$S'$連在一起嗎？
答案是否定的
當$cnt=0$的時候才一定正確。
然而當$cnt=1$時有時候會出錯。
為什麼？這裡就要注意一個陷阱。
剛說過，出現奇數次的那個字母一定要在最終回文$S$的最中間。
換句話說，若$cnt=1$，則出現奇數次的那個字母絕對要在最終回文$S$的最中間。
也就是說若$cnt=1$，則最中間的那個字母是釘死的
也就是說假設出現奇數次的那種字母是$C$，則答案為$S,C,S'$依序連在一起。
總時間複雜度$O(n)$或$O(n\log n)$，而會有不同的複雜度，是因為求$S'$的方法不同。
:::spoiler 官方解(C++) O(n)
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
ll q;
cin>>q;
while(q--)
{
ll cnt[30]={0},k=-1,x=0;
string s,t;
cin>>s;
for(int i=0;i<s.size();i++)
{
cnt[s[i]-'a']++;
}
for(int i=0;i<26;i++)
{
if(cnt[i]%2)
{
x++,k=i;
}
}
if(x>1) cout<<"-1\n";
else
{
for(int i=0;i<26;i++)
{
char c='a'+i;
for(int j=0;j<cnt[i]/2;j++) cout<<c;
}
if(k!=-1)
{
char c='a'+k;
cout<<c;
}
for(int i=25;i>=0;i--)
{
char c='a'+i;
for(int j=0;j<cnt[i]/2;j++) cout<<c;
}
cout<<"\n";
}
}
return 0;
}
```
:::
:::spoiler 官方解(C++) O(nlogn)
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
ll q;
cin>>q;
while(q--)
{
ll cnt[30]={0},k=-1,x=0;
string s,t;
cin>>s;
for(int i=0;i<s.size();i++)
{
cnt[s[i]-'a']++;
}
for(int i=0;i<26;i++)
{
if(cnt[i]%2)
{
x++,k=i;
}
}
if(x>1) cout<<"-1\n";
else
{
for(int i=0;i<26;i++)
{
char c='a'+i;
for(int j=0;j<cnt[i]/2;j++) t.push_back(c);
}
cout<<t;
if(k!=-1)
{
char c='a'+k;
cout<<c;
}
reverse(t.begin(),t.end());
cout<<t<<"\n";
}
}
return 0;
}
```
:::
這裡再次為幾件事道個歉：
(1)字串專有名詞定義和題目限制只用寫數學表達，沒多做說明
(2)題目不夠語法
### Problem I - 我打怪獸～打怪獸
**出題者 : 隨風** 參考題目來源: [Qualification Round 2020 pB](https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9f)
對每個怪獸跑一次
我們只要一直迴護兩個性質:
1. 用一個變數Ｌ紀錄使**當前左括號的數量等於當前怪獸的能力值**
2. 如果上一個怪獸的能力值大於下一個那就靠右括號平衡數量
然後因為最後都要讓所有怪獸能力值為0，所以幫怪獸字串加了一個0, 觸發第二個性質，讓最後一個怪獸能力值歸零，其他怪獸也會因為先前都被第二性質平衡過了，所以只要一直補足下一個怪獸所需的括號直到最後一個怪獸就會剛好完全抵消了。
然後題目好像沒有敘述到不能讓怪獸能力為小於0抱歉QQ
:::spoiler 官方解(C++) O(N)
```cpp=
//Author: Suifeng0214
#include <bits/stdc++.h>
using namespace std;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for (int i = 1; i <= t; i++){
string s, ans;
int l=0;
cin >> s;
s+='0';
for (int i = 0; i < s.size()-1; i++){
while(l<s[i]-'0'){
ans+='(';
l++;
}
ans += s[i];
while(l>s[i+1]-'0'){
l--;
ans+=')';
}
}
cout << "Round #" << i << ": " << ans << "\n";
}
}
```
:::
### Problem J - 工程師玩的桌遊
**Idea : J.T.**
參考題目來源:
http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d068
河內塔是遞迴的經典題型
不出單色河內塔是因為太經典了，用搜的就搜尋的到
為了配合規則大在下小在上，在移動過程中我把柱子分為三根
1.src:起始點(start) 2.dst:終點(end) 3.tmp:緩衝(buffer)
接著就是觀察移動規則並寫成函式即可
範例測資就是給大家觀察用的(~~偷分用~~)<3
:::spoiler 官方解(C++，不一定是最佳解)
```cpp=
#include<bits/stdc++.h> //finished,auther J.T.
using namespace std;
long long cnt=0;
void h(int n,char src,char dst,char tmp){ //src=start,dst=end,tmp=buffer
if(n<=0){
return;
}else{
h(n-1,src,tmp,dst);
cout<<"ring "<<n<<" : "<<src<<" => "<<dst<<endl;
cnt++;
h(n-1,tmp,dst,src);
}
}
void dist(int n,char src,char dst,char tmp){ //src=start,dst=end,tmp=buffer
if(n<=0){
return;
}else{
h(n-1,src,tmp,dst);
cout<<"ring "<<n<<" : "<<src<<" => "<<dst<<endl;
cnt++;
dist(n-2,tmp,src,dst);
}
}
int main(){
int n;
while(cin>>n){
dist(n,'A','C','B'); //(n,start,end,buffer)
cout<<"total="<<cnt<<" steps"<<endl;
cnt=0;
}
}
:::
我要跟大家道個歉，本來想出遞迴當防破台
結果發現題目出太難了有點超出這次的範圍，真的很抱歉
然後因為我是第一次出題，如果題目或官解打得不好請多多包涵><
Google Drive
Gist
Clipboard
Sign in with Wallet
