嘘~ 正在从服务器偷取页面 . . .

AT_birthday0410_x - この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を 题解

算法 OCR 字符串 随机化
OI
发布日期:   2023-12-27
更新日期:   2023-12-28
文章字数:   6.3k

AT_birthday0410_x - この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を 题解

题目链接：AT_birthday0410_x

因为此题是道非常残忍的题，可以的话我认为你应该先开心地做其他题，如果其他题做完了还有时间的话，就以此题为消遣吧（以上为题目名称）

题目背景

如果你想AK这场比赛（お誕生日コンテスト），你可以尝试挑战这道题。从准备比赛的阶段开始，我就很担心我是否可以出这样的题目，但我还是决定冒一次险，因为这是一场具有挑战性的比赛。

题目描述

给出一个式子，由一位数整数，括弧，四则运算符号(加减乘除)组成，请输出计算结果。

（译者注：请不要忙着打，先把后面看完。）

输入格式

\(\begin{array}{ll} t & \\ W \quad H \\ B_1 & \\ B_2 & \\ \cdots & \\B_H &\end{array}\)

其中， \(t\) 是非负整数，表示此为第 \(t\) 组数据。 \(W\) 和 \(H\) 都是正整数，分别表示输入的图像的横长和纵长。

对于任意 \(B_i(1 \leq i \leq H)\) ，都是由.和#组成的长为 \(W\) 的字符串。

它的第 \(j\) 个字符 \((1 \leq j \leq W)\) 表示图像从上数第 \(i\) 行，从左数第 \(j\) 列的像素。

如果此字符为.，则表示该像素为白色；如果此字符为#，则表示该像素为黑色。

输出格式

\(A\)

\(A\) 表示输入图像中黑色像素组成的表达式的计算结果。

数据范围

  • 对于所有输入数据，满足 \(H=65\) 且 \(1 \leq W \leq 9000\) 。

所有输入数据按以下步骤生成。

  • 开始时给出长度小于等于 \(L\) 的包含一位数整数，括弧，四则运算符号的表达式，计算结果和运算过程中得出的数都在 \(32\) 位有符号整数型的范围内（数据不一定是随机的）。另外，除法运算只保留整数。也就是说，舍弃代数意义上商的小数部分（比如， \(-7/3=-2\) ）。但是，不存在像 \(-5\) 这样的负数和像 \(-(2+3)\) , \(+1\) 这样的最前面带符号的项。

表达式中所含的每个字符对应的图像生成方法如下：

  • 字体使用Courier Prime，字体大小为 \(64\) ，生成描绘该字体粗体字的二进制图像。像这样生成的图像，与由它转换而来的由.和#组成的文本，都能够在此页下方的提示中进行下载。
  • 生成倍率 \(M(M \leq 1)\) ，将图片整个扩大成原来的 \(M\) 倍（实际上就是在缩小）。
  • 生成纵向倍率 \(M_h(M_h \leq 1)\) 和横向倍率 \(M_w(M_w \leq 1)\) ，将图片纵向上变为原来的 \(M_h\) 倍，横向上变为原来的 \(M_w\) 倍。
  • 生成角度 \(R\) ，将整个图片旋转 \(R\) 度。
  • 生成两个参数 \(S_x\) 和 \(S_y\) ，根据这个参数来使图像失真。具体来说，将坐标为 \((x,y)\) 的像素移动到 \((x+S_yy,S_xx+y)\) 。
  • 将每个字符对应的图像横向连接起来组成一个新的图像，此时：
  • 对于横向的位置，对于任意相邻的字符，它们之间会有 \(10\) 个像素的空白。
  • 对于纵向的位置，对于整个图像在进行扩大缩小，旋转，失真的操作之前图像的大小，是在合适的范围内随机决定的。
  • 最后为概率 \(P\) ，使每个像素都有 \(P\) 的概率会黑白反转（因此你可能需要降噪）。

这里表达式长度上限 \(L\) 和noise的概率 \(P\) 是对整幅图适用的，而倍率 \(M,M_h,M_w\) ,角度 \(R\) ,失真参数 \(S_x,S_y\) 是对于表达式中每个字符互相独立的。

这个问题的数据有 \(140\) 组，这些数据从 \(0\) 开始编号。这就对应着输入数据中 \(t\) 的值。另外，以下 \(x∈[a,b]\) 这样的记法表示“ \(x\) 是大于等于 \(a\) ，小于等于 \(b\) 的任一实数”。

  • 对于 \(0 \leq t < 30\) 的输入数据：

    • \(L=3\)

    • \(M∈[0.9,1]\)

    • \(M_h∈[0.9,1],M_w∈[0.9,1]\)

    • \(R∈[-2,2]\)

    • \(S_x=0,S_y=0\)

    • \(P=0\)

  • 对于 \(30 \leq t < 90\) 的输入数据：

    • \(L=50\)
    • \(M∈[0.9,1]\)
    • \(M_h∈[0.9,1],M_w∈[0.9,1]\)
    • \(R∈[-10,10]\)
    • \(S_x∈[-0.1,0.1],S_y∈[-0.1,0.1]\)
    • \(P=0.05\)

  • 对于 \(90 \leq t < 140\) 的输入数据：

    • \(L=200\)
    • \(M∈[0.9,1]\)
    • \(M_h∈[0.9,1],M_w∈[0.9,1]\)
    • \(R∈[-15,15]\)
    • \(S_x∈[-0.1,0.1],S_y∈[-0.1,0.1]\)
    • \(P=0.05\)

