Nhà Từ Thiện Swyrin
Đề bài
TUTHIEN – Nhà từ thiện Swyrin
Swyrin đang trên con đường trở thành một coder. Chị ấy code từ sáng đến trưa, trưa đến chiều, chiều đến tối. Code mãi nhưng không kiếm ra nổi đồng nào nên "bần cùng sinh đạo tặc", tiện là đang thấy mùa lũ nên là chị ấy nghĩ ra cách là khều từ thiện và dùng số tiền đó cho bản thân.
Swyrin kiểm tra trên bản đồ lũ và thấy 1 làng đang đứng trước nguy cơ bị lũ cuốn trôi. Nhận thấy rằng trên con đường lũ đến người dân đang xây 1 con đập để ngăn lũ, mà lại dùng đồ xịn nên chả ngán con lũ nào. Lo sợ rằng "cần câu cơm" của mình sẽ bốc hơi, Swyrin muốn nhờ các Luyencoder xem là chị ấy có thể xin từ thiện tại làng này được không.
Swyrin thấy rằng con đường lũ đến có thể được đơn giản hóa thành 1 ma trận 2 hàng, $N$ cột. Người dân có thể đóng 1 cột ở ngay ô chưa được đóng, hoặc là có thể nhổ (không phá vì làng nghèo) cột đã được đóng để tiết kiệm ngân sách. Lũ sẽ bắt đầu chảy từ ô $(1, 1)$ và ngôi làng nằm ở ô $(2, N)$. Swyrin chỉ có thể có cớ khều tiền từ thiện nếu lũ có thể chảy từ ô $(1, 1)$ đến ô $(2, N)$ mà không bị cản bởi các cọc.
Vì có người tình báo siêu việt nên Swyrin đã có được 1 danh sách gồm $Q$ kế hoạch xây dựng và cô ấy muốn bạn biết rằng cô ấy có thể kiếm được tiền từ thiện ở ngôi làng đó hay không? Hãy giúp Swyrin nào, các luyencoder ơi :D
Dữ liệu vào:
- $N$: hiểu nó là chiều rộng đường đi cũng được.
- $Q$: số kế hoạch xây dựng.
- $Q$ dòng tiếp theo: gồm 2 số $(y, x)$ biểu thị vị trí (hàng – cột) của cột sắp đóng/bị nhổ.
- Nếu ở ô $(y, x)$ chưa được đóng, thì ô đó sẽ bị đóng, và ngược lại.
- Ràng buộc: $1 \le N$ $\le 100.000;\ 1$ $\le Q$ $\le 100;\ 1$ $\le y$ $\le 2;\ 1$ $\le x$ $\le N$.
- Dữ kiện cho sẽ không nằm ở ô $(1, 1)$ và $(2, N)$.
- Format:
N Q y1 x1 y2 x2 ...
Dữ liệu ra: Gồm $Q$ dòng, mỗi dòng ghi YES nếu có thể lập quỹ từ thiện, NO nếu ngược lại.
9 5
2 1
1 2
2 1
2 2
2 3YES
NO
YES
NO
NOBan đầu có bản đồ như sau (F là vị trí của lũ, V là vị trí ngôi làng):
| F | · | · | · | · | · | · | · | · |
| · | · | · | · | · | · | · | · | V |
Kế hoạch đầu tiên – đóng cọc ở ô $(2, 1)$:
| F | · | · | · | · | · | · | · | · |
| x | · | · | · | · | · | · | · | V |
Hiển nhiên có thể thấy là lũ có thể tự do chảy đến làng, nên kết quả là Swyrin có thể lấy lý do khều từ thiện được, nên kết quả là "YES".
Kế hoạch thứ hai – đóng cọc ở ô $(1, 2)$:
| F | x | · | · | · | · | · | · | · |
| x | · | · | · | · | · | · | · | V |
Giờ có thể thấy là lũ không thể chảy đến làng, nên là Swyrin không thể lấy cớ xin tiền, nên kết quả là "NO".
Kế hoạch thứ ba – nhổ cọc ở ô $(2, 1)$:
| F | x | · | · | · | · | · | · | · |
| · | · | · | · | · | · | · | · | V |
Giờ có thể thấy là lũ có thể tự do chảy đến làng, nên kết quả là Swyrin có thể lấy lý do khều từ thiện được, nên kết quả là "YES".
Tương tự như thế, 2 kế hoạch cuối là "NO" theo 2 ví dụ ở dưới.
Kế hoạch thứ 4:
| F | x | · | · | · | · | · | · | · |
| · | x | · | · | · | · | · | · | V |
Kế hoạch thứ 5:
| F | x | · | · | · | · | · | · | · |
| · | x | x | · | · | · | · | · | V |
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Mình sẽ đi từ cách "thật thà" là BFS lại mỗi lần (ăn subtask 1), rồi tới cách đếm số cặp cọc chặn nước để ăn trọn điểm nhé.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1N ≤ 10⁵, Q ≤ 100: BFS lại sau mỗi kế hoạch
Ta có thể giải quyết như sau: với mỗi kế hoạch trong $Q$ kế hoạch, ta cập nhật ô $(y, x)$ (đang trống '.' thì đóng cọc thành 'x', đang có cọc thì nhổ về '.'), rồi duyệt BFS trên mảng $2 \times N$ xuất phát từ ô $(1, 1)$, đi sang 4 ô kề (trái, phải, trên, dưới) không có cọc, để tìm xem có đường đi từ $(1, 1)$ đến $(2, N)$ hay không.
Như thế độ phức tạp sẽ là $O(Q \cdot 2 \cdot N)$, thì với $N$ tối đa $10^5$, $Q$ tối đa $100$ thì $Q \cdot 2 \cdot N = 100 \cdot 2 \cdot 10^5 = 2 \cdot 10^7$ (20 triệu) thì vẫn đảm bảo chạy trong 1 giây với C++.
Code Subtask 1 – BFS lại sau mỗi kế hoạch, O(Q·N)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, q, y, x;
cin >> n >> q;
vector<vector<char>> a(3, vector<char>(n + 1, '.'));
while(q--){
cin >> y >> x;
if(a[y][x] == '.'){
a[y][x] = 'x';
}
else{
a[y][x] = '.';
}
vector<vector<bool>> check(3, vector<bool>(n + 1, false));
queue<pair<int, int>> q;
// first: y (dong), second: x (cot)
q.push({1, 1});
check[1][1] = true;
bool flag = false;
while(!q.empty()){
pair<int, int> pr = q.front();
q.pop();
if(pr.first == 2 && pr.second == n){
flag = true;
break;
}
if(pr.second - 1 >= 1 && a[pr.first][pr.second - 1] == '.' && check[pr.first][pr.second - 1] == false){
q.push({pr.first, pr.second - 1});
check[pr.first][pr.second - 1] = true;
}
if(pr.second + 1 <= n && a[pr.first][pr.second + 1] == '.' && check[pr.first][pr.second + 1] == false){
q.push({pr.first, pr.second + 1});
check[pr.first][pr.second + 1] = true;
}
if(pr.first - 1 >= 1 && a[pr.first - 1][pr.second] == '.' && check[pr.first - 1][pr.second] == false){
q.push({pr.first - 1, pr.second});
check[pr.first - 1][pr.second] = true;
}
if(pr.first + 1 <= 2 && a[pr.first + 1][pr.second] == '.' && check[pr.first + 1][pr.second] == false){
q.push({pr.first + 1, pr.second});
check[pr.first + 1][pr.second] = true;
}
}
if(flag == true){
cout << "YES\n";
}
else{
cout << "NO\n";
}
}
return 0;
}import sys
from collections import deque
input = sys.stdin.readline
n, q = map(int, input().split())
a = [['.'] * (n + 1) for _ in range(3)]
for _ in range(q):
y, x = map(int, input().split())
a[y][x] = '.' if a[y][x] == 'x' else 'x'
check = [[False] * (n + 1) for _ in range(3)]
dq = deque()
dq.append((1, 1))
check[1][1] = True
flag = False
while dq:
yy, xx = dq.popleft()
if yy == 2 and xx == n:
flag = True
break
if xx - 1 >= 1 and a[yy][xx - 1] == '.' and not check[yy][xx - 1]:
dq.append((yy, xx - 1))
check[yy][xx - 1] = True
if xx + 1 <= n and a[yy][xx + 1] == '.' and not check[yy][xx + 1]:
dq.append((yy, xx + 1))
check[yy][xx + 1] = True
if yy - 1 >= 1 and a[yy - 1][xx] == '.' and not check[yy - 1][xx]:
dq.append((yy - 1, xx))
check[yy - 1][xx] = True
if yy + 1 <= 2 and a[yy + 1][xx] == '.' and not check[yy + 1][xx]:
dq.append((yy + 1, xx))
check[yy + 1][xx] = True
if flag:
print("YES")
else:
print("NO")Tuy code C++ được 50/100 nhưng code Python chỉ được 45/100, không lấy trọn điểm của subtask 1 được, lý do là Python chạy chậm hơn C++.
100%Q, N ≤ 8 · 10⁵: đếm số cặp cọc chặn nước
Với Subtask 2 khi mà $N, Q$ tối đa $8 \cdot 10^5$ thì cách làm ở trên có độ phức tạp $O(Q \cdot 2 \cdot N)$ $= 8 \cdot 10^5 \cdot 2 \cdot 8 \cdot 10^5$ $= 128 \cdot 10^{10}$ (1280 tỷ) thì đã vượt quá giới hạn 100 triệu của 1 giây với C++ rồi nên chắc chắn sẽ bị TLE. Ta cần có cách tốt hơn.
Khi nào lũ bị chặn?
Bản đồ chỉ có 2 hàng, nên lũ muốn đi từ trái sang phải thì chỉ bị chặn khi có 1 cọc ở hàng trên và 1 cọc ở hàng dưới "chạm" nhau: cùng cột (chặn dọc) hoặc lệch nhau đúng 1 cột (chặn chéo). Nếu 2 cọc ở 2 hàng cách nhau từ 2 cột trở lên thì lũ vẫn len qua được khoảng trống ở giữa.
| F | x | · | · | · | · | · | · | · |
| x | · | · | · | · | · | · | · | V |
| F | · | · | · | x | · | · | · | · |
| · | · | · | · | x | · | · | · | V |
| F | · | · | x | · | · | · | · | · |
| · | · | · | · | · | x | · | · | V |
cnt (trong lời giải mình gọi là res) là số cặp cọc $(1, x_1)$ – $(2, x_2)$ với $|x_1 - x_2| \le 1$, tức là số "điểm" có thể chặn được nước. Lũ đến được làng khi và chỉ khi cnt = 0.Cứ mỗi vị trí $y, x$ truyền vào, kiểm tra nếu tại đó chưa có cọc thì nghĩa là giờ sẽ đặt cọc xuống hen. Khi đã đặt cọc xuống dòng $y$, cột $x$ thì ta sẽ kiểm tra dòng còn lại: nếu $y$ hiện tại là dòng 1 thì dòng còn lại là dòng 2, nếu $y$ hiện tại là dòng 2 thì dòng còn lại là dòng 1.
Ta sẽ kiểm tra dòng còn lại tại các vị trí $x - 1, x, x + 1$, là những vị trí tiếp giáp với vị trí dòng $y$, cột $x$ mà có thể ngăn nước. Vị trí nào mà đang có cọc thì lúc này cnt++ (thêm 1 cặp chặn nước).
Thì tương tự ngược lại như trên, nếu trong trường hợp dòng $y$ cột $x$ truyền vào tại đó đang có cọc, nghĩa là ta sẽ huỷ cọc đó, thì kiểm tra dòng còn lại tại các vị trí $x - 1, x, x + 1$, chỗ nào mà có cọc nghĩa là tụi nó đang đóng vai trò chặn nước cùng cọc này, giờ huỷ cọc tại dòng $y$ cột $x$ đi thì cứ thế cnt-- với mỗi trường hợp đó.
Sau cùng kiểm tra nếu cnt bằng 0 thì in ra YES, khác 0 in ra NO. Biến cnt ở đây hiểu là biến lưu số lượng vị trí điểm mà ta có thể chặn không cho nước chảy đến làng. Nên nếu cnt = 0 tức là chẳng có điểm nào chặn nước cả ⇒ làng sẽ bị lũ đến ⇒ YES. Còn nếu cnt khác 0 tức là có điểm để chặn nước ⇒ làng sẽ không bị lũ đến ⇒ NO.
Em nhập $N$ và các kế hoạch rồi bấm Tiếp để xem cnt thay đổi thế nào sau mỗi kế hoạch:
Mỗi kế hoạch chỉ kiểm tra đúng 3 ô nên độ phức tạp là $O(1)$ cho mỗi kế hoạch, tổng cộng $O(N + Q)$ (tạo mảng + xử lý $Q$ kế hoạch).
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, q, y, x, y2, x2, cnt = 0;
cin >> n >> q;
vector<vector<char>> a(3, vector<char>(n + 1, '.'));
int dx[] = {-1, 0, 1};
while(q--){
cin >> y >> x;
y2 = 1;
if(y == 1){
y2 = 2;
}
x2 = x;
if(a[y][x] == '.'){
a[y][x] = 'x';
for(int i = 0; i < 3; ++i){
x2 = x + dx[i];
if(1 <= x2 && x2 <= n && a[y2][x2] == 'x'){
cnt++;
}
}
}
else{
a[y][x] = '.';
for(int i = 0; i < 3; ++i){
x2 = x + dx[i];
if(1 <= x2 && x2 <= n && a[y2][x2] == 'x'){
cnt--;
}
}
}
if(cnt != 0){
cout << "NO\n";
}
else{
cout << "YES\n";
}
}
return 0;
}import sys
input = sys.stdin.readline
n, q = map(int, input().split())
a = [['.'] * (n + 1) for _ in range(3)]
dx = [-1, 0, 1]
cnt = 0
for _ in range(q):
y, x = map(int, input().split())
y2 = 2 if y == 1 else 1
if a[y][x] == '.':
a[y][x] = 'x'
for d in dx:
x2 = x + d
if 1 <= x2 <= n and a[y2][x2] == 'x':
cnt += 1
else:
a[y][x] = '.'
for d in dx:
x2 = x + d
if 1 <= x2 <= n and a[y2][x2] == 'x':
cnt -= 1
if cnt != 0:
print("NO")
else:
print("YES")
Nhận xét
Đăng nhận xét