大家好！我是小码匠。
今天分享的题目是AtCoder ABC326的D题。
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成：5道
- 待完成：295道
已完成题目：
分类 | 算法 | 题目 |
|---|---|---|
算法基础 | 前缀和 | 【第001题】题解分享：湖南省选->激光炸弹 |
算法基础 | 差分 | 【第002题】题解分享：P4552 [Poetize6] IncDec Sequence |
算法基础 | 高维前缀和 | 【第003题】题解及代码分享：CodeForces 165E Compatible Numbers |
算法基础 | 尺取 | 【第004题】题解及代码分享：AtCoder ARC100E Or Plus Max |
AtCoder | DP | 【第005题】题解及代码分享：AtCoder ABC326-D |
前置知识
- 模拟
- DFS
题目描述
题目链接
- 题目地址：https://atcoder.jp/contests/abc326/tasks/abc326_d
- 题解地址：https://atcoder.jp/contests/abc326/editorial/326
正解
思路
就是一个搜索，4ms的时限还怕什么，更别说n还这么小，这个题给我感觉有点像数独那道题（洛谷可搜），然后再多开数组维护是否满足题目所要求的第一个字符对应就行
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
int a[6], b[6], n;
char str[7] = {'.', 'A', 'B', 'C', '.', '.', '.'};
bool r[7][7];
bool c[7][7];
int k[7][7];
string row, col;
void dfs(int x, int y) {
if (k[x][y] != 0) {
if (x == n && y == n) {
cout << "Yes" << endl;
for (int i = 1; i <= n; i) {
for (int j = 1; j <= n; j) {
cout << str[k[i][j]];
}
cout << endl;
}
exit(0);
}
if (y == n) {
dfs(x 1, 1);
} else {
dfs(x, y 1);
}
} else{
for (int i = 1; i <= n; i) {
if (r[x][i] || c[y][i] || (a[x] == 0 && i < 4 && str[i] != row[x - 1]) || (b[y] == 0 && i < 4 && str[i] != col[y - 1])) {
continue;
}
r[x][i] = true;
c[y][i] = true;
k[x][y] = i;
if (a[x] == 0 && i < 4) {
a[x] = i;
}
if (b[y] == 0 && i < 4) {
b[y] = i;
}
if (x == n && y == n) {
cout << "Yes" << endl;
for (int s = 1; s <= n; s) {
for (int j = 1; j <= n; j) {
cout << str[k[s][j]];
}
cout << endl;
}
exit(0);
}
if (y == n) {
dfs(x 1, 1);
} else {
dfs(x, y 1);
}
r[x][i] = false;
c[y][i] = false;
if (a[x] == k[x][y]) {
a[x] = 0;
}
if (b[y] == k[x][y]) {
b[y] = 0;
}
k[x][y] = 0;
}
}
}
void best_coder() {
cin >> n;
cin >> row >> col;
dfs(1, 1);
cout << "No";
for (int i = 1; i <= 5; i) {
a[i] = 0;
b[i] = 0;
for (int j = 1; j <= 5; j) {
r[i][j] = false;
c[i][j] = false;
k[i][j] = 0;
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
参考代码
代码语言：javascript复制#include <bits/stdc .h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::string R, C;
std::cin >> N >> R >> C;
int tot = 0;
std::vector<int> row(N), col(N);
std::vector ans(N, std::string(N, '.'));
auto dfs = [&](auto self, int x, int y) {
if (x == N) {
if (tot == 3 * N) {
std::cout << "Yesn";
for (int i = 0; i < N; i ) {
std::cout << ans[i] << "n";
}
std::exit(0);
}
return;
}
if (y == N) {
return self(self, x 1, 0);
}
self(self, x, y 1);
for (int i = 0; i < 3; i ) {
if (row[x] == 0 && i 'A' != R[x]) {
continue;
}
if (col[y] == 0 && i 'A' != C[y]) {
continue;
}
if (row[x] >> i & 1) {
continue;
}
if (col[y] >> i & 1) {
continue;
}
ans[x][y] = 'A' i;
row[x] ^= 1 << i;
col[y] ^= 1 << i;
tot = 1;
self(self, x, y 1);
ans[x][y] = '.';
row[x] ^= 1 << i;
col[y] ^= 1 << i;
tot -= 1;
}
};
dfs(dfs, 0, 0);
std::cout << "Non";
return 0;
}
