2023 Benelux Algorithm Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/104790
比賽影片
---
{%youtube Zi6slfuS6W4 %}
記分板
---
題解
---
### A. $\texttt{apt upgrade}$
---
#### 題目摘要
QAQ 就算AC後我也看不懂題目要幹嘛
#### 想法
前(m+k)大的和除以總和
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<ll> v(n);
for(auto &x:v) cin >> x;
sort(v.begin(), v.end(), greater<int>());
ll sum=accumulate(v.begin(), v.end(), 0LL);
ll tmp=0;
for(int i=0;i<min(n, m+k);i++){
tmp+=v[i];
}
double ans=100.0*tmp/sum;
cout << fixed << setprecision(10) << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### B. Battle Bots
---
#### 題目摘要
給一個$\,n\,$，每次操作能把他除2或減1(有小數點)，求把它變不大於0的最少操作
#### 想法
$\lceil\log_2n\rceil + 1$
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
void solve() {
ll n; cin >> n;
ll cnt = 0, cur = 1;
while (cur < n) {
cnt++;
cur <<= 1;
}
cout << cnt + 1 << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### C. Compressing Commands
---
#### 題目摘要
給你很多個檔案的絕對路徑，可以利用 ../ 移動檔案夾位置，問從哪個資料夾為起始點，到所有檔案經過的檔案夾 (相對路徑長度) 最短。
#### 想法
建一棵有虛根的樹，權重都在葉節點，以那些權重來找樹重心，再從樹重心出發就會是答案，若樹重心在葉節點就把他往上提一格就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pll pair<ll, ll>
#define F first
#define S second
#define pii pair<int, int>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
const ll MOD = 100000004849LL, cc = get_rand(128, 1000);
const int MAXN = 1e6 + 5;
vector<int> adj[MAXN];
int leaf[MAXN];
void solve() {
int n; cin >> n;
map<pll, int> mp;
int id = 1;
mp[{-1, -1}] = id++;
map<pii, int> edge;
rep (i, 0, n) {
string s; cin >> s;
string cur = "";
int m = s.size();
int pre = 1;
rep (i, 1, m) {
if (s[i] == '/') {
ll hash = 0;
for (char c : cur) {
hash = (hash * cc % MOD + c) % MOD;
}
if (mp.find({pre, hash}) == mp.end()) {
// if (id == 7) cout << cur << '\n';
mp[{pre, hash}] = id++;
}
if (edge[minmax(mp[{pre, hash}], pre)] == 0) {
adj[pre].pb(mp[{pre, hash}]);
adj[mp[{pre, hash}]].pb(pre);
edge[minmax(mp[{pre, hash}], pre)] = 1;
}
pre = mp[{pre, hash}];
cur.clear();
} else {
cur.pb(s[i]);
}
}
if (!cur.empty()) {
ll hash = 0;
for (char c : cur) {
hash = (hash * cc + c) % MOD;
}
if (mp.find({pre, hash}) == mp.end()) {
// if (id == 8) cout << cur << '\n';
mp[{pre, hash}] = id++;
}
// cout << pre << ' ' << mp[{pre, hash}] << '\n';
leaf[mp[{pre, hash}]]++;
if (mp[{pre, hash}] != 1 && edge[minmax(mp[{pre, hash}], pre)] == 0) {
adj[pre].pb(mp[{pre, hash}]);
adj[mp[{pre, hash}]].pb(pre);
edge[minmax(mp[{pre, hash}], pre)] = 1;
}
pre = mp[{pre, hash}];
cur.clear();
}
}
// rep (i, 1, id) {
// for (int x : adj[i]) cerr << x << ' ';
// cerr << '\n';
// }
// cout << id << '\n';
int head = 1, tot = id;
bool f = 0;
if (adj[1].size() == 1) head = adj[1][0], f = 1;
int sum = 0;
// cout << tot << '\n';
vector<int> sz(tot);
vector<int> dep(tot, 0);
rep (i, head, tot) sz[i] = leaf[i];
rep (i, head, tot) sum += sz[i];
// rep (i, head, tot) cout << sz[i] << '\n';
int cen = 0;
auto dfs = [&](auto self, int u, int pa) -> void {
int mx = 0;
for (int v : adj[u]) {
if (v == pa) continue;
if (f && v == 1) continue;
dep[v] = dep[u] + 1;
self(self, v, u);
sz[u] += sz[v];
mx = max(mx, sz[v]);
}
mx = max(mx, sum - sz[u]);
if (mx <= sum / 2) {
cen = u;
}
};
dfs(dfs, head, -1);
fill(all(dep), 0);
if (leaf[cen]) cen = adj[cen][0];
// cout << cen << '\n';
dfs(dfs, cen, -1);
ll ans = 0;
rep (i, 2, tot) if (leaf[i]) {
ans += 1LL * dep[i] * leaf[i];
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### D. Democratic Naming
---
#### 題目摘要
給每個人對每個咚咚的投票，求最後長怎樣(先比最多次數再比字典序)
#### 想法
水題，用map記後輸出
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
int main() {
int n, m; cin >> n >> m;
vector cnt(m, vector<int>(26, 0));
rep (i, 0, n) {
string s; cin >> s;
rep (j, 0, m) cnt[j][s[j] - 'a']++;
}
rep (i, 0, m) {
int mx = 0, pos = 0;
rep (j, 0, 26) {
if (cnt[i][j] > mx) {
mx = cnt[i][j];
pos = j;
}
}
cout << (char)('a' + pos);
}
}
```
:::
### E. Exam Study Planning
---
#### 題目摘要
有$n$場考試，第$i$場考試在$s_i$開始，若讀超過$a_i$就會沒過並且考試在$e_i$結束，否則通過且在$p_i$結束，在沒考試的時間都能讀書。問從時間0開始，最多能通過多少考試
#### 想法
建$dp_{i,\ j}$為考試前$i$場並通過$j$場剩下的最大時間是什麼，最後再看考完$n-1$場後剩下的時間能不能通過最後的考試
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
const int N=2005;
const ll LINF=1e18+7;
ll dp[N][N];
ll s[N], p[N], e[N], a[N];
void solve() {
int n;
cin >> n;
for(int i=1;i<=n;i++) {
cin >> s[i] >> p[i] >> e[i] >> a[i];
}
for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=-LINF;
dp[0][0]=s[1];
for(int i=1;i<=n-1;i++){
if (dp[i-1][0]!=-LINF) dp[i][0]=dp[i-1][0]+s[i+1]-e[i];
for(int j=1;j<=i;j++){
if (dp[i-1][j]!=-LINF) dp[i][j]=dp[i-1][j]+s[i+1]-e[i];
if (dp[i-1][j-1]!=-LINF&&dp[i-1][j-1]>=a[i]) dp[i][j]=max(dp[i][j], dp[i-1][j-1]+s[i+1]-p[i]-a[i]);
}
}
int ans=0;
for(int i=0;i<n;i++){
if (dp[n-1][i]>=a[n]) ans=i+1;
if (dp[n-1][i]>=0) ans=max(ans, i);
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### F. Funicular Frenzy
---
#### 題目摘要
排隊搭纜車，有$n$批人每次纜車能載$m$個人，你想要在最好時機入場使得你能最早搭到且排隊等待時間最少，你要排在跟你同時進去的那批人後面。
#### 想法
可以很簡單的算出來對於每個時間點入場能搭上的時間，找到搭上時間跟進場時間差最小那個就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
void solve() {
int n; ll c; cin >> n >> c;
vector<ll> pre(n + 1, 0), cur;
cur.pb(0);
rep (i, 1, n + 1) {
int a; cin >> a;
pre[i] = pre[i - 1] + a;
cur.pb(cur.back() + c);
}
vector<int> t(n + 1);
int mi = n + 1, pos = -1;
rep (i, 1, n + 1) {
t[i] = upper_bound(all(cur), pre[i]) - cur.begin();
t[i] = max(t[i], i);
if (t[i] == n + 1) continue;
if (t[i] - i < mi) {
mi = t[i] - i;
pos = i;
}
}
if (pos != -1) cout << pos - 1 << '\n';
else cout << "impossible\n";
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### G. Geometry Game
---
#### 題目摘要
給4個點，判它是正方形、長方形、菱形、平行四邊形、梯形、箏形或什麼都不是
#### 想法
算平行邊數量、四邊等長、四角都垂直，可以先把前5個判完，最後再特判箏形就好
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pll pair<ll, ll>
#define F first
#define S second
pll operator+(const pll a, const pll b) {
return {a.F + b.F, a.S + b.S};
}
pll operator-(const pll a, const pll b) {
return {a.F - b.F, a.S - b.S};
}
ll dot(pll a, pll b) {
return {a.F * b.F + a.S * b.S};
}
ll cross(pll a, pll b) {
return {a.F * b.S - a.S * b.F};
}
ll dis(pll a) {
return a.F * a.F + a.S * a.S;
}
void solve() {
vector<pll> pt(4);
for (auto &[x, y] : pt) cin >> x >> y;
int par = 0;
par += cross(pt[1] - pt[0], pt[2] - pt[3]) == 0;
par += cross(pt[3] - pt[0], pt[2] - pt[1]) == 0;
bool len = 1;
rep (i, 0, 3) len &= dis(pt[i + 1] - pt[i]) == dis(pt[(i + 2) % 4] - pt[i + 1]);
bool ort = 1;
rep (i, 0, 3) ort &= dot(pt[i + 1] - pt[i], pt[(i + 2) % 4] - pt[i + 1]) == 0;
if (len && ort) {
cout << "square\n";
return;
}
if (ort) {
cout << "rectangle\n";
return;
}
if (len) {
cout << "rhombus\n";
return;
}
if (par == 2) {
cout << "parallelogram\n";
return;
}
if (par == 1) {
cout << "trapezium\n";
return;
}
if (((dis(pt[0] - pt[1]) == dis(pt[0] - pt[3])) && (dis(pt[2] - pt[1]) == dis(pt[2] - pt[3]))) ||
((dis(pt[1] - pt[0]) == dis(pt[1] - pt[2])) && (dis(pt[3] - pt[0]) == dis(pt[3] - pt[2])))) {
cout << "kite\n";
return;
}
cout << "none\n";
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### H. Hidden Art
---
#### 題目摘要
給你一個含{g, r, b, w}的可以無限複製的Grid長$\,h\,$寬$\,w\,$，問能不能構造出一個正方形的四個角落恰好包含四個不同的元素
#### 想法
觀察：任一個無限延伸產生的好正方形四個角落可以對應到原本grid裡矩形的四個角落。
但不是任何一個subgrid都可以延伸成正方形，若現在選擇一個subgrid的長$\,x\,$寬$\,y\,$，放在無限延伸的grid上可以表示成長$\,x+kh\,$寬$\,y+\ell w\,$
可以知道若要成為一個正方形必須符合：
\begin{equation}
\begin{aligned}
x + kh &= y + \ell w \\
x - y &= \ell w - kh
\end{aligned}
\end{equation}
根據貝祖定理可以知道有解的狀況發生在$\gcd(w, h)\,|\,x - y$
因此可以有做法是枚舉可能的四個角落，但這樣會吃TLE
觀察到只要固定底部的寬，高的可以很好的維護將模$\gcd(w, h)$下抓起來一起維護
因此可以用到$O(hw^2)$解決
枚舉兩個$w$，然後將以這兩為寬的所有高模$\gcd(w, h)$的圖形維護好，
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pll pair<ll, ll>
#define F first
#define S second
#define pii pair<int, int>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
const int MAXN = 1e6 + 5;
map<char, int> mp;
void solve() {
mp['w'] = 1, mp['r'] = 2, mp['b'] = 4, mp['g'] = 8;
int n, m; cin >> n >> m;
int g = __gcd(n, m);
vector<string> G(n);
rep (i, 0, n) cin >> G[i];
rep (i, 0, m - 1) rep (j, i + 1, m) {
int w = j - i;
vector check(g, vector<bool>(16, 0));
rep (h, 0, n) {
check[h % g][mp[G[h][i]] | mp[G[h][j]]] = 1;
int cur = (mp[G[h][i]] | mp[G[h][j]]);
if (check[(h + w) % g][15 ^ cur] || (check[((h - w) % g + g) % g][15 ^ cur])) {
cout << "possible\n";
return;
}
}
}
cout << "impossible\n";
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### I. International Irregularities
---
#### 題目摘要
給一張完全圖，第$i$點有點權$t_i和r_i(r遞增)$，若$r_i>r_j+m$，則$i到j$的邊權是$t_j+1，否則為1$。有$q$筆詢問，問從$x到y(x\not =y)$的最短距離
#### 想法
首先，若$x<y$時，答案一定是1$(因為r_x\le r_y+m)$。否則，移動方式可以分成4種方式討論，但要先定義走路方法：
1. hop：走邊權$1$的邊
2. jump：走邊權$t_i+1$的邊
不論哪種移動方式都一定是最多1次jump，並且若jump一定是在第一步
1. 若發生兩次以上jump，那直接從起點跳到最後被jump的點一定更短
2. 若jump不發生在第一步，則一定是先hop一些個點再jump到最後點，那這直接jump到最後點就好
因此就能說明4種移動方式：
1. 從$x$ hop到$y$：這能用倍增表處理
2. 從$x$ jump到$y$：答案是$t_y+1$
3. 從$x$ jump到$mid(mid<y)$，再從$mid$ hop到$y$：記前綴min
4. 從$x$ jump到$mid(mid>y)$，再從$mid$ hop到$y$：維護一個線段樹記從某點並jump過一次最後到$i$的最短距離，因此線段樹初始值都是$t_i+1$。點從大到小枚舉，並拿到$i$的距離+1更新所有$i$能hop到的所有小於$i$點，查詢時直接單點詢問到$y$的距離就好。這裡可能會有個疑惑，若這個最短路徑jump後的點<x的話是合理的，但如果是>x的時候會發生什麼是?因為這種路徑一定會被第1種移動方式判掉，所以這不用特別做處理
:::spoiler 實作
```cpp=
#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#define ORENOOSHIKYOUMOKAWAIII ios::sync_with_stdio(false), cin.tie(0);
typedef pair<int, int> pii;
#define F first
#define S second
/*
1 <- 2 <- 3 <- 4 <- ... <- n-1 <- n
case x < y: ans=1
case x > y:
define hop : move which cost 1
define jump: move left which cost t
1. hop x -> y: sparse table
2. jump x -> y: cost ty+1
3. jump x -> mid(mid<y), hop mid -> y: use prefix min to find mid
4. jump x -> mid(mid>y), hop mid -> y: offline query + segment tree
*/
const int N=1e5+10, INF=2e9+3;
int sp[20][N];
int r[N], t[N], ans[N], pre[N];
int seg[N<<2], tag[N<<2];
void build(int v, int l, int r){
tag[v]=INF;
if (l==r){
seg[v]=t[l]+1;
return;
}
int m=l+r>>1;
build(v<<1, l, m);
build(v<<1|1, m+1, r);
seg[v]=max(seg[v<<1], seg[v<<1|1]);
}
void update(int v, int k){
seg[v]=min(seg[v], k);
tag[v]=min(tag[v], k);
}
void push(int v){
update(v<<1, tag[v]);
update(v<<1|1, tag[v]);
tag[v]=INF;
}
void modify(int v, int l, int r, int ql, int qr, int k){
if (ql>qr) return;
if (ql<=l&&r<=qr){
update(v, k);
return;
}
int m=l+r>>1;
push(v);
if (ql<=m) modify(v<<1, l, m, ql, qr, k);
if (qr>m) modify(v<<1|1, m+1, r, ql, qr, k);
seg[v]=min(seg[v<<1], seg[v<<1|1]);
}
int query(int v, int l, int r, int x){
if (l==x&&r==x) return seg[v];
int m=l+r>>1;
push(v);
if (x<=m) return query(v<<1, l, m, x);
return query(v<<1|1, m+1, r, x);
}
int main(){
ORENOOSHIKYOUMOKAWAIII;
int n, q, m;
cin >> n >> q >> m;
for(int i=1;i<=n;i++) cin >> r[i];
for(int i=1;i<=n;i++) cin >> t[i];
pre[0]=INF;
for(int i=1;i<=n;i++) pre[i]=min(t[i]+1, pre[i-1]);
for(int i=1;i<=n;i++) sp[0][i]=lower_bound(r+1, r+i+1, r[i]-m)-r;
for(int j=1;j<20;j++) for(int i=1;i<=n;i++) sp[j][i]=sp[j-1][sp[j-1][i]];
vector<tuple<int, int, int>> qry(q);
for(int i=0;i<q;i++){
auto &[ed, st, idx]=qry[i];
cin >> st >> ed;
idx=i;
ans[i]=INF;
if (st<ed) ans[i]=1;
else{
ans[i]=min(t[ed]+1, pre[ed-1]+1);
int x=st, cnt=0;
for(int j=19;~j;--j){
if (sp[j][x]>ed){
cnt+=(1<<j);
x=sp[j][x];
}
}
if (sp[0][x]<=ed) ans[i]=min(ans[i], cnt+1);
}
}
sort(qry.begin(), qry.end(), greater<tuple<int, int, int>>());
int j=0;
build(1, 1, n);
for(int i=n;i;--i){
int tmp=query(1, 1, n, i);
modify(1, 1, n, sp[0][i], i-1, tmp+1);
while(j<q){
auto [ed, st, idx]=qry[j];
if (ed!=i) break;
if (st>ed) ans[idx]=min(ans[idx], query(1, 1, n, ed));
j++;
}
}
for(int i=0;i<q;i++) cout << ans[i] << '\n';
}
```
:::
### J. Jungle Job
---
#### 題目摘要
給一棵樹，第$i$天有$i$隻猴子，並猴子只會在一個節點上，問每天猴子都相鄰的方法數
#### 想法
建$dp_{i,\ j}$為$j$隻猴子在$i$的子樹相鄰且$i$上有猴子的方法數，並且記每個數最多能容納多少猴子。對於節點$i$，先枚舉子節點，再枚舉節點$i$要有幾隻猴子，最後再枚舉目前子樹要放多少猴子去轉移，這樣就能求到$i$的子樹中放$j$隻猴子的方法數，但因為dp要求節點$i$一定要有猴子，所以算完的答案要右移1格。這樣複雜度雖然看起來是$O(n^3)$，但只要把枚舉節點$i$需要多少猴子從跑$n$變成跑目前最大能有多少猴子，複雜度就會降到$O(n^2)$
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
const int N=1005, mod=1e9+7;
int sz[N];
ll dp[N][N], tmp[N][N];
vector<int> v[N];
void dfs(int x){
sz[x]=1;
dp[x][0]=1LL;
for(auto e:v[x]){
dfs(e);
sz[x]+=sz[e];
for(int i=sz[x];~i;--i){
for(int j=1;j<=sz[e];j++){
if (i<j) break;
dp[x][i]+=dp[x][i-j]*dp[e][j]%mod;
dp[x][i]%=mod;
}
}
}
for(int i=sz[x];~i;--i){
dp[x][i]=dp[x][i-1];
}
dp[x][0]=1LL;
}
void solve() {
int n;
cin >> n;
for(int i=1;i<n;i++){
int p;
cin >> p;
v[p].push_back(i);
}
dfs(0);
for(int i=1;i<=n;i++){
ll ans=0;
for(int j=0;j<n;j++) ans=(ans+dp[j][i])%mod;
cout << ans << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### K. King of the Hill
---
#### 題目摘要
互動題，給一張$n\times n$的圖，保證這張圖只有一個點比四周的點都高，且每個高度都不同，每次可以詢問一個點的高度，在$10\,n + 100$次內找到最高點
#### 想法
維護目前的最佳答案以及它的位置，做個十字的二分搜，每次對上下和左右各找一條中線，暴力把這個十字上的所有值都詢問過，再對最佳答案位置的上下左右都詢問一格，若最佳答案剛好在十字上就直接輸出，否則比較目前的左右上下界與最佳答案位置的關係縮界，最後那一個點就是答案，大概只會詢問$2n + n + \frac{n}{2} + \cdots = 4n$次
可行的原因是沿著上下左右最大的那個點一直走一條路徑一定能找到答案，畫個十字上的最大值，若他是目前最佳答案且不是最高的點，代表他答案在附近兩格的其中一塊(十字上的高度都更小被困住所以不會出去)，找到哪塊更大就能繼續做下去了。
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pll pair<ll, ll>
#define F first
#define S second
#define pii pair<int, int>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
int ans = 0, n, cnt = 0, px = -1, py = -1;
map<pii, int> mp;
void ask(int x, int y) {
if (x < 1 || y < 1 || x > n || y > n) return;
if (mp[{x, y}]) return;
cnt++;
assert(cnt <= 10 * n + 100);
cout << "? " << x << ' ' << y << endl;
int v; cin >> v;
mp[{x, y}] = v;
if (ans < v) {
ans = v;
px = x, py = y;
}
}
void out() {
cout << "! " << ans << endl;
exit(0);
}
void solve() {
cin >> n;
auto dc = [&](auto self, int l, int r, int x, int y) -> void {
if (l < 0 || l > r || x < 0 || x > y || r > n || y > n) return;
int mid = l + r >> 1, mid2 = x + y >> 1;
rep (i, x, y + 1) ask(mid, i);
rep (i, l, r + 1) ask(i, mid2);
int cx = px, cy = py;
rep (i, cx - 1, cx + 2) rep (j, cy - 1, cy + 2) ask(i, j);
if (mid == px || mid2 == py) return;
if (px < mid) r = mid - 1;
else l = mid + 1;
if (py < mid2) y = mid2 - 1;
else x = mid2 + 1;
self(self, l, r, x, y);
};
dc(dc, 1, n, 1, n);
out();
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
### L. Locking Doors
---
#### 題目摘要
給你$n$個房間$m$個門，兩個房間只能從其中一邊關門，問你最少需要開幾個向外連通的緊急逃生口，使你可以關掉所有的門，並且最後走出來。
#### 想法
可以知道$a,b$之間的門如果要從$a$關，那麼代表你要從b走到a，所以可以建立$b$到$a$的有向邊，因為入口可以跟出口共用，所以只要找要蓋出口的地方，也就是你有幾個地方關完門沒地方走，因為環一定可以鎖完以後走出去，所以做SCC後數出度為0的點，跟1取max
:::spoiler 實作
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> adj(n);
rep (i, 0, m) {
int a, b; cin >> a >> b;
a--, b--;
adj[b].pb(a);
}
int cnt = 0, id = 0;
vector<int> dfn(n, 0), low(n, 0), scc(n, 0);
vector<bool> inst(n, 0);
stack<int> st;
auto dfs = [&](auto self, int u) -> void {
st.push(u);
inst[u] = 1;
dfn[u] = low[u] = ++cnt;
for (int v : adj[u]) {
if (!inst[v] && dfn[v]) continue;
if (!dfn[v]) self(self, v);
low[u] = min(low[u], low[v]);
}
if (low[u] == dfn[u]) {
while (st.top() != u) {
inst[st.top()] = 0;
scc[st.top()] = id;
st.pop();
}
scc[u] = id;
inst[u] = 0;
st.pop();
id++;
}
};
rep (i, 0, n) if (!dfn[i]) dfs(dfs, i);
vector<int> out(id, 0);
// cout << id << '\n';
rep (i, 0, n) for (int v : adj[i]) {
if (scc[v] != scc[i]) {
out[scc[i]]++;
}
}
int ans = 0;
rep (i, 0, id) if (out[i] == 0) {
ans++;
}
if (ans == 0) ans++;
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
solve();
}
```
:::
Sign in with Wallet
Connect another wallet