信息素養復賽模擬 1

---

1：樓層編號

#include<bits/stdc++.h>
using namespace std;
int main(){int n, t;cin >> n >> t;int res = 0;for(int i = 1; i <= n; i ++){int x = i;bool ok = true;while(x){if(x % 10 == t){ok = false;}x /= 10;}res += ok;} cout << res << endl;return 0;
} 

---

2：阿姆斯特朗數 (打表)

#include<bits/stdc++.h>
using namespace std;
int a[15] = {153, 370,371,407,1634,8208,9474,54748,92727,93084,548834,1741725,4210818,9800817,9926315}; 
int main(){for(int i = 0; i < 15; i ++) cout << a[i] << endl;return 0;
} 

---

3：蚱蜢

#include<bits/stdc++.h>
using namespace std;
int main(){string s;cin >> s;int n = s.size();s = " " + s;int ma = 0;int last = 0;for(int i = 1; i < s.size(); i ++){if(s[i] == 'A' || s[i] == 'E' || s[i] == 'I' || s[i] == 'O' || s[i] == 'U' || s[i] == 'Y'){ // 能跳 ma = max(ma, i - last);last = i; }}ma = max(ma, (int)s.size() - last);cout << ma << endl;return 0;
} 

---

4：二分查找1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main(){	int n, x;cin >> n >> x;for(int i = 1; i <= n; i ++){cin >> a[i];}sort(a + 1, a + 1 + n);cout << a[upper_bound(a + 1, a + 1 + n, x) - a - 1];return 0;
} 

---

5：砍伐樹木 (二分答案，模板二)

#include<bits/stdc++.h>
using namespace std;
int n, m;
#define int long long 
const int N = 1e6 + 10;
int a[N]; 
bool check(int mid){int res = 0;for(int i = 1; i <= n; i ++){if(a[i] >= mid){res += a[i] - mid;}}return res >= m;
}
signed main(){cin >> n >> m;for(int i = 1; i <= n; i ++){cin >> a[i];} int l = 0, r = 1e9;while(l < r){int mid = l + r + 1>> 1;if(check(mid)) l = mid;else r = mid - 1; } cout << l << endl;return 0;
} 

---

信息素養復賽模擬 2

---

1：排隊接水（貪心）

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
pair<int, int> a[N]; 
signed main(){int n;cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i].first;a[i].second = i; }sort(a + 1, a + 1 + n);double ans = 0;int res = 0; for(int i = 1; i <= n ;i ++){res += a[i].first;ans += res;cout << a[i].second << ' ';}cout << endl;cout << fixed << setprecision(2) << ans / n << endl; return 0;
} 

---

2：整數區間（貪心）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
pair<int, int> a[N];
bool cmp(pair<int, int> x, pair<int, int> y){return x.second < y.second; 
}
signed main(){int n;cin >> n;for(int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second;sort(a + 1, a + 1 + n, cmp);int ans = 0;int last = -1;for(int i = 1; i <= n; i ++){if(a[i].first > last){last = a[i].second;ans ++;}}cout << ans << endl;return 0;
} 

---

3：乘積為n的素數（唯一分解定理）

#include<bits/stdc++.h>
using namespace std;
signed main(){int n;cin >> n;vector<int> v; for(int i = 2; i * i <= n; i ++){while(n % i == 0){v.push_back(i);n /= i;}}if(n > 1){v.push_back(n);}sort(v.begin(), v.end());cout << v.size() << endl;for(auto x : v){cout << x << ' ';  }cout << endl;return 0;
} 

---

4：最小公倍數（歐幾里得算法）

#include<bits/stdc++.h>
using namespace std;
int main(){int a, b;cin >> a >> b;cout << a * b / __gcd(a, b) << endl;return 0;
} 

---

5：冪取模（快速冪）

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int qmi(int a, int b, int mod){int res = 1;while(b){if(b & 1) res = res * a % mod; a = a * a % mod;b >>= 1;}return res;
}
signed main(){int a, b, c;cin >> a >> b >> c;cout << qmi(a, b, c) << endl;return 0;
} 

---