# KSPGC 前測題解
###### tags: `題解`
## pA 歡迎加入程式設計社
源自去年前測
### 常見錯誤：忘記有驚嘆號
==
:::spoiler 錯誤code (python)
```python
print("Hello KSPGC")
```
:::
### 正確做法
其實不管你有沒有讀取輸入，你都會過
:::spoiler 官解 (C\++)
```cpp
#include <iostream>
using namespace std;
int main(){
cout << "Hello KSPGC!";
}
```
:::
:::spoiler 官解 (python)
```python
print("Hello KSPGC!")
```
:::
## pB 買月餅
Idea by niter
### 常見錯誤：用"/"運算符來計算除法(python)
python有"/"和"//"兩種除法運算符，
第一種是用來計算浮點數的，不論是否整除，它總是輸出浮點數
第二種是用來計算整數的，它會無視餘數，總是輸出整數
如果使用"/"，最後輸出的答案就會含有小數點(必吃WA)
### 常見錯誤：以為買盒裝的總是比買單個的便宜
:::spoiler 錯誤code (C\++)
```cpp
#include <iostream>
using namespace std;
int main(){
int n, m, a, b;
cin >> n;
for(int i=0; i<n; i++){
cin >> m >> a >> b;
cout << (m/6)*a+(m%6)*b << endl;
}
return 0;
}
```
:::
可以卡掉這個解法的測資：
m = 6, a = 100, b = 1
這段錯誤的程式碼會輸出100，但答案是6
### 正確做法
我們要先判斷買越多盒裝的越好，還是全買單個的比較好
:::spoiler 官解 (C\++)
```cpp
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
int m, a ,b;
cin >> m >> a >> b;
int ans = (m/6)*a + m%6*b;
if(a > 6*b) ans = m*b;
cout << ans << endl;
}
return 0;
}
```
:::
判斷a是否大於6b，就相當於判斷：買盒裝跟單個，哪一種平均一個月餅比較貴
如果你要寫a/6>b，就要用浮點數計算，
因為C\++的整數除法會捨去小數點後的所有數字，因此在C\++中，7/3和2相等
另一個可行的寫法：
:::spoiler code (C\++)
```cpp
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
int m, a ,b;
cin >> m >> a >> b;
int ans = (m/6)*a + m%6*b;
if(((float)(a))/6 > b) ans = m*b; // 這一行的條件式
cout << ans << endl;
}
return 0;
}
```
:::
## pC 二次方程式
語法經典題，因式分解用得到
因為judge的部分我沒用好，所以我rejudge了
部份的人TLE只剩55分
### 常見錯誤：用int來讀取輸入
你不能用int來讀取浮點數輸入，會出現意想不到的結果
你應該用double存取浮點數
### 關於用python然後TLE這件事
我發現如果使用eval()函數把浮點數字串轉成整數，會消耗大量的時間，然後就TLE了
你應該使用float()函數
::: spoiler AC code (python)
```python
while True:
try:
a = input()
except:
break
print(int((int(float(a)))**0.5))
```
:::
如果再搭配輸入輸出優化，效率可以提升到超過10倍
### 正確做法
直接讀取double輸入，因為它的精度很高
然後再利用一個特性：把浮點數指派給整數變數時，小數部分會被自動捨去(剛好如題目要求)
註：sqrt函數的功能是開根號
:::spoiler 官解 (C\++)
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
double n;
while(cin >> n){
int ans = sqrt(n); // 自動捨去小數部分
cout << ans << "\n";
}
}
```
:::
## pD 找X
Idea by 鄭勝宇(sean9575)
他原本給我的題目其實更難，下次再出好了(可以先猜猜是什麼)
### 常見錯誤：雙迴圈(每次詢問時都搜尋一次整個陣列)
如果$n,q$給到最大($10^6$)，且每次詢問的位置都是最後一項呢？
那麼就要跑$10^6\times10^6=10^{12}$次迴圈!!!
如果電腦1秒可以跑$10^8$次加法(通常寫題目的時候都是用這個值來算會不會過)，
那麼這個程式就要跑$\approx\frac{10^{12}}{10^8}=10^4$秒，一定會TLE
### 正確做法
注意到$a_i$的值域不大
所以我們可以建一個$10^6$項的陣列left，left[x]代表數字x在陣列a中由左到右第1個出現的位置的索引值
一開始，我們設定整個陣列left的值都是-1，代表還沒有出現任何數字
然後，我們由左到右搜索整個陣列a，
對於每個a[i]，我們檢查left[a[i]]是否為-1，
如果是-1，表示在目前的索引值i之前還沒有出現任何跟a[i]相同的數，
我們就可以把left[a[i]]的值設為i，表示a[i]這個數在索引值i的地方第一次出現
如果不是-1，表示a[i]這個數已經在比索引值i更前面的地方出現過了，
因此我們保留這個值，不作任何更動
在詢問時，對於輸入的數字x，我們可以直接輸出left[x]，因為它就是答案
因為題目保證不會沒有答案，所以left[x]不可能是-1
:::spoiler 官解 (C\++)
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
int left[1000010], a[1000010];
for(int i = 0; i <= 1000000; i++){
left[i] = -1;
}
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < n; i++){
if(left[a[i]] == -1){
left[a[i]] = i;
}
}
int x;
for(int i = 0; i < q; i++){
cin >> x;
cout << left[x] << "\n";
}
return 0;
}
```
:::
<br>其實你可以一邊輸入一邊對left陣列做處理，少開一個a陣列
:::spoiler 優化後的code (C\++)
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
int left[1000010], in;
for(int i = 0; i <= 1000000; i++){
left[i] = -1;
}
for(int i = 0; i < n; i++){
cin >> in; // in 就是 a[i]
if(left[in] == -1){
left[in] = i;
}
}
int x;
for(int i = 0; i < q; i++){
cin >> x;
cout << left[x] << "\n";
}
return 0;
}
```
:::
## pE 陣列搜尋
Idea by niter
雖然我很想把lower bound（$O(n\log n+n\log n)$）卡掉，但其實不太可能（官解$O(n\log n)$）
### 常見錯誤：直接模擬(雙迴圈)
遍歷整個陣列，尋找最大的數(最多$n$圈)，然後標記它
以上動作重複$n$次
這樣最差情況下需要$n^2$次計算，總共跑了$(10^5)^2=10^{10}$次，
也就是$\approx100$秒，這樣就會TLE
(有沒有發現這個做法很像Selection sort？)
(知道要排序之後，是不是可以改用比Selection sort更好的排序法？)
### 正確做法
注意到$a_i$的初始值必大於0，所以已經變成0的數就不會再改變了，
因此這些數字變成0的順序就只跟它原本的大小有關
最大的一定第一個變成0，最小的一定最後變成0，
我們只需要`排序`就能得知這些數的大小順序(變成0的順序)
(C\++的內建排序是$O(n\log n$))
再來就是實作的問題了，要注意一樣的數會同時變成0
我們用pair資料結構，在排序的同時紀錄數字原本的位置($i$)，
把數字的值放在pair的第一項，他原本的位置放在第二項
這樣排序時就會先排數值，再排位置
我們用for迴圈遍歷排序後的陣列，並以run變數來記錄這個數字會在第幾次操作後變成0，
因為相同的數值會被排在一起(可以把排序後的陣列print出來觀察看看)，
所以只要跟前一項作比較，就能知道是不是相同的數
如果是，run變數就不要增加，代表兩個數會同時變成0
否則run變數加1，代表目前的數會在前一個數變成0之後的下一次操作才變成0
:::spoiler 官解 (C\++)
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
int Ans[n];
pair<int,int> a[n];
for(int i = 0; i < n; i++){
cin >> a[i].first;
a[i].second = i;
}
sort(a, a+n, greater<pair<int,int>>());
int run = 1;
Ans[a[0].second] = run;
for(int i = 1; i < n; i++){
if(a[i].first != a[i-1].first) // 相同的數會同時變成0
run++; // run變數+1表示是不同的數
Ans[a[i].second] = run;
}
for(int i = 0; i < n; i++){
cout << Ans[i] << " ";
}
cout << "\n";
}
```
:::
:::spoiler lower bound解 by 2006lennon (C\++)
cv陣列表示原本的a陣列
r陣列是a陣列排序後且刪除重複項所形成的陣列
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector <int> cv(n),v(n),r;
for(int i=0;i<n;i++) cin>>v[i];
cv=v;
sort(v.begin(),v.end(),greater<int>());
r.push_back(v[0]);
for(int i=1;i<n;i++){
if(v[i]!=*(r.end()-1)) r.push_back(v[i]);
}
for(int i=0;i<n;i++){
int it=lower_bound(r.begin(),r.end(),cv[i],greater<int>())-r.begin();
cout<<it+1<<" ";
}
return 0;
}
```
:::
:::spoiler 2nlogn解 by cmj0415, niter (python)
改自 `wayne.tw` 的code
```python
import bisect
from sys import stdin, stdout
x = int(stdin.readline())
y = list(map(int,stdin.readline().split()))
a = set(y)
z = sorted(set(y))
#print(z)
for i in y:
stdout.write(str(len(a)-bisect.bisect(z,i)+1))
stdout.write(" ")
```
:::
## pF 1x2骨牌
由陳連恩(2006lennon)提供(後來我發現網路上也有這題)
### 常見錯誤：沒有$mod10^9+7$
mod就是取餘數的意思
第11行的%符號很重要，沒有mod你就只剩10分 :(
:::spoiler 100分解法 by khhsu (C\++)
```cpp=
#include<iostream>
using namespace std;
int main(){
int n,a=1,b=2,c;
cin>>n;
if(n==1||n==2){cout<<n;}
else{
for(int i=3;i<=n;i++){
c=(a+b)%1000000007;
a=b;
b=c;
}
cout<<c;
}
}
```
:::
### 正確做法
假設圖形的寬(上下)是2、長(左右)是n
我們可以從`遞迴`的方向思考
你會發現所有的排列都是由兩種最基本的排法組成的
第一種是擺一個直的(2x1)
第二種是擺兩個橫的(並排2x2)
假設$2\times n$的格子有$f(n)$不同的排法
( $f(1)=1,f(2)=2$ )
則$f(x)+f(x+1)=f(x+2)$ ($x\geq 1$)
上面的兩種基本排法中，
第一種代表從$f(x+1)$的狀態轉移到$f(x+2)$的狀態
第二種代表從$f(x)$的狀態轉移到$f(x+2)$的狀態
100分解法請見上方的常見錯誤
### 150分做法
其實從上面的遞迴式可以觀察到：$f(x)$其實就是費氏數列的第$x+1$項
而上面的100分解法，複雜度是$O(n)$
在$1 \leq n \leq 10^6$的情況下不會TLE
但$n$到了$10^{15}$時，這樣的複雜度是不夠快的
所以我們要使用矩陣快速冪($O(\log n)$)，以更快的方法求費氏數列
矩陣快速冪暫時不需要學，有興趣再去查就好了，我們還不確定何時會教到
Sign in with Wallet
Connect another wallet