赌场 题解

· · 题解

可是啊 我却 却愿意去相信

最渺小最微弱最柔软最无畏的你

赌场 题解

下文记 Azzurro 为小 A，Bordeaux 为小 B，Chiaro 为小 C。

理论信息位

小 A/B 获胜的关键是通过二维矩阵使得小 B 能够准确地接受小 A 传递来的信息。

考虑到 s 只有 51 个字符 A/B，而这个二维矩阵有 64 个 0/1 的位置。

由于小 C 可以对一条路径进行修改，而这条路径的长度恒定为 15。如果我们考虑被修改过的位置都是无效信息位，那就完蛋了——我们只有 49 个信息位。

但是你注意到：(1,1) 和 (8,8) 两个位置都是确定被小 C 翻转的，那么相当于小 C 的修改我们都知道，那就是没有修改，所以这样我们就有 51 个信息位了。

维护信息位

一个直接的思路是维护 a_{x,y} 表示一个字符。然而，字符的维护顺序是很重要的。

如果我们考虑以一行或者一列为一个单位维护，这样的信息位数确实很多，但是小 C 可能在一行走很多步，这样就 WA 了。所以我们必须换一种方式维护信息。

我们考虑：非信息位的个数为 13。而一个正方形的斜对角线条数为 15。除去左上方右下方两个点，还剩 13 条。所以我们考虑以一条左下到右上的对角线为单元维护信息。

信息加密

假设我们现在是小 B。在这个单元内，我们想知道小 A 给我们的原始信息是什么。

显然小 C 对原始信息的一位做了操作。我们需要排除这一位的影响。

假设我们知道上一单元，小 C 走到了 (X,Y)。那么在这个单元，他只能走到 (X+1,Y) 或者 (X,Y+1)。

所以我们对于一个对角线，维护 k 个信息位和 1 个异或位。异或位是所有 x 为奇数的信息位的 a_{x,y} 之异或和（x+y 为定值）。

这样，当小 B 拿到矩阵之后，判断异或位的信息是否和所有 x 为奇数的信息位的 a_{x,y} 之异或和对得上即可。总体来讲：

对角线分类讨论

显然斜对角线有两种：

红色系的对角线 x+y\le 9，左边以 y=1 的位置为终点；

蓝色系对角线 x+y\ge 10，下边以 x=n 的位置为终点。

对这两种对角线，我们选择的信息位是不一样的。

一个显然的思路是：

这样的紫色位置选的是对的，但是如果绿色也这么选，只能得 62 分。

为什么呢？

我们考虑当小 C 恰好走到异或位的情况。如果这个异或位的 x 是奇数，那么没问题，因为这样也算信息差异，而且这种情况唯一。可是如果是偶数，那么问题就出现了。

如果小 C 现在在 (7,2)，下一个对角线信息位是 (8,2)。

如果小 C 下移，那么就会出现信息差异，从而错误。

如果小 C 右移，那么还是会出现信息差异。

这样会导致我们无法区分这两种情况，从而爆炸。

所以我们必须把异或位选在一个 x 为奇数的地方。就像这样：

这样就完成了。然后就是一堆细节，比如 0-index 和 1-index 啥的，还有通信题难以调试的问题。

::::success[Code] 初版代码太丑了，经过了 Deepseek 格式化，所以会和我平时的代码有些不一样。

#include<bits/stdc++.h>
using namespace std;
std::vector<std::vector<int>> Azzurro(int n, int L, std::string S){
    std::string s = ' ' + S; n = 8;
    int l = L;
    while(l <= 51){ s += 'A'; l++; }
    std::vector<std::vector<int>> a;
    a.resize(9);
    for(int i=0;i<=8;i++)a[i].resize(9);
    a[1][1] = (s[1] == 'A' ? 0 : 1);
    int tot = 1;
    for(int i=3;i<=15;i++){
        if(i <= 8+1){
            int x=i-1, y=1, sum=0;
            for(;x>=1;x--,y++){
                if(x==1) a[x][y]=sum;
                else {
                    a[x][y] = (s[++tot]=='A' ? 0 : 1);
                    if(x&1) sum ^= a[x][y];
                }
            }
        } else {
            int x=i-8, y=8, sum=0;
            for(;x<=n;y--,x++){
                if(x==7) a[x][y]=sum;
                else {
                    a[x][y] = (s[++tot]=='A' ? 0 : 1);
                    if(x&1) sum ^= a[x][y];
                }
            }
        }
    }
    a[8][8] = (s[51]=='A' ? 0 : 1);
    std::vector<std::vector<int>> b;
    b.resize(8);
    for(int i=0;i<=7;i++)b[i].resize(8);
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
            b[i-1][j-1] = a[i][j];
    return b;
}
char getc(int x){
    return x==0 ? 'A' : 'B';
}
std::string Bordeaux(int n, int l, std::vector<std::vector<int>> b){
    std::string s = " ", ans = ""; n = 8;
    std::vector<std::vector<int>> a;
    a.resize(9);
    for(int i=0;i<=8;i++)a[i].resize(9);
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
            a[i][j] = b[i-1][j-1];
    a[1][1] ^= 1;
    int X=1, Y=1;
    for(int i=3;i<=15;i++){
        if(i <= n+1){
            int x=i-1, y=1;
            int sum = a[y][x];
            for(;x>=1;x--,y++){
                if(x==1){
                    if(sum==0){ if(X&1) X++; else Y++; }
                    else { if(X&1) Y++; else X++; }
                    a[X][Y] ^= 1;
                } else {
                    if(x&1) sum ^= a[x][y];
                }
            }
        } else {
            int x=i-8, y=8;
            int sum = a[7][i-7];
            for(;x<=n;y--,x++){
                if(x>=n-1){
                    continue;
                } else {
                    if(x&1) sum ^= a[x][y];
                }
            }
            if(X==8) Y++;
            else if(Y==8) X++;
            else if(sum==0){ if(X&1) X++; else Y++; }
            else { if(X&1) Y++; else X++; }
            a[X][Y] ^= 1;
        }
    }
    a[8][8] ^= 1;
    for(int k=2;k<=16;k++){
        if(k<=9){
            for(int j=1,i;j<k;j++){
                i=k-j;
                if(i==1){ if(j==1) s+=getc(a[i][j]); continue; }
                if(j==8){ if(i==8) s+=getc(a[i][j]); continue; }
                s += getc(a[i][j]);
            }
        } else {
            for(int i=k-8, j=8; i<=8; i++, j--){
                if(i==7 && j==k-7) continue;
                s += getc(a[i][j]);
            }
        }
    }
    for(int i=1;i<=l;i++) ans += s[i];
    return ans;
}

::::