# 🌟CPE一星題練習(下)
題目表來源:https://yuihuang.com/cpe-level-1-49/
接續上篇:https://hackmd.io/@herbert1018/BkOGIOQcke
# 📦26~30題
## 26. d492. 10226 - Hardwood species
搞笑，測資硬要給你卡一個空格在那邊
```cpp=
#include<iostream>
#include<iomanip>
#include<map>
using namespace std;
int main(){
map<string, int> mp;
int n;
cin>>n;
string str;
getline(cin, str);
getline(cin, str);
while(n--){
int sum=0;
mp.clear();
while(getline(cin, str)){
if(str=="")break;
mp[str]++;
sum++;
}
for(auto x: mp){
cout<<setprecision(4)<<fixed<<x.first<<" "<<(double)x.second/sum*100<<'\n';
}
cout<<'\n';
}
return 0;
}
```
## 27. d387. 10235 – Simply Emirp
我最喜歡用bitset建表了，我是bitset玩家
```cpp=
#include<iostream>
#include<bitset>
using namespace std;
int reverse(int x){
int temp=0;
while(x>0){
temp+=x%10;
temp*=10;
x/=10;
}
return temp/10;
}
int main(){
bitset<1000000> bs;
bs.set(0);bs.set(1);
for(int i=2; i<1001; i++){
if(!bs[i]){
for(int j=i*2; j<1000000; j+=i)bs.set(j);
}
}
int N;
while(cin>>N){
cout<<N;
if(bs[N])cout<<" is not prime.\n";
else if(reverse(N)==N|| bs[reverse(N)])cout<<" is prime.\n";
else cout<<" is emirp.\n";
}
return 0;
}
```
## 28. e512. 10242 – Fourth Point!!
無情if機器人拖垮效能
```cpp=
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
double a[8], d;
int index=0;
double x1, x2, x3, y1, y2, y3;
while(cin>>d){
a[index]=d;
index=(index+1)%8;
if(index==0){
if(a[0]==a[4]&&a[1]==a[5]){
x1=a[6], x2=a[0], x3=a[2];
y1=a[7], y2=a[1], y3=a[3];
}
else if(a[0]==a[6]&&a[1]==a[7]){
x1=a[4], x2=a[0], x3=a[2];
y1=a[5], y2=a[1], y3=a[3];
}
else if(a[2]==a[4]&&a[3]==a[5]){
x1=a[6], x2=a[2], x3=a[0];
y1=a[7], y2=a[3], y3=a[1];
}
else{
x1=a[4], x2=a[2], x3=a[0];
y1=a[5], y2=a[3], y3=a[1];
}
cout<<fixed<<setprecision(3)<<x1-x2+x3<<" "<<y1-y2+y3<<'\n';
}
}
return 0;
}
```
## 29. e507. 10252 – Common Permutation
no comment
```cpp=
#include<iostream>
#include<bitset>
#include<algorithm>
using namespace std;
int main(){
int cnta[26], cntb[26];
string a, b;
while(cin>>a>>b){
for(int i=0; i<26; i++){
cnta[i]=0; cntb[i]=0;
}//也可以用fill
for(char c: a)cnta[c-'a']++;
for(char c: b)cntb[c-'a']++;
for(int i=0; i<26; i++){
int t=min(cnta[i], cntb[i]);
while(t--)cout<<(char)('a'+i);
}cout<<'\n';
}
return 0;
}
```
## 30. f444: 10268 – 498-bis
wow sstream還可以這樣用，學到了
```cpp=
#include<iostream>
#include<cmath>
#include<sstream>
#include<vector>
using namespace std;
int main(){
int x, a, ans;
string str;
while(cin>>x){
ans=0;
vector<int> poly;
getline(cin, str);//cin.ignore();
getline(cin, str);
stringstream ss(str);
while(ss>>a){
poly.push_back(a);
}
for(int i=poly.size()-2, n=1; i>=0; i--, n++){
ans+=pow(x, n-1)*poly[i]*n;
}
cout<<ans<<'\n';
}
return 0;
}
```
# 📦31~35題
## 31. e516. 10409 – Die Game
owo
```cpp=
#include<iostream>
using namespace std;
int main(){
int n=-1;
string s;
while(cin>>n && n!=0){
int dir[3]={1, 2, 3};
while(n--){
cin>>s;
if(s=="north"){
swap(dir[0], dir[1]);
dir[0]=7-dir[0];
}
else if(s=="south"){
swap(dir[0], dir[1]);
dir[1]=7-dir[1];
}
else if(s=="east"){
swap(dir[0], dir[2]);
dir[2]=7-dir[2];
}
else{
swap(dir[0], dir[2]);
dir[0]=7-dir[0];
}
}
cout<<dir[0]<<'\n';
}
return 0;
}
```
## 32. e531. 10415 – Eb Alto Saxophone Player
建表bro
```cpp=
#include<iostream>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
int main(){
map<char, vector<bool>> mp;
mp['c']={0, 1, 1, 1, 0, 0, 1, 1, 1, 1};
mp['d']={0, 1, 1, 1, 0, 0, 1, 1, 1, 0};
mp['e']={0, 1, 1, 1, 0, 0, 1, 1, 0, 0};
mp['f']={0, 1, 1, 1, 0, 0, 1, 0, 0, 0};
mp['g']={0, 1, 1, 1, 0, 0, 0, 0, 0, 0};
mp['a']={0, 1, 1, 0, 0, 0, 0, 0, 0, 0};
mp['b']={0, 1, 0, 0, 0, 0, 0, 0, 0, 0};
mp['C']={0, 0, 1, 0, 0, 0, 0, 0, 0, 0};
mp['D']={1, 1, 1, 1, 0, 0, 1, 1, 1, 0};
mp['E']={1, 1, 1, 1, 0, 0, 1, 1, 0, 0};
mp['F']={1, 1, 1, 1, 0, 0, 1, 0, 0, 0};
mp['G']={1, 1, 1, 1, 0, 0, 0, 0, 0, 0};
mp['A']={1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
mp['B']={1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
bitset<10> finger;
string str;
int t;
cin>>t;
getline(cin, str);
while(t--){
vector<int> time(10, 0);
getline(cin, str);
finger.reset();
for(char c: str){
vector<bool> hold=mp[c];
for(int i=0; i<10; i++){
if(hold[i]){
if(!finger[i]){
finger.set(i);
time[i]++;
}
}
else finger.reset(i);
}
}
for(int i: time)cout<<i<<" ";
cout<<'\n';
}
return 0;
}
```
## 33. a743. 10420 – List of Conquests
c++玩家最喜歡用auto然後甚麼都不管了
```cpp=
#include<iostream>
#include<map>
using namespace std;
int main(){
int n;
cin>>n;
map<string, int> mp;
string str;
getline(cin, str);
while(n--){
cin>>str;
mp[str]++;
getline(cin, str);
}
for(auto p: mp)cout<<p.first<<" "<<p.second<<'\n';
return 0;
}
```
## 34. i859. 10642 - Can You Solve It?
直接算出距離(0, 0)的位置在相減後絕對值。
溢位問題(用long long)
```cpp=
#include<iostream>
#include<cmath>
using namespace std;
long long decar(long long p[3]){
long long ans=p[0]+((1+p[0])*p[0]/2)-(p[0]-p[1]);
return ans;
}
int main(){
int n;
long long p1[3]={0}, p2[3]={0};
cin>>n;
for(int i=1; i<=n; i++){
cin>>p1[1]>>p1[2]>>p2[1]>>p2[2];
p1[0]=p1[1]+p1[2];
p2[0]=p2[1]+p2[2];
cout<<"Case "<<i<<": "<<abs(decar(p1)-decar(p2))<<'\n';
}
return 0;
}
```
## 35. c022. 10783 – Odd Sum
自己推一下公式
```cpp=
#include<iostream>
using namespace std;
int main(){
int n, a, b;
cin>>n;
for(int i=1; i<=n; i++){
cin>>a>>b;
int l=(a%2==1)?(a+1)/2:a/2;
int u=(b%2==1)?(b-1)/2:b/2;
cout<<"Case "<<i<<": "<<(b*b-a*a+a+b)/2-(u*u-l*l+l+u)<<'\n';
}
return 0;
}
```
# 📦36~40題
## 36. c004. 10812 – Beat the Spread!
(x+y)+(x-y)=2x
(x+y)-(x-y)=2y
```cpp=
#include<iostream>
using namespace std;
int main(){
int n, a, b;
cin>>n;
while(n--){
cin>>a>>b;
if((a+b)%2 || a<b)cout<<"impossible\n";
else cout<<(a+b)/2<<" "<<(a-b)/2<<'\n';
}
return 0;
}
```
## 37. e575. 10908 – Largest Squares
沒想到吧，我用三維的dp，空間換時間
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int T, M, N, Q, r, c;
cin>>T;
while(T--){
cin>>M>>N>>Q;
cout<<M<<" "<<N<<" "<<Q<<'\n';
vector<vector<char>> sq(M, vector<char>(N));
for(int i=0; i<M; i++){
for(int j=0; j<N; j++)cin>>sq[i][j];
}
vector<vector<vector<int>>> test(4, vector<vector<int>>(M, vector<int>(N, 1)));
for(int i=0; i<M; i++){
for(int j=1; j<N; j++)test[0][i][j]=(sq[i][j]==sq[i][j-1])?test[0][i][j-1]+1:1;
for(int j=N-2; j>=0; j--)test[1][i][j]=(sq[i][j]==sq[i][j+1])?test[1][i][j+1]+1:1;
}
for(int j=0; j<N; j++){
for(int i=1; i<M; i++)test[2][i][j]=(sq[i][j]==sq[i-1][j])?test[2][i-1][j]+1:1;
for(int i=M-2; i>=0; i--)test[3][i][j]=(sq[i][j]==sq[i+1][j])?test[3][i+1][j]+1:1;
}
while(Q--){
cin>>r>>c;
int k=min(min(test[0][r][c], test[1][r][c]), min(test[2][r][c], test[3][r][c]));
cout<<(2*k-1)<<'\n';
}
}
return 0;
}
```
## 38. d672. 10922 – 2 the 9s
基礎遞迴練習
```cpp=
#include<iostream>
#include<string>
using namespace std;
int degree(string str, int de){
int sum=0;
for(int i=str.length()-1; i>=0; i--){
sum+=str[i]-'0';
}
if(sum%9!=0)return 0;
else if(sum!=9)return degree(to_string(sum), de+1);
else return de;
}
int main(){
string str;
while(cin>>str){
if(str=="0")return 0;
cout<<str;
int ans=degree(str, 1);
if(ans!=0)cout<<" is a multiple of 9 and has 9-degree "<<ans<<".\n";
else cout<<" is not a multiple of 9.\n";
}
return 0;
}
```
## 39. d235. 10929 – You can say 11
喜歡用三元運算子
```cpp=
#include<iostream>
#include<string>
using namespace std;
int main(){
string str="";
while(cin>>str){
if(str=="0")return 0;
cout<<str;
int ans=0;
for(int i=str.length()-1; i>=0; i--){
ans+=(i&1)?(str[i]-'0'):-(str[i]-'0');
}
if(ans%11!=0)cout<<" is not a multiple of 11.\n";
else cout<<" is a multiple of 11.\n";
}
return 0;
}
```
## 40. a132. 10931 – Parity
我也試了bs.test()或直接用一個bool維護的版本，但感覺差不了多少
```cpp=
#include<iostream>
#include<bitset>
using namespace std;
int main(){
bitset<33> bs;
int n;
while(cin>>n){
if(n==0)return 0;
bs=n;
string str=bs.to_string();
cout<<"The parity of ";
for(int i=str.find('1'); i<33; i++)cout<<str[i];
cout<<" is "<<bs.count()<<" (mod 2).\n";
}
return 0;
}
```
# 📦41~45題
## 41. UVA-11005 Cheapest Base
vjudge的測資在搞，必須要求格式嚴格相同，害我吃了兩次PE
```cpp=
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int n, test, num;
cin>>n;
for(int i=1; i<=n; i++){
cout<<"Case "<<i<<":\n";
vector<int> cost(37);
for(int j=0; j<36; j++)cin>>cost[j];
cin>>test;
while(test--){
cin>>num;
cout<<"Cheapest base(s) for number "<<num<<":";
vector<int> spend(37, 0);
for(int k=2; k<=36; k++){
int temp=num;
while(temp>=k){
spend[k]+=cost[temp%k];
temp/=k;
}spend[k]+=cost[temp];
}
int cheap=*min_element(spend.begin()+2, spend.end());
for(int base=2; base<=36; base++)if(spend[base]==cheap)cout<<" "<<base;
cout<<'\n';
}
if(i!=n)cout<<'\n';
}
return 0;
}
```
## 42. d123. 11063 – B2-Sequence
這題測資沒檢查必須嚴格遞增
```cpp=
#include<iostream>
#include<bitset>
using namespace std;
int main(){
int N, i=1;
bitset<20001> show, add;
while(cin>>N){
show.reset();
add.reset();
int p;
bool flag=false;
while(N--){
cin>>p;
show.set(p);
if(((show<<p)&add).any())flag=true;
add|=show<<p;
}
if(flag)cout<<"Case #"<<i++<<": It is not a B2-Sequence.\n\n";
else cout<<"Case #"<<i++<<": It is a B2-Sequence.\n\n";
}
return 0;
}
```
## 43. d189. 11150 – Cola
這題題目應該要在加一句「每次喝都可以再借，但借多少就要還多少」
1. 多借1->剛好可以還
2. 多借2->只會給你一個瓶子導致不夠還
3. 借更多->更不夠還
```cpp=
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int N;
while(cin>>N){
cout<<floor(3*N/2)<<'\n';
}
return 0;
}
```
## 44. d750. 11321 – Sort! Sort!! and Sort!!!
自從學會lambda後，沒有問題解不出來的，~~寫程式就是開容器跟排序~~
```cpp=
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int N, M;
while(cin>>N>>M){
cout<<N<<" "<<M<<'\n';
if(N==0&&M==0)return 0;
vector<int> vc(N);
for(int i=0; i<N; i++)cin>>vc[i];
sort(vc.begin(), vc.end(), [&](int x, int y){
int tx=x%2, ty=y%2;
if((x%M==y%M)){
if(tx!=ty){
return (tx)?true:false;
}
else if(tx==1&&ty==1){
return x>y;
}
else{
return x<y;
}
}else return (x%M)<(y%M);
});
for(int i=0; i<N; i++)cout<<vc[i]<<'\n';
}
return 0;
}
```
## 45. c813. 11332 – Summing Digits
喜歡擠在一起，非常難讀
```cpp=
#include<iostream>
#include<functional>
using namespace std;
int main(){
int n;
function<int(int)> g=[&](int x){
string str=to_string(x);
int ans=0;
for(int i=str.size()-1; i>=0; i--)ans+=(str[i]-'0');
return (ans<10)?ans:g(ans);
};
while(cin>>n && n!=0){
cout<<g(n)<<'\n';
}
return 0;
}
```
# 📦46~49題
## 46. e513. 11349 – Symmetric Matrix
被搞兩次，負數跟long long
```cpp=
#include<iostream>
#include<vector>
using namespace std;
int main(){
int T, N;
char c;
cin>>T;
for(int k=1; k<=T; k++){
bool flag=false;
cin>>c>>c>>N;
vector<vector<long long>> M(N, vector<long long>(N));
for(int i=0; i<N; i++){
for(int j=0; j<N; j++)cin>>M[i][j];
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(M[i][j]!=M[N-i-1][N-j-1]||M[i][j]<0){
flag=true;
}
}
}
if(flag)cout<<"Test #"<<k<<": Non-symmetric.\n";
else cout<<"Test #"<<k<<": Symmetric.\n";
}
return 0;
}
```
## 47. d255. 11417 – GCD
想知道125251哪來的
可以去寫看看leetcode這題
1128. Number of Equivalent Domino Pairs
```cpp=
#include<iostream>
using namespace std;
int gcd(int x, int y){
while((x%=y)&&(y%=x));
return x+y;
}
int main(){
int n;
uint16_t map[125251]={0};
for(int i=1; i<500; i++){
for(int j=i+1; j<=500; j++){
map[(j*(j-1)/2+i-1)]=gcd(j, i);
}
}
while(cin>>n && n!=0){
int ans=0;
for(int i=1; i<n; i++){
for(int j=i+1; j<=n; j++){
ans+=map[(j*(j-1)/2+i-1)];
}
}
cout<<ans<<'\n';
}
return 0;
}
```
## 48. d186. 11461 – Square Numbers
向下取整還有向上取整
```cpp=
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int a, b;
while(cin>>a>>b&&(a!=0&&b!=0)){
cout<<floor(sqrt(b))-ceil(sqrt(a))+1<<'\n';
}
return 0;
}
```
## 49. f709. 12019 – Doom’s Day Algorithm
1月1號是Saturday
```cpp=
#include<iostream>
using namespace std;
int main(){
//1 2 3 4 5 6 7 8 9 10 11 12
int month[12]={0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}, T, M, D;
string day[7]={"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
cin>>T;
while(T--){
cin>>M>>D;
cout<<day[(month[M-1]+D+4)%7]<<'\n';
}
return 0;
}
```
# 📜後記
感覺zerojudge測資跟題目敘述很多都不完整，比較像是考通靈，
而且題目難度蠻簡單就是有些很浪費時間，不過就是考基礎I/O所以還可以接受。
相比之下正式cpe就是在考英文+讀題目，外加其他題目稍微難那麼億點🤏🤏
這邊放上來提供參考交流，要直接抄我也管不著，反正就是做一個紀錄🤯
~~~
舉一些後面4~7題常出現的題目類型dp、bfs、dfs、subset、圖論、(外加一坨沒聽過的演算法)...
✨知識點: vector、sort(lambda自訂排序)、map、bitset、
sstream、iomanip(setw、setpercition)、fixed、
getline、字串處理(find等)...
✨操作手法: 建表(質數、prefix)、輾轉相除、two pointer、二分搜、sliding window、
快速冪(可搭配狀態轉移矩陣)、...
基本上靠這些東西就可以5~6題了，阿7題看運氣，
考cpe就像在大鍋炒，把input翻過來炒過去，然後端出一坨給judge
~~~
Sign in with Wallet
Connect another wallet