最後編輯時間: 2025/05/01
114/5/1(四)刷題心得整理
▌TF::OJ刷的題目
▌覺得有趣或值得紀錄的題目以及心得感想
- 例題 P-2-2. 離散化 – sort
這題使用unordered_map存值就好了，很簡單，只不過一開始講義內範例題目是放二分搜的方式進行輸出，後面提到資料結構才用map，只不過這種東西還挺好玩，離散化未來應該是會整天燒機的東西。 - 例題 P-2-3. 快速冪
當要算一個東西的次方時如果一個一個算，時間不知道要花多久，快速幕利用兩個n次方相乘等於2n次方的方式進行運算，利用這樣疊加的方式將一個需要運算1000次的東西變得只要運算14次，非常牛逼 - 習題 Q-2-4. 快速冪–200 位整數
一開始看到200位整數直接傻眼，沒有任何資料型態可以存200位整數，不過仔細想想，他需要做取模p，取模的值int就可以存，那最後輸入的值其實只要取<p的值，所以先存字元串後在從後面一個一個位數取模即可 - 習題 Q-2-5. 快速計算費式數列第 n 項
這題雖然講義已經寫了算是，但我根本不會矩陣，學了好一段時間才搞懂原理，不過其實這題真的不難 - 例題 P-2-6. Two-Number problem
這題兩個題互補就拿unordered_set存值，再來目標k-輸入值看看set有沒有存這值就好。 - 習題 Q-2-7. 互補團隊 (沒AC)
我這題原本採用上面那題的方式解，但因為直接進行數字計算會導致一定的組合下出錯，因此我用了加權，製造了類似哈希的方式解，但是不知道位什麼怎麼改都是錯誤的，最後…放學了:)
▌程式
例題 P-2-2. 離散化 – sort
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;cin >> n;
int a[100001],b[100001];
for(int i=0;i<n;i++) {
int w;cin >> w;
a[i]=w;b[i]=w;
}
unordered_map<int,int> c;
sort(a,a+n);int k=0;
for(int i=0;i<n;i++){
if(a[i]!=a[i-1]){
c[a[i]] = k;
k++;
}
}
for(int i=0;i<n;i++){
cout << c[b[i]] << " ";
}
return 0;
}
例題 P-2-3. 快速冪
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL e(LL x,LL y,LL p){
if(y==0) return 1;
if(y&1) return (e(x,y-1,p)*x)%p;
LL t = e(x,y/2,p);
return (t*t)%p;
}
int main(){
LL x,y,p;cin >> x >> y >>p;
cout << e(x,y,p) << endl;
}
習題 Q-2-4. 快速冪–200 位整數
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL e(LL x, LL y, LL p) {
if (y == 0) return 1;
if (y & 1) return (e(x, y - 1, p) * x) % p;
LL t = e(x, y / 2, p);
return (t * t) % p;
}
LL mod_string(const string& a, LL r) {
LL res = 0;
for (char ch : a) {
res = (res * 10 + (ch - '0')) % r;
}
return res;
}
int main() {
string a, p;
int y;
cin >> a >> y >> p;
LL r = stoll(p);
LL w = mod_string(a, r);
cout << e(w, y, r) << endl;
return 0;
}
習題 Q-2-5. 快速計算費式數列第 n 項
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL w[2][2]={{1,1},{1,0}};
LL p=1000000007;
LL e(LL n){
if(n<=1) return 0;
if(n&1) {
e(n-1);
long long a = w[0][0],b = w[0][1],c = w[1][0],d = w[1][1];
w[0][0]=(a*1+b*1)%p;
w[0][1]=(a*1+b*0)%p;
w[1][0]=(c*1+d*1)%p;
w[1][1]=(c*1+d*0)%p;
return 0;
}
e(n/2);
long long a = w[0][0],b = w[0][1],c = w[1][0],d = w[1][1];
w[0][0]=(a*a+b*c)%p;
w[0][1]=(a*b+b*d)%p;
w[1][0]=(c*a+d*c)%p;
w[1][1]=(c*b+d*d)%p;
return 0;
}
int main(){
LL n;
while(1){
cin >> n;
if(n==-1) break;
e(n-1);
cout << w[0][0] << endl;
w[0][0]=1;w[0][1]=1;w[1][0]=1;w[1][1]=0;
}
}
例題 P-2-6. Two-Number problem
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,k,s=0;
unordered_set<int> a;
cin >> n >> m >> k;
while(n--){
int t;cin >> t;
a.insert(t);
}
while(m--){
int t;cin >> t;
if(a.count(k-t)) s++;
}
cout << s << endl;
}