分数按以下方式进行计算：

  • 对于 \(0 \leq t < 55\) 的数据，每组数据 \(2\) 分。
  • 对于 \(55 \leq t < 90\) 的数据，每组数据 \(4\) 分。
  • 对于 \(90 \leq t < 140\) 的数据，每组数据 \(5\) 分。

另外，对于 \(30 \leq t < 50\) 的数据，输入文件和可视化图片(PNG)可以进行下载。此处

输入输出样例

举例来说，考虑将以下图像作为输入的情况。

此图对应的输入数据

（由于原数据尺寸太大不便观察，所以此链接中的数据已经经过缩放处理以便理解。此链接中的数据组数编号 999 也是假的。）

对此式 \((3×3-4)\) 进行计算得出结果为 \(5\)

因此输出为一行：

5

提示

字体数据：

0123456789()+-*/ 这十六个字符的图像和文字形式的字体数据(zip)可以在此链接处下载。将此zip文件解压可以得到两个文件夹：txt/和png/。这两个文件夹中包含了文字形式和图像(PNG)形式的字体数据。

文字形式的数据省略了 \(t\) ，只给出 \(W\) 和 \(H\) 。

文本嵌入提示：

将以上所述的标准字体嵌入到程序中的文本可以在 此处 下载。你也可以对其进行一些加工。

注意： 光这个嵌入文本就占了约 44,000bites 。AtCoder允许提交的最长代码长度为UTF-8标准的 60,000 字符以下，所以写程序的时候请务必注意程序的长度。

标程能够通过所有测试数据，以及用和生成测试数据一样的方法生成的另外大约 \(200\) 组数据。（我们也尽梨了）

这道题还是很巧妙的，不过涉及了很多 OI 完全不会考的东西，并且代码极其长。

考虑对原图进行降噪处理。简单起见，我们可以直接使用众数滤波，效果如下图所示（直接搬过来的图）

什么是众数滤波呢？我们考虑一个点它是否是噪点，感性理解就是白纸上有一个黑点

那么这种降噪方式也是非常通俗易懂的，我们直接令 \(a_{i,j}\) 为周围相邻格子内出现的最多的颜色（黑/白）

注意，我们降噪后生成的是一张新的图，而不是在 \(a_{i,j}\) 的基础上直接修改。

// 对图片进行降噪处理
Image reducenoice(const Image &img)
{
	Image tmp(img);  // 对img进行复制
	auto valid = [&](int x, int y) { return x >= 0 && x < img.sx && y >= 0 && y < img.sy; };  // 判定访问是否越界
	int dx[] = { 0, 1, 1, 0, -1, -1, -1, 0, 1 };
	int dy[] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };   // 创建遍历列表
	for (int x = 0; x < img.sx; x++)
    {
		for (int y = 0; y < img.sy; y++) // 对每个 x,y 进行循环
        {
			int cnt1 = 0, cnt2 = 0;  // cnt1 为周围一圈黑点数量, cnt2 为周围一圈点的数量
			for (int k = 0; k < 9; k++) // 遍历周围的点
            {
				int nx = x + dx[k], ny = y + dy[k];
				if (valid(nx, ny)) { ++cnt2, cnt1 += img[nx][ny]; }
			}
			tmp[x][y] = (cnt1 * 2 > cnt2);  // 判定周围黑点数量是否比白点多, 若是则将此处涂黑
		}
	}
	return tmp;
}

对整张图片进行降噪后，我们就可以准确分离出各个字符了，因为题目保证了：

  • 对于横向的位置，对于任意相邻的字符，它们之间会有 \(10\) 个像素的空白。

因此我们可以将图片逐列从上往下扫以得到这些字符。

// 将大于minsize大小的联通块分离出来
vector<Image> split(Image img, int minsize = 15)
{
    vector<Image> res;
    queue< pair<int, int> > q;
    int minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN;
    auto init = [&]() { minx = INT_MAX, maxx = INT_MIN, maxy = INT_MAX, maxy = INT_MIN; };
    auto valid = [&](int x, int y) { return x >= 0 && x < img.sx && y >= 0 && y < img.sy; };
    // 将当前联通块中所有黑点全部加入到队列 q 中
    auto bfs = [&](int x, int y)
    {   
        queue< pair<int,int> > q1;
        int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0};
        q1.push({x, y}); q.push(q1.back());
        up(maxx, x); up(maxy, y); down(minx, x); down(miny, y); img[x][y] = 0;
        while(!q1.empty())
        {
            auto h = q1.front(); int x = h.first, y = h.second; q1.pop();
            for(int i = 0; i < 4; i++)
            {
                int nx = x + dx[i], ny = y + dy[i];
                if(valid(nx, ny) && img[nx][ny])
                {
                    q1.push({nx, ny}); q.push(q1.back()); img[nx][ny] = 0;
                    up(maxx, nx); up(maxy, ny); down(minx, nx); down(miny, ny);
                }
            }
        }
    };
    for(int j = 0; j < img.sy; j++)
    {
        for(int i = 0; i < img.sx; i++) // 遍历整张图, 注意 i,j 顺序
        {
            if(img[i][j]) // 如果此处存在黑点
            {
                init(); bfs(i,j);
                if(q.size() >= minsize) // 防止未处理干净的噪点的影响
                {
                    Image tmpimg(maxx - minx + 1, maxy - miny + 1, img.conv1, img.conv2); //依据大小构建子图
                    while(!q.empty())
                    {
                        auto p = q.front(); q.pop();
                        int x = p.first, y = p.second;
                        tmpimg[x - minx][y - miny] = 1; // 将队列里的黑点放到子图的相应位置
                    }
                    res.push_back(tmpimg); // 将子图放到列表里面
                }
                while(!q.empty()) q.pop();
            }
        }
    }
    return res;
}

