@codeforces - 1205C@ Palindromic Paths

素颜马尾好姑娘i 2023-06-01 13:59 262阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

**这是一道交互题。**

现在有一个 n\*n 的矩阵，每个位置是 0 或 1。现在已知 n 为奇数、左上角为 1、右下角为 0。

你可以向交互库给出询问 "? x1 y1 x2 y2"，交互库会回答是否存在一条路径从 (x1, y1) 出发仅往右或往下走到达 (x2, y2)，且路径上所有数拼起来形成回文串。如果存在为 1，否则为 0。  
请注意询问时必须保证 x1 <= x2, y1 <= y2 且 (x2 - x1) + (y2 - y1) > 1，即 (x1, y1) 在 (x2, y2) 的左上方，且它们不能相邻。

请使用不超过 n^2 组询问，还原出这个矩阵。

**Input**  
第一行包含一个奇数 n (3 <= n < 50)。

**Interaction**  
你可以按照格式 "? x1 y1 x2 y2" 给出询问，含义如上。

当你决定好了矩阵中的所有元素，请输出一行 "!"，紧接着输出你的矩阵。

**Example**  
**Input**  
3  
0  
1  
0  
1  
1  
1  
1  
**Output**  
? 1 1 1 3  
? 1 1 2 3  
? 2 1 2 3  
? 3 1 3 3  
? 2 2 3 3  
? 1 2 3 2  
? 1 2 3 3  
!  
100  
001  
000

## @solution@ ##

考虑一个长度为 3 的询问，实际上 是不是回文串 只跟 开头与末尾是否相同 有关。  
于是将矩阵黑白染色后，可以通过若干长度为 3 的询问得到黑格之间的相对关系，白格之间的相对关系。这个可以用带权并查集。  
因为是相对关系，所以 n^2 个点只询问 n^2 - 1 次询问，实际上因为已经给定左上与右下，所以实际还会少一点点。

我们假设左上角为黑格，则所有黑格的数字都已经可以确定。  
我们接下来就是尝试找到 1 个询问，使我们可以确定某个白格的数字，这样总询问次数也不会超过上界。

考虑一个 2\*3 的子矩形，询问左上角的 (x, y) 到右下角的 (x + 1, y + 2)（同理可以推到 3\*2 上面去）。  
因为是 2\*3，所以 (x, y) 与 (x + 1, y + 2) 必然有一个黑格，不失一般性设 (x, y) 为黑格。  
假如 (x + 1, y + 2) 填充与 (x, y) 不同，必然没有回文串；否则假如填充相同时一定存在回文串，我们就可以通过这个询问确定白格。

讨论几种情况：

（1）假如 (x + 1, y + 1) ≠ (x, y + 2)，则路径 (x, y) -> (x, y + 1) -> (x, y + 2) -> (x + 1, y + 2) 与 (x, y) -> (x, y + 1) -> (x + 1, y + 1) -> (x + 1, y + 2) 中必然有一个回文串。

（2）假如 (x + 1, y) ≠ (x, y + 1)，则同理可得路径 (x, y) -> (x + 1, y) -> (x + 1, y + 1) -> (x + 1, y + 2) 与 (x, y) -> (x, y + 1) -> (x + 1, y + 1) -> (x + 1, y + 2) 中必然有一个回文串。

（3）假如上述两种情况对于任意子矩形都不满足，等价于所有 左上 - 右下 的对角线上的数全部相同。  
这时候考虑，假如 (x, y) = (x + 1, y + 1) 与 (x + 1, y + 2) = (x, y + 1) 同时满足或者同时不满足，则也必然存在一个回文串。

否则当 (x + 1, y + 2) ≠ (x, y + 1) 时，(x, y) 所在对角线与 (x + 1, y + 1) 所在对角线相同；又因以 (x, y + 1) 为左上角时，又可以推出 (x + 1, y + 1) 与 (x + 2, y + 2) 所在对角线相同。进一步推出所有黑格对角线相同，然而这与左上角为 1 右下角为 0 矛盾。  
当 (x + 1, y + 2) = (x, y + 1)，大概就是所有黑格对角线形成 10101... 这样间隔开来的形式。然而因为 n 为奇数，所以有奇数条黑格对角线，于是这又与左上角为 1 右下角为 0 矛盾。

