# 111 學年度 師大附中資訊學科能力競賽 上機題解
---
# 工作人員
----
## 出題
author/setter
A 林哲宇/林哲宇
B 侯欣緯/侯欣緯
C 林哲宇/侯欣緯
D 侯欣緯/侯欣緯
E 侯欣緯/侯欣緯
F 林哲宇/林哲宇
----
## 驗題
黃致皓
賴昭勳
王褕立
李政遠
林柏瑄
林煜傑
王品翔
鄭允臻
鄭詠堯
---
<!-- .slide: data-background="https://i.imgur.com/AJyPIqE.jpg" -->
<font color="black" size=7><b> pA 特戰英豪 (Valorant) </b></font>
----
## Subtask 1
$N \le 12$
- 不用考慮攻守交換、延長賽的問題
- 一定是 Match in Progress
- 數有幾個 A 跟 D 就好
----
## Subtask 2, 3
$N \le 24$
- 不用考慮延長賽的問題
- 比賽結束條件:其中一隊到達 13 分
- 如果到達 13 分後還有後面的局數則回報出錯
- 記得處理 9-3 詛咒
- 紀錄半場哪一隊 9 分,注意後半場攻守互換
----
## Subtask 2, 4
前 12 局結束時兩隊的分數皆不為 9 分
- 不用處理 9-3 詛咒
- 延長賽
- 前 24 局達到 13 分則比賽結束
- 否則判斷是否連續兩局由同一隊拿下
- 可以將延長賽視為每局都攻守交換
----
## Subtask 5
無額外限制
- 處理所有狀況
- 實作題(好像太難了)
----
## 常見錯誤
- 注意若比賽尚未結束,輸出的是最後一局的進攻及防守方
- 有人輸出成下一局的了
- 可以把換局視為某一局開始的事件,不是結束後的
- 記錄 9-3 詛咒時,詛咒是在「隊伍」上
- 不是記錄在攻方或守方
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
//{
//#pragma gcc optimize("Ofast,unroll-loops")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double
#define MP make_pair
#define F first
#define S second
#define P 3
// #define MOD 998244353
//}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
for (int Case = 1; Case <= T; Case++)
{
cout << "Match " << Case << ":\n";
int N;
string A, D, S;
cin >> N >> A >> D >> S;
int Ascr = 0, Bscr = 0, Aatk = 0, edr = 0, tag = 0;
for (int i = 1; i <= N; i++)
{
if (i == 1 || i == 13 || i > 24)
Aatk = !Aatk;
if ((S[i - 1] == 'A' && Aatk) || (S[i - 1] == 'D' && !Aatk))
Ascr++;
else
Bscr++;
if (max(Ascr, Bscr) >= 13 && abs(Ascr - Bscr) >= 2)
{
edr = i;
break;
}
if (i == 12)
if (Ascr == 9)
tag = -1;
else if (Bscr == 9)
tag = 1;
else;
}
if (edr > 0 && edr != N)
cout << "something went wrong :(\n";
else
{
string X = "DEF", Y = "ATK";
if (Aatk)
swap(X, Y);
cout << X << ' ' << A << " | " << Ascr << " : " << Bscr << " | " << D << ' ' << Y << '\n';
if (edr > 0)
{
if (S[N - 1] == 'A')
cout << "Attackers Win";
else
cout << "Defenders Win";
if ((tag == -1 && Bscr > Ascr) || (tag == 1 && Ascr > Bscr))
cout << ", 9-3 Curse!";
cout << '\n';
}
else
cout << "Match in Progress\n";
}
}
return 0;
}
// ***** ***** * * * ***** * * ***** *****
// * * * * * * * ** * * * *
// * * * ***** * * * * * * *****
// * * * * * * * * ** * *
// **** ***** * ***** ***** * * * *
```
---
<!-- .slide: data-background="https://i.imgur.com/hsgcDAb.jpg" -->
<font color="black" size=7><b> pB 垃圾清理 (Garbage) </b></font>
----
~~pA 應該要被清理掉~~
(確實)
----
## Subtask 1
$N=2$
你只要知道第一個撿的是哪個就好
----
## Subtask 2
$c_1 = 3$
對於 $1 \leq i < Q$,若 $c_i = 3$ 則 $c_{i+1} = 1$ 或 $c_{i+1} = 3$;若 $c_i = 1$ 則 $c_{i+1} = 3$
白話文:已經撿的區間是連續的
維護撿了的區間左右界
往前一格移的時候就是移到左界前一格
撿東西的話就是看現在在左界還右界,擴展那一邊後
移到右界後一格
----
## Subtask 3
$N,Q \leq 1000$
暴力模擬
----
## Subtask 4
linked list or set
~~相信大家在筆試時都有學會 linked list~~
----
```cpp=
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define eb(a) emplace_back(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " ";\
pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
int main(){
StarBurstStream
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> l(n), r(n);
for(int i = 0; i < n; i++){
l[i] = (i - 1 + n) % n;
r[i] = (i + 1) % n;
}
int now = 0;
for(int i = 0; i < q; i++){
//cerr << "owo " << now << "\n";
int c;
cin >> c;
if(c == 1){
now = l[now];
continue;
}
else if(c == 2){
now = r[now];
continue;
}
cout << now + 1 << " ";
l[r[now]] = l[now];
r[l[now]] = r[now];
now = r[now];
}
cout << "\n";
return 0;
}
```
---
<!-- .slide: data-background="https://i.imgur.com/VmU8XfN.jpg" -->
<font color="black" size=7><b> pC 彈珠汽水 (Ramune) </b></font>
----
我以為那個彈珠是用來阻止你喝太快的
這題是驗題者公認最簡單題 (?)
----
## Subtask 1
$K=2$
喝兩個送一個
= 你喝掉一瓶時,如果還剩至少一瓶,那你會多得到一瓶不能拿來換的
一開始有 $M$ 瓶,你最後會喝到 $2M-1$ 瓶
$2M-1 \geq N \implies M \geq \frac{N+1}{2}$
----
## Subtask 2
$K=3$
喝三個送一個
= 你喝掉兩瓶時,如果還剩至少一瓶,那你會多得到一瓶不能拿來換的
一開始有 $M$ 瓶,你最後會喝到 $M+\lfloor\frac{M-1}{2}\rfloor$ 瓶
----
## Subtask 3,4
$N,T \leq 100$
$N,T \leq 1000$
暴力
----
## Subtask 5
$T \leq 10^5$
注意到一開始的汽水越多,最後就可以喝越多
二分搜 + 暴力模擬
暴力模擬:一次喝掉 $\lfloor \frac{M}{K}K \rfloor$ 瓶
複雜度 $O(T \log^2 N)$
常數太大可能會被卡
----
## Subtask 6
如果你一開始有 $M$ 瓶
那你最後可以喝這麼多瓶
\\[ M + \left\lceil \frac{M}{K-1} \right\rceil - 1 \\]
\+ 二分搜
複雜度 $O(T \log N)$
----
Bonus: $O(1)$ solution
----
```cpp=
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define eb(a) emplace_back(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
ll calc(ll K, ll c){
return iceil(c, K - 1) - 1 + c;
}
void solve(){
ll n, K;
cin >> n >> K;
ll l = 1, r = n;
while(l < r){
ll mid = (l + r) / 2;
if(calc(K, mid) < n) l = mid + 1;
else r = mid;
}
cout << l << "\n";
}
int main(){
StarBurstStream
int T;
cin >> T;
while(T--) solve();
return 0;
}
```
---
<!-- .slide: data-background="https://i.imgur.com/cVGvs8K.jpg" -->
<font color="black" size=7><b> pD 轉移據點 (Rotate) </b></font>
----
白話文:有敵人的點之間的邊不能走
可以看成操作是在刪邊
----
## Subtask 1
圖是一條 $1,2,\dots,N$ 的鏈
用 set 存被刪掉的邊
詢問時只要看兩個點之間有沒有被刪的邊就好
----
## Subtask 2
$N,M,Q \leq 1000$
BFS/DFS 暴力
----
## Subtask 3
這是一個「不斷刪邊問連通性」的問題
倒過來看就變成「不斷加邊問連通性」的問題
DSU
~~相信大家在筆試都有學會 DSU~~
----
```cpp=
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define eb(a) emplace_back(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
vector<int> dsu;
int findDSU(int a){
if(dsu[a] != a) dsu[a] = findDSU(dsu[a]);
return dsu[a];
}
void unionDSU(int a, int b){
a = findDSU(a);
b = findDSU(b);
dsu[b] = a;
}
int main(){
StarBurstStream
int n, m;
cin >> n >> m;
dsu.resize(n + 1);
iota(iter(dsu), 0);
vector<pii> e(m);
vector<vector<int>> g(n + 1);
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
g[u].eb(v);
g[v].eb(u);
e[i] = mp(u, v);
}
vector<bool> black(n + 1);
int q;
cin >> q;
vector<vector<pair<int, pii>>> qry(q);
for(int i = 0; i < q; i++){
int ty;
cin >> ty;
if(ty == 1){
int w;
cin >> w;
black[w] = true;
for(int j : g[w]){
if(!black[j]) continue;
qry[i].eb(mp(1, mp(w, j)));
}
}
else{
int a, b;
cin >> a >> b;
qry[i].eb(mp(2, mp(a, b)));
}
}
for(pii i : e){
if(black[i.F] && black[i.S]) continue;
unionDSU(i.F, i.S);
}
vector<int> ans(q, -1);
for(int i = q - 1; i >= 0; i--){
for(auto j : qry[i]){
if(j.F == 1) unionDSU(j.S.F, j.S.S);
else ans[i] = findDSU(j.S.F) == findDSU(j.S.S);
}
}
for(int i = 0; i < q; i++){
if(ans[i] != -1){
if(ans[i] == 0) cout << "NO\n";
else cout << "YES\n";
}
}
return 0;
}
```
---
<!-- .slide: data-background="https://i.imgur.com/ZihejvJ.jpg" -->
<font color="black" size=7><b> pE 斯普拉遁 (Splatoon) </b></font>
----
白話文:
每兩個格子的交界有一個權重
操作問一段區間不同色交界的權重和
----
## Subtask 1
$N=2$
只有兩個格子和一個交界
應該很好做
----
## Subtask 2
$N,Q \leq 1000$
暴力
----
## Subtask 3
所有佔領都在詢問之前
先把最後的顏色長相處理好
(有很多方法
一種方法是倒著塗配 DSU 或 set 等等
或直接用 set 塗顏色)
~~如果你用線段樹的話你應該要會做滿分~~
詢問:區間和 -> 前綴和
----
## Subtask 4
每次佔領塗的顏色都不一樣
塗色 = 範圍中間的交界都會消失
要判斷的只有兩邊有沒有其他顏色
這個子題只要維護哪裡有塗過顏色就好
因為前面塗的顏色一定是不一樣的
----
## Subtask 5
$g_i=1$
不會寫線段樹?
你還有 PBDS
----
## Subtask 6
維護總和的部分:線段樹
維護顏色的部分:線段樹 or set
(兩個線段樹其實是一樣的)
----
```cpp=
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define eb(a) emplace_back(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
if(pvaspace) b << " "; \
pvaspace=true;\
b << pva;\
}\
b << "\n";}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.F << ',' << p.S << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
struct Node{
ll sum = 0, tag = -1;
int sz = 0;
};
int n;
vector<Node> st;
#define lc 2 * id + 1
#define rc 2 * id + 2
void addtag(ll v, int id){
st[id].tag = v;
st[id].sum = v * st[id].sz;
}
void push(int id){
if(st[id].tag == -1) return;
addtag(st[id].tag, lc);
addtag(st[id].tag, rc);
st[id].tag = -1;
}
void pull(int id){
st[id].sum = st[lc].sum + st[rc].sum;
}
void build(int L = 1, int R = n, int id = 0){
st[id].sz = R - L + 1;
if(L == R) return;
int M = (L + R) / 2;
build(L, M, lc);
build(M + 1, R, rc);
}
void modify(int l, int r, ll v, int L = 1, int R = n, int id = 0){
if(l <= L && R <= r){
addtag(v, id);
return;
}
push(id);
int M = (L + R) / 2;
if(r <= M) modify(l, r, v, L, M, lc);
else if(l > M) modify(l, r, v, M + 1, R, rc);
else{
modify(l, r, v, L, M, lc);
modify(l, r, v, M + 1, R, rc);
}
pull(id);
}
ll query(int l, int r, int L = 1, int R = n, int id = 0){
if(l <= L && R <= r) return st[id].sum;
push(id);
int M = (L + R) / 2;
if(r <= M) return query(l, r, L, M, lc);
else if(l > M) return query(l, r, M + 1, R, rc);
else{
return query(l, r, L, M, lc) + query(l, r, M + 1, R, rc);
}
}
int main(){
StarBurstStream
cin >> n;
int q;
cin >> q;
st.resize(4 * n);
vector<ll> s(n + 1);
for(int i = 1; i < n; i++) cin >> s[i];
build();
map<int, int> clr;
clr.insert(mp(1, 0));
auto getcolor = [&](int x){
return prev(clr.upper_bound(x))->S;
};
auto check = [&](int x){
if(x >= n || x < 1) return;
int cx = getcolor(x), cy = getcolor(x + 1);
if(cx != 0 && cy != 0 && cx != cy) modify(x, x, s[x]);
else modify(x, x, 0);
};
while(q--){
int ty;
cin >> ty;
if(ty == 2){
int l, r;
cin >> l >> r;
cout << query(l, r - 1) << "\n";
continue;
}
int l, r, c;
cin >> l >> r >> c;
if(r + 1 <= n){
int t = getcolor(r + 1);
clr[r + 1] = t;
}
auto it = clr.lower_bound(l);
while(it != clr.end() && it->F <= r){
it = clr.erase(it);
}
clr[l] = c;
if(l < r) modify(l, r - 1, 0);
check(l - 1);
check(r);
}
return 0;
}
```
---
<!-- .slide: data-background="https://i.imgur.com/IRA3q3v.jpg" -->
<font color="black" size=7><b> pF 學力測驗 (Quiz) </b></font>
----
## Subtask 3
$v_i=1$
- $1$ 跟任何數互質
- 全部都要換掉
- 換成 $2$ 就好了
- 答案為 $2N$
- **故不管一開始的 $v_i$ 長怎樣,答案都不會超過 $2N$**
----
## Subtask 1
$N=2$
- 只有兩個數字
- 如果它們不互質,答案為 $0$
- 如果互質,則可以:
- 把其中一邊換成另一邊的因數,或
- 把兩邊都換成 $2$
----
不管一開始的 $v_i$ 長怎樣,答案都不會超過 $2N$
- 每個數字只可能是
- 不改變
- 變為某個不超過 $2N$ 的數字
----
## Subtask 2
$N \le 100$
- 設 $dp1[u][j]$ 為將 $v_u$ 設為 $j$ 的且整棵子樹滿足不互質條件的花費
- 設 $dp2[u]$ 為將 $v_u$ 維持不變且整棵子樹滿足不互質條件的花費
----
每個 $j$(或維持原狀),
對於每個子節點 $c$ 分別選擇與 $j$ 不互質的數字,
並將各個子節點花費最小的可行數字加總
- 更新 $dp1[u][j]$:
- 枚舉 $x$,選所有 $j$ 與 $x$ 不互質的最小 $dp1[c][x]$
- 若 $j$ 與 $v_c$ 不互質,也可以選 $dp2[c]$
- 更新 $dp2[u]$:
- 枚舉 $x$,選所有 $v_u$ 與 $x$ 不互質的最小 $dp1[c][x]$
- 若 $v_u$ 與 $v_c$ 不互質,也可以選 $dp2[c]$
----
處理 $N$ 個節點時,
對於每個子節點,我們枚舉 $O(N)$ 個可能值
子節點數量總和為 $N-1$,
總時間複雜度 $O(N^3)$
----
## Subtask 4, 5
$v_i \le N$
$p_i=i$(一條鏈)
- 或許有特別的作法(?
----
## Subtask 6
無額外限制
- 考慮是否互質時,可以只維護 $j$ 是質數的 $dp1[u][j]$
- 一個數 $x$ 的質因數不超過 $\log{x}$ 個
- 時間複雜度下降到 $O(N^2\log{N})$
----
```cpp=
#include<bits/stdc++.h>
using namespace std;
//{
//#pragma gcc optimize("Ofast,unroll-loops")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double
#define MP make_pair
#define F first
#define S second
#define MOD 1000000007
//}
int N;
vector<bool> vis;
vector<int> v, pfac, prime, par;
vector<vector<int>> edge, plst, dp;
void dfs(int u)
{
vis[u] = true;
for (int &i : edge[u])
if (!vis[i])
par[i] = u, dfs(i);
for (int i = 2; i <= N * 2; i++)
{
int ans = 0;
if (v[u] != i)
ans = i;
for (int &j : edge[u])
{
int tmp = MOD;
if (__gcd(i, v[j]) > 1)
tmp = min(tmp, dp[j][1]);
for (int &k : plst[i])
tmp = min(tmp, dp[j][k]);
ans += tmp;
}
for (int &j : plst[i])
dp[u][j] = min(dp[u][j], ans);
}
int t = v[u];
vector<int> spe;
for (int &i : prime)
{
int cc = 0;
while (t % i == 0)
t /= i, cc++;
if (cc)
spe.push_back(i);
}
dp[u][1] = 0;
for (int &j : edge[u])
{
int tmp = MOD;
if (__gcd(v[u], v[j]) > 1)
tmp = min(tmp, dp[j][1]);
for (int &k : spe)
tmp = min(tmp, dp[j][k]);
dp[u][1] = min(MOD, dp[u][1] + tmp);
}
for (int &j : spe)
dp[u][j] = min(dp[u][j], dp[u][1]);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N, v = vector<int>(N + 1), edge = vector<vector<int>>(N + 1);
for (int i = 1; i <= N; i++)
cin >> v[i];
for (int i = 2; i <= N; i++)
{
int p;
cin >> p, edge[p].push_back(i);
}
pfac = vector<int>(N * 2 + 1, 1);
for (int i = 2; i <= N * 2; i++)
{
if (pfac[i] == 1)
prime.push_back(i);
for (int &j : prime)
{
if (i * j > N * 2)
break;
pfac[i * j] = j;
if (i % j == 0)
break;
}
}
plst.resize(N * 2 + 1);
for (int i = 2; i <= N * 2; i++)
{
int t = i;
while (pfac[t] > 1)
plst[i].push_back(pfac[t]), t /= pfac[t];
plst[i].push_back(t);
sort(plst[i].begin(), plst[i].end()), plst[i].resize(unique(plst[i].begin(), plst[i].end()) - plst[i].begin());
}
vis = vector<bool>(N + 1);
par = vector<int>(N + 1);
dp = vector<vector<int>>(N + 1, vector<int>(N * 2 + 1, MOD));
dfs(1);
int ans = MOD;
for (int i = 1; i <= N * 2; i++)
ans = min(ans, dp[1][i]);
cout << ans << '\n';
return 0;
}
// ***** ***** * * * ***** * * ***** *****
// * * * * * * * ** * * * *
// * * * ***** * * * * * * *****
// * * * * * * * * ** * *
// **** ***** * ***** ***** * * * *
```
{"metaMigratedAt":"2023-06-17T10:21:19.521Z","metaMigratedFrom":"YAML","title":"111 學年度 師大附中資訊學科能力競賽 上機題解","breaks":true,"contributors":"[{\"id\":\"02353542-5acb-4a66-abd0-128b1af24abb\",\"add\":18493,\"del\":58},{\"id\":\"6b95215f-91a7-4eaf-bcfe-d43740108f96\",\"add\":2300,\"del\":123}]"}