接下来就是本题最为巧妙的字符识别过程了。

注意到题目给出了 \(t\) 在不同数据范围内的参数以及表达式图片的生成方式

这意味着我们可以根据参数的范围进行一定的尝试，即随机生成多张图像并找到最相似的那一个字符是什么。

Image balance(const Image &img)
{
    Image res(65, 38);
    int sumx = 0, sumy = 0, sumc = 0;
    for(int i = 0; i < img.sx; i++)
        for(int j = 0; j < img.sy; j++)
            if(img[i][j]) { sumx += i, sumy += j, sumc++; }
    int cx = (2 * sumx + sumc) / (2 * sumc), cy = (2 * sumy + sumc) / (2 * sumc); // 确定中心位置
    int px = 32 - cx, py = 19 - cy; // 确定偏移量
    res = cover(res, img, px, py); // 进行平移
    return res;
}
void init(int t)
{
    for(int i = 0; i < 16; i++)
    {
        // 这里原作者为了减少代码长度, 只截取了各个字符的黑色区域, 保存了它们的左上角坐标, 这一步做的就是还原它们原来所在的位置
        Signset[i] = cover(Image(65, 38), Signset[i], Signpos[i][0], Signpos[i][1]);
    }
    double Mmin = 0.9, Mmax = 1, Rmin, Rmax, Smin, Smax;
    if(t >= 0 && t < 30) { Rmin = -1, Rmax = 2, Smin = Smax = 0; }
    else if(t >= 30 && t < 90) { Rmin = -10, Rmax = 10, Smin = -0.1, Smax = 0.1; }
    else { Rmin = -15, Rmax = 15, Smin = -0.1, Smax = 0.1; }
    // uniform_real_distribution 类m模板默认返回 double 型的连续分布
    uniform_real_distribution M(Mmin, Mmax), R(Rmin, Rmax), S(Smin, Smax);
	default_random_engine gen(time(NULL));  //初始化随机数生成器
    auto trans = [&](const Image &img, double M, double Mx, double My, double R, double Sx, double Sy)
    {
        auto valid = [=](int x, int y) { return x >= 0 && x < 65 && y >= 0 && y < 38; };
        Image imgans(65, 38);
        for(int i = 0; i < 65; i++)
        {
            for(int j = 0; j < 38; j++)
            {
                if(img[i][j])
                {
                    double y = i + 0.5 - 32.5, x = j + 0.5 - 19; // 先对像素点进行平移，方便后面的旋转,扭曲操作
                    x *= M * Mx, y *= M * My; // 进行横向/纵向伸缩变换
                    double nx = x * cos(torad(R)) - y * sin(torad(R)), ny = x * sin(torad(R)) + y * cos(torad(R)); // 进行旋转变换
                    x = nx + Sy * ny, y = ny + Sx * nx;
                    int X = (int)(round(y + 32.5 - 0.5)), Y = (int)(round(x + 19 - 0.5)); // 最终的 X,Y 坐标
                    if(valid(X, Y)) { imgans[X][Y] = 1; }
                }
            }
        }
        return balance(reducenoice(imgans)); // 对变换后的图像降噪后再摆正位置
    };
    for(int i = 0; i < 16; i++) // 枚举每个字符
    {
        for(int j = 0; j < maxitertime; j++) // 在参数范围内随机生成至多 maxitertime 张图像
        {
            double _M = M(gen), _Mx = M(gen), _My = M(gen), _R = R(gen), _Sx = S(gen), _Sy = S(gen);
            randomset[i][j] = trans(Signset[i], _M, _Mx, _My, _R, _Sx, _Sy); // 生成随机图像
        }
    }
}

然后我就不贴各个部分的代码了，直接放所有代码好了。

本代码共 1079 行，其中至少一大半都是原有的字符图数据。

时间复杂度 \(\mathcal{O}(k\sum |S_i|)\) ，大概吧

代码：

// 2023年12月27日 16:16:12
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x,T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x,T y) { x > y ? x = y : 0; }

#define Range(x) (x).begin(), (x).end()
const int maxitertime = 75;
const double pi = 3.141592653589793;
const char convtable[] = "0123456789()+-*/";  //字符转换表

double torad(double x) { return x / 180.0 * pi; } // 转弧度制

const function<int(char)> conv1 = [](const char c) { return c == '.' ? 0 : 1; };
const function<char(int)> conv2 = [](const int c) { return c ? '#' : '.'; };

