AT Birthday0410 X - 论如何在 2.9k 以内解决战斗

TL;DR

本题可以以 在 Linux 上通过测试。

本题可以以 在 Windows 上通过测试。

前言

upd 2022/7/15: 优化到 7k 以下，原先 9k。

upd 2022/8/1: 修正了一些错误，之前的不计换行符应为换行符记为一个字符，记换行符应为换行符记两个字符；增加了新内容。

2022/8/1: 最终停在了 4k 的门槛上啊，累了。

upd 2022/8/2: www，非常抱歉食言了，发出来之后发现了一些不能容忍的错误。以及隔了一天之后我又不累了。

2022/8/2: 进入了 4k 大关。

upd 2022/9/24: 进入 3.6k 大关。

upd 2022/10/27: 修复代码错误，补档一个特性的解释。

upd 2022/11/11: 答案是优化之后的代码只能在 Windows 系统上跑。

2022/11/11: 答案是 Western Windows-1252 编码，我的评价是：笨比 Linux 的游戏理解就到这了好吧。

upd 2022/11/12: ，永远永远的结束了。

2022/11/12: 总之我是魔怔了。

upd 2023/7/12: 随便更一句（其实是老早之前就发现的）：本题可以取 。之前老以为工程界的圆周率是整数是刻板印象。啊不对就是刻板印象。

2023/7/12: 还有大家别 copy 了，现在 以内的都是我代码……小心哪天就点国策大清洗（

upd 2023/8/11: 更新长度。

upd 2023/10/19: 更新长度。

upd 2023/12/21: 更新长度。

我寻思这题也不难啊，我才交了四发搞定一些弱智错误就有 480 了。

要 A 掉不就交了 17 发，花了两个晚上一个下午大概两位数小时么。

论如何在 23k 以内迅速地解决战斗

首先（一开始）我没有使用压缩技术把图像压缩进去。

当时写着写着，开始调了，突然发现自己好像可以（在洛谷上）整个最短解。

降噪与分离

首先因为这题是个大模拟，考虑封装一个 image 类便于操作图像：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct image{
    int rx,ry;  // 长宽信息
    vector<vector<bool>> raw,null,vis;
    // raw 表示图像信息，null 表示空的图（用于给 vis 赋值），vis 是工具人（

    image(const char *s){  // 从字符串构造，以换行符作为分隔符
        int i=0;
        raw.resize(1);
        null.resize(1);
        for(;*s!=0;++s)
            if(*s=='\n'){
                if(raw[i].size()<raw[0].size()) break;
                null[i].resize(raw[i].size());
                raw.resize(++i+1);
                null.resize(i+1);
            }else
                raw[i].push_back(*s=='#');
        ry=raw[0].size();
        if((int)raw.back().size()<ry){
            raw.pop_back();
            null.pop_back();
        }
        rx=raw.size();
    }

    image(int x,int y){  // 给定长宽，构造一个空图像
        raw.resize(rx=x+1);
        ry=y+1;
        for(int i=0;i<=x;++i) raw[i].resize(y+1);
        null=raw;
    }   
}

众所周知我们在处理二维图的时候经常要要遍历整张图，或者对一个点去寻找与它联通的点，所以我们可以考虑对这两种东西做一个封装：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct image{
    // ......
    template<class A,class B>
    void expand(int x,int y,bool now,const A &check,const B &next){
        // 拓展一个点周围的点
        for(int i=0;i<8;++i){
            int nx=x+fx[i][0],ny=y+fx[i][1];
            if(~nx&&~ny&&nx<rx&&ny<ry&&check(nx,ny)&&raw[nx][ny]==now)
                next(nx,ny);
        }
    }
    template<class T>
    void foreach(const T &func){
        // 遍历整张图
        for(int i=0;i<rx;++i)
            for(int j=0;j<ry;++j)
                func(i,j);  // 对每个点执行函数
    }
}

然鹅后来发现 expand 用的太少了，我给它优化掉了。

具体用法，比如我们要降噪，使用众数滤波器，要统计周围的合法的点数以及黑点的数量，就可以这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct image{
    // ......
    image &reno(){
        vis=null;  // null 是在初始化时创建好的一个空二维 vector，这句话等同于清空
        foreach([&](int i,int j){
            int all=1,bk=raw[i][j];
            expand(i,j,1,
                   [&](int x,int y){
                       ++all;
                       // 这是 check，这就是为什么 check 的判断放在了判断颜色连通性之前
                       return(1);
                   },
                   [&](int x,int y){
                       ++bk;
                       // 这是 next，由于判断了颜色为 1，直接加即可。
                   });
            raw[i][j]=bk<<1>all;
        });
        return(*this);
    }
}

众数滤波，即对每个点计算（包含自身的）周围的点的情况，选取最多的颜色进行着色。

不过这里其实可以不统计四周合法点的数量，接触边缘的点我们可以直接当作噪音。

再比如，我们调试要输出整张图像，就可以这么写：

1
2
3
4
5
6
7
8
struct image{
    // ......
    void print(){
        foreach([&](int x,int y){
            putchar(raw[x][y]?'#':' ');
            if(y==ry-1) puts("");});
    }
}

这个 print 太好使了，没有它根本没法调试。

指写出了 charset[i].rotate(j).cut(-.1,-.1).reno().print() 的魔怔人。

然后接下来，由于我们对图像做操作，以及分离的时候需要框出图像的四边，所以我们再封装一个类：

1
2
3
4
5
6
7
8
9
10
11
struct sqr{
    int x0,x1,y0,y1;
    void operator+=(const sqr &b){
        x0=min(x0,b.x0);x1=max(x1,b.x1);
        y0=min(y0,b.y0);y1=max(y1,b.y1);
    }
    void operator+=(pair<int,int> b){
        x0=min(x0,b.first);x1=max(x1,b.first);
        y0=min(y0,b.second);y1=max(y1,b.second);
    }
};

分离大概长这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct image{
    // ......
    sqr find(int x,int y){  // 遍历整个连通块，返回图像四周的坐标
        sqr re={x,x,y,y};
        vis[x][y]=1;
        expand(x,y,raw[x][y],
               [&](int x,int y){return(!vis[x][y]);},
               [&](int x,int y){re+=find(x,y);});
        return(re);
    }
    image get(int x,int y){  // 将连通块所占据的矩形复制成新的图像
        sqr out=find(x,y);
        image re(out.x1-out.x0,out.y1-out.y0);
        for(int i=out.x0;i<=out.x1;++i)
            for(int j=out.y0;j<=out.y1;++j)
                re[i-out.x0][j-out.y0]=raw[i][j];
        return(re);
    }
    vector<image> split(){
        vector<image> re;
        vis=null;
        for(int i=0;i<ry;++i)
            for(int j=0;j<rx;++j)
                if(raw[j][i]&&!vis[j][i]){
                    re.emplace_back(get(j,i));
                    if(re.back().rx*re.back().ry<80)
                        re.pop_back();
                    // 判断块大小，太小的直接放弃，防止降噪不充分（真的会发生的）
                }
        return(re);
    }
}

然后我们就得到一个由 image 组成的 vector，下一步可以开始匹配了。

不过在此之前……

变换与预处理

