题解 | J. 破译密码

J. 破译密码

题面故意整的很长，且题号靠后的签到题

我们发现三种不同加密规则得到的结果，其具备的特征也是唯一的：

1. 同行规则： 是同行的，加密后也是同行
2. 同列规则： 是同列的，加密后也是同列
3. 矩阵规则： 是不同行不同列的，加密后也是不同行不同列

所以我们可以直接对每一组密文 逆向解密回去

对于 的情况，同时满足规则 ，但是题目只要求我们的明文可以合法，所以两种逆向选一种即可

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

const string mat[] = {
    "PLAYF", "IRBCD", "EGHKM", "NOQST", "UVWXZ",
};

int x[26], y[26];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

#define to(x) ((x) - 'A')

    foreach (ch, 'A', 'Z')
    {
        if (ch == 'J')
        {
            tie(x[to(ch)], y[to(ch)]) = tpl(x[to('I')], y[to('I')]);
            continue;
        }

        bool found = 0;
        foreach (i, 0, 4)
        {
            foreach (j, 0, 4)
            {
                if (ch == mat[i][j])
                {
                    found = 1;
                    tie(x[to(ch)], y[to(ch)]) = tpl(i, j);
                    break;
                }
            }

            if (found) break;
        }
    }

    int n;
    cin >> n;

    foreach (i, 1, n)
    {
        string s, t;
        cin >> s;

        int sz = s.size();
        t.reserve(sz);

        for (int i = 0; i < sz; i += 2)
        {
            auto [x1, y1] = tpl(x[to(s[i])], y[to(s[i])]);
            auto [x2, y2] = tpl(x[to(s[i + 1])], y[to(s[i + 1])]);

            if (x1 == x2)
            {
                if (!y1--) y1 += 5;
                if (!y2--) y2 += 5;
            }
            else if (y1 == y2)
            {
                if (!x1--) x1 += 5;
                if (!x2--) x2 += 5;
            }
            else
                swap(y1, y2);

            t.push_back(mat[x1][y1]);
            t.push_back(mat[x2][y2]);
        }

        cout << t << "\n";
    }

    return 0;
}

扩展思考：如果要求输出所有可能明文中 字典序最小 的，怎么做呢？