综上，以上 3 种情况必然有一个成立，这个算法可以找出解。

## @accepted code@ ##

#include<cstdio> int query(int x1, int y1, int x2, int y2) { printf("? %d %d %d %d\n", x1, y1, x2, y2); fflush(stdout); int x; scanf("%d", &x); return x; } int num[50 + 5][50 + 5], n; int fa[50*50 + 5], f[50*50 + 5]; int find(int x) { if( fa[x] == x ) return x; int y = fa[x]; fa[x] = find(fa[x]); f[x] ^= f[y]; return fa[x]; } void link(int x, int y, int k) { int fx = find(x), fy = find(y); fa[fx] = fy, f[fx] = f[x]^f[y]^k; } int d[50*50 + 5]; int main() { scanf("%d", &n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) num[i][j] = (i - 1)*n + j; for(int i=1;i<=n*n;i++) fa[i] = i, f[i] = 0; link(num[1][1], num[2][2], !query(1, 1, 2, 2)); for(int i=3;i<=n;i+=2) link(num[1][i], num[1][i-2], !query(1, i-2, 1, i)); for(int i=4;i<=n;i+=2) link(num[2][i], num[2][i-2], !query(2, i-2, 2, i)); for(int i=4;i<=n;i+=2) for(int j=2;j<=n;j+=2) link(num[i-2][j], num[i][j], !query(i-2, j, i, j)); for(int j=1;j<=n;j+=2) for(int i=3;i<=n;i+=2) link(num[i-2][j], num[i][j], !query(i-2, j, i, j)); link(num[2][1], num[3][2], !query(2, 1, 3, 2)); for(int i=3;i<=n;i+=2) { link(num[i-2][2], num[i][2], !query(i-2, 2, i, 2)); link(num[2][i-2], num[2][i], !query(2, i-2, 2, i)); } for(int i=4;i<=n;i+=2) for(int j=1;j<=n;j+=2) { link(num[i-2][j], num[i][j], !query(i-2, j, i, j)); link(num[j][i-2], num[j][i], !query(j, i-2, j, i)); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) find(num[i][j]); for(int i=1;i+2<=n;i++) { for(int j=1;j+1<=n;j++) { if( (f[num[i][j]] == f[num[i+2][j]]) == (f[num[i+1][j]] == f[num[i+2][j+1]]) || f[num[i+1][j]] != f[num[i][j+1]] || f[num[i+2][j]] != f[num[i+1][j+1]] ) { if( (i+j) & 1 ) d[fa[num[i][j]]] = f[num[i+2][j+1]]^(!query(i, j, i+2, j+1))^f[num[i][j]]; else d[fa[num[i+2][j+1]]] = f[num[i][j]]^(!query(i, j, i+2, j+1))^f[num[i+2][j+1]]; puts("!"); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%d", d[fa[num[i][j]]]^f[num[i][j]]); puts(""); } return 0; } if( (f[num[j][i]] == f[num[j][i+2]]) == (f[num[j][i+1]] == f[num[j+1][i+2]]) || f[num[j][i+1]] != f[num[j+1][i]] || f[num[j][i+2]] != f[num[j+1][i+1]] ) { if( (i+j) & 1 ) d[fa[num[j][i]]] = f[num[j+1][i+2]]^(!query(j, i, j+1, i+2))^f[num[j][i]]; else d[fa[num[j+1][i+2]]] = f[num[j][i]]^(!query(j, i, j+1, i+2))^f[num[j+1][i+2]]; puts("!"); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%d", d[fa[num[i][j]]]^f[num[i][j]]); puts(""); } return 0; } } } }

## @details@ ##

因为时间不够我也没仔细研究官方给出的构造方法，不过构造方法据我了解也比较多。

像这种构造题主要还是从小的数据范围考虑起，把复杂问题简单化吧。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11402409.html