昨晚 ARC A 题解
2026-02-09 12:58:28
发布于：广东
24阅读
0回复
0点赞
Difficulty：3- / Easy
Tag：构造
赛时：感觉挺难的样子啊。写了个 的 DP，WA 了不想调了。
睡前：不兑！
我怎么切不了橙了。
先讲构造方法。只需要构造右上 左下的数相同即可。如果这种方法构造不出来那就不可能实现。
证明：
首先如果想要 只有一个值，那 每一个格子的值都得确定。这很显然吧，赛时没想出来。
所以每个格不管往上或往左倒推， 前面那一格的值都得相等。所以一直这么推就能发现如果两个格子到 曼哈顿距离相等，那它们的值也得相等。
然后分层就能 构造了。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <std::string> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
a[i] = " " + a[i] + " ";
}
std::mt19937_64 rng(20260209);
for(int i = 2; i <= n * 2; i++){
int cur = -1;
for(int j = 1; j < i; j++){
if(j > n || i - j > n) continue;
if(a[j][i - j] == '?') continue;
if(cur != -1 && cur != a[j][i - j]){
std::cout << "-1\n";
return;
}
cur = a[j][i - j];
}
if(cur == -1) cur = rng() % 10 + '0';
for(int j = 1; j <= i; j++){
if(j > n || i - j > n) continue;
a[j][i - j] = cur;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
std::cout << a[i][j];
}
std::cout << '\n';
}
}
}
有帮助，赞一个