110南山校內資訊競賽題目

第一題：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'; 
}