---
tags: 解題報告,todo
---

# 成大高中生邀請賽考古
:::info
link: [http://hspc2023.csie.ncku.edu.tw/history](http://hspc2023.csie.ncku.edu.tw/history)
:::
## 2022
### A
最大獲利在該產品淨收入為正值時,所有產品皆賣出可以有最大獲利
反之淨收入為負值時,只賣出最低數量為最小虧損
:::spoiler 程式碼

#include<iostream>
#define int long long

using namespace std;

int Px, Py, Cx, Cy, Sx, Sy, Hx, Hy;
int x, y, t=0;
bool sell_x = false, sell_y = false;

signed main(){
    cin>>Px>>Py>>Cx>>Cy>>Sx>>Sy>>Hx>>Hy;
    x = Px - Cx; y = Py - Cy;
    if (x > 0) sell_x = true;
    if (y > 0) sell_y = true;
    if (sell_x) t += x*Sx;
    else t += x*Hx;
    if (sell_y) t += y*Sy;
    else t += y*Hy;
    cout<<t<<"\n";
    if (sell_x) cout<<Sx;
    else cout<<Hx;
    cout<<" ";
    if (sell_y) cout<<Sy;
    else cout<<Hy;
    return 0;
}

:::
### B
建表儲存每個點的相鄰點
迴圈找相鄰點已經使用的頻率
從1開始找未使用的頻率,並設定該點頻率
紀錄是否有使用新的頻率
:::spoiler 程式碼

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2e8+5;
int N, M, X, Y;
vector<vector<int> > table;
int values[MAXN];
int r=0;

int main(){
    // input
    cin>>N>>M;
    
    // init values
    for (int i=1; i<=N; i++) values[i] = -1;
    for (int i=0; i<=N; i++){
    	vector<int> temp;
    	table.push_back(temp);
    }
    
    // also input
    for (int n=0; n< M; n++){
        cin>>X>>Y;
        table[X].push_back(Y);
        table[Y].push_back(X);
    }

    // solve
    for (int i=1; i<=N; i++){
        set<int> used;
        for (int j=0; j<table[i].size(); j++){
        	int p = table[i][j];
            if (values[p] != -1) used.insert(values[p]);
        }
        // find not use
        int v = 1;
        while (used.count(v)) v++;
        values[i] = v;
        r = max(r, v);
    }
    cout<<r;
    return 0;
}

:::
### C
紀錄各隊伍的資料並排序
:::spoiler 程式碼

#include<bits/stdc++.h>
#define int long long

using namespace std;

int N, Q, X, T, K;
string S;

struct team
{
    int score;
    int time;
    string name;
    
    team(){}
    team(int s, int t, string n){
        score=s; time=t; name=n;
    }
};

bool comp(team t1, team t2){
    if (t1.score == t2.score) return t1.time < t2.time;
    else return t1.score > t2.score;
}

signed main(){
    cin>>N>>Q;
    vector<team> vec(N);
    for (int n=0; n<N; n++){
        cin>>X>>T>>S;
        
        vec.push_back(team(X, T, S));
    }
    sort(vec.begin(), vec.end(), comp);

    for (int q = 0; q<Q; q++){
        cin>>K;
        cout<<vec[K-1].name<<"\n";
    }
    return 0;
}

(不確定實際上會不會TLE)
:::

## 2017
### A
紀錄各個字母出現次數並計算
:::spoiler 程式碼

#include<bits/stdc++.h>
using namespace std;

int T;
string text;

signed main(){
    cin>>T;
    getline(cin, text);
    for (int i=0; i<T; i++){
        int N=0, C=0, K=0, U=0, S=0, I=0, E=0;
        getline(cin, text);
        for (auto w = text.begin(); w != text.end(); w++){
            switch (*w){
                case 'N':
                N++; break;
                case 'C':
                C++; break;
                case 'K':
                K++; break;
                case 'U':
                U++; break;
                case 'S':
                S++; break;
                case 'I':
                I++; break;
                case 'E':
                E++; break;
            }
        }
        cout<<min(N, min(C/2, min(K, min(U, min(S, min(I, E))))))<<"\n";
    }
    return 0;
}

:::
### B
DP
:::spoiler 程式碼1

#include <iostream>
using namespace std;

// 一個輔助函數(helper function)，用來計算將n分解成不超過m的正整數之和的方法數
int partition(int n, int m) {
	// 如果n為0，表示已經找到一種分解方法
	if (n == 0) return 1;
	// 如果n小於0或者m為0，表示沒有找到分解方法
	if (n < 0 || m == 0) return 0;
	// 否則，將問題分成兩種情況：
	// (1) 將n分解成至少包含一個m的正整數之和
	// (2) 將n分解成不超過m-1的正整數之和
	// 兩種情況的方法數相加就是答案
	return partition(n-m, m) + partition(n, m-1);
}
	
// 主函數(main function)，用來讀取輸入並呼叫輔助函數
int main() {
	int n; // 要分解的正整數
	while (cin >> n) { // 讀取每筆測資
	cout << partition(n, n) << endl; // 計算並輸出答案
	}
	return 0;
}

:::warning
this code is generate by bing chat
:::

:::spoiler 程式碼2

#include <bits/stdc++.h>
using namespace std;

// 輔助函數(partition function)，用來計算正整數 n 的分割數
int partition(int n, int m) {
    vector<vector<int> > dp(n, vector<int>(n)); // 動態規劃表格
    for (int i = 0; i <= n; i++) { // i 代表分割數的個數
        for (int j = 0; j <= m; j++) { // j 代表最大加數，即分割數中最大的數字
            if (i == 0) dp[i][j] = 1; // 初始化，當 i 為 0 時，dp[i][j] 為 1，因為當 i 為 0 時，只有一種分割方法，就是不分割，所以 dp[0][j] 等於 1
            else if (j == 0) dp[i][j] = 0; // 初始化，當 j 為 0 時，dp[i][j] 為 0，因為當 j 為 0 時，無法分割，所以 dp[i][0] 等於 0
            else if (j > i) dp[i][j] = dp[i][j-1]; // 略過，當 j 大於 i 時，無法分割，所以 dp[i][j] 等於 dp[i][j-1]
            else dp[i][j] = dp[i-j][j] + dp[i][j-1]; // 計算，dp[i][j] 等於 dp[i-j][j] 加上 dp[i][j-1]，因為分割數可以分為兩種情況，一種是最大加數為 j，另一種是最大加數不為 j，所以 dp[i][j] 等於這兩種情況的總和
        }
    }
    return dp[n][m]; // 回傳答案
}


// 主函數(main function)，用來讀取輸入並呼叫輔助函數
int main() {
	int n; // 要分解的正整數
	while (cin >> n) { // 讀取每筆測資
	cout << partition(n, n) << endl; // 計算並輸出答案
	}
	return 0;
}

:::warning
this code is generate by [cursor](https://www.cursor.so/)
:::

---
{%hackmd @henry-lee-code23/dark-theme %}