Hướng dẫn cho PVHOI3 - Bài 2: Trang trí ngày xuân
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask 1: \(r\times c \leq 21\)
Tutorial
Vì số lượng ô bé, ta có thể duyệt qua tất cả các cách đặt hoa.
ĐPT: \(O(2^{r\times c}\times r \times c)\)
Solution
C++
#include <bits/stdc++.h>
#define Bit(x, y) bool(x & (1 << y));
#define Mask(x) (1 << (x))
using namespace std;
const int N = 69;
int numRow, numCol, div3[N], a[N][N], res[N][N];
int dx[] = {1, 1, 2, 2};
int dy[] = {-2, 2, -1, 1};
void Update(int a[][N]) {
for (int i = 0; i < numRow; i++) {
int sum = 0;
for (int j = 0; j < numCol; j++) {
if (a[i][j]) {
sum++;
bool flag = true;
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < 0 || x >= numRow || y < 0 || y >= numCol) continue;
if (a[x][y]) {
flag = false;
break;
}
}
if (!flag) return;
}
}
if (div3[i] < 3 && sum % 3 != div3[i]) return;
}
for (int i = 0; i < numRow; i++) {
for (int j = 0; j < numCol; j++) {
if (a[i][j]) res[i][j]++;
}
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
freopen("TETQUYMAO.inp", "r", stdin);
freopen("TETQUYMAO.out", "w", stdout);
cin >> numRow >> numCol;
for (int i = 0; i < numRow; i++) {
cin >> div3[i];
}
for (int mask = 0; mask < Mask(numRow * numCol); mask++) {
for (int i = 0; i < numRow; i++) {
for (int j = 0; j < numCol; j++) {
int id = i * numCol + j;
a[i][j] = Bit(mask, id);
}
}
Update(a);
}
for (int i = 0; i < numRow; i++) {
for (int j = 0; j < numCol; j++) {
cout << res[i][j] << " ";
}
cout << "\n";
}
}
Subtask 2: \(c = 1\)
Tutorial
Khi khu vườn chỉ có \(1\) cột, ta có thể bỏ qua ràng buộc hai ô thể hiện nước đi hợp lệ của quân mã không được trồng hoa. Nếu có ít nhất một giá trị \(i\) mà \(a_i=2\) thì kết quả của tất cả các ô sẽ là \(0\). Ngược lại, gọi số lượng \(i\) mà \(a_i=3\) là \(cnt\), khi đó kết quả ở ô \((i,1)\) sẽ là:
- \(0\) nếu \(a_i=0\)
- \(2^{cnt}\) nếu \(a_i=1\)
- \(2^{cnt-1}\) nếu \(a_i=3\)
ĐPT: \(O(r)\)
Solution
C++
#include <bits/stdc++.h>
#define Bit(x, y) bool(x & (1 << y));
#define Mask(x) (1 << (x))
using namespace std;
const int N = 69;
const int M = (int)1e9 + 19972207;
void add(int &x, int y) {
x += y;
if (x >= M) x -= M;
}
int power(int x, int y) {
int res = 1;
for (int i = 1; i <= y; i++) {
res = 1LL * res * x % M;
}
return res;
}
int numRow, numCol, three[N], dp[N];
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
freopen("TETQUYMAO.inp", "r", stdin);
freopen("TETQUYMAO.out", "w", stdout);
cin >> numRow >> numCol;
for (int i = 0; i < numRow; i++) {
cin >> three[i];
if (three[i] == 2) {
for (int i = 0; i < numRow; i++) {
cout << "0\n";
}
return 0;
}
}
int cntThree = 0;
for (int i = 0; i < numRow; i++) {
if (three[i] == 3) cntThree++;
}
for (int i = 0; i < numRow; i++) {
if (three[i] == 0) {
cout << "0\n";
} else {
cout << power(2, cntThree - (three[i] == 3)) << "\n";
}
}
}
Subtask 3,4,5: \(r\leq 6\)
Tutorial
Gọi \(F(i, pre, cur)\) là số cách đặt hoa từ hàng \(1\) tới hàng \(i\) sao cho trạng thái ở hàng \(i\) là \(cur\) và trạng thái ở hàng \(i-1\) là \(pre\). Với mỗi bộ \((i, pre, cur)\), ta cần duyệt qua các \(nxt\) là trạng thái đặt hoa cho hàng \(i+1\) và cập nhật \(F(i+1, cur, nxt)\).
Gọi \(G(i, nxt, cur)\) là số cách đặt hoa từ hàng \(i\) tới hàng \(r\) sao cho trạng thái ở hàng \(i\) là \(cur\) và trạng thái ở hàng \(i+1\) là \(nxt\). Ta có thể tính \(G\) tương tự như tính \(F\).
Để tính kết quả của mỗi ô, ta duyệt qua từng hàng \(i\). Ở mỗi hàng \(i\), ta duyệt qua tất cả các cặp \((pre, cur)\) hợp lệ. Khi đó, các ô ở hàng \(i\) được đặt hoa ở trạng thái \(cur\) sẽ được cộng thêm \(F(i, pre, cur) \times G(i-1, cur, pre)\).
ĐPT: \(O(r\times 2^{3\times c})\)
Solution
C++
#include <bits/stdc++.h>
#define Bit(x, y) bool(x & (1 << y))
#define Mask(x) (1 << (x))
using namespace std;
const int N = 69;
const int M = (int)1e9 + 19972207;
void add(int &x, int y) {
x += y;
if (x >= M) x -= M;
}
int numRow, numCol, three[N], dpPref[N][1 << 10][1 << 10], dpSuff[N][1 << 10][1 << 10], res[N];
bool validOne[1 << 10][1 << 10], validTwo[1 << 10][1 << 10];
void CalcDp(int three[], int dp[][1 << 10][1 << 10]) {
for (int cur = 0; cur < Mask(numCol); cur++) {
if (three[0] < 3 && __builtin_popcount(cur) % 3 != three[0]) {
dp[0][0][cur] = 0;
} else {
dp[0][0][cur] = 1;
}
}
for (int i = 0; i < numRow - 1; i++) {
for (int pre = 0; pre < Mask(numCol); pre++) {
for (int cur = 0; cur < Mask(numCol); cur++) {
if (dp[i][pre][cur] == 0) continue;
for (int nxt = 0; nxt < Mask(numCol); nxt++) {
if (three[i + 1] < 3 && __builtin_popcount(nxt) % 3 != three[i + 1]) continue;
if (!validOne[cur][nxt] || !validTwo[pre][nxt]) continue;
add(dp[i + 1][cur][nxt], dp[i][pre][cur]);
}
}
}
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
freopen("TETQUYMAO.inp", "r", stdin);
freopen("TETQUYMAO.out", "w", stdout);
cin >> numRow >> numCol;
for (int i = 0; i < numRow; i++) {
cin >> three[i];
}
for (int pre = 0; pre < Mask(numCol); pre++) {
for (int cur = 0; cur < Mask(numCol); cur++) {
bool flag = true;
for (int j = 0; j < numCol; j++) {
if (Bit(cur, j)) {
if ((j >= 2 && Bit(pre, j - 2)) || (j < numCol - 2 && Bit(pre, j + 2))) {
flag = false;
break;
}
}
}
validOne[pre][cur] = flag;
}
for (int nxt = 0; nxt < Mask(numCol); nxt++) {
bool flag = true;
for (int j = 0; j < numCol; j++) {
if (Bit(nxt, j)) {
if ((j >= 1 && Bit(pre, j - 1)) || (j < numCol - 1 && Bit(pre, j + 1))) {
flag = false;
break;
}
}
}
validTwo[pre][nxt] = flag;
}
}
CalcDp(three, dpPref);
reverse(three, three + numRow);
CalcDp(three, dpSuff);
reverse(three, three + numRow);
reverse(dpSuff, dpSuff + numRow);
for (int i = 0; i < numRow; i++) {
for (int j = 0; j < numCol; j++) {
res[j] = 0;
}
for (int cur = 0; cur < Mask(numCol); cur++) {
int sum = 0;
if (three[i] < 3 && __builtin_popcount(cur) % 3 != three[i]) continue;
for (int pre = 0; pre < Mask(numCol); pre++) {
if (!validOne[pre][cur]) continue;
if (i >= 1) {
add(sum, 1LL * dpPref[i][pre][cur] * dpSuff[i - 1][cur][pre] % M);
} else {
add(sum, dpSuff[i][pre][cur]);
}
}
for (int j = 0; j < numCol; j++) {
if (Bit(cur, j)) {
add(res[j], sum);
}
}
}
for (int j = 0; j < numCol; j++) {
cout << res[j] << " ";
}
cout << "\n";
}
}
Subtask 6: \(c\leq 10\)
Tutoial
Ta sẽ cải tiến thuật toán của subtask 5. Tuy rằng có tổng cộng tối đa \(2^{20}\) cặp \((pre, cur)\) cần phải duyệt, tuy nhiên chỉ có \(28561\) cặp là hợp lệ. Do đó, ta có thể tiền xử lý để tìm ra \(28651\) cặp này trước. Ngoài ra, với mỗi cặp, ta cũng có danh sách các bit bị "khóa" ở \(nxt\). Do đó, khi duyệt qua các \(nxt\), ta chỉ cần duyệt qua các tập hợp con của tập hợp các bit không bị "khóa" ở \(nxt\).
Solution
C++
#include <bits/stdc++.h>
#define Bit(x, y) bool(x & (1 << y))
#define Mask(x) (1 << (x))
#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second
using namespace std;
const int N = 69;
const int M = (int)1e9 + 19972207;
void add(int &x, int y) {
x += y;
if (x >= M) x -= M;
}
int numRow, numCol, three[N], dpPref[N][1 << 10][1 << 10], dpSuff[N][1 << 10][1 << 10], res[N], numValidState = 0;
piii validState[30000];
bool valid[1 << 10][1 << 10];
void CalcDp(int three[], int dp[][1 << 10][1 << 10]) {
for (int cur = 0; cur < Mask(numCol); cur++) {
if (three[0] < 3 && __builtin_popcount(cur) % 3 != three[0]) {
dp[0][0][cur] = 0;
} else {
dp[0][0][cur] = 1;
}
}
int dem = 0;
for (int i = 0; i < numRow - 1; i++) {
for (int o = 0; o < numValidState; o++) {
int pre = validState[o].fi.fi, cur = validState[o].fi.se, mask = validState[o].se;
if (dp[i][pre][cur] == 0) continue;
for (int nxt = mask; ; nxt = (nxt - 1) & mask) {
if (three[i + 1] == 3 || __builtin_popcount(nxt) % 3 == three[i + 1]) {
add(dp[i + 1][cur][nxt], dp[i][pre][cur]);
}
if (!nxt) break;
}
}
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
freopen("TETQUYMAO.inp", "r", stdin);
freopen("TETQUYMAO.out", "w", stdout);
cin >> numRow >> numCol;
for (int i = 0; i < numRow; i++) {
cin >> three[i];
}
for (int pre = 0; pre < Mask(numCol); pre++) {
for (int cur = 0; cur < Mask(numCol); cur++) {
bool flag = true;
for (int j = 0; j < numCol; j++) {
if (Bit(cur, j)) {
if ((j >= 2 && Bit(pre, j - 2)) || (j < numCol - 2 && Bit(pre, j + 2))) {
flag = false;
break;
}
}
}
if (flag) {
int mask = 0;
for (int j = 0; j < numCol; j++) {
if (Bit(cur, j)) {
if (j >= 2) mask |= Mask(j - 2);
if (j < numCol - 2) mask |= Mask(j + 2);
}
if (Bit(pre, j)) {
if (j >= 1) mask |= Mask(j - 1);
if (j < numCol - 1) mask |= Mask(j + 1);
}
}
validState[numValidState++] = piii(pii(pre, cur), mask ^ (Mask(numCol) - 1));
valid[pre][cur] = true;
}
}
}
CalcDp(three, dpPref);
reverse(three, three + numRow);
CalcDp(three, dpSuff);
reverse(three, three + numRow);
reverse(dpSuff, dpSuff + numRow);
for (int i = 0; i < numRow; i++) {
for (int j = 0; j < numCol; j++) {
res[j] = 0;
}
for (int cur = 0; cur < Mask(numCol); cur++) {
int sum = 0;
if (three[i] < 3 && __builtin_popcount(cur) % 3 != three[i]) continue;
for (int pre = 0; pre < Mask(numCol); pre++) {
if (!valid[pre][cur]) continue;
if (i >= 1) {
add(sum, 1LL * dpPref[i][pre][cur] * dpSuff[i - 1][cur][pre] % M);
} else {
add(sum, dpSuff[i][pre][cur]);
}
}
for (int j = 0; j < numCol; j++) {
if (Bit(cur, j)) {
add(res[j], sum);
}
}
}
for (int j = 0; j < numCol; j++) {
cout << res[j] << " ";
}
cout << "\n";
}
}
Bình luận