#define N ((int)())

struct Image
{
    vector< vector<int> > raw;
    function <int(char)> conv1 = [](const char c) { return (int)c; };
    function <char(int)> conv2 = [](const int c) { return (char)c; };

    Image() = default; // 使用默认构造函数

    int sx, sy;
    Image(int sx, int sy, function<int(char)> c1 = ::conv1, function<char(int)> c2 = ::conv2) : 
        sx(sx), sy(sy), conv1(c1), conv2(c2) { raw.resize(sx); fill(Range(raw), vector<int>(sy)); }

    auto& operator[](int x) { return raw[x]; } // auto& 表示改变量可能被编译器推导为引用变量
    const auto& operator[](int x) const { return raw[x]; }

    // 从字符串构造 Image
    Image(const string &a, function<int(char)> c1 = ::conv1, function<char(int)> c2 = ::conv2) : conv1(c1), conv2(c2)
    {
        sx = sy = 0; stringstream s1; string s2;
        // stringstream 类似于 istream,ostream, 十分有用, 以下简称 ss
        // ss << x 会把 x 输出到 s1.str() 这个字符串 (本质上是: 数字 -> ss对象 -> string)
        // ss >> x 会把 s1.str() 输入到 x 中 (本质上是: string -> ss对象 -> 数字)
        for(s1 << a; s1 >> s2; )
        {
            vector<int> s3;
            for(const auto i : s2) { s3.push_back(conv1(i)); }
            raw.push_back(s3); ++sx; up(sy, (int)s3.size());
        }
    }
    Image(const char *a, function<int(char)> c1 = ::conv1, function<char(int)> c2 = ::conv2) : conv1(c1), conv2(c2) 
    {
        sx = sy = 0; stringstream s1; string s2;
        for(s1 << a; s1 >> s2; )
        {
            vector<int> s3;
            for(const auto i : s2) { s3.push_back(conv1(i)); }
            raw.push_back(s3); ++sx; up(sy, (int)s3.size());
        }
    }
    friend int colorcount(const Image &img)
    {
        int cnt = 0;
        for(const auto &i : img.raw)
            for(const auto &j : i) cnt += j;
        return cnt;
    }
    Image subImage(int sx, int sy, int ex, int ey) const // 这里 const 表示 *this 是不可修改的
    {
        Image res(ex - sx + 1, ey - sy + 1);
        for(int i = sx; i <= ex; i++)
            for(int j = sy; j <= ey; j++) res[i - sx][j - sy] = raw[i][j];
        return res;
    }
    tuple<int, int, int, int> getminmaxrange() const
    {
        int minx = INT_MAX, maxx = 0, miny = INT_MAX, maxy = 0;
        for(int i = 0; i < sx; i++)
            for(int j = 0; j < sy; j++) if(raw[i][j]) {
                up(maxx, i); down(minx, i); up(maxy, j); down(miny, j);
            }
        return {minx, miny, maxx, maxy};
    }
    void resize(int nx, int ny)
    {
        sx = nx; sy = ny; raw.resize(ny);
        for_each(Range(raw), [=](auto &i){ i.resize(nx); }); // [=] 按值的方式捕获所有变量
    }
    friend ostream& operator<<(ostream& out, const Image& img)
    {
        for(const auto& i : img.raw)
        {
            for(const auto j : i) cout << img.conv2(j);
            cout << '\n';
        }
        return out;
    }
};
//各个字符对应的图像, R"(xxxxxx)" 方法可以直接在代码里嵌入 xxxxxx 字符串并不做转义
vector<Image> Signset{  
R"(
...........########...........
.........############.........
.......################.......
......##################......
.....####################.....
....######################....
...########################...
...##########....##########...
..#########........#########..
..########..........########..
.#########..........#########.
.########............########.
.########............########.
.########............########.
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
########..............########
.########............########.
.########............########.
.########............########.
.#########..........#########.
..########..........########..
..#########........#########..
...##########....##########...
...########################...
....######################....
.....####################.....
......##################......
.......################.......
.........############.........
...........########...........
)",
R"(
.............####..........
...........#######.........
........##########.........
.....#############.........
..################.........
.#################.........
.#################.........
.#################.........
.#################.........
..######..########.........
..###.....########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
..........########.........
.##########################
###########################
###########################
###########################
###########################
.##########################
)",
R"(
.........#########..........
......##############........
...###################......
..#####################.....
.#######################....
.#######################....
.########################...
.#########......#########...
.#######.........#########..
.#######..........########..
.#######..........########..
.#######..........########..
.#######..........########..
..######..........########..
.................#########..
.................########...
................#########...
...............##########...
..............##########....
.............###########....
............###########.....
...........###########......
..........###########.......
.........###########........
........###########.........
.......###########..........
......###########.....#####.
.....###########.....#######
....###########......#######
...###########.......#######
..###########........#######
.###########.........#######
############################
############################
############################
############################
############################
.###########################
)",
R"(
.........##########.........
.....################.......
...####################.....
..######################....
..#######################...
..########################..
..########################..
..########.......##########.
..#######.........#########.
..#######..........########.
..#######..........########.
...######..........########.
...................########.
...................########.
..................########..
.................#########..
..........###############...
.........###############....
.........##############.....
.........###############....
.........################...
..........################..
.................##########.
...................########.
...................#########
....................########
....................########
....................########
....................########
...................#########
..###.............##########
.########........##########.
.##########################.
.#########################..
##########################..
.########################...
.######################.....
....#################.......
.......###########..........
)",
R"(
.................#####........
................#######.......
...............########.......
..............#########.......
.............##########.......
............###########.......
............###########.......
...........############.......
..........#############.......
.........##############.......
........###############.......
.......################.......
.......########.#######.......
......########..#######.......
.....########...#######.......
....########....#######.......
...#########....#######.......
...########.....#######.......
..########......#######.......
.########.......#######.......
##############################
##############################
##############################
##############################
##############################
##############################
...............########.......
...............########.......
...............########.......
...............########.......
...............########.......
...............########.......
.........####################.
........#####################.
........#####################.
........#####################.
........#####################.
.........####################.
)",
R"(
...######################...
...#######################..
...#######################..
...#######################..
...#######################..
...######################...
...#######..................
...#######..................
...#######..................
...#######..................
...#######..................
...#######..................
..########..########........
..####################......
..######################....
..#######################...
..########################..
..########################..
..#########################.
..########.......##########.
.....##...........#########.
...................#########
....................########
....................########
....................########
....................########
....................########
....................########
...#...............#########
..####............#########.
.########.......###########.
.##########################.
.#########################..
#########################...
.#######################....
..#####################.....
....#################.......
........##########..........
)",
R"(
....................######...
...............###########...
............###############..
..........#################..
........###################..
.......####################..
......####################...
.....################........
....############.............
...###########...............
...#########.................
..#########..................
..########...................
.########....................
.########....................
.#######....########.........
.#######..#############......
#########################....
##########################...
###########################..
###########################..
############......##########.
##########.........#########.
#########...........#########
########.............########
########.............########
########.............########
.#######.............########
.#######.............########
.########...........#########
.#########.........#########.
..##########.....###########.
...#########################.
...########################..
....######################...
.....####################....
......##################.....
........##############.......
...........########..........
)",
R"(
###########################.
############################
############################
############################
############################
###########################.
#######...........#########.
#######...........#########.
#######..........#########..
#######..........#########..
#######..........########...
#######.........#########...
#######.........########....
#######........#########....
.#####.........#########....
...............########.....
..............#########.....
..............########......
.............#########......
.............########.......
............#########.......
............#########.......
............########........
...........#########........
...........########.........
..........#########.........
..........########..........
..........########..........
.........########...........
.........########...........
........#########...........
........########............
........########............
.......########.............
.......########.............
.......#######..............
.......#######..............
.........#####..............
)",
R"(
..........#########.........
........#############.......
......#################.....
.....###################....
....#####################...
...#######################..
...#######################..
...#########.....#########..
..#########.......#########.
..########.........########.
..########.........########.
..########.........########.
..########.........########.
..########.........########.
...########.......########..
...#########.....#########..
....#####################...
.....###################....
......#################.....
......#################.....
....#####################...
...#######################..
..#########......##########.
.########..........########.
.########..........#########
########............########
########............########
########............########
########............########
#########..........#########
#########..........#########
.##########......##########.
.##########################.
..########################..
..########################..
...######################...
....####################....
......################......
.........##########.........
)",
R"(
.........#########..........
.......#############........
.....#################......
....###################.....
...#####################....
..#######################...
.########################...
.##########......#########..
.#########........#########.
#########..........########.
########............#######.
########............#######.
########............########
########............########
########............########
#########..........#########
.########.........##########
.##########......###########
..##########################
..##########################
...#########################
....########################
......############..########
........########....#######.
....................#######.
...................########.
...................########.
..................########..
.................#########..
...............##########...
.............############...
.........###############....
....###################.....
...###################......
...##################.......
...################.........
...##############...........
...############.............
....######..................
)",
R"(
...............####..
..............######.
............########.
...........##########
..........###########
.........############
........############.
.......###########...
......###########....
.....###########.....
.....##########......
....##########.......
....#########........
...#########.........
...########..........
..#########..........
..########...........
.#########...........
.########............
.########............
.########............
#########............
########.............
########.............
########.............
########.............
########.............
########.............
########.............
########.............
########.............
########.............
.########............
.########............
.########............
.#########...........
..########...........
..#########..........
..#########..........
...#########.........
...##########........
....#########........
.....#########.......
.....##########......
......###########....
.......###########...
........###########..
.........############
..........###########
...........##########
............#########
.............#######.
...............####..
.................#...
)",
R"(
..####...............
.######..............
#########............
##########...........
###########..........
############.........
.############........
...###########.......
....###########......
.....##########......
......##########.....
.......##########....
........#########....
.........#########...
..........########...
..........#########..
...........########..
...........#########.
............########.
............########.
............########.
............#########
.............########
.............########
.............########
.............########
.............########
.............########
.............########
.............########
.............########
.............########
............########.
............########.
............########.
...........#########.
...........########..
..........#########..
..........#########..
.........#########...
........##########...
.......##########....
.......#########.....
.....###########.....
....###########......
...###########.......
..###########........
############.........
###########..........
##########...........
#########............
.#######.............
..####...............
...#.................
)",
R"(
...........#####...........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
###########################
###########################
###########################
###########################
###########################
###########################
###########################
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
..........#######..........
...........#####...........
)",
R"(
.##########################.
############################
############################
############################
############################
############################
.###########################
)",
R"(
...........####...........
..........######..........
..........#######.........
.........########.........
.........########.........
..........#######.........
..........######..........
.#####....######.....####.
.######...######...#######
#########..#####.#########
###############.##########
##########################
##########################
.########################.
......##############......
.........########.........
........###########.......
.......#############......
.....########.#######.....
....########..########....
....########..#########...
...########....########...
...########....########...
....#######.....#######...
.....#####......######....
......###.........##......
)",
R"(
......................####..
......................######
.....................#######
.....................#######
....................########
....................#######.
...................########.
...................#######..
..................########..
..................#######...
.................########...
.................#######....
................########....
................########....
................#######.....
...............########.....
...............#######......
..............########......
..............#######.......
.............########.......
.............#######........
............########........
............#######.........
...........########.........
...........#######..........
..........########..........
..........#######...........
..........#######...........
.........########...........
.........#######............
........########............
........#######.............
.......########.............
.......#######..............
......########..............
......#######...............
.....########...............
.....#######................
....########................
....#######.................
...########.................
...########.................
...#######..................
..########..................
..#######...................
.########...................
.#######....................
########....................
#######.....................
.######.....................
..#####.....................
)",
};
int Signpos[16][2] = {  // 字符在原来尺寸下的左上角的位置
	{ 7, 4 },
	{ 7, 6 },
	{ 7, 5 },
	{ 7, 5 },
	{ 7, 4 },
	{ 8, 5 },
	{ 7, 5 },
	{ 8, 6 },
	{ 7, 5 },
	{ 7, 5 },
	{ 4, 8 },
	{ 4, 9 },
	{ 13, 6 },
	{ 23, 5 },
	{ 7, 6 },
	{ 3, 5 }
};
Image randomset[16][maxitertime];