首先我们先把基础字体塞进一个 vector<image> 里面，使用 C++11 的原始字符串字面量，大概像这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<image> charset({R"(.#.
#.#
#.#
#.#
.#.
)",R"(##.
.#.
.#.
.#.
###)",R"(###
..#
###
#..
###)",R"(以下
省略)"});

众所周知只有基础字体的图像（以下称“本源图像”），我们是不可能 A 掉这道题的。

由于题目给出的图像已经变换的很厉害了，所以试图对这些图像做逆变换可能不是个好主意。所以我们要对本源图像做亿些变换，使得它们更加像题目中给定的图像。

然后看到题目中给出了变换顺序：

  1. 整体缩小。
  2. 对 方向与 方向分别缩小（改变比例）。
  3. 旋转 度。
  4. 剪切变换。其实最开始我没看到这个变换所以只拿了 480 分，看到之后就有 490 了。

所以我们的图像也要按顺序变换，先进行旋转。

这个问题是这样的，因为缩放的参数预先猜测效果并不好，但是如果其他变换都做完了，缩放的参数其实可以通过图像信息得出，所以我们不妨到了要匹配的时候再进行缩放。

旋转按照公式写即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct image{
    // ......
    image rotate(db ang){
        vector<pair<int,int>> point;
        sqr out={INF,-INF,INF,-INF};
        // 创建一个黑点集合，以及记录集合的四边

        ang=ang/180*pi;
        db csa=cos(ang),sia=sin(ang),cex=rx/2.,cey=ry/2.;

        foreach([&](int x,int y){
            if(!raw[x][y]) return;
            db nx=(x-cex)*csa+(y-cey)*sia,ny=-(x-cex)*sia+(y-cey)*csa;
            // 按照公式变换
            point.emplace_back(nx+cex,ny+cey);
            out+=make_pair(nx+cex,ny+cey);});

        image re(out.x1-out.x0,out.y1-out.y0);
        for(auto i:point)
            re[i.first-out.x0][i.second-out.y0]=1;
        // 将黑点集合放入图像
        return(re);
    }
}

然后是剪切变换：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct image{
    // ......
    image cut(db cx,db cy){
        vector<pair<int,int>> point;
        sqr out={INF,-INF,INF,-INF};
        // 创建一个黑点集合，以及记录集合的四边

        foreach([&](int x,int y){
            if(!raw[x][y]) return;
            db nx=x+y*cy,ny=y+x*cx;  // 按照公式变换
            point.emplace_back(nx,ny);
            out+=make_pair(nx,ny);});

        image re(out.x1-out.x0,out.y1-out.y0);
        for(auto i:point)
            re[i.first-out.x0][i.second-out.y0]=1;
        // 将黑点集合放入图像
        return(re);
    }
}

封装的收益这个时候就体现出来了。

最后是缩小操作（强调缩小是因为放大需要额外增加黑点，比较难处理，我写的这个比较简单，只能缩小）：

1
2
3
4
5
6
7
8
9
10
11
12
struct image{
    // .....
    image fit(int rxt,int ryt){  // 这里传入的是目标的图像大小
        image re(rxt,ryt);
        db delx=(db)rxt/rx,dely=(db)ryt/ry;  // 计算缩小比例

        foreach([&](int x,int y){
            if(raw[x][y]) re[x=x*delx][y=y*dely]=1;});

        return(re);
    }
}

然后在预处理中搞出若干张图像来，方便处理。我没有使用随机，而是直接按照一定分度值枚举参数。

1
2
3
4
5
6
7
8
9
10
11
12
void init(){
    for(int i=0;i<16;++i)  // 枚举字符
        for(db j=-15;j<16;j+=3){  // 枚举旋转角
            auto tmp=charset[i].rotate(j);
            trans[i].emplace_back(tmp.cut(-.1,-.1).reno());
            trans[i].emplace_back(tmp.cut(-.1,.1).reno());
            trans[i].emplace_back(tmp.cut(.1,-.1).reno());
            trans[i].emplace_back(tmp.cut(.1,.1).reno());
            // 我们只对四角的最极端的四种剪切做预处理，事实证明这是足够的
            trans[i].emplace_back(tmp.reno());
        }
}

这里使用降噪是因为变换容易搞出中心空点。

匹配与计算

也就是主函数！

我们使用暴力匹配法，对于每一个位置进行匹配，最后通过匹配的数量除以总的数量得到匹配率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct image{
    // ......
    db match(image &x){
        if(min(abs((db)ry/rx-(db)x.ry/x.rx),abs((db)rx/ry-(db)x.rx/x.ry))>0.25) 
            return(0);
        // 对于长宽比相差过大的直接放弃，否则在进行剧烈缩小的时候会丢失大量的信息导致误判
        int re=0,mix=min(rx,x.rx)-1,miy=min(ry,x.ry)-1;
        // 这里我们将两张图像都进行缩小，按照两个维度缩小到最小的大小，因为并不能放大
        // fit 没写好，所以我要减一
        auto a=this->fit(mix,miy),b=x.fit(mix,miy);

        a.foreach([&](int x,int y){re+=a[x][y]==b[x][y];});

        return((db)re/(a.rx*a.ry));  // 返回使用比例，因为每次匹配的大小是不定的
    }
}

那么经过了大量的封装，主函数只需要调用即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main(){
    init();
    fread(BuF,1,FSIZE,stdin);

    read(t);read(n);read(m);

    for(;*InF<33;++InF);
    image in(InF);

    for(auto &i:in.reno().split()){
        db bestmatch=0,tmp;
        int bestnum=0;
        for(int j=0;j<16;++j){
            tmp=i.match(charset[j]);
            if(tmp>0&&tmp<.5) continue;
            // 先对本源图做一次匹配，如果匹配率太低直接放弃

            for(auto &k:trans[j])
                if((tmp=i.match(k))>bestmatch){
                    bestmatch=tmp;
                    bestnum=j;
                }
        }
        ans+=charname[bestnum];
    }
    printf("%d\n",calc(ans));
}

计算我是直接 copy 的，大家可以去看其他的题解（雾）。

最后一步

Final Step!

把所有的空格缩进换成 Tab （雾）。

后记

这道题我实际写起来比想的容易很多（？

一开始甚至没有看到剪切操作就拿到了 480pts。

这也证明了考场上打这个做法是非常不错的，因为好写又好拿分（？

感谢 @xiyihan 提供的字符表以及最后一步计算的代码（指我直接进行一个厚颜无耻的 copy）。

完整代码可以在 AtCoder 的提交记录中查看。

最后，Clang 吊打 GCC！

论如何在 9k 以内优雅地解决战斗

字符表压缩

首先我们观察字符表，发现这东西巨大，肯定要压缩。

我选择了游码，主要是因为它易于解码，而且这题的字符集为二，非常适合游码发挥（更好的方法解码更复杂，效果其实没有理论那么好）。

实测大约是 的压缩率，效果还是很不错的。

具体的过程，我们可以将输入看作为一维字符串进行，解码时再额外传一个宽度即可还原成二维矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct image{
    // ......
    image(initializer_list<int> v){
        // initializer_list 的第一个值是宽度
        int i=0;bool p=0;auto k=v.begin();
        raw.resize(1);
        null.resize(1);
        for(ry=*k;++k!=v.end();p^=1)
            for(int j=0;j<*k;++j){
                raw[i].eb(p);
                if(raw[i].size()==ry&&k+1!=v.end()){
                    // 对于最后一个数据不再新开一行
                    raw.resize(++i+1);
                    null.resize(i+1);
                }
            }
        rx=raw.size();
    }
}

然后我们的 16 个字符就是这样的画风：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<image> charset({
{30,11,8,20,12,16,16,13,18,11,20,9,22,7,24,6,10,4,10,5,9,8,9,4,8,10,8,3,9,10,9,2,8,12,8,2,8,12,8,2,8,12,8,1,8,14,16,14,16,14,16,14,16,14,16,14,16,14,16,14,16,14,16,14,16,14,8,1,8,12,8,2,8,12,8,2,8,12,8,2,9,10,9,3,8,10,8,4,9,8,9,5,10,4,10,6,24,7,22,9,20,11,18,13,16,16,12,20,8},
{27,13,4,21,7,17,10,14,13,11,16,10,17,10,17,10,17,10,17,11,6,2,8,11,3,5,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,10,134,1,26},{28,9,9,16,14,11,19,8,21,6,23,5,23,5,24,4,9,6,9,4,7,9,9,3,7,10,8,3,7,10,8,3,7,10,8,3,7,10,8,4,6,10,8,19,9,19,8,19,9,18,10,17,10,17,11,16,11,16,11,16,11,16,11,16,11,16,11,16,11,5,5,6,11,5,7,4,11,6,7,3,11,7,7,2,11,8,7,1,11,9,147,1,27},
{28,9,10,14,16,10,20,7,22,6,23,5,24,4,24,4,8,7,10,3,7,9,9,3,7,10,8,3,7,10,8,4,6,10,8,20,8,20,8,19,8,19,9,12,15,12,15,13,14,14,15,13,16,13,16,19,10,20,8,20,9,20,8,20,8,20,8,20,8,19,9,2,3,13,10,1,8,8,10,2,26,2,25,2,26,3,24,4,22,9,17,14,11},
{30,17,5,24,7,22,8,21,9,20,10,19,11,19,11,18,12,17,13,16,14,15,15,14,16,14,8,1,7,13,8,2,7,12,8,3,7,11,8,4,7,10,9,4,7,10,8,5,7,9,8,6,7,8,8,7,7,7,180,15,8,22,8,22,8,22,8,22,8,22,8,16,20,9,21,9,21,9,21,9,21,10,20},
{28,3,22,6,23,5,23,5,23,5,23,5,22,6,7,21,7,21,7,21,7,21,7,21,7,20,8,2,8,10,20,8,22,6,23,5,24,4,24,4,25,3,8,7,10,6,2,11,9,20,9,20,8,20,8,20,8,20,8,20,8,20,8,3,1,15,9,2,4,12,9,2,8,7,11,2,26,2,25,2,25,4,23,6,21,9,17,15,10},
{29,20,6,18,11,15,15,12,17,10,19,9,20,8,20,8,16,12,12,16,11,18,9,19,9,20,8,20,8,21,8,21,7,4,8,10,7,2,13,6,25,4,26,3,27,2,27,2,12,6,10,1,10,9,9,1,9,11,17,13,16,13,16,13,8,1,7,13,8,1,7,13,8,1,8,11,9,1,9,9,9,3,10,5,11,4,25,4,24,6,22,8,20,10,18,13,14,18,8},
{28,0,27,1,139,1,7,11,9,1,7,11,9,1,7,10,9,2,7,10,9,2,7,10,8,3,7,9,9,3,7,9,8,4,7,8,9,5,5,9,9,19,8,19,9,19,8,19,9,19,8,19,9,19,9,19,8,19,9,19,8,19,9,19,8,20,8,19,8,20,8,19,9,19,8,20,8,19,8,20,8,20,7,21,7,23,5},
{28,10,9,17,13,13,17,10,19,8,21,6,23,5,23,5,9,5,9,4,9,7,9,3,8,9,8,3,8,9,8,3,8,9,8,3,8,9,8,3,8,9,8,4,8,7,8,5,9,5,9,6,21,8,19,10,17,11,17,9,21,6,23,4,9,6,10,2,8,10,8,2,8,10,17,12,16,12,16,12,16,12,17,10,18,10,9,1,10,6,10,2,26,3,24,4,24,5,22,7,20,10,16,15,10},
{28,9,9,17,13,13,17,10,19,8,21,6,23,4,24,4,10,6,9,3,9,8,9,1,9,10,8,1,8,12,7,1,8,12,7,1,8,12,16,12,16,12,17,10,9,1,8,9,10,1,10,6,11,2,26,2,26,3,25,4,24,6,12,2,8,8,8,4,7,21,7,20,8,20,8,19,8,19,9,17,10,16,12,12,15,8,19,8,19,9,18,10,16,12,14,14,12,17,6},
{21,15,4,16,6,13,8,12,10,10,11,9,12,8,12,8,11,9,11,9,11,10,10,10,10,11,9,11,9,12,8,12,9,12,8,12,9,12,8,13,8,13,8,12,9,12,8,13,8,13,8,13,8,13,8,13,8,13,8,13,8,13,8,13,8,14,8,13,8,13,8,13,9,13,8,13,9,12,9,13,9,12,10,12,9,13,9,12,10,12,11,11,11,11,11,11,12,10,11,11,10,12,9,13,7,16,4,19,1},
{21,2,4,16,6,14,9,12,10,11,11,10,12,10,12,11,11,11,11,11,10,12,10,12,10,12,9,13,9,13,8,13,9,13,8,13,9,13,8,13,8,13,8,13,9,13,8,13,8,13,8,13,8,13,8,13,8,13,8,13,8,13,8,13,8,12,8,13,8,13,8,12,9,12,8,12,9,12,9,11,9,11,10,10,10,11,9,10,11,9,11,9,11,9,11,8,12,9,11,10,10,11,9,13,7,15,4,18,1},
{27,11,5,21,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,10,189,10,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,21,5},
{28,1,26,1,140,1,32},
{26,11,4,21,6,20,7,18,8,18,8,19,7,19,6,11,5,4,6,5,4,2,6,3,6,3,16,2,5,1,24,1,62,1,24,7,14,15,8,17,11,14,13,11,8,1,7,9,8,2,8,8,8,2,9,6,8,4,8,6,8,4,8,7,7,5,7,8,5,6,6,10,3,9,2},
{28,22,4,24,6,21,7,21,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,21,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,22,6,23,5}});

这里缩了一点点，删掉了最后一个数字，即忽略掉了最后的若干个 0，因为初始就会填充为 0.

大概？我也不知道为什么没有 push_back 能行，反正过了。

2022/10/27 更新

这是一个 STL 特性，因为 vector<> 对 bool 类型特化，使用 64 位整数（取决于机子，如果是 32 位机子就 32 位整数，跟 bitset<> 一个道理），来储存信息。

这就会导致其实我们的 vector 长度如果小于 64 的话实际上对于内存而言没什么意义，因为它至少要开一个整数。

而显然的，我们字符集中的字符宽度小于 64（哪怕 32 也恰好没到），所以每一行都只会使用一个整数储存。

这就意味着，虽然我们的最后一行没有 push_back，但是内存是存在的，所以我们在访问这些位置时不会越界，而只是会得到随机值（访问未初始化内存）。

但这无关紧要，因为它一定会被降噪干掉。

所以如果你使用 int 存，但是提前 reserve 一下的话，大概也是这个效果吧。

重构与优化

  1. 我们把 expand 优化了（因为只在类的内部调用了两次，而且 API 还不是很合适，所以给它内联掉）。

  2. 我们把 get 优化了（因为只在类的内部调用了一次，所以给它内联掉）。

  3. 因为 push_back 与 emplace_back 太多了，所以全部替换成 #define eb emplace_back。

  4. 返回值可以用 auto。

  5. 我们发现 rotate 与 cut 包含大量重复代码，所以我们可以：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    template<class T>image trans(T func){
        vector<pair<int,int>> point;
        sqr out={INF,-INF,INF,-INF};
        foreach([&](int x,int y){
            if(!raw[x][y]) return;
            auto p=func(x,y);
            // 对坐标进行变换，返回一个 pair<double,double> 表示新坐标
            point.eb(p);
            out+=p;});
        image re(out.x1-out.x0,out.y1-out.y0);
        for(auto i:point)
            re[i.first-out.x0][i.second-out.y0]=1;
        return(re);
    }

    然后 rotate 变成这样：

    1
    2
    3
    4
    5
    6
    auto rotate(db ang){
        ang=ang/180*pi;
        db csa=cos(ang),sia=sin(ang),cex=rx/2.,cey=ry/2.;
        return(trans([&](int x,int y){
            return(make_pair((x-cex)*csa+(y-cey)*sia+cex,-(x-cex)*sia+(y-cey)*csa+cey));}));
    }

    cut 这么写：

    1
    2
    3
    auto cut(db cx,db cy){
        return(trans([&](int x,int y){return(make_pair(x+y*cy,y+x*cx));}));
    }

  6. 优化最后的计算代码。

  7. 其他非常多的优化，有兴趣的话还是翻到下面见源码吧。

最后一步

把所有的空格缩进换成 Tab （大雾）。

后记

你怎么这么多后记！

感谢 @xiyihan 的题解提供的思路 以及让我看到了这道题是可以写的。

在没有过多的牺牲代码的可读性的前提下（没有过于奇怪的变量名以及过度离谱的压行），最终得到的代码约有 的有效代码以及 的数据。

用 Clang 提交最慢的数据点耗时 ，总的效率还是不错的。

完整代码见提交记录。

再复读一遍愚蠢的 GCC：

Python 占据最短提交第一的历史，终于结束了。虽然我估摸着很快就会有人给我干掉。

论如何在 8k 以内解决战斗

额，我们直接进入正题吧。

但是我们并不满足于 的压缩率。

以下“压缩组”指游码得到的一个数，即一个表示一块相同颜色的大小的数。

我们观察压缩表，发现里面有大量的一位数与二位数，实际上，使用优秀的文本编辑器我们可以快速看出里面最大的二位数是一个 ，而第二大的是 。

而三位数并没有几个，最大的是 。

这启发我们可以将小数字压缩起来，我们按照 为一个单位放入数字（恰好可以放入 ），如果数字大于 就强制完成当前数字，注意如果出来的数字小于 则需要还原回去（似乎实战并没有这种情况）。

需要注意的是 unsigned long long 有 ，对 取模余 ，这样最后一个数字可能差 写不进去，但也有可能能写进去（能写进去即小于 ），这需要判断一下。

解码仍比较简单，我们对于小于 的数直接按照一个压缩组处理，对于大于等于（虽然也没有等于）的数按照 为一节从低到高拆开，然后依次作为压缩组处理即可。为了照顾解码器，我们选择将靠前的数字放到小端，这顺便可以解决数字 游码压缩后第一个数为 的问题。

将较大的数字按照 进制输出，最终压缩率大约为 。

压缩器代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
using uni=unsigned long long;
const int FSIZE=1<<20;
const uni INF=0xffffffffffffff;
vector<uni> ans;
char BuF[FSIZE],*InF=BuF;
void push(uni &x){
    if(x>189) ans.push_back(x);  // 如果大于等于 190 则直接放入
    else if(x)  // 否则进行解构，还原成原始状态
        for(;x;x>>=4)
            ans.push_back(x&15);
    x=0;
}
int main(){
    for(;~scanf("%s",InF);*InF++='\n') for(;*InF;++InF);
    bool p=0;
    uni rest=0,t=0,now=0;
    for(InF=BuF;*InF;++InF){
        for(;*InF<33&&*InF;++InF);
        if(*InF!='.'&&*InF!='#') continue;
        if((*InF=='#')==p) ++now;
        else{
            if(now>32||t>60||(t==60&&now>15)){  // 因为过大或溢出而不能放入压缩数中
                push(rest);
                t=0;
            }
            if(now<32){  // 能放入压缩数中
                rest+=now<<t;
                t+=5;
            }else{
                push(rest);
                t=0;
                ans.push_back(now);
            }
            now=1;
            p^=1;
        }
    }
    if(now>32||t>60||(t==60&&now>15)){
        push(rest);
        t=0;
    }
    if(now<32){
        push(rest+=now<<t);
    }else{
        push(rest);
        ans.push_back(now);
    }
    for(auto i:ans){
        if(i<10000000000){
            printf("%llu,",i);
        }else{
            printf("0x%llx,",i);
        }
    }
}

解压器（即 image 类的构造函数）如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct image{
    // ......

    image(initializer_list<uni> v){
        int i=0;bool p=0;auto k=v.begin();
        raw.resize(1);
        auto get=[&](int k){
            for(int j=0;j<k;++j){
                raw[i].eb(p);
                if(raw[i].size()==ry) raw.resize(++i+1);
            }
            p^=1;};
        for(ry=*k;++k!=v.end();)
            if(*k<190) get(*k);
            else for(uni x=*k;x;x>>=5) get(x&31);
        raw.pop_back();
        null.resize(rx=raw.size());
        for(int i=0;i<rx;++i) null[i].resize(ry);
    }
}

最终得到的压缩表如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<image> charset({
{30,0x7b268b936106510b,0x852089424aa228d8,0x243102431024a923,0x741d0741c80a188,0x741d0741d0741d0,0x812188121880a1d0,0x84910a40d2a4890c,0x5d1363e0ca228a9,9274147250,11},
{27,0xa8aa0b6b9513d48d,0x828d681197154551,0x44d1344d1344d13,0x44d1344d1344d13,0x44d1344d1344d13,0x291344d13,134,833},
{28,0xb96e6aa26b74129,0x38d293912649305,0x38d0a38d0a38d0a,0x4cd134cd0a3110a,0x5c1705c17154552,0x598a55c1705c170,0x588e758ce6590e5,9798888,147,865},
{28,0x4c16e6b1e8a83949,0x851c6949c6a3a098,0x45114428c4428e3,0xd7b9cd7b1ec4cd13,0x8a2289a228a9c1b0,0x84054d1893345114,0x4d8981e8591684a,339409},
{30,0x5cd544d5163e0b1,0xe839ef741b164973,0x859c6861c4869c28,0x6424e5428e44a8e4,242458887,180,0x45916459164590f,0x1a2aa9aa6a9aa690},
{28,0x6b16e5b96e5b9ac3,0x8a1ea7a9ea7a9ea7,0x4c1305b9ac8a2902,0x8a2689588ca3a079,0xf08d144511445114,0x1684b3a04961049,0x529f14d4d726459},
{29,0x8a266a8b1ef5c8d4,0x8a266992e0c64114,0x6688ea410f545514,0xa0a8cc16c5b1e899,0x14360d8362b48529,0x90a5680a1a70a1a7,0x8b1b04c916550d29,0x5224e6c954},
{28,1888,139,0x24a8e14ace14ace1,0x71a5271a14712547,0x44d292952839109,0x4cd3344d3344d33,0x451134cd134cd13,0x44d1444d3345113,0xe2dcf53d114},
{28,0x5b9aa89aa2d6c52a,0x84a0693a4892a4b7,0x3425034250342503,0x324a92a0e822128,0x925cd54c57154d15,0xc8322a4090a40946,0xa328295495164190,0xf82a87b1704c0f42,298},
{28,0x4b9aa89aa2d6c529,0x8524294246932898,0xc831013b1013b101,0xb3282a4a02954590,0x840986c1323d0b42,0x99a268a2287a9c88,0xa926689a1ec64151,0x91a2c73990},
{21,0x86256a5310d3408f,0x95a94a52d2b4ad0c,0xd4312c4312c4312b,0x86a1a86a189621a8,0xe4350d4350d4350d,0x9625a86a5a86a1a8,0xb5b14c4b52c5312d,0x76a58a5ad4c5ad6b,3198096},
{21,0xa6296b5312e34082,0x96298a6296b5ad6c,0xd4352d4352d4352d,0x86a1a86a1a96a1a8,0xc4350d4350d4350d,0x962588625886a1a8,0x95a56a4ad4a52d2b,0x76a56a52d2c42d2b,17877135},
{27,0x3d0f43d0f43d4ab,0xa3d0f43d0f4,189,0x3d0f43d0f43d0ea,0x2cb53d0f43d0f4},
{28,1857,140,865},
{26,0x3cd12448f43548b,0x330cc2214c42acd3,58758224,62,0x142dae5c50f71f01,0x8220c91210812127,0xa318a8394e741106,198947},
{28,0x3d1143d4f536096,0x3d1143d1143d114,0x450f4450f445114,0x450f4450f4450f4,0x3d1143d4f4450f4,0x3d1143d1143d114,0x451143d1143d114,0x450f4450f4450f4,0x54b7358f4}});

最后的代码长度 ，压缩表 。

完整代码仍然是见 AtCoder 上的提交记录，不过这份代码的压缩表有一点点小问题，比上面给的多了 。

Anything More Exciting?

到这一步我其实不大会了，但是还是有一些不那么聪明的办法继续压缩。

我们发现我们的数字都是 进制，而且还有很多凑数的 0x 占位符。而众所周知，ASCII 有 个可见字符和一个可以显示为一个奇怪的东西的 0x7f（也就是说我们实际上有 个可用字符）。我们可以把数字转换成 进制（去掉一个分隔符），然后把空格当作分隔符整个放入字符串中，这样就可以做到 的压缩率。

表长度 ，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<image> charset({
{30,"/(Z>k5rpG- 05|Tes`Cbl %.)|F7>Tu5 oo3$s$lNM oo3$s/)(] /iV1d;jA>K 0/t0K-(usu `2O#f.n=G S%2Op3 "},
{27,"4;{D@&Ol^x /xoT%W-H Oe%.AxXC5 Oe%.AxXC5 Oe%.AxXC5 \"ID8yq \"H )j "},
{28,"+Mm-u+r60= 05kx9`fP'\\ (l?:yvmH\\( 4;|B@rIg:# _QwDo9;'' ,[0E@,wQP6 Sh:[IpOZP \"U *+ "},
{28,")cKS}@p1aD 05kx9`@[os Ou2:MXQ0| 9`+Zk=.dpe 0lBpTs;8Fp 0)zxq3Q?Gt U]FR>4oH. FZf "},
{30,"`\"pAl[\\K# ;U@Xq(T{S6 0;5oU%v}!m ,Ke6O>2pa( #}l8n \"v P6LVwNc`t #4ySB5i,x "},
{28,"-8/eJXT]M8 0l32ni_ecN )c;vg@iA.j 0lR{i<~bGD <PhMqXvpa; 0<5X1fSWr Y);f+{U:* "},
{29,"0lRMbF!8wy 0lRL7Yx_SH ,eb&_jD~Vh 3D!XEg<#NV #>Rj1Z7L*b 1T(FG.o^*z 0vvDh$?P\\d NYT%H` "},
{28,"4t \"M %32,I{nYnJ -C1BZI\"y/ OeEu3c$?{ U/M^Xc}Q> Ou0p'}`{+ Oe&]KK|_d 64j90R$ "},
{28,"+M|;cpYJ[F 00S,13#;^b &|D-U=zs\\? C.=c-%,17 1feVt=l2qQ 7uJ6=&~X}V 3_-]065<>e =DM\"WnRe=Y $. "},
{28,")^1i*Xxot+ 06,/jya!3S 7uEU#Pb}jU 5Nx13cQ{?C 0*,{fU\"MZY 2Vcx.kHhAS 4A6]cbs'j4 qpQpj< "},
{21,"0A$&=F3'Ba 2+U;$UvGD/ 99fCq\"2p_~ 0F=p1!?(*p ;)aRed1r)W 20oUjR3+f* 5jLYN_H`p2 .Va|8bD*3+ $fC1 "},
{21,"3j7^;;Iyw 204P[FOo4 99vP~Sd5*W 0F=p1!f8a> 7J+NR4p][# 20o%s!.]h_ 2+E_4w$-Zf .VaLA1?Q?5 5qqD "},
{27,R"(JKhf2n"v; 0>qwv>q " JKhf2n"l0 "v42HHf&g )"},{28,"4U \"N *+ "},
{26,"J<*z]Vh( &pNR}bx5_b eSZ\\ _ #>1#V6Hu.5 /tF\">9a{Ct 3^N.E-.1}M 7%2 "},
{28,"JL9YFlFi\" JL9Y:!~TT OtaHl7%r OtaHl7%R JL9YFk8F* JL9Y:!~TT Ou27IYGzC OtaHl7%R #z3[eZ "}});

理论上还可以做的更绝一点，我们可以将 ASCII 前面 个字符（除去空字符）全部用出来（前面的字符也能显示为奇怪的东西），做到 进制。但是我试了试似乎不是很行（可能是编辑器的锅，也有可能是编译器），而且只能节省 个字符，所以还是算了吧。

而后面的字符会出更多的问题，它们很容易被解释为 UTF-8 编码然后导致解码失败，就算本地能行（而且其实本地也很难复制这些字符，要实现可能得直接改二进制文件），复制粘贴到浏览器环境中也很有可能寄掉。

2022/8/2 更新

事实上，由于不同 cv 限定符的同一类型作为参数允许同时出现在同一函数的重载中，所以我们可以将宽度信息当作一个压缩组编码进字符串中。

发现这样十分有效，而且把新的解码器写出来，发现解码器只多了 （雾）。

大概是我的码风问题。

一个更有趣的是，接下来我们将 进制换成 进制，得到的结果更短。

小编也很惊讶.jpg

因为实操的时候，转换出的字符串并不能完美地直接使用，其中存在的 "\ 两种字符需要转义，所以会产生一点细微的差别。

原始字符串字面量可以解决这个问题，但是一个代价 有点贵。

我们发现字体的一些极小的空白会影响我们的压缩（游码的特性），但是对匹配的影响不大，所以可以滤除一些空白。

影响不一定都是负面的，需要一个一个地尝试来确定。

然后使用 unsigned __int128！

最终，我们的表长 ，压缩率为 。

不过因为一些原因，以下提交记录的表长为 。

2022/10/27 更新

由于有了上面的结论，所以我们可以将最后一个压缩组省掉，对于最后一个压缩组为 #，我们直接向本源图像人为添加一个 . 即可。

表长 ，乍看起来好像有优化一样。

2022/11/11 更新

我试了试，可以把所有的字符都用上，只要没有空字符都能简单搞，带空字符的话就要直接改二进制文件。

于是我们压缩有两个参数，进制（使用的最大字符数量）与位移（分隔符的 ASCII 码，从分隔符之后选取字符）。

经尝试使用 进制，分隔符为 是最优的（\" 与 \n 与 \r 较少），共 ，压缩率来到 。

（虽然 但是最高位的数个字符都没有用上，所以没有问题，总之我也觉得挺神奇的）。

但是非常不幸的是，这份压缩表并不能在 Linux 上运行（只有 Western Windows-1252 能支持这个压缩表）。

但是不论怎么样，这仍然是一个巨大的进步。

2022/11/12 更新

那怎么办呢，我没辙了。

只能考虑有损压缩了（其实之前也算是有损压缩吧，虽然损失大概可以算是忽略不计）。

我们有两条路径：

  1. 把图像缩小。

    具体什么效果我不清楚，因为我走的另一条路径。

  2. 调整压缩组

    不知道在什么精神状态下想出来的奇异方法。

    考虑如果我们每个压缩组都是偶数的话（其实本来想的是奇数的，因为奇数的压缩组比偶数的多，但是有一个 bug 级的 所以没办法），那么我们就可以把最后一位省掉。

    具体的调整方法就遇到大于 的奇数就减一，然后再遇到就加回去，然后对于 强制加一。

    然后全部除二，你发现大部分的数都小于等于 ，所以我们整一个 进制即可。

    由于宽度都大于 ，所以你发现对于第一位一定恰好是一个字符表示宽度，所以可以将其后的分隔符删去。

    出来的图像是这样的：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    ............####...........
    ...........######..........
    ........##########.........
    .....############..........
    ..################.........
    .################..........
    ##################.........
    .################..........
    ##################.........
    .######..########..........
    ..##......########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ..........########.........
    .........########..........
    ###########################
    ###########################
    ###########################
    ###########################
    ###########################
    #########################..

    但是在降噪的鼎力相助下反正是过了。

然后又研究一些语法总之是压下去了，删掉了（最后）一个优化，幸好只跑了 。

其实可以两种压缩方法结合一下，但是我已经把整个代码压缩得少于 了，就不管了。

压缩情况：

  • Windows：，压缩率 。
  • Linux：，压缩率 。

最后的最后

不后记了是吧。

这道题作为一道大模拟写起来其实非常舒服（至少我觉得很舒服），尤其地考验了对与 STL 库、模板等 C++ 特性的理解（大概？）。

但是耗时还是确实耗时的，而且万一思路不是非常好的话会寄的很难受。

对于图像压缩的思考确实非常有趣，我觉得下次可以出一个给定图像，要求提交程序输出该图像，按照程序长度评分这样的题目。

以下是开始的一些尝试的进程（前八份代码可读，至少本人可读）：

  1. （）提交记录
  2. （）提交记录
  3. （）提交记录
  4. （）提交记录
  5. （）提交记录
  6. （）提交记录
  7. （）提交记录
  8. （）提交记录
  9. （）提交记录

Linux 下可运行的代码目前为 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#import<bits/stdc++.h>
#define E emplace_back(
#define V vector
#define B back()
#define P pop_back()
#define O auto
#define R return
#define F for
#define Z size()
#define G[&](I x,I y)
#define A r[x][y]
#define C(t,x)case t:u.B x##=n;break;
#define p(e)F(;v.Z&&e;v.P){I n=u.B;u.P;switch(v.B){C(2,+)C(3,-)C(4,*)C(5,/)}}
#define H(a,c)F(I a=0;a<c;++a)
using namespace std;using I=int;using d=float;struct _{I x,y;};struct g{I h,w=0;V<V<I>>r,n,v;O e(I x){n.resize(h=x);F(O&i:n)i.resize(w);}g(){char b[1<<21],*s=b;fread(b,1,2e6,stdin);F(r.E);s[2];++s)*s<33?r.E),0:r.B.E*s<46);w=r.B.Z;e(r.Z);}g(I x,I y){w=y+1;e(x+1);r=n;}g(O*s){I p=1;O g=[&](I k){F(p^=1,k+=k;k--;r.B.Z==w?r.E),0:0)r.B.E p);};r.E);w=*s-2;F(__int128 k=0;*++s;)if(*s>1)k=k*124+*s-2;else if(k<99)g(k),k=0;else F(;k;k/=14)g(k%14);e(r.Z);}struct z{I a,b,c,d;O k(z x){a=min(a,x.a);b=max(b,x.b);c=min(c,x.c);d=max(d,x.d);}};z m(I x,I y){z e{x,x,y,y};v[x][y]=1;H(i,3)H(j,3)if(I k=x+i-1,l=y+j-1;~k&&~l&&!v[k][l]&&r[k][l]==A)e.k(m(k,l));R e;}O f(O e){H(j,w)H(i,h)e(i,j);}O&e(){v=n;f(G{I c=0,k,l;H(i,3)H(j,3)c+=~(k=x+i-1)&&~(l=y+j-1)&&k<h&&l<w&&r[k][l];A=c>4;});R*this;}O s(){V<g>e;v=n;f(G{if(A&&!v[x][y])if(O[a,b,c,d]=m(x,y);d-c>5){g n(b-a,d-c);n.f(G{n.A=r[x+a][y+c];});e.E n);}});R e;}O t(O c){V<_>n;z o{h,0,w,0};f(G{if(A){O p=c(x,y);n.E p);o.k({p.x,p.x,p.y,p.y});}});g e(o.b-o.a,o.d-o.c);F(O i:n)e.r[i.x-o.a][i.y-o.c]=1;R e.e();}O i(I a,I b){g e(a++,b);f(G{e.r[(x*a-1)/h][y*b/w]|=A;});R e;}d m(g&x){I e=0,y=min(h,x.h)-1,z=min(w,x.w)-1;if(abs(w*x.h/d(h*x.w)-1)<.3){O a=i(y,z),b=x.i(y,z);a.f(G{e+=a.A==b.A;});}R(d)e/y/z;}};V<g>t[16],a={"Ph5o2m_1iy^r)A/v90Ztwp+j2SBFt:oNP9_8ZLaNiNg)5/D[","Pm,U'9),;c*}XO%8@gNUGo\\4=D:p{qO*CuiPuMf=e-wl@Zqj$+k@K","U=)Aef15RI` hZTovrWc_#","c","Lzh7<@,v9C:)NvBwb0#dJ8/_S4O",R"(*|#ztFb    g`3}^<	#7poL*K\|gVrLnd4}*
Wvc
vg4\tfN:)"," OM<h}8>@rIe#9P54!jS+x:aKK(<qcgv%pQTu|877wgQ>D","/$eB.pFhsL=:U-BK'xxkT*(R","Be+-#<n#8T@C(k^'RfR5#[.Oac    -\"M[py(XPt TY","A|Ob.&z&v,2n}{@<%xi)JHo60R|hJ9Uoe] \\V "," 0Cg`O'#QWu@b;k0A r\nIs\n9\\:lg`PanJP`U","0K\"fi$_e+_<aU4uP=&hZHG\\K^jONXnH","Ge}f\"i,w+rK?6E|wA8;:63dsl[EuUY%X$!)","U*?rrM3+SEh\"wIU<%R\\4DAZWC(]6\n_7iZW@]","6N`f<Y	A2G`v.dB&na%k/a6_`$^3<b#UC5O[dDDh4>tGk","O\r4ZWdpY1'KeLog841>|R-Ih[4['mOvs7G=,7[9x"};I w,z,c;V<I>u,v;main(){scanf("%*d%*d%*d ");H(i,16)H(j,13){d r=(j-6)*.05,c=cos(r),s=sin(r);O e=a[i].t(G{R _{x*c+y*s,y*c-x*s};});F(d a:{-.1,.1})F(d b:{-a,a})t[i].E e.t(G{R _{x+y*b,y+x*a};}));}F(O&i:g().e().s()){d m=0;H(j,16)F(O&k:t[j])if(d p=i.m(k);p>m)m=p,c=j;if(c>5)w=w*10+c-6,z=1;else{z?u.E w),z=w=0:0;if(c)p((c<4||v.B>3)&&v.B)c==1?v.P,0:v.E c);}}z&&u.E w);p(1)cout<<u.B<<endl;}

