第一題:Bubble Sort
題目 (NPSC流水不腐)
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t, n;
cin >> t;
while(t--){
cin >> n;
int id[n], kg[n], ans=0;
for(int i=0; i<n; i++)
cin >> id[i];
for(int i=0; i<n; i++)
cin >> kg[i];
//bubble sort
for(int i=n-1; i>=1; i--){
for(int j=0; j<i; j++){
if(id[j] > id[j+1]){
ans+=kg[j]+kg[j+1];
swap(id[j], id[j+1]);
swap(kg[j], kg[j+1]);
}
}
}
cout << ans << '\n';
}
}
第二題:Stack
題目 (中序轉後序)
#include <bits/stdc++.h>
using namespace std;
int priority(char op){
switch(op){
case '*': case '/': return 2;
case '+': case '-': return 1;
default: return 0;
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
string s, ans;
cin >> s;
stack<char> st;
for(int i=0; i<s.length(); i++){
char c = s[i];
switch(c){
case '(':
st.push(c);
break;
case '+': case '-': case '*': case '/':
while(!st.empty() && priority(st.top()) >= priority(c)){
ans += st.top();
st.pop();
}
st.push(c);
break;
case ')':
while(st.top() != '('){
ans += st.top();
st.pop();
}
st.pop();
break;
default:
ans += c;
}
}
while(!st.empty()){
ans += st.top();
st.pop();
}
cout << ans << '\n';
}
第三題:遞迴(DP)
題目:爬 n 階樓梯,每次可爬 1 或 2 階,求方法數。
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
int arr[n];
arr[0] = 1;
arr[1] = 2;
for(int i=2; i<n; i++)
arr[i] = arr[i-1] + arr[i-2];
cout << arr[n-1] << '\n';
}
第四題:String
題目 (ZeroJudge b051: 2. 排列最大值)
#include <bits/stdc++.h>
using namespace std;
bool cmp(string s1, string s2){
string ss1 = s1+s2;
string ss2 = s2+s1;
return ss1 > ss2;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
string s[n];
for(int i=0; i<n; i++)
cin >> s[i];
sort(s, s+n, cmp);
for(int i=0; i<n; i++)
cout << s[i];
cout << '\n';
}
第五題:DP
走n*n地圖,左上角出發點,右下角終點,每一格有 value,只能向下或向右走,求最佳路線 value 總和。
#include <bits/stdc++.h>
using namespace std;
long long arr[200][200];
long long dp[200][200];
int f(int i, int j){
if(dp[i][j] != -1) return dp[i][j];
if(i==0){
dp[i][j] = f(i, j-1) + arr[i][j];
return dp[i][j];
}
if(j==0){
dp[i][j] = f(i-1, j) + arr[i][j];
return dp[i][j];
}
dp[i][j] = max(f(i-1, j), f(i, j-1))+arr[i][j];
return dp[i][j];
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
memset(dp, -1, sizeof(dp));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin >> arr[i][j];
dp[0][0] = arr[0][0];
f(n, n);
cout << dp[n][n] << '\n';
}