Image cover(const Image &img1, const Image &img2, int sx, int sy)
{
    Image imgans(img1);
    for(int i = max(0, -sx); i < min(img2.sx, img1.sx - sx); i++)
        for(int j = max(0, -sy); j < min(img2.sy, img1.sy - sy); j++)
            imgans[i + sx][j + sy] = img2[i][j];
    return imgans;
}

// 对图片进行降噪处理
Image reducenoice(const Image &img)
{
	Image tmp(img);  // 对img进行复制
	auto valid = [&](int x, int y) { return x >= 0 && x < img.sx && y >= 0 && y < img.sy; };  // 判定访问是否越界
	int dx[] = { 0, 1, 1, 0, -1, -1, -1, 0, 1 };
	int dy[] = { 0, 0, 1, 1, 1, 0, -1, -1, -1 };   // 创建遍历列表
	for (int x = 0; x < img.sx; x++)
    {
		for (int y = 0; y < img.sy; y++) // 对每个 x,y 进行循环
        {
			int cnt1 = 0, cnt2 = 0;  // cnt1 为周围一圈黑点数量, cnt2 为周围一圈点的数量
			for (int k = 0; k < 9; k++) // 遍历周围的点
            {
				int nx = x + dx[k], ny = y + dy[k];
				if (valid(nx, ny)) { ++cnt2, cnt1 += img[nx][ny]; }
			}
			tmp[x][y] = (cnt1 * 2 > cnt2);  // 判定周围黑点数量是否比白点多, 若是则将此处涂黑
		}
	}
	return tmp;
}

