# 前言

今天 2026 年 1 月 5 日，我突然開始想要考 CPE，下次考試是 3/24，我的目標是破台，希望可以成功，現在是凌晨，睡覺起來開始準備，準備的內容預計是從 CSES Leetcode CPE歷屆來寫 ，全英文真的有點頭痛，不過我應該行的。

這篇文章主要是紀錄我每天有沒有好好練習，寫了什麼題目，學了甚麼之類的。

# 1/5

# 1975. Maximum Matrix Sum

今天的第一題，大概花了 15 分鐘，一開始楞了一下，太久沒寫題目，還在思考是不是有可能遞迴剪枝或是 DP，最後觀察下來貪心。

	class Solution {
	public:
	long long maxMatrixSum(vector<vector<int>>& matrix) {
	long long sum = 0;
	int mn=INT_MAX;
	int x=0;
	for(auto &u:matrix){
	for(auto &v:u){
	bool temp = (v < 0)? true : false;
	sum += temp? -v : v;
	mn = min(mn,temp? -v : v);
	if(temp) x++;
	}
	}
	if(x&1){
	return sum - 2*mn;
	}else{
	return sum;
	}
	}
	};

# 10041 Vito's Family

我打算先把一顆星集選寫完，這題我沒想到是中位數，想了一陣子

當 Vito 從位置 m 往右移動一小步 δ 時：
他左邊的每個親戚，距離都會增加 δ
他右邊的每個親戚，距離都會減少 δ
所以總距離的變化 = (左邊親戚數 - 右邊親戚數) × δ
這告訴我們：
如果左邊人數 > 右邊人數 → 往右移會增加總距離（不好）
如果左邊人數 < 右邊人數 → 往右移會減少總距離（好）
當左右人數相等時 → 達到最佳點

	#include <bits/stdc++.h>
	using namespace std;
	#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);

	int main(){
	Rabbir_Reaper
	int t;
	cin>>t;
	while(t--){
	int r;
	cin>>r;
	vector<int> v;
	for(int i=0,temp;i<r;i++){
	cin>>temp;
	v.push_back(temp);
	}
	sort(v.begin(),v.end());
	int k = v[v.size()/2];


	int total = 0;
	for(int i=0;i<r;i++){
	total += abs(k-v[i]);
	}
	cout<<total<<"\n";
	}
	}

# 10055 Hashmat the Brave Warrior

這題超簡單

vice versa 的意思是反之亦然

	#include <bits/stdc++.h>
	using namespace std;
	#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);

	int main(){
	Rabbir_Reaper
	long long a,b;
	while(cin>>a>>b){
	cout<<abs(a-b)<<"\n";
	}
	}

# 10035 Primary Arithmetic

我一開始忽視了進位後還要計算，這邊要特別注意

	#include <bits/stdc++.h>
	using namespace std;
	#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);

	int main(){
	Rabbir_Reaper
	string a,b;

	while(cin>>a>>b){
	if(a == "0" && b == "0") break;
	int _a = a.size();
	int _b = b.size();
	int ans=0,carry=0;

	while(true){
	_a--;
	_b--;
	if(_a < 0 && _b < 0) break;
	int ta = (_a >= 0) ? a[_a] - '0' : 0;
	int tb = (_b >= 0) ? b[_b] - '0' : 0;
	if(ta + tb + carry >= 10){
	ans++;
	carry=1;
	}else carry = 0;
	}
	if(ans == 0) cout<<"No carry operation.";
	else if(ans == 1) cout<<ans<<" carry operation.";
	else cout<<ans<<" carry operations.";
	cout<<"\n";
	}
	}

# 100 The 3n + 1 problem

這題要注意輸入的範圍 i 跟 j 不一定是 i<=j ， = =

	#include <bits/stdc++.h>
	using namespace std;
	#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);

	int f(int k,int t = 0){
	if(k == 1) return ++t;
	if(k & 1) return f(k*3 + 1,++t);
	else return f(k/2,++t);
	}

	int main(){
	Rabbir_Reaper

	int a,b;
	while(cin>>a>>b){
	int mx=0;
	for(int i=min(a,b);i<=max(a,b);i++){
	mx = max(mx,f(i));
	}
	cout<<a<<" "<<b<<" "<<mx<<"\n";
	}
	}

# 1/6

今天太忙了只有寫一題

# 1161. Maximum Level Sum of a Binary Tree

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode() : val(0), left(nullptr), right(nullptr) {}
	* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	* TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {}
	* };
	*/
	class Solution {
	public:
	int maxLevelSum(TreeNode* root) {
	queue<TreeNode*> q;
	q.push(root);

	pair<long long,int> pli = {INT_MIN,1};
	int k=1;
	while(!q.empty()){
	int s=q.size();
	long long sum=0;
	for(int i=0;i<s;i++){
	TreeNode* temp = q.front();
	q.pop();
	sum += temp->val;
	if(temp->left) q.push(temp->left);
	if(temp->right) q.push(temp->right);
	}

	if(sum > pli.first){
	pli.first = sum;
	pli.second = k;
	}


	k++;
	}
	return pli.second;
	}
	};

# 1/7

# 1339. Maximum Product of Splitted Binary Tree

這題很像 AP325 裡面的 Q-8-6. 樹狀圖的距離總和 ，下面順便附上 Q-8-6. 樹狀圖的距離總和 這題的程式碼

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode() : val(0), left(nullptr), right(nullptr) {}
	* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	* TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {}
	* };
	*/
	class Solution {
	public:
	long long mx=0;
	int maxProduct(TreeNode* root) {
	dfs1(root);
	dfs2(root->left,root);
	dfs2(root->right,root);
	return mx%1000000007;
	}

	int dfs1(TreeNode* root){
	if(!root) return 0;

	root->val += dfs1(root->left);
	root->val += dfs1(root->right);
	return root->val;
	}

	void dfs2(TreeNode* root,TreeNode* _root){
	if(!root) return;

	mx = max(mx,(long long)(_root->val - root->val)*root->val);
	dfs2(root->left,_root);
	dfs2(root->right,_root);
	}
	};

	#include<bits/stdc++.h>
	using namespace std;
	#define N 100005
	int n,w[N],num[N]={0};
	long long total=0,dis_son[N]={0},dis[N]={0};
	vector<int> child[N];
	void dfs(int p){//O(n)
	for(auto e:child[p]){
	int u=e;
	dfs(u);
	dis_son[p]+=dis_son[u]+num[u]*w[u];
	num[p]+=num[u];
	}
	num[p]++;
	}
	void dfs_dis(int p){//O(n)
	for(auto e:child[p]){
	int u=e;
	dis[u]=dis[p]-(dis_son[u]+num[u]w[u])+(n-num[u])w[u]+dis_son[u];
	total+=dis[u];
	dfs_dis(e);
	}
	}
	queue<int> q;
	void bfs_dis(){// 算總和的時候 bfs 程式碼
	while(!q.empty()){
	int p=q.front();
	q.pop();
	for(auto t:child[p]){
	int u=t;
	q.push(u);
	dis[u]=dis[p]-(dis_son[u]+num[u]w[u])+(n-num[u])w[u]+dis_son[u];
	total+=dis[u];
	}
	}
	}
	int main(){
	cin>>n;
	for(int i=2,temp;i<=n;i++){
	cin>>temp;
	child[temp].push_back(i);
	}
	for(int i=2;i<=n;i++)
	cin>>w[i];
	dfs(1);
	dis[1]=dis_son[1];

	dfs_dis(1);

	// q.push(1);
	// bfs_dis();

	cout<<total+dis_son[1];
	}

# Q-8-9. 服務中心選位置

這一題是 最小支配集(Minimum Dominating Set) 問題

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

	#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);
	#define int long long
	const int N = 100005;
	vector<int> adj[N];
	int dp[N][3];
	// 0 : 不選此點，未被支配
	// 1 : 不選此點，已被子節點支配
	// 2 : 選取此點，已被自己支配
	void dfs(int x,int p){
	dp[x][0] = 0;
	dp[x][1] = 1e5;
	dp[x][2] = 1;

	int sum=0;
	for(auto &u:adj[x]){
	if(u == p) continue;
	dfs(u,x);
	dp[x][0] += dp[u][1];
	sum += min(dp[u][1],dp[u][2]);
	dp[x][2] += min({dp[u][0],dp[u][1],dp[u][2]});
	}

	for(auto &u : adj[x]){
	if(u == p) continue;
	dp[x][1] = min(dp[x][1], sum - min(dp[u][1], dp[u][2]) + dp[u][2]);
	}
	}

	signed main(){
	int n;
	cin>>n;
	n--;
	for(int i=0,u,v;i<n;i++){
	cin>>u>>v;
	adj[u].push_back(v);
	adj[v].push_back(u);
	}

	dfs(1,-1);
	cout<<min(dp[1][1],dp[1][2]);
	}

# 01292 - Strategic game

這一題是 最小點覆蓋(Minimum Vertex Cover) 問題
這題的輸入有點棘手要用一些特殊的方法處理

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

	void dfs(int x, int p, vector<vector<int>> &adj, vector<vector<int>> &dp) {
	dp[x][0] = 0; // 不選 x
	dp[x][1] = 1; // 選 x

	for (auto &u : adj[x]) {
	if (u == p) continue;
	dfs(u, x, adj, dp);
	dp[x][0] += dp[u][1]; //x 不選，子節點必須選
	dp[x][1] += min(dp[u][0], dp[u][1]); //x 選了，子節點隨意
	}
	}

	int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	while (cin >> n) {
	cin.ignore();
	vector<vector<int>> adj(n);
	vector<vector<int>> dp(n, vector<int>(2, 0));

	for (int i = 0; i < n; i++) {
	string line;
	getline(cin, line);
	int u, k;
	sscanf(line.c_str(), "%d:(%d)", &u, &k);

	if (k > 0) {
	int pos = line.find(')') + 1;
	string rest = line.substr(pos);
	stringstream ss(rest);
	for (int j = 0; j < k; j++) {
	int v;
	ss >> v;
	adj[u].push_back(v);
	adj[v].push_back(u);
	}
	}
	}

	dfs(0, -1, adj, dp);
	cout << min(dp[0][0], dp[0][1]) << "\n";
	}
	}

# 1/8

# 1458. Max Dot Product of Two Subsequences

這一題是 LCS 問題的變化版

	class Solution {
	public:
	int dp[505][505];
	int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
	for(int i=0;i<=nums1.size();i++) for(int j=0;j<=nums2.size();j++) dp[i][j] = -1e9;
	for(int i=0;i<nums1.size();i++){
	for(int j=0;j<nums2.size();j++){
	dp[i+1][j+1] = max({nums1[i]nums2[j],nums1[i]nums2[j] + dp[i][j],dp[i+1][j],dp[i][j+1]});
	}
	}
	return dp[nums1.size()][nums2.size()];
	}
	};

# 1/9

# 865. Smallest Subtree with all the Deepest Nodes

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode() : val(0), left(nullptr), right(nullptr) {}
	* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	* TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* subtreeWithAllDeepest(TreeNode* root) {
	return dfs(root).first;
	}

	pair<TreeNode,int> dfs(TreeNode x,int d=1){
	if(!x) return {nullptr,0};

	pair<TreeNode*,int> a=dfs(x->left,d+1);
	pair<TreeNode*,int> b=dfs(x->right,d+1);

	if(a.second > b.second) return a;
	if(b.second > a.second) return b;
	if(a.second == 0 && b.second == 0) return {x,d};
	return {x,b.second};
	}
	};

# 1/10

# 712. Minimum ASCII Delete Sum for Two Strings

這題想有點久

dp 定義每格代表到當前兩個字串長度的最優解
dp[0][1] 代表 a 字串長度 0 ， b 字串長度 1 ，所以最優解釋刪掉 b 字串 dp[0][1]=(int)b[1] ，反過來也一樣，這樣就定義完了
剩下的選與不選就蠻直覺的

下方提供兩段程式碼，第二個是空間優化過的，因為最多只需要上一行的狀態，所以一維就夠了

	class Solution {
	public:
	int minimumDeleteSum(string s1, string s2) {
	vector<vector<int>> dp(s1.size()+1,vector<int>(s2.size()+1));
	dp[0][0] = 0;
	for(int i=0;i<s1.size();i++)
	dp[i+1][0] = (int)s1[i] + dp[i][0];
	for(int j=0;j<s2.size();j++)
	dp[0][j+1] = (int)s2[j] + dp[0][j];
	for(int i=1;i<=s1.size();i++){
	for(int j=1;j<=s2.size();j++){
	if(s1[i-1] == s2[j-1]){
	dp[i][j] = dp[i-1][j-1];
	}else{
	dp[i][j] = min({
	dp[i-1][j] + (int)s1[i-1],
	dp[i][j-1] + (int)s2[j-1]
	});
	}
	}
	}
	return dp[s1.size()][s2.size()];
	}
	};

	int minimumDeleteSum(string s1, string s2) {
	int m = s1.size(), n = s2.size();
	vector<int> dp(n + 1);

	// 初始化第一行
	for(int j = 0; j < n; j++) {
	dp[j + 1] = dp[j] + s2[j];
	}

	// 逐行更新
	for(int i = 0; i < m; i++) {
	int prev = dp[0]; // 保存 dp [i][j-1]
	dp[0] += s1[i]; // 更新第一列

	for(int j = 0; j < n; j++) {
	int temp = dp[j + 1]; // 保存下次需要的 prev
	if(s1[i] == s2[j]) {
	dp[j + 1] = prev;
	} else {
	dp[j + 1] = min(dp[j + 1] + s1[i], dp[j] + s2[j]);
	}
	prev = temp;
	}
	}

	return dp[n];
	}

# 1/12

# 1266. Minimum Time Visiting All Points

	class Solution {
	public:
	int minTimeToVisitAllPoints(vector<vector<int>>& points) {
	int ans=0;
	for(int i=1;i<points.size();i++){
	int x = abs(points[i][0] - points[i-1][0]);
	int y = abs(points[i][1] - points[i-1][1]);
	if(x < y) swap(x,y);
	ans += y;
	ans += (x-y);
	}
	return ans;
	}
	};

# 1/13

# 3453. Separate Squares I

這一題有兩個寫法，我是想到用對答案二分搜的方式，另一種方法是掃描線演算法
掃描線演算法的程式碼是 AI 改寫的，這邊我都放上來
這一題有點像以前 APCS 的線段覆蓋長度 b966. 3. 線段覆蓋長度

	class Solution {
	public:
	double separateSquares(vector<vector<int>>& squares) {
	double l=0,r=10e12;

	while((r-l) > 0.00001){
	double mid = (r+l)/2;
	double above=0,below=0;
	for(auto &u:squares){
	if(u[1] > mid){
	above += (double)u[2]*u[2];
	}else if(u[1] + u[2] < mid){
	below += (double)u[2]*u[2];
	}else{
	above += (double)u[2]*(u[2]-(mid-u[1]));
	below += (double)u[2]*(mid-u[1]);
	}
	}
	if(below >= above){
	r = mid;
	}else{
	l = mid;
	}
	}
	return r;
	}
	};

	class Solution {
	public:
	double separateSquares(vector<vector<int>>& squares) {
	int n = squares.size();
	vector<pair<int, int>> events; // {高度，寬度變化}
	long long totalArea = 0;

	// 建立事件
	for (auto& sq : squares) {
	int y = sq[1], len = sq[2];
	events.push_back({y, len}); // 底部：增加寬度
	events.push_back({y + len, -len}); // 頂部：減少寬度
	totalArea += (long long)len * len;
	}

	// 排序事件
	sort(events.begin(), events.end());

	// 掃描線
	long long area = 0;
	int currentWidth = 0;
	int prevHeight = 0;

	for (auto& [height, widthChange] : events) {
	// 計算從 prevHeight 到 height 的面積
	long long deltaArea = (long long)currentWidth * (height - prevHeight);

	// 檢查是否達到一半
	if (area + deltaArea >= totalArea / 2.0) {
	// 在這個區間內找到精確位置
	double remaining = totalArea / 2.0 - area;
	return prevHeight + remaining / currentWidth;
	}

	area += deltaArea;
	currentWidth += widthChange;
	prevHeight = height;
	}

	return 0; // 不會到達這裡
	}
	};

時間複雜度比較

二分搜方法： O (log (10^15) × n) ≈ O (50n)
掃描線方法： O (2n log (2n)) ≈ O (2n log n)

當 n = 50,000 時：

二分搜方法：≈ 2,500,000 次操作
掃描線：≈ 1,500,000 次操作

# 1/28

看來必須先終止這個準備了。

最近突然要忙別的事情

不知道什麼時候會忙完...

# 3/30

今天開始應該會回歸刷題，今天的題目是關於 hashtable 不過我的寫法沒有使用到這個概念，當下直覺就這樣寫了，時間與空間的複雜度都不太好，下面再附上官解與解釋

# 2840. Check if Strings Can be Made Equal With Operations II

	//Rabbir
	class Solution {
	public:
	bool checkStrings(string s1, string s2) {
	vector<int> odd[2];
	vector<int> even[2];

	for(int i=0;i<s1.size();i++){
	if(i&1){
	odd[0].push_back((int)s1[i]);
	odd[1].push_back((int)s2[i]);
	}else{
	even[0].push_back((int)s1[i]);
	even[1].push_back((int)s2[i]);
	}
	}
	sort(odd[0].begin(),odd[0].end());
	sort(odd[1].begin(),odd[1].end());
	sort(even[0].begin(),even[0].end());
	sort(even[1].begin(),even[1].end());

	return (odd[0] == odd[1] && even[0] == even[1]) ? true : false ;
	}
	};

	// 官解
	class Solution {
	public:
	bool checkStrings(string s1, string s2) {
	if (s1.length() != s2.length()) {
	return false;
	}

	int counts[256] = {0};// 宣告 hashtable

	for (int i = 0; i < s1.length(); i++) {
	int offset = (i & 1) << 7;// 因為小寫字母從 97 開始
	// 這邊分成兩個區塊 0~127,128~255
	// 實際上會用到的區塊 97~122 , 128~183
	// 如果希望節省空間
	// 可以宣告 64 個空間
	// 每次減掉 (int)'a'=97
	// 就可以使用 0~25 , 32~57
	// 想要更省當然可以宣告剛好 2*26
	// 不過會需要多個 if 判斷與設定，不能用上面快速的寫法
	counts[offset + s1[i]]++;
	counts[offset + s2[i]]--;
	}

	// 如果正負都抵銷代表剛好一樣
	for (int i = 0; i < 256; i++) {
	if (counts[i] != 0) {
	return false;
	}
	}

	return true;
	}
	};