2022/10/27: 之前的代码出了问题，见谅，现在这个能通过所有数据。

2022/11/12: 的 提交记录，AtCoder 计算换行是按照 计算的，但这不影响我们冲进 。

2023/7/12: 的 提交记录

2023/8/11: 的 提交记录

2023/10/19: 的 提交记录

2023/12/21: 的 提交记录

Windows 下可运行的代码目前为 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#import<bits/stdc++.h>
#define E emplace_back(
#define V vector
#define B back()
#define P pop_back()
#define O auto
#define R return
#define F for
#define Z size()
#define G[&](I x,I y)
#define A r[x][y]
#define C(t,x)case t:u.B x##=n;break;
#define p(e)F(;v.Z&&e;v.P){I n=u.B;u.P;switch(v.B){C(2,+)C(3,-)C(4,*)C(5,/)}}
#define H(a,c)F(I a=0;a<c;++a)
using namespace std;using I=int;using d=float;struct _{I x,y;};struct g{I h,w=0;V<V<I>>r,n,v;O e(I x){n.resize(h=x);F(O&i:n)i.resize(w);}g(){char b[1<<21],*s=b;fread(b,1,2e6,stdin);F(r.E);s[2];++s)*s<33?r.E),0:r.B.E*s<46);w=r.B.Z;e(r.Z);}g(I x,I y){w=y+1;e(x+1);r=n;}g(O*s){I p=1,c;O g=[&](I k){F(p^=1,k+=k;k--;r.B.Z==w?r.E),0:0)r.B.E p);};r.E);w=*s-2;F(__int128 k=0;c=(uint8_t)*++s;)if(c>1)k=k*254+c-2;else if(k<99)g(k),k=0;else F(;k;k/=14)g(k%14);e(r.Z);}struct z{I a,b,c,d;O k(z x){a=min(a,x.a);b=max(b,x.b);c=min(c,x.c);d=max(d,x.d);}};z m(I x,I y){z e{x,x,y,y};v[x][y]=1;H(i,3)H(j,3)if(I k=x+i-1,l=y+j-1;~k&&~l&&!v[k][l]&&r[k][l]==A)e.k(m(k,l));R e;}O f(O e){H(j,w)H(i,h)e(i,j);}O&e(){v=n;f(G{I c=0,k,l;H(i,3)H(j,3)c+=~(k=x+i-1)&&~(l=y+j-1)&&k<h&&l<w&&r[k][l];A=c>4;});R*this;}O s(){V<g>e;v=n;f(G{if(A&&!v[x][y])if(O[a,b,c,d]=m(x,y);d-c>5){g n(b-a,d-c);n.f(G{n.A=r[x+a][y+c];});e.E n);}});R e;}O t(O c){V<_>n;z o{h,0,w,0};f(G{if(A){O p=c(x,y);n.E p);o.k({p.x,p.x,p.y,p.y});}});g e(o.b-o.a,o.d-o.c);F(O i:n)e.r[i.x-o.a][i.y-o.c]=1;R e.e();}O i(I a,I b){g e(a++,b);f(G{e.r[(x*a-1)/h][y*b/w]|=A;});R e;}d m(g&x){I e=0,y=min(h,x.h)-1,z=min(w,x.w)-1;if(abs(w*x.h/d(h*x.w)-1)<.3){O a=i(y,z),b=x.i(y,z);a.f(G{e+=a.A==b.A;});}R(d)e/y/z;}};V<g>t[16],a={"�����}�v�W���)P !\n�0����X����,~W��n�4�Cc��*�","���\n����9M1��Ø}��    �;<��q��/�{2b���N�&3","g��^yy)��`�? ����u�","c","���Z�e���+:�C�=܊7�X!&�&K�S","\\����~lJ-I#E����ъB�	�]G[�O�?���*Q���"," C��j7s�?���j�>��1~��o$����PѤ�J�N=���ġ���8�","W�ﳱ��j�x�ޡ^W���a��7#p]O��.�R","@u�����bx��A�jQ��)�-�N�X4g��V��<�Y","�vX7��c��6.%�*I�n($���^f��G���/�`n�"," N�_6�	�<��&p`�#Qq�l\\\nlN�)'�6{7","G��Э~��\\����pHAڐN�@�f�ص8���w�x","�a˲`���Z� �5q�C�KWr��I2�R�[[S�I���D","UHp��ދ)MB�9I�q�#�L('x�r���:�","A�x[-�^�'�-J�O`���^<���~Fg�P��<b1g>��NV","CUhݡqU�f|�^)�o�[�+B6��&S�_�^��ϟ�0��l��",};I w,z,c;V<I>u,v;main(){scanf("%*d%*d%*d ");H(i,16)H(j,13){d r=(j-6)*.05,c=cos(r),s=sin(r);O e=a[i].t(G{R _{x*c+y*s,y*c-x*s};});F(d a:{-.1,.1})F(d b:{-a,a})t[i].E e.t(G{R _{x+y*b,y+x*a};}));}F(O&i:g().e().s()){d m=0;H(j,16)F(O&k:t[j])if(d p=i.m(k);p>m)m=p,c=j;if(c>5)w=w*10+c-6,z=1;else{z?u.E w),z=w=0:0;if(c)p((c<4||v.B>3)&&v.B)c==1?v.P,0:v.E c);}}z&&u.E w);p(1)cout<<u.B<<endl;}

