Nội dung Bài tập
- Mã:
- AND
- Tên:
- Phép AND trên đồ thị
- Dạng thi:
- oi
- Thang điểm:
- 7 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- VNOI Online 2018
- Được tạo bởi:
- phuc
Cho một đồ thị gồm N đỉnh, đỉnh thứ i được gán nhãn Ai . Hai đỉnh i và j có cạnh nối đến nhau khi và chỉ khi ( Ai AND Aj ) > 0 ("AND" là toán tử trên bit, tham khảo phần "Chú ý" bên dưới để hiểu rõ hơn). Thực hiện Q truy vấn thuộc một trong hai loại:
● Thay đổi nhãn của một đỉnh;● Đếm số thành phần liên thông của đồ thị.
Các số A i trước và sau mỗi truy vấn đều nằm trong đoạn [0; 109 ].
Dữ liệu
● Dòng đầu chứa số nguyên dương N , là số đỉnh của đồ thị (1 ≤ N ≤ 100000);● Dòng thứ hai chứa N số nguyên không âm A1 , A2 , …, AN , là nhãn ban đầu của các đỉnh (0 ≤ Ai ≤ 109 );● Dòng thứ ba chứa số nguyên dương Q , là số truy vấn cần thực hiện (1 ≤ Q ≤ 100000);● Q dòng tiếp theo, mỗi dòng có một trong hai dạng:
"! x y": Thay đổi nhãn của đỉnh x thành y , nói cách khác, gán Ax = y (1 ≤ x ≤ N, 0 ≤ y ≤ 109);"?": In ra số thành phần liên thông của đồ thị hiện tại.
Kết quả
● Với mỗi truy vấn dạng "?" , in ra một dòng chứa số nguyên là số thành phần liên thông của đồ thị tại thời điểm được hỏi.
Ví dụ:
AND.INP AND.OUT
Chấm điểm
● Subtask 1 (30% số điểm): N , Q ≤ 300;● Subtask 2 (70% số điểm): Không có ràng buộc gì thêm.
Chú ý
Cho x và y là hai bit (hai số nguyên chỉ mang giá trị 0 hoặc 1). Giá trị của biểu thức x AND y được tính dựa vào bảng sau:
Cho x và y là hai dãy bit có độ dài bằng nhau. Biểu thức x AND y là một dãy bit được tính bằng cách áp dụng toán tử AND đối với mỗi cặp bit tương ứng của x và y .
Ví dụ: 01012 AND 00112 = 00012 .
Cho x và y là hai số nguyên không âm. Biểu thức x AND y là một số nguyên không âm được tính bằng cách thực hiện toán tử AND đối với biểu diễn nhị phân của x và biểu diễn nhị phân của y , sau đó biến đổi dãy bit kết quả thành số nguyên không âm tương ứng.
Ví dụ: 5 AND 3 = 1.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận