<style>
.flex {
background-color: transparent;
backdrop-filter: blur(0px);
}
body {
background-image: url("https://imgur.com/omd6Nt2.png");
background-repeat: no-repeat;
background-attachment: fixed;
background-position: center;
background-size: cover;
}
.markdown-body strong {
color: #000000;
}
.markdown-body h1, .markdown-body h2 {
border-bottom-color: #c8c8c8;
}
.markdown-body hr {
margin: 15px;
height: 0px;
border-top: 1px solid #c8c8c8;
}
.temp a:link, a:visited, a:hover, a:active {
color: #cca158;
}
.markdown-body a:link, a:visited, a:hover, a:active {
color: #73c9e6;
background-color: transparent;
text-decoration: none;
}
</style>
# 113學年度 成大資工智慧系統組 二階上機考 題解
:::warning
注意：我只會C++，然後前方大量map跟pair出沒，害怕的人請先行避難
:::
<ul style="font-size: 20px; font-weight: bold;">
<li><a href=#前情提要 smoothhashscroll>前情提要</a></li>
<li><a href=#操作們 smoothhashscroll>操作們</a><br></li>
<ul style="font-size: 16px;">
<li><a href=#1-A smoothhashscroll>1-A</a></li>
<li><a href=#1-B smoothhashscroll>1-B</a></li>
<li><a href=#2-A smoothhashscroll>2-A</a></li>
<li><a href=#2-B smoothhashscroll>2-B</a></li>
<li><a href=#3 smoothhashscroll>3</a></li>
<li><a href=#4 smoothhashscroll>4</a></li>
<li><a href=#5 smoothhashscroll>5</a></li>
<li><a href=#6-A smoothhashscroll>6-A</a></li>
<li><a href=#6-B smoothhashscroll>6-B</a></li>
</ul>
<li><a href=#寫完題解的心得 smoothhashscroll>寫完題解的心得</a>
<li><a href=#一年後的心得 smoothhashscroll>一年後的心得(2025/4/18新增)</a><br></li>
</ul>
## 前情提要
<b><a href="https://hackmd.io/@binghua/rJyxJdiQA">這裡</a></b>有題目，我就不寫了，請自行開左右分頁對照著看(感謝公開題目的大佬)
然後我就直接照著題目的順序寫下去
每個子題只會付跟那個子題有關的部分程式碼(除了最後的滿分解)
## 操作們
先把基本的程式碼打一下，剩下的就分子題動態加東西
跨操作的資結跟資節的操作我應該都會放全域(solve外面)
剩下操作的大部分都會在區域(solve裡面)
整體程式碼大概會長得像這樣
(你會發現N==1跟5寫在一起，這個之後會解釋)
:::spoiler code
```cpp=
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define X first
#define Y second
#define pii pair<int, int>
#define pLL pair<LL, LL>
#define mkp make_pair
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
#define LL loli
#define loli long long
using namespace std;
const LL mod = 1e9+7, LLinf = 9e18, intinf = 2e9;
...
void solve() {
int N; cin >> N;
if(N==1 || N==5) {
...
return;
}
if(N==2) {
...
return;
}
if(N==9) {
...
return;
}
if(N==4) {
...
return;
}
if(N==3) {
...
return;
}
if(N==6) {
...
return;
}
if(N==7) {
...
return;
}
if(N==8) {
...
return;
}
if(N==10) {
...
return;
}
}
int main() {
IO;
LL TT;
cin >> TT;
for(int cs=0; cs<TT; cs++) {
solve();
}
}
```
:::
---
### 1-A
因為總操作次數不會超過100
所以可以直接很trivial的開vector存名字、編號、顏色
操作1就push_back，操作2或9就窮舉vec找到目標的人然後操作
然因為編號會到10^18，所以直接用LL存所有整數(我就是沒這樣做，一開始20分我debug了快半小時)
又因為我懶得開struct所以直接用pair<string, pLL>存
:::spoiler 全域code片段
```cpp=
vector<pair<string, pLL> > vec; // vec[i] = (name, (number, color))
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1) {
string name;
LL num, color;
cin >> name >> num >> color;
vec.pb(mkp(name, mkp(num, color)));
return;
}
if(N==2) {
LL num;
string str;
cin >> num >> str;
for(auto &i : vec) {
if(i.S.F == num) {
i.F = str;
break;
}
}
return;
}
if(N==9) {
string str;
cin >> str;
for(auto &i : vec) {
if(i.F == str) {
cout << i.S.S << endl;
break;
}
}
return;
}
```
:::
---
### 1-B
這次操作變成10^5次，顯然剛才的方法一定TLE
所以就用底下的提示用hash map來過
但因為C++的unordered_map實在爛，所以直接用map來弄
大概開2個map就可以維護好這些東西
mp的key存編號、value存名字
mp2的key存名字、value存(編號，顏色)
然後在改名(操作2)的時候，因為詢問(操作9)輸入的名字保證會存在，所以不必把mp中舊名字刪掉
只是要在mp2把新名字對應的顏色設成舊名字的
:::spoiler 全域code片段
```cpp=
map<LL, string> mp; // num -> name
map<string, pLL> mp2; // name -> (num, color)
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1) {
string name;
LL num, color;
cin >> name >> num >> color;
mp[num] = name;
mp2[name] = mkp(num, color);
return;
}
if(N==2) {
LL num;
string name;
cin >> num >> name;
LL color = mp2[mp[num]].S;
mp2[name] = mkp(num, color);
mp[num] = name;
return;
}
if(N==9) {
string name;
cin >> name;
cout << mp2[name].S << endl;
return;
}
```
:::
---
### 2-A
題目一開始就有說用DSU，所以就直接在全域建一個DSU就好了
因為我懶得講原理跟寫法所以請自行google
然後因為只有操作1、3、4要弄，我們可以發現顏色跟本沒用到所以不用紀錄
但有一個問題是操作4是輸入名字、操作3是輸入編號
所以還是要用一個map去讓名字找到對應的編號，然後用編號維護DSU(為什麼不是用名字2-B會說)
又因為編號很大，所以一樣要用map去建DSU，然後DSU的初始化就在操作1裡面去做
:::spoiler 全域code片段
```cpp=
map<string, LL> mp; // name -> num
map<LL, LL> anc, sz;
LL find(LL x) {
if(x == anc[x]) return x;
return anc[x] = find(anc[x]);
}
void joint(LL a, LL b) {
if(sz[a] < sz[b]) swap(a, b);
anc[b] = a;
sz[a] += sz[b];
}
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1) {
string name;
LL num, color;
cin >> name >> num >> color;
mp[name] = num;
anc[num] = num, sz[num] = 1;
return;
}
if(N==4) {
string A, B;
cin >> A >> B;
LL a = find(mp[A]), b = find(mp[B]);
if(a != b) joint(a, b);
return;
}
if(N==3) {
LL a, b;
cin >> a >> b;
a = find(a), b = find(b);
cout << (a==b ? "Yes" : "No") << endl;
return;
}
```
:::
---
### 2-B
其實整體跟2-A差不多，只是多了改名然後顏色紀錄回來
而2-A裡提到為什麼要用編號維護DSU而不是用名字是因為編號不會變但名字會
所以用編號是最簡單的方式
最後把2-A結合1-B應該就可以過這個子題了
:::spoiler 全域code片段
```cpp=
map<LL, string> mp; // num -> name
map<string, pLL> mp2; // name -> (num, color)
map<LL, LL> anc, sz;
LL find(LL x) {
if(x == anc[x]) return x;
return anc[x] = find(anc[x]);
}
void joint(LL a, LL b) {
if(sz[a] < sz[b]) swap(a, b);
anc[b] = a;
sz[a] += sz[b];
}
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1) {
string name;
LL num, color;
cin >> name >> num >> color;
mp[num] = name;
mp2[name] = mkp(num, color);
anc[num] = num, sz[num] = 1;
return;
}
if(N==2) {
LL num;
string name;
cin >> num >> name;
LL color = mp2[mp[num]].S;
mp2[name] = mkp(num, color);
mp[num] = name;
return;
}
if(N==9) {
string name;
cin >> name;
cout << mp2[name].S << endl;
return;
}
if(N==4) {
string A, B;
cin >> A >> B;
LL a = find(mp2[A].F), b = find(mp2[B].F);
if(a != b) joint(a, b);
return;
}
if(N==3) {
LL a, b;
cin >> a >> b;
a = find(a), b = find(b);
cout << (a==b ? "Yes" : "No") << endl;
return;
}
```
:::
---
### 3
操作5的部分我們可以維護一個set裡面存名字，輸入名字的時候直接加到set裡
因為set會從小到大排序(字串的話就是依字典序)，所以可以二分搜找答案
操作5的時候就一樣先加名字進st然後lower_bound找他的位置
如果他在st.begin()則表示在加他之前沒有比他小的
否則他位置的前一格就會是答案
而因為操作1跟5有一大部份的操作都一樣，所以其實可以寫在同一個if裡面
(這就是為什麼罪一開始的code中N==1跟5寫在一起)
然後因為這個子題只有名字在做事，所以連map都不用建，全域有一個set就可以了
:::spoiler 全域code片段
```cpp=
set<string> st;
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1 || N==5) {
string name;
LL num, color;
cin >> name >> num >> color;
st.insert(name);
if(N==5) {
auto it = st.lower_bound(name);
if(it == st.begin()) cout << -1 << endl;
else cout << *(prev(it)) << endl;
}
return;
}
```
:::
---
### 4
這是我覺得整場考試中最難的子題(當然6-A跟6-B不算)
操作6要用到Trie這個神奇資結，因為很難在這裡講他的具體寫法所以請自行google
反正大致上就是能把字串放在樹上的神奇資結
操作1每次輸入的時候就可以把名字加到Trie中，每個node存該節點的答案，跑到一個node就跟原本的答案取max
操作6的時候就把輸入的字串從Trie的根一直跑下去，跑到不能再跑的時候就是最長共同前綴了
然後因為操作1的時候有對每個節點取max，可以保證操作6跑到的最終節點中的答案會是字典序最大的那個
這就符合題目中的「如果有多個人的名字是最長共同前綴，請你輸出字典序最大的那一個。」
跟子題3一樣，我們只有字串要做事，所以我們不用map也不用set，一顆Trie就可以了
然後可以寫一個函數把A\~z轉成0\~51，這樣一個node中就可以開52個分支
寫這個函數滿簡單的，就不多做說明了
:::spoiler 全域code片段
```cpp=
struct Trie {
Trie* arr[52];
string ans;
Trie() {
for(auto &i : arr) i=nullptr;
ans = "";
}
LL ctoi(char c) {
if(isupper(c)) return c-'A';
return 26 + c-'a';
}
void insert(string str) {
Trie *cur = this;
cur->ans.insert(str);
for(auto &c : str) {
LL i = ctoi(c);
if(!cur->arr[i]) cur->arr[i] = new Trie();
cur = cur->arr[i];
cur->ans.insert(str);
}
}
string search(string str) {
Trie *cur = this;
for(auto &c : str) {
LL i = ctoi(c);
if(!cur->arr[i]) return cur->ans;
cur = cur->arr[i];
}
return cur->ans;
}
} *trie = new Trie();
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1) {
string name;
LL num, color;
cin >> name >> num >> color;
trie->insert(name);
return;
}
if(N==6) {
string str;
cin >> str;
cout << trie->search(str) << endl;
return;
}
```
:::
---
### 5
看到區間就想到BIT，這個子題就是用map建BIT(不然也可以離線然後離散化建BIT但那好麻煩)
也是因為我懶得講原理，所以請自行google
反正就是BIT可以算單點修改後的前綴和，所以可以做到單點修改區間查詢(因為一個區間和可以變成兩個前綴和相減)
但因為是用map建BIT，我們要設一個上限讓modify不會跑到LL範圍外爛掉
由於每次跳到下一個位置最多只會\*2，所以上限可以設10^18+5，不會跑到LL外面去
跟前面子題不一樣我們這次是編號要做事，但一樣的事我們不用開map存人，一個BIT就可以了
然後講個神奇的事，有人開IO優化用set二分搜過了這個子題，電爛
:::spoiler 全域code片段
```cpp=
#define lowbit(x) ((x)&(-x))
LL maxN = 1e18+5;
map<LL, LL> BIT;
void modify(LL pos) {
while(pos < maxN) {
BIT[pos] ++ ;
pos += lowbit(pos);
}
}
LL query(LL pos) {
LL ret = 0;
while(pos) {
ret += BIT[pos];
pos -= lowbit(pos);
}
return ret;
}
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1) {
string name;
LL num, color;
cin >> name >> num >> color;
modify(num);
return;
}
if(N==7) {
LL l, r;
cin >> l >> r;
cout << query(r) - query(l-1) << endl;
return;
}
```
:::
---
### 6-A
因為我不知道6-A大概怎樣會過，而且6-B的操作也不難，所以直接跳到6-B
---
### 6-B
剩下就是全部混在一起了，因為很多操作會互相影響，所以滿難寫題解的
這裡直接先用2-B的程式碼，然後一個一個加入操作動態修改會影響的部分
(操作8跟10下面會寫)
然後加入每個操作後的程式碼也都只會付跟那個操作有關的部分程式碼
不然就真的很長
#### 加入操作5
跟子題3一樣用set
會影響的是操作2的改名，只要在set中刪掉舊名插入新名就可以了
:::spoiler 全域code片段
```cpp=
set<string> st;
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1||N==5) {
string name;
LL num, color;
cin >> name >> num >> color;
st.insert(name);
if(N==5) {
auto it = st.lower_bound(name);
if(it == st.begin()) cout << -1 << endl;
else cout << *(prev(it)) << endl;
}
return;
}
if(N==2) {
LL num;
string name;
cin >> num >> name;
LL color = mp2[mp[num]].S;
mp2[name] = mkp(num, color);
// mp[num] = name;
string oldname = mp[num];
st.erase(oldname);
st.insert(name);
mp[num] = name;
return;
}
```
:::
#### 加入操作6
跟子題4一樣用Trie
但因為操作2會改名字，所以節點存的答案就不能再是存單一的字串，而是要用set
當字串跑過每個節點的時候就在該節點的set插入字串，查詢最後的答案會是該節點set的最後一格
而這就表示改名時會需要刪除節點set中的名字，保險起見，我們要從字串尾端刪除
所以要把跑過Trie順序記起來然後倒序操作回去
如果節點的set變空了就表示那個分支沒有字串了，要刪掉該節點不然會爛掉
刪掉的部分，可以直接把指標設成nullptr，然後把上一個節點指向他的指標也設成nullptr
(其實我不知道這樣做空間會不會爆掉，應該是沒事)
:::spoiler 全域code片段
```cpp=
struct Trie {
Trie* arr[52];
set<string> ans;
Trie() {
for(auto &i : arr) i=nullptr;
ans.clear();
}
LL ctoi(char c) {
if(isupper(c)) return c-'A';
return 26 + c-'a';
}
void insert(string str) {
Trie *cur = this;
cur->ans.insert(str);
for(auto &c : str) {
LL i = ctoi(c);
if(!cur->arr[i]) cur->arr[i] = new Trie();
cur = cur->arr[i];
cur->ans.insert(str);
}
}
void erase(string str) {
Trie *cur = this;
vector<Trie*> vec;
vec.pb(cur);
for(auto &c : str) {
cur = cur->arr[ctoi(c)];
vec.pb(cur);
}
for(int i=vec.size()-1; i>=0; i--) {
vec[i]->ans.erase(str);
if(vec[i]->ans.empty()) {
vec[i] = nullptr;
if(i) vec[i-1]->arr[ctoi(str[i-1])] = nullptr;
}
}
}
string search(string str) {
Trie *cur = this;
for(auto &c : str) {
LL i = ctoi(c);
if(!cur->arr[i]) return *(prev(cur->ans.end()));
cur = cur->arr[i];
}
return *(prev(cur->ans.end()));
}
} *trie = new Trie();
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1||N==5) {
string name;
LL num, color;
cin >> name >> num >> color;
trie->insert(name);
return;
}
if(N==2) {
LL num;
string name;
cin >> num >> name;
string oldname = mp[num];
trie->erase(oldname);
trie->insert(name);
return;
}
if(N==6) {
string str;
cin >> str;
cout << trie->search(str) << endl;
return;
}
```
:::
#### 加入操作7
這個直接把子題5加進來就可以了，因為他跟其他操作沒有影響
:::spoiler 全域code片段
```cpp=
#define lowbit(x) ((x)&(-x))
LL maxN = 1e18+5;
map<LL, LL> BIT;
void modify(LL pos) {
while(pos < maxN) {
BIT[pos] ++ ;
pos += lowbit(pos);
}
}
LL query(LL pos) {
LL ret = 0;
while(pos) {
ret += BIT[pos];
pos -= lowbit(pos);
}
return ret;
}
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1||N==5) {
string name;
LL num, color;
cin >> name >> num >> color;
modify(num);
return;
}
if(N==7) {
LL l, r;
cin >> l >> r;
cout << query(r) - query(l-1) << endl;
return;
}
```
:::
<br>
接下來就是還沒寫過的操作了
#### 加入操作8
其實就只有改顏色滿簡單的，唯一要注意的是他有可能會輸入名字或編號這件事
剩下跟其他操作基本不衝突，所以直接改map裡面的資訊就可以了
:::spoiler 全域code片段
```cpp=
```
:::
:::spoiler 區域code片段
```cpp=
if(N==8) {
string str;
LL color;
cin >> str >> color;
if(isdigit(str[0])) str = mp[stoi(str)];
mp2[str].S = color;
return;
}
```
:::
#### 加入操作10
只有操作4跟8會影響這個操作
又為了要快速的查詢答案
我們觀察一下不難想出以下方法
對DSU中每個群體紀錄每個顏色有幾個人 -> map<LL, LL> anc_to_color[105];
紀錄此時每個顏色的答案 -> LL color_to_ans[105];
每格都先初始化為0
當遇到操作4，只要找到兩群體中同顏色的人數並相乘，就可以更新color_to_ans的值
這可以直接在DSU的joint操作中完成
當遇到操作8，只要找到自己屬於的群體中就顏色跟新顏色的人數，也可以更新color_to_ans的值
當遇到操作10，直接輸出color_to_ans中的值就可以了
我們只要在操作1跟5中初始化anc_to_color以及上述操作，就可以完整的維護這些答案
(細節詳見code)
:::spoiler 全域code片段
```cpp=
const LL maxN2 = 105;
map<LL, LL> anc_to_color[maxN2];
LL color_to_ans[maxN2];
void joint(LL a, LL b) {
if(sz[a] < sz[b]) swap(a, b);
anc[b] = a;
sz[a] += sz[b];
for(int i=0; i<maxN2; i++) color_to_ans[i] += anc_to_color[a][i] * anc_to_color[b][i];
for(int i=0; i<maxN2; i++) anc_to_color[a][i] += anc_to_color[b][i];
}
```
:::
:::spoiler 區域code片段
```cpp=
if(N==1||N==5) {
string name;
LL num, color;
cin >> name >> num >> color;
anc_to_color[num][color] ++ ;
return;
}
if(N==8) {
string str;
LL color;
cin >> str >> color;
if(isdigit(str[0])) str = mp[stoi(str)];
LL num = mp2[str].F, Anc = find(num), oldcolor = mp2[str].S;
anc_to_color[Anc][oldcolor] -- ;
color_to_ans[oldcolor] -= anc_to_color[Anc][oldcolor];
color_to_ans[color] += anc_to_color[Anc][color];
anc_to_color[Anc][color] ++ ;
mp2[str].S = color;
return;
}
if(N==10) {
LL color;
cin >> color;
cout << color_to_ans[color] << endl;
return;
}
```
:::
#### 最後的滿分解
最後就是把所有東西都喇在一起
就會變成這樣
:::spoiler code
```cpp=
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#define IO cin.tie(0) -> sync_with_stdio(0)
#define endl "\n"
#define F first
#define S second
#define X first
#define Y second
#define pii pair<int, int>
#define pLL pair<LL, LL>
#define mkp make_pair
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
#define LL loli
#define loli long long
using namespace std;
const LL mod = 1e9+7, LLinf = 9e18, intinf = 2e9;
map<LL, string> mp; // num -> name
map<string, pLL> mp2; // name -> (num, color)
map<LL, LL> anc, sz;
const LL maxN2 = 105;
map<LL, LL> anc_to_color[maxN2];
LL color_to_ans[maxN2];
LL find(LL x) {
if(x == anc[x]) return x;
return anc[x] = find(anc[x]);
}
void joint(LL a, LL b) {
if(sz[a] < sz[b]) swap(a, b);
anc[b] = a;
sz[a] += sz[b];
for(int i=0; i<maxN2; i++) color_to_ans[i] += anc_to_color[a][i] * anc_to_color[b][i];
for(int i=0; i<maxN2; i++) anc_to_color[a][i] += anc_to_color[b][i];
}
set<string> st;
struct Trie {
Trie* arr[52];
set<string> ans;
Trie() {
for(auto &i : arr) i=nullptr;
ans.clear();
}
LL ctoi(char c) {
if(isupper(c)) return c-'A';
return 26 + c-'a';
}
void insert(string str) {
Trie *cur = this;
cur->ans.insert(str);
for(auto &c : str) {
LL i = ctoi(c);
if(!cur->arr[i]) cur->arr[i] = new Trie();
cur = cur->arr[i];
cur->ans.insert(str);
}
}
void erase(string str) {
Trie *cur = this;
vector<Trie*> vec;
vec.pb(cur);
for(auto &c : str) {
cur = cur->arr[ctoi(c)];
vec.pb(cur);
}
for(int i=vec.size()-1; i>=0; i--) {
vec[i]->ans.erase(str);
if(vec[i]->ans.empty()) {
vec[i] = nullptr;
if(i) vec[i-1]->arr[ctoi(str[i-1])] = nullptr;
}
}
}
string search(string str) {
Trie *cur = this;
for(auto &c : str) {
LL i = ctoi(c);
if(!cur->arr[i]) return *(prev(cur->ans.end()));
cur = cur->arr[i];
}
return *(prev(cur->ans.end()));
}
} *trie = new Trie();
#define lowbit(x) ((x)&(-x))
LL maxN = 1e18+5;
map<LL, LL> BIT;
void modify(LL pos) {
while(pos < maxN) {
BIT[pos] ++ ;
pos += lowbit(pos);
}
}
LL query(LL pos) {
LL ret = 0;
while(pos) {
ret += BIT[pos];
pos -= lowbit(pos);
}
return ret;
}
void solve() {
int N; cin >> N;
if(N==1||N==5) {
string name;
LL num, color;
cin >> name >> num >> color;
mp[num] = name;
mp2[name] = mkp(num, color);
anc[num] = num, sz[num] = 1;
st.insert(name);
if(N==5) {
auto it = st.lower_bound(name);
if(it == st.begin()) cout << -1 << endl;
else cout << *(prev(it)) << endl;
}
trie->insert(name);
modify(num);
anc_to_color[num][color] ++ ;
return;
}
if(N==2) {
LL num;
string name;
cin >> num >> name;
LL color = mp2[mp[num]].S;
mp2[name] = mkp(num, color);
// mp[num] = name;
string oldname = mp[num];
st.erase(oldname);
st.insert(name);
mp[num] = name;
trie->erase(oldname);
trie->insert(name);
return;
}
if(N==9) {
string name;
cin >> name;
cout << mp2[name].S << endl;
return;
}
if(N==4) {
string A, B;
cin >> A >> B;
LL a = find(mp2[A].F), b = find(mp2[B].F);
if(a != b) joint(a, b);
return;
}
if(N==3) {
LL a, b;
cin >> a >> b;
a = find(a), b = find(b);
cout << (a==b ? "Yes" : "No") << endl;
return;
}
if(N==6) {
string str;
cin >> str;
cout << trie->search(str) << endl;
return;
}
if(N==7) {
LL l, r;
cin >> l >> r;
cout << query(r) - query(l-1) << endl;
return;
}
if(N==8) {
string str;
LL color;
cin >> str >> color;
if(isdigit(str[0])) str = mp[stoi(str)];
LL num = mp2[str].F, Anc = find(num), oldcolor = mp2[str].S;
anc_to_color[Anc][oldcolor] -- ;
color_to_ans[oldcolor] -= anc_to_color[Anc][oldcolor];
color_to_ans[color] += anc_to_color[Anc][color];
anc_to_color[Anc][color] ++ ;
mp2[str].S = color;
return;
}
if(N==10) {
LL color;
cin >> color;
cout << color_to_ans[color] << endl;
return;
}
}
int main() {
IO;
LL TT;
cin >> TT;
for(int cs=0; cs<TT; cs++) {
solve();
}
}
```
:::
這樣應該就可以拿滿分了
## 寫完題解的心得
~~幹這根本競程~~
耶終於打完了OwO
剛好今天去sogo打完機回來完全不累
索性直接熬夜打題解到早上
結果還真的給我打完了，酷欸
因為試後沒有可以測題的地方，所以75分之上的分數不確定正不正確
但我有自己生一點測資試過了，複雜度也應該都是好的
所以我相信應該可以是好的(吧
話說考完學長有說可以把map裡的東西當放到Trie上
但我好懶而且map好香所以我就不弄了，有興趣的可以自己寫寫看
題解有問題或有錯字(應該都會有滿多的)都可以直接跟我講，我會馬上改
有問題也可以問我
就這樣，好累
## 一年後的心得
在修了一下的資料結構與物件導向之後才發現出題跟這個的性質比較像
當初會覺得是競程大概有幾個原因
1. 我只會競程
2. 競程裡也滿常用到像STL, struct這類的東西的
3. 出題者是競程大佬
這樣的話確實能說跟「智慧系統組」這個名稱是挺有關聯的了，但就是不知道之前apcs組都考什麼還有之後到底會出怎樣的題型，畢竟今年也才第一年
阿然後雖然現在講可能有點太遲，但也祝有看到這個HackMD的考生們金榜題名，進入理想的學校，雖然真心來說我覺得不管進哪一間只要是資工就都是爆肝就是了:D
Sign in with Wallet
Connect another wallet