本当の本当に終わり

后附文件

感谢你看到这里。

如果想尝试这题，以下可能有帮助。

不再维护的某个版本的最短代码可读版（去除了压缩表，包含两种解码，为了保留代码原貌，有些地方不是很可读）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include<bits/stdc++.h>
using namespace std;
struct image{
    int h,w=0;
    vector<vector<bool>> raw,null,vis;
    void empty(int x){    // 初始化 null 数组
        null.resize(h=x);
        for(auto &i:null) i.resize(w);
    }
    image(auto *s){    // 从字符集直接构建图片
        for(raw.emplace_back();*s;++s)
            *s<33?raw.emplace_back(),0
                :raw.back().emplace_back(*s<46);

        // 最后一行会多一个换行，将其弹出
        raw.pop_back();

        w=raw.back().size();
        empty(raw.size());
    }
    image(int x,int y){    // 从长宽构建图片
        w=y+1;
        empty(x+1);
        raw=null;
    }
    image(const auto *s){
        int p=1,c;

        // 处理单个压缩组
        auto get=[&](int k){
            for(p^=1,k+=k;k--;
                raw.back().size()==w?
                    raw.emplace_back(),0:0)
                raw.back().emplace_back(p);
            };

        raw.emplace_back();
        w=*s-2;
        // For Linux version
        for(__uint128_t k=0;*++s;)
            if(*s>1)k=k*124+*s-2;    // 124 进制，分隔符为 1
            else if(k<99)get(k),k=0;
            else for(;k;k/=14)get(k%14);

        // For Windows version
        for(__uint128_t k=0;c=(uint8_t)*++s;)    // 注意这里需要将 char 强转为 unsigned char
            if(c>1) k=k*254+c-2;    // 254 进制，分隔符为 2
            else if(k<99) get(k),k=0;
            else for(;k;k/=14) get(k%14);

        empty(raw.size());
    }
    struct out{    // 图像边缘类
        int a,b,c,d;
        // a 表示 x 轴左边缘
        // b 表示 x 轴右边缘
        // c 表示 y 轴下边缘
        // d 表示 y 轴上边缘
        void add(out x){
            a=min(a,x.a);
            b=max(b,x.b);
            c=min(c,x.c);
            d=max(d,x.d);
        }
    };
    out find(int x,int y){    // 遍历连通块，返回其四边范围
        out re{x,x,y,y};
        vis[x][y]=1;
        for(int i:{-1,0,1})
            for(int j:{-1,0,1})
                if(int k=x+i,l=y+j;
                    ~k&&~l&&k<h&&l<w&&!vis[k][l]&&raw[k][l]==raw[x][y])
                    re.add(find(k,l));
        return re;
    }
    template<typename T>void foreach(T func){    // 遍历整个图像
        // 注意这里的遍历顺序是先列后行，这是为了分离图像的时候也能使用这个 API
        for(int j=0;j<w;++j)
            for(int i=0;i<h;++i)
                func(i,j);
    }
    image& reno(){    // 降噪
        vis=null;
        foreach([&](int x,int y){
            int c=0,k,l;
            for(int i:{-1,0,1})
                for(int j:{-1,0,1})
                    c+=~(k=x+i-1)&&~(l=y+j-1)&&k<h&&l<w&&raw[k][l];
            raw[x][y]=c>4;});
        return *this;
    }
    vector<image> split(){    // 分离图像
        vector<image> re;
        vis=null;

        // 注意如果 foreach 是先行后列的，那么这里就不能使用，必须先列后行
        foreach([&](int x,int y){
            if(raw[x][y]&&!vis[x][y])
                if(auto [a,b,c,d]=find(x,y);(b-a)*(d-c)>80){    // 如果联通块过小，放弃
                    image now(b-a,d-c);

                    // 遍历整个矩形范围，然后 copy
                    now.foreach([&](int x,int y){now.raw[x][y]=raw[x+a][y+c];});
                    re.emplace_back(now);
                }});
        return re;
    }
    template<typename T>image trans(T c){    // 根据给定函数进行图像变换
        vector<pair<int,int>> point;
        out side{h,0,w,0};
        foreach([&](int x,int y){
            if(raw[x][y]){
                pair<int,int> p=c(x,y);
                point.emplace_back(p);
                side.add({p.first,p.first,p.second,p.second});    // 把四边记录下来
            }});

        // 将所有点整体位移至合法范围，然后放入新图中
        image re(side.b-side.a,side.d-side.c);
        for(auto i:point)
            re.raw[i.first-side.a][i.second-side.c]=1;
        return re.reno();    // 最后降噪
    }
    auto fit(int a,int b){    // 将图像缩放为给定大小
        image re(a,b);
        foreach([&](int x,int y){
            if(raw[x][y])
                re.raw[ceil(x*a/float(h-1))][ceil(y*b/float(w-1))]=1;
        });
        return re;
    }
    float match(image& x){    // 对给定图像进行匹配，返回实数作为匹配率
        int re=0,y=min(h,x.h)-1,z=min(w,x.w)-1;
        if(abs(w*x.h/float(h*x.w)-1)<.3){    // 对于长宽差异过大，放弃
            auto a=fit(y,z),b=x.fit(y,z);    // 变换为同一长宽
            // 暴力匹配
            a.foreach([&](int x,int y){re+=a.raw[x][y]==b.raw[x][y];});
        }
        return(float)re/y/z;    // 其实这里的 y,z 应该加一的，所以这样会有大于 1 的匹配率
    }
};
vector<image> t[16],a={

/*压缩表*/

};
int now=0,num=0,bestnum;
vector<int> st0,st1;
char BuF[1<<21];

// 判断运算符号，然后将数字栈顶与下一个栈顶运算
#define calc(t,x)case t:st0.back()x##=top;break;

// 连续弹出符号栈直到其优先级高于自己
/* 优先级为：(     0
           ) + - 1
           * /   2
*/
// 越小越高
#define pops(e)\
    for(;st1.size()&&e;st1.pop_back()){\
        int top=st0.back();\
        st0.pop_back();\
        switch(st1.back()){\
            calc(12,+)\
            calc(13,-)\
            calc(14,*)\
            calc(15,/)\
        }\
    }
int main(){
    scanf("%*d%*d%*d ");
    fread(BuF,1,2e6,stdin);
    for(int i=0;i<16;++i)
        for(int j=-15;j<16;j+=3){    // 从 -15 到 15 度，分度值为 3
            float r=j*acos(-1)/180,c=cos(r),s=sin(r);

            // 旋转变换
            auto e=a[i].trans(
                [&](int x,int y){return make_pair(x*c+y*s,y*c-x*s);});
            for(float a:{-.1,.1})
                for(float b:{-a,a})
                    // 剪切变换
                    t[i].emplace_back(
                        e.trans(
                            [&](int x,int y){return make_pair(x+y*b,y+x*a);}));
            t[i].emplace_back(e);
        }
    for(auto &i:image(BuF).reno().split()){
        float bestmatch=0;
        for(int j=0;j<16;++j)
            for(auto &k:t[j])
                if(float p=i.match(k);p>bestmatch)
                    bestmatch=p,
                    bestnum=j;

        // bestnum 对应字符为 "0123456789()+-*/"[bestnum]
        if(bestnum<10) now=now*10+bestnum,num=1;
        else{
            // 如果有数字，将其压入栈
            if(num)
                st0.emplace_back(now),
                num=now=0;

            // 如果不是左括号，尝试弹栈
            if(bestnum>10)
                pops((bestnum<14||st1.back()>13)&&st1.back()>10)

            // 如果是右括号，把栈顶的左括号弹出，否则入栈
            bestnum==11?
                st1.pop_back(),0:
                st1.emplace_back(bestnum);
        }
    }
    if(num) st0.emplace_back(now);
    pops(1)    // 全部弹栈
    cout<<st0.back()<<endl;
}

数据生成器（可以生成单个字符，并进行测试，注意需要调整被测试代码直接输出匹配字符串）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<cmath>
#include<vector>
#include<string>
#define cmin(x,y) if(x>y) x=y;
#define cmax(x,y) if(x<y) x=y;
#define eb emplace_back
using namespace std;
using db=double;
using uni=unsigned long long;
const int FSIZE=1<<26,INF=0x7fffffff,fx[8][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
const db pi=acos(-1);
struct image{
    int rx,ry;
    vector<vector<bool>> raw,null,vis;
    image(int x,int y){
        raw.resize(rx=x+1);
        ry=y+1;
        for(int i=0;i<=x;++i) raw[i].resize(y+1);
        null=raw;
    }
    image(initializer_list<uni> v){
        int i=0;bool p=0;auto k=v.begin();
        raw.resize(1);
        auto get=[&](int k){
            for(int j=0;j<k;++j){
                raw[i].eb(p);
                if(raw[i].size()==ry) raw.resize(++i+1);
            }
            p^=1;};
        for(ry=*k;++k!=v.end();)
            if(*k<190) get(*k);
            else for(uni x=*k;x;x>>=5) get(x&31);
        raw.pop_back();
        null.resize(rx=raw.size());
        for(int i=0;i<rx;++i) null[i].resize(ry);
        print();
    }
    auto &operator[](int x){return(raw[x]);}
    struct sqr{
        int x0,x1,y0,y1;
        void operator+=(sqr b){
            cmin(x0,b.x0)cmax(x1,b.x1)
            cmin(y0,b.y0)cmax(y1,b.y1)
        }
        void operator+=(pair<int,int> b){
            cmin(x0,b.first)cmax(x1,b.first)
            cmin(y0,b.second)cmax(y1,b.second)
        }
    };
    template<class T>void foreach(T func){
        for(int i=0;i<rx;++i)
            for(int j=0;j<ry;++j) func(i,j);
    }
    template<class T>auto trans(T func){
        vector<pair<int,int>> point;
        sqr out={INF,-INF,INF,-INF};
        foreach([&](int x,int y){
            if(!raw[x][y]) return;
            auto p=func(x,y);
            point.eb(p);
            out+=p;});
        image re(out.x1-out.x0,out.y1-out.y0);
        for(auto i:point)
            re[i.first-out.x0][i.second-out.y0]=1;
        return(re);
    }
    auto rotate(db ang){
        ang=ang/180*pi;
        db csa=cos(ang),sia=sin(ang),cex=rx/2.,cey=ry/2.;
        return(trans([&](int x,int y){
            return(make_pair((x-cex)*csa+(y-cey)*sia+cex,-(x-cex)*sia+(y-cey)*csa+cey));}));
    }
    auto cut(db cx,db cy){
        return(trans([&](int x,int y){return(make_pair(x+y*cy,y+x*cx));}));
    }
    auto fit(int rxt,int ryt){
        db delx=(db)(rxt-1)/(rx-1),dely=(db)(ryt-1)/(ry-1);
        return(trans([&](int x,int y){return(make_pair(ceil(x*delx),ceil(y*dely)));}));
    }
    void print(){
        foreach([&](int x,int y){
            putchar(raw[x][y]?'#':'.');
            if(y==ry-1) puts("");});
    }
};
vector<image> charset({{30,11,8,20,12,16,16,13,18,11,20,9,22,7,24,6,10,4,10,5,9,8,9,4,8,10,8,3,9,10,9,2,8,12,8,2,8,12,8,2,8,12,8,1,8,14,16,14,16,14,16,
14,16,14,16,14,16,14,16,14,16,14,16,14,16,14,8,1,8,12,8,2,8,12,8,2,8,12,8,2,9,10,9,3,8,10,8,4,9,8,9,5,10,4,10,6,24,7,22,9,20,11,18,13,16,16,12,20,8},
{27,13,4,21,7,17,10,14,13,11,16,10,17,10,17,10,17,10,17,11,6,2,8,11,3,5,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,19,8,
19,8,19,8,19,8,19,8,19,8,19,8,10,134,1,26},{28,9,9,16,14,11,19,8,21,6,23,5,23,5,24,4,9,6,9,4,7,9,9,3,7,10,8,3,7,10,8,3,7,10,8,3,7,10,8,4,6,10,8,19,9,
19,8,19,9,18,10,17,10,17,11,16,11,16,11,16,11,16,11,16,11,16,11,16,11,5,5,6,11,5,7,4,11,6,7,3,11,7,7,2,11,8,7,1,11,9,147,1,27},
{28,9,10,14,16,10,20,7,22,6,23,5,24,4,24,4,8,7,10,3,7,9,9,3,7,10,8,3,7,10,8,4,6,10,8,20,8,20,8,19,8,19,9,12,15,12,15,13,14,14,15,13,16,13,16,19,10,20,
8,20,9,20,8,20,8,20,8,20,8,19,9,2,3,13,10,1,8,8,10,2,26,2,25,2,26,3,24,4,22,9,17,14,11},
{30,17,5,24,7,22,8,21,9,20,10,19,11,19,11,18,12,17,13,16,14,15,15,14,16,14,8,1,7,13,8,2,7,12,8,3,7,11,8,4,7,10,9,4,7,10,8,5,7,9,8,6,7,8,8,7,7,7,180,
15,8,22,8,22,8,22,8,22,8,22,8,16,20,9,21,9,21,9,21,9,21,10,20},
{28,3,22,6,23,5,23,5,23,5,23,5,22,6,7,21,7,21,7,21,7,21,7,21,7,20,8,2,8,10,20,8,22,6,23,5,24,4,24,4,25,3,8,7,10,6,2,11,9,20,9,20,8,20,8,20,8,20,8,20,
8,20,8,3,1,15,9,2,4,12,9,2,8,7,11,2,26,2,25,2,25,4,23,6,21,9,17,15,10},
{29,20,6,18,11,15,15,12,17,10,19,9,20,8,20,8,16,12,12,16,11,18,9,19,9,20,8,20,8,21,8,21,7,4,8,10,7,2,13,6,25,4,26,3,27,2,27,2,12,6,10,1,10,9,9,1,9,11,
17,13,16,13,16,13,8,1,7,13,8,1,7,13,8,1,8,11,9,1,9,9,9,3,10,5,11,4,25,4,24,6,22,8,20,10,18,13,14,18,8},
{28,0,27,1,139,1,7,11,9,1,7,11,9,1,7,10,9,2,7,10,9,2,7,10,8,3,7,9,9,3,7,9,8,4,7,8,9,5,5,9,9,19,8,19,9,19,8,19,9,19,8,19,9,19,9,19,8,19,9,19,8,19,9,19,
8,20,8,19,8,20,8,19,9,19,8,20,8,19,8,20,8,20,7,21,7,23,5},
{28,10,9,17,13,13,17,10,19,8,21,6,23,5,23,5,9,5,9,4,9,7,9,3,8,9,8,3,8,9,8,3,8,9,8,3,8,9,8,3,8,9,8,4,8,7,8,5,9,5,9,6,21,8,19,10,17,11,17,9,21,6,23,4,9,
6,10,2,8,10,8,2,8,10,17,12,16,12,16,12,16,12,17,10,18,10,9,1,10,6,10,2,26,3,24,4,24,5,22,7,20,10,16,15,10},
{28,9,9,17,13,13,17,10,19,8,21,6,23,4,24,4,10,6,9,3,9,8,9,1,9,10,8,1,8,12,7,1,8,12,7,1,8,12,16,12,16,12,17,10,9,1,8,9,10,1,10,6,11,2,26,2,26,3,25,4,
24,6,12,2,8,8,8,4,7,21,7,20,8,20,8,19,8,19,9,17,10,16,12,12,15,8,19,8,19,9,18,10,16,12,14,14,12,17,6},
{21,15,4,16,6,13,8,12,10,10,11,9,12,8,12,8,11,9,11,9,11,10,10,10,10,11,9,11,9,12,8,12,9,12,8,12,9,12,8,13,8,13,8,12,9,12,8,13,8,13,8,13,8,13,8,13,
8,13,8,13,8,13,8,13,8,14,8,13,8,13,8,13,9,13,8,13,9,12,9,13,9,12,10,12,9,13,9,12,10,12,11,11,11,11,11,11,12,10,11,11,10,12,9,13,7,16,4,19,1},
{21,2,4,16,6,14,9,12,10,11,11,10,12,10,12,11,11,11,11,11,10,12,10,12,10,12,9,13,9,13,8,13,9,13,8,13,9,13,8,13,8,13,8,13,9,13,8,13,8,13,8,13,8,13,8,
13,8,13,8,13,8,13,8,13,8,12,8,13,8,13,8,12,9,12,8,12,9,12,9,11,9,11,10,10,10,11,9,10,11,9,11,9,11,9,11,8,12,9,11,10,10,11,9,13,7,15,4,18,1},
{27,11,5,21,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,10,189,10,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,20,7,21,5},
{28,1,26,1,140,1,32},
{26,11,4,21,6,20,7,18,8,18,8,19,7,19,6,11,5,4,6,5,4,2,6,3,6,3,16,2,5,1,24,1,62,1,24,7,14,15,8,17,11,14,13,11,8,1,7,9,8,2,8,8,8,2,9,6,8,4,8,6,8,4,8,7,
7,5,7,8,5,6,6,10,3,9,2},
{28,22,4,24,6,21,7,21,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,21,7,20,8,
20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,8,20,7,20,8,20,7,20,8,20,7,20,8,20,7,22,6,23,5}});
image out(60,40);
char charname[17]="0123456789()+-*/";
#include<random>
#include<chrono>
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int main(){
    for(;;){
        freopen("AT678.in","w",stdout);
        printf("0 0 0\n");
        int p=rnd()&15;
        image i=charset[p];
        uniform_real_distribution<> R1(0.9,1);
        uniform_real_distribution<> R2(-.1,.1);
        db a=R1(rnd),b=R1(rnd),c=R1(rnd);
        i=i.fit(i.rx*a,i.ry*a);
//        i.print();
        i=i.fit(i.rx*b,i.ry);
//        i.print();
        i=i.fit(i.rx,i.ry*c);
//        i.print();
        i=i.rotate(uniform_real_distribution<>(-18,18)(rnd));
//        i.print();
        i=i.cut(R2(rnd),R2(rnd));
//        i.print();
        out=image(60,40);
        i.foreach([&](int x,int y){
            out[x+5][y+5]=i[x][y];
        });
        out.foreach([&](int x,int y){
            if(!uniform_int_distribution<>(0,19)(rnd))
                out.raw[x][y]=!out.raw[x][y];
        });
        out.print();
        fclose(stdout);
        freopen("","w",stdout);
        printf("%c\n",charname[p]);
        system("AT678_s4tmp < AT678.in > AT678.out");
        freopen("AT678.out","r",stdin);
        if(getchar()!=charname[p]){
            exit(1);
        }
    }
}
≡