Image reducesize(const Image &img)
{
	const auto& rng = img.getminmaxrange();
	int minx, maxx, miny, maxy;
	tie(minx, maxx, miny, maxy) = rng;
	return img.subImage(minx, maxx, miny, maxy);
}
// 将大于minsize大小的联通块分离出来
vector<Image> split(Image img, int minsize = 15)
{
    vector<Image> res;
    queue< pair<int, int> > q;
    int minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN;
    auto init = [&]() { minx = INT_MAX, maxx = INT_MIN, maxy = INT_MAX, maxy = INT_MIN; };
    auto valid = [&](int x, int y) { return x >= 0 && x < img.sx && y >= 0 && y < img.sy; };
    // 将当前联通块中所有黑点全部加入到队列 q 中
    auto bfs = [&](int x, int y)
    {   
        queue< pair<int,int> > q1;
        int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0};
        q1.push({x, y}); q.push(q1.back());
        up(maxx, x); up(maxy, y); down(minx, x); down(miny, y); img[x][y] = 0;
        while(!q1.empty())
        {
            auto h = q1.front(); int x = h.first, y = h.second; q1.pop();
            for(int i = 0; i < 4; i++)
            {
                int nx = x + dx[i], ny = y + dy[i];
                if(valid(nx, ny) && img[nx][ny])
                {
                    q1.push({nx, ny}); q.push(q1.back()); img[nx][ny] = 0;
                    up(maxx, nx); up(maxy, ny); down(minx, nx); down(miny, ny);
                }
            }
        }
    };
    for(int j = 0; j < img.sy; j++)
    {
        for(int i = 0; i < img.sx; i++) // 遍历整张图, 注意 i,j 顺序
        {
            if(img[i][j]) // 如果此处存在黑点
            {
                init(); bfs(i,j);
                if(q.size() >= minsize) // 防止未处理干净的噪点的影响
                {
                    Image tmpimg(maxx - minx + 1, maxy - miny + 1, img.conv1, img.conv2); //依据大小构建子图
                    while(!q.empty())
                    {
                        auto p = q.front(); q.pop();
                        int x = p.first, y = p.second;
                        tmpimg[x - minx][y - miny] = 1; // 将队列里的黑点放到子图的相应位置
                    }
                    res.push_back(tmpimg); // 将子图放到列表里面
                }
                while(!q.empty()) q.pop();
            }
        }
    }
    return res;
}

