第一題

題目

AOE還是單體？

思路

貪心

剩余怪物數量 >x時，使用AOE；否則使用單體

代碼

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n, x;
int arr[N];
int main()
{cin >> n >> x;for (int i = 1; i <= n; i++)cin >> arr[i];sort(arr + 1, arr + 1 + n);long long ret = 0;int index = max(0, n - x); // 處理 x 過?的情況ret += arr[index] * x;for (int i = index + 1; i <= n; i++)ret += arr[i] - arr[index];cout << ret << endl;return 0;
}

第二題

題目

kotori和n皇后

思路

統計每一個皇后能攻擊的位置，若已經有兩個皇后可以相互攻擊，則后續結果都為True

代碼

#include <iostream>
#include <unordered_set>using namespace std;unordered_set<long long> row; // 標記? y
unordered_set<long long> col; // 標記列 x
unordered_set<long long> dig1; // 標記主對?線 y - x
unordered_set<long long> dig2; // 標記副對?線 y + xint main()
{int n; cin >> n;int res = 1e5;for(int i = 1; i <= n; i++){int x, y; cin >> x >> y;if(res != 1e5) continue;if(row.count(y) || col.count(x) || dig1.count(y - x) || dig2.count(y + x)){res = i;}row.insert(y); col.insert(x); dig1.insert(y - x); dig2.insert(y + x);}int t; cin >> t;while(t--){int i;cin >> i;if(i >= res) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

第三題

題目

NC393 取金幣

思路

動態規劃

• dp[i][j] 表示[i, j] 區間?共能獲得多少?幣

代碼

class Solution {public:/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param coins int整型vector* @return int整型*/int arr[110] = { 0 };int dp[110][110] = { 0 };int getCoins(vector<int>& coins) {// write code hereint n = coins.size();arr[0] = arr[n + 1] = 1;for (int i = 1; i <= n; i++) arr[i] = coins[i - 1];for (int i = n; i >= 1; i--) {for (int j = i; j <= n; j++) {for (int k = i; k <= j; k++) {dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);}}}return dp[1][n];}
};