# APCS 2023/10/22
## 前言
APCS好好玩 :D
當天整個爆忙，考完之後搞化學又搞辯論。
初筆:2023/10/22
末筆:2023/11/7
## 觀念題
第一節題目偏簡單，最難可能就bubble sort或逆序數對，沒什麼好說的。
第二節有BS、更難的bubble sort&逆序，噁心的雙遞迴、還有一堆我覺得只是在考計算的怪東西。
> 總之我覺得不好玩，然後88分是甚麼殘念鬼分數
## 實作題
### P1 [機械鼠](https://zerojudge.tw/ShowProblem?problemid=m370)
題意大概就是給你一個一維座標x，判剩下座標在x的左邊還右邊之後做一些小記錄。
> 水題無誤
:::spoiler code
```C++=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1.5e5;
main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, x;
cin >> x >> n;
int lmn = 101, rmx = -101, lcnt = 0, rcnt = 0;
while (n--){
int a; cin >> a;
if (a < x){ //判max跟min不用在if裡面，但沒差啦
lcnt++; lmn = min(lmn, a);
}else{
rcnt++; rmx = max(rmx, a);
}
}
if (rcnt > lcnt){
cout << rcnt << " " << rmx << endl;
}else{
cout << lcnt << " " << lmn << endl;
}
}
```
:::
### P2 [卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371)
#### 題敘
跟之前的題目比算很好寫的二維陣列實作題，zj上的測資目前不夠強，只要做一次判斷就夠了。
> 仍然水，但我犯了一個蠢bug只拿60分，幸好有5級分，想看我的雲霄飛車體驗請往下走。
### P3 [搬家](https://zerojudge.tw/ShowProblem?problemid=m372)
#### 題敘
給n*m個形狀的水管(以不同字元表示)，問依它的規則轉換後最大的連通塊大小
#### 解法
我是直接用dfs算連通塊，麻煩的是判定兩個水管是否連通，這裡使用布林陣列/bitset就可以快速計算啦(例如說{左, 上, 右, 下}，1代表該方向能通，用(i + 2) % 4可以很快處理)。
> zj上要用bfs才能AC喔
#### 小趣事
我這題因為x座標的+1、-1寫反debug超久，但是心裡默念幾個學長姐、前輩的名字幾分鐘後就de出來了。(感謝李學姊、郭學長、黃老師、還有~~我忘記有沒有想到的~~黃學長可能有給我的加持)
> 上面那幾個人有一半不打競程，法力超強
> 2、3題因為code太麻煩又沒什麼營養就不打了
### P4 [投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
#### 題敘
算最大連續區間和，但最多可以忽略k個數的值。
#### 解法
令dp[i][j]代表考慮到第i個，用了j個金牌的答案
$O(nk)$ 的dp，轉移蠻直觀的。
```C++
dp[i][j] = max(dp[i - 1][j] + A[i], dp[i - 1][j - 1])
```
:::spoiler code
```C++
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1.5e5;
ll A[MAXN + 10], dp[MAXN + 10][21];
main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> A[i];
for (int i = 0; i <= n; i++) for (int j = 0; j <= k; j++) dp[i][j] = -1e18;
dp[1][0] = A[1];
ll ans = max(dp[1][0], 0ll);
for (int i = 2; i <= n; i++) dp[i][0] = max(0ll, dp[i - 1][0]) + A[i], ans = max(dp[i][0], ans);
for (int j = 1; j <= k; j++){
for (int i = 1; i <= n; i++){
dp[i][j] = max(dp[i - 1][j] + A[i], dp[i - 1][j - 1]);
ans = max(dp[i][j], ans);
}
}
cout << ans << "\n";
}
```
:::
## 心得
先說成績，實作5😍😍😍😍❤️❤️❤️❤️
打競程的應該都知道APCS的題目並沒有多難，就算拿到5級分也不代表多強。但是其實APCS對我來說有蠻多特殊意義的，也才會有這篇怪怪心得文的出現。
我的程式之路說長不長，說短不短(從小學開始寫python的怪人)。不過我真正開始下定決心踏上這條道路的時候是在國三，而契機就是APCS。
我國三第一次去考APCS是滿懷期待、自信去的，結果被現實的4+3狠狠上了一課。從那時候才真正看到自己實力的不足，也看到了自己與電神們的差距。後來也許是因為不甘，抑或是對成為強者的追求，又或者是單純地想要好好享受比賽的過程，我決定讓競程進入生活，讓它成為我青春的一部分。
之後因緣際會下去上了[AA競程](https://aacpschool.com/)的課跟參加IONC(都超推)，算是真正踏入了競程圈。光一個暑假，就學到了很多東西，AA的之後再細說吧。其實主要就是實力上的躍進與心態上的調整。如果當初沒有那場APCS，這一切都不會發生。
>幾個月是可以改變一個人很多的 by 學長
回到這次的檢定，P1、P2前20分鐘就處理掉了，沒什麼好說的。接下來P3看一下立刻想出解法就開始寫code，但是遇到了該死的bug，詳細可以看P3那邊的小趣事(HackMD才有)。這邊我在心態上的成長就顯現出來了，我毫不猶豫的去寫P4，剛好這次P4偏簡單，大概10幾分鐘就AC了，之後再調整好自己才回去debug P3並拿到AC。如果是之前的我，可能會糾結P3很久導致最後連P4都拿不到吧。
我覺得這次檢定算是對我進步的最大證明。例如在賽中一看到題目腦中立刻出現的解法，在看到的那刻就知道怎麼解的欣喜，讓我有 我的練習有價值 的感覺，實作的過程中也會想到一些自己過去吃的bug從而避開。而迅速想到第四題的轉移也代表~~我真的會通靈~~，我是指了解到dp的意義了。
還有終於可以快速冷靜下來debug，~~雖然可能跟學姊做法加持關聯比較大~~，即便可能之後還是會出現這種情況，可是不會像之前那樣往往過於短視近利，看到自己終於擺脫過去那種完全被情緒支配的感覺真的很好。
還有很多小東西也都令我蠻開心的，不過那些事就不足為外人道了。總之這些種種都讓我真真切切感受到，我進步了! 相信這就是當時的我想要得到的吧。
我還算不上是甚麼大電神。在別人眼中我的感動可能微不足道。這也不會是我的終點，可能連一個成就都稱不上(甚至我沒有特別準備這次檢定)。不過這次檢定是我對過去自己的一個交代，也象徵著我即將進行更高層次的追求。期待未來的我也能給現在的我一個完美的交代吧!
### 小去世
今天(11/7)9:00開放查成績，我在8:00的時候想到P2犯了致命的bug，整個人心情墜入谷底。毫不誇張的說，我那時候幾乎快哭出來了。但是後來我轉念一想，興許運氣好能過一些測資呢？然後我就開始拜天、拜地、拜學姊(X 最後成績出來拿了60分，加上其他三題拿滿共360，實作5級分！！！（那個，有在幫我做法的麻煩繼續，我很需要🤪🤪🤪
## 結語
之後(希望)有空再補code跟其他細節。
這次題目算蠻簡單了，我好幸運!
Sign in with Wallet
Connect another wallet