// 对图像进行线性拉伸变换
Image resize(const Image &img, int nx, int ny)
{
    Image res(nx, ny);
    auto valid = [=](int x, int y) { return x >= 0 && x < nx && y >= 0 && y < ny; };
    double cx = (double)nx / img.sx, cy = (double)ny / img.sy;
    if(cx < 1)
    {
        for(int i = 0; i < img.sx; i++)
        {
            if(cy < 1) {
                for(int j = 0; j < img.sy; j++) {
                    if(img[i][j]) res[(int)(i * cx)][(int)(j * cy)] = 1;
                }
            }else {
                for(int j = 0; j < ny; j++) {
                    if(img[i][(int)(j / cy)]) res[(int)(i * cx)][j] = 1;
                }
            }
        }
    }else
    {
        for(int i = 0; i < nx; i++)
        {
            if(cy < 1) {
                for(int j = 0; j < img.sy; j++) {
                    if(img[(int)(i / cx)][j]) res[i][(int)(j * cy)] = 1;
                }
            }else {
                for(int j = 0; j < ny; j++) {
                    if(img[(int)(i / cx)][(int)(j / cy)]) res[i][j] = 1;
                }
            }
        }
    }
    return res;
}

// 对图像进行旋转变换
Image rotate(const Image &img, double angle)
{
    angle = torad(angle);
    double minx = 1e5, maxx = -1e5, miny = 1e5, maxy = -1e5;
    vector< pair<double, double> > points;
    auto singlerotate = [](pair<double, double> p, double angle)
    {
        double x = p.second, y = -p.first;
        double nx = x * cos(angle) - y * sin(angle), ny = x * sin(angle) + y * cos(angle);
        return pair<double, double>({-ny, nx});
    };
    for(int i = 0; i < img.sx; i++)
        for(int j = 0; j < img.sy; j++)
            if(img[i][j]) points.push_back({i, j});
    for(auto& i : points)
    {
        i = singlerotate(i, angle);
        up(maxx, i.first); down(minx, i.first);
        up(maxy, i.second); down(miny, i.second);
    }
    Image res((int)(maxx - minx + 1), (int)(maxy - miny + 1));
    for(const auto& i : points) {
        int x = (i.first - minx), y = (i.second - miny); res[x][y] = 1;
    }
    return res;
}

double operator==(const Image &img1, const Image &img2)
{
    int bx = img2.sx, by = img2.sy; double cnt = 0;
    for(int i = 0; i < img1.sx; i++)
        for(int j = 0; j < img1.sy; j++) cnt += (img2[i][j] == img1[i][j]) ? 1 : 0;
    return (cnt / (double)(img1.sx * img1.sy));
}

Image balance(const Image &img)
{
    Image res(65, 38);
    int sumx = 0, sumy = 0, sumc = 0;
    for(int i = 0; i < img.sx; i++)
        for(int j = 0; j < img.sy; j++)
            if(img[i][j]) { sumx += i, sumy += j, sumc++; }
    int cx = (2 * sumx + sumc) / (2 * sumc), cy = (2 * sumy + sumc) / (2 * sumc); // 确定中心位置
    int px = 32 - cx, py = 19 - cy; // 确定偏移量
    res = cover(res, img, px, py); // 进行平移
    return res;
}

char recognize(const Image &img)
{
    double rate = 0; int idx = -1; Image imgtmp = balance(img); // 调整 img 的位置
    for(int i = 0; i < maxitertime; i++)
        for(int j = 0; j < 16; j++)
        {
            double r = (imgtmp == randomset[j][i]);
            if(r > rate) { rate = r; idx = j; }
        }
    return convtable[idx];
}
int t,n,m;
Image test;
vector<Image> test2, signset;
int calc(const string &s)
{
    vector<int> stk1; vector<char> stk2;
    int optnum = 0, isd = 0;
    auto cal = [&](char c)
    {
        int rhs = stk1.back(); stk1.pop_back();
        int lhs = stk1.back(); stk1.pop_back();
        switch(c)
        {
            case '+': stk1.push_back(lhs + rhs); break;
            case '-': stk1.push_back(lhs - rhs); break;
            case '*': stk1.push_back(lhs * rhs); break;
            case '/': stk1.push_back(lhs / rhs); break;
            default: break;
        }
    };
    auto level = [](char c)
    {
        switch(c)
        {
            case '(': return 0; break;
            case '+':
            case '-': return 1; break;
            case '*':
            case '/': return 2; break;
            default: return -1; break;
        }
    };
    for(const auto c : s)
    {
        if(isdigit(c)) {
            optnum = 10 * optnum + (c - 48); isd = 1;
        }else
        {
            if(isd)
            {
                stk1.push_back(optnum); isd = 0; optnum = 0;
            }
            if(stk2.empty()) { stk2.push_back(c); }
            else
            {
                switch(c)
                {
                    case '(': stk2.push_back(c); break;
                    case ')':
                        while(stk2.back() != '(') {
                            cal(stk2.back()); stk2.pop_back();
                        }
                        stk2.pop_back(); break;
                    default:
                        while(!stk2.empty() && level(c) <= level(stk2.back())) {
                            cal(stk2.back()); stk2.pop_back();
                        }
                        stk2.push_back(c);
                }
            }
        }
    }
    if(isdigit(s.back())) { stk1.push_back(optnum); }
    while(!stk2.empty()) { cal(stk2.back()); stk2.pop_back(); }
    return stk1.back();
}

void init(int t)
{
    for(int i = 0; i < 16; i++)
    {
        // 这里原作者为了减少代码长度, 只截取了各个字符的黑色区域, 保存了它们的左上角坐标, 这一步做的就是还原它们原来所在的位置
        Signset[i] = cover(Image(65, 38), Signset[i], Signpos[i][0], Signpos[i][1]);
    }
    double Mmin = 0.9, Mmax = 1, Rmin, Rmax, Smin, Smax;
    if(t >= 0 && t < 30) { Rmin = -1, Rmax = 2, Smin = Smax = 0; }
    else if(t >= 30 && t < 90) { Rmin = -10, Rmax = 10, Smin = -0.1, Smax = 0.1; }
    else { Rmin = -15, Rmax = 15, Smin = -0.1, Smax = 0.1; }
    // uniform_real_distribution 类m模板默认返回 double 型的连续分布
    uniform_real_distribution M(Mmin, Mmax), R(Rmin, Rmax), S(Smin, Smax);
	default_random_engine gen(time(NULL));  //初始化随机数生成器
    auto trans = [&](const Image &img, double M, double Mx, double My, double R, double Sx, double Sy)
    {
        auto valid = [=](int x, int y) { return x >= 0 && x < 65 && y >= 0 && y < 38; };
        Image imgans(65, 38);
        for(int i = 0; i < 65; i++)
        {
            for(int j = 0; j < 38; j++)
            {
                if(img[i][j])
                {
                    double y = i + 0.5 - 32.5, x = j + 0.5 - 19; // 先对像素点进行平移，方便后面的旋转,扭曲操作
                    x *= M * Mx, y *= M * My; // 进行横向/纵向伸缩变换
                    double nx = x * cos(torad(R)) - y * sin(torad(R)), ny = x * sin(torad(R)) + y * cos(torad(R)); // 进行旋转变换
                    x = nx + Sy * ny, y = ny + Sx * nx;
                    int X = (int)(round(y + 32.5 - 0.5)), Y = (int)(round(x + 19 - 0.5)); // 最终的 X,Y 坐标
                    if(valid(X, Y)) { imgans[X][Y] = 1; }
                }
            }
        }
        return balance(reducenoice(imgans)); // 对变换后的图像降噪后再摆正位置
    };
    for(int i = 0; i < 16; i++) // 枚举每个字符
    {
        for(int j = 0; j < maxitertime; j++) // 在参数范围内随机生成至多 maxitertime 张图像
        {
            double _M = M(gen), _Mx = M(gen), _My = M(gen), _R = R(gen), _Sx = S(gen), _Sy = S(gen);
            randomset[i][j] = trans(Signset[i], _M, _Mx, _My, _R, _Sx, _Sy); // 生成随机图像
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);

    string tmp1, tmp2; cin >> t >> n >> m; init(t);
    while(cin >> tmp2) { tmp1 += tmp2 + ' '; }

    test = Image(tmp1); // 从字符串构造图像
    test = reducenoice(test); // 对图像进行降噪
    test2 = split(test); // 分离单个字符;

    tmp2.clear();
    for(const auto &i : test2) { tmp2 += recognize(i); } // 分别与列表中的字符逐一识别, 并加到字符串中

    cout << calc(tmp2) << '\n'; // 完结撒花~
    return 0;
}

参考文献：

[1] https://www.luogu.com.cn/blog/xiyihan/ti-xie-at678-post

题外话：

这道题我在N多年之前就看到过了，当时编号是 AT678

然后好像一直没人 AC ，直到我看的这篇题解 AC 了，但后来也没什么空写这题。

今天没事看了下这道题，虽说这个算法没什么研究的必要（就 OI 而言），但是还是可以学到很多东西的

然后这道题的题解有点过于长了，主要是代码有点过于极端了（嗯？），以至于我的 Typora 都卡住了。

不得不说，现在能一眼看出这题能带来的和不能带来的能力增加，也来源于以前的吃的亏呢。

另外，我感觉我现在好像很喜欢说一些不符合中文语序的奇怪长难句，不知道为什么。

文章作者: q779
文章链接: https://q779.cn/2023/12/27/at-birthday0410-x-ti-jie/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
算法 OCR 字符串 随机化
评论
  目录