AtCoder お誕生日コンテスト - X：この問題はほんとうにひどい問題であるため（Ry

AtCoder お誕生日コンテスト - X：「この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇を」题解

原题传送门：AtCoder.

题意简述

给定字符集 $S=\texttt{0123456789()+-*/}$，每个字符给定一个 $65\times38$ 的 0-1 矩阵表示字符模板（从 Courier Prime 64pt 字体中提取）。白色（$1$）用 # 表示，黑色（$0$）用 . 表示。将字符经过处理之后拼接成一个 $W\times 38$ 的黑白图片，形成一个表达式的图片。要求求出这个表达式的值。

其中，对字符的处理按照如下步骤进行：

1. 随机取 $M, M_x, M_y\in[0.9, 1]$，将模板整体放大 $M$ 倍，并接着在 $x$、$y$ 方向上分别放大 $M_x, M_y$ 倍。由于放大倍数均 $<1$，因此实际上这一步在做缩小。

2. 随机取 $R\in[-15\degree, 15\degree]$，将放缩后的图片旋转 $R$ 度。

3. 随机取 $S_x, S_y \in[-0.1, 0.1]$，将旋转后的图片做剪切变换，即

   $$\begin{pmatrix} x'\\y' \end{pmatrix} = \begin{pmatrix} 1 & S_x\\S_y & 1 \end{pmatrix} \begin{pmatrix} x\\y \end{pmatrix}.$$

4. 将剪切后的字符模板从左到右拼接，中间留 $10$ 列空像素分割，拼成一个表达式图片。

5. 对最终的表达式图片，每个像素均有 $P=0.05$ 的概率被随机翻转。

解题思路

不难得到整个 pipeline 是：

预处理 $\to$ 分割 $\to$ 识别 $\to$ 计算表达式

分条阐述。

预处理

读取转化为 0-1 矩阵是不难的。代码略。

这一步最主要的就是消除噪声。由于噪声是随机的，并且原图是二值图，我们采用 $3\times 3$ 核的众数滤波降噪。众数滤波的基本思想是用邻域内像素的众数来代替中心像素的值。即

#define FOR_BITMAP(i, j, h, w) \
    for (int i = 0; i < h; i++) \
        for (int j = 0; j < w; j++)
int bitmap[H][W];
void commonest_filter(int h, int w)
{
    FOR_BITMAP(i, j, h, w)
    {
        int cnt1 = 0, cnt0 = 0;
        for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++)
            {
                int x = i + dx, y = j + dy;
                if (x < 0 || x >= h || y < 0 || y >= w)
                    continue;
                cnt1 += bitmap[x][y] == 1;
                cnt0 += bitmap[x][y] == 0;
            }
        bitmap[i][j] = cnt1 > cnt0;
    }
}

分割

这个也不难。BFS 搜索连通块，然后扔掉面积小于某一阈值的连通块即可。阈值可以取 $40$.

搜索的顺序有点讲究。由于图片是从左到右拼接的，因此我们希望 BFS 搜索的顺序是从左到右、从上到下。这样可以保证我们得到的连通块是按照字符在表达式中出现的顺序排列的。因此循环需要先 $W$ 再 $H$.

一个技巧是让 BFS 返回这个联通快的 Bounding Box，即

$$x_1=\min_{(x,y)}\{x\}, x_2=\max_{(x,y)}\{x\}\\ y_1=\min_{(x,y)}\{y\}, y_2=\max_{(x,y)}\{y\}$$

然后用 $(y_2-y_1-1)\cdot(x_2-x_1-1)$ 计算面积。

这样就切出每一个单独的字符了。

识别

这一步最难。

观察字符的产生过程。注意到剪切的参数很小；存在不等比例的放缩；有较大角度的旋转。因此考虑逐个处理这些问题。

对于放缩：我们让每个字符以几何中心为中心，等比例地 缩放到 $64\times 64$ 的大小。由于放缩倍数均小于 $1$，因此不会出现字符被截断的情况。即

struct BBox
{
    int x1, y1, x2, y2;
};
int buffer[64][64];
void scale(BBox b)
{
    int cx = (b.x1 + b.x2) / 2;
    int cy = (b.y1 + b.y2) / 2;
    double scale_x = 64.0 / (b.x2 - b.x1 + 1);
    double scale_y = 64.0 / (b.y2 - b.y1 + 1);
    double scale = min(scale_x, scale_y);
    for (int i = 0; i < 64; i++)
        for (int j = 0; j < 64; j++)
        {
            int x = (i - 32) / scale + cx + 0.5; // + 0.5 四舍五入
            int y = (j - 32) / scale + cy + 0.5; // + 0.5 四舍五入
            if (x < b.x1 || x > b.x2 || y < b.y1 || y > b.y2)
                buffer[i][j] = 0;
            else
                buffer[i][j] = bitmap[x][y];
        }
}

这样就解决了缩放。

接下来处理剪切。注意到剪切的参数范围不大，我们考虑将这个 $64\times64$ 的图均匀地切成 $8\times8$ 的小块（patches），每个 patch 大小也是 $8\times 8$，然后统计每个 patch 中黑色像素的数量，展平塞到一个 $64$ 维向量中。同样我们也对模板做放缩+patchify，得到模版的向量。这样，我们期望同类字符的 patch 向量之间是「相似的」。这里相似的定义是两个向量之间夹角最小，即

// returns cos<a, b>
double similarity(int *a, int *b)
{
    double dot = 0, norm_a = 0, norm_b = 0;
    for (int i = 0; i < 64; i++)
    {
        dot += a[i] * b[i];
        norm_a += a[i] * a[i];
        norm_b += b[i] * b[i];
    }
    return dot / (sqrt(norm_a) * sqrt(norm_b));
}

也就是余弦相似度。自然这个相似度越高越好。

最后是旋转。旋转的角度范围是 $[-15\degree, 15\degree]$，因此我们可以枚举每个字符的旋转角度，步长为 $5\degree$，然后计算相似度，取最大值即可。也就是说，每个字符模版会产生 $7$ 个不同旋转角度的子模板，也就是总共 $16\times 7$ 个 patch 向量。这就是 $16\times 7\times 64\approx7000$ 个 $0\sim 64$ 的整数。

注意到 ASCII 字符集从 $\texttt 0$ 开始，有连续的 65 个可见字符，因此将字符模板按照 ASCII 编号存储在一个数组中即可。这样极大压缩了代码长度。

计算表达式

两个栈。略。

代码

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
const int MIN_BBOX_SIZE = 50;
int bitmap[100][100000], buffer[100][100000];
char IObuf[100000];
// ASCII 编码后的 patch 向量
const char *featstring[16][7] = {
    {"03Tf^?000VoUdp>03pU05j^0?pS00Xn00j`00Lp:0Wn80Jp208lhPp_000>\\jU00", "01PlfB000RoXcpB00jX02j`03pT00Tp00n^00Mp60Yn40To009pdRpV000>ahV40", "00MpfL100MpX`pL08hc03hd2>nZ00Pp8@pX00Pp86ag00Tl40Ip^Nk[000Skpb20", "00KlnP100Hp\\YoP02ai00ah1@pX00Pp8@pX00Pp84df00^j20MpTQnU000SnoX20", "00Kfp\\100DpdVmU04^j20Vl4@pX00Po7@pX00Pp88hb02df30SpPYpQ000TpjT20", "00:Z`N2006phZpQ00Vo80Vn00l`00Mp63pU00Rp00lX01hb00UnP^pF002XnkJ00", "00:TdM0005hkXp\\00To:0Kp20hb00Kp:?pS00Vo06pT04ha00YnM`pB004\\kdD00"},
    {"01Li00007`pp60004_NpH000002pZ000000^k000000Lp<>2006QppoB00phUH40", "01Gn<0003fppH0000O=pS000000n^000000`i000000Pp01001DXpjp20?lbUN@0", "02GhM0000gmpX0000G?pX000000fb000000`h000000Zk30003:\\p[S00VohhZS0", "03@Xl0000Vppp00009;Xp000000Xp000000Xp000000Xp0000:@^p@>00mpppph0", "01CMdT0006llpJ00005BpH00000JpC00000Pp@00000Sp:000MVap<700PZhhnh0", "00>MZd0000Peoj000000kZ000006pO00000BpH00000Pp8000bhjpH600>JT`jX0", "000ZdnG0000VapB00000Vp400000kb000008pM000E>Np@000[oppK80000DTfO0"},
    {"07VjZ500;liRoZ005pE0`g000H76k_00000UpBJ200:oVAp<01\\pfllE01gbQ>40", "0;Ynd:003pgSkl000mK0Up300:62hf00000ZpA6000EpUFp308hpRdp:0BnhXPB6", "0C\\pbE007niPfn807nP0Jp@00640^p80002[pM0000Jp]B]00CnlJ[p00\\pih^X0", "0=ZpnR100XlT\\pF00V`08pX00000RpJ0000Ppc2000OpcAL02QpkBXp07mppppp0", "06Xnpe900@pZRmX008`<0ah00000IoW0000Lpg;004YpZ?D00cpiH\\h00UXdhlg0", "00F\\dV6000^gVk_000NH0Ul40000<ke0000Qoj900;cpYA?01bpiP]a00;FR\\iT0", "00:dfX4000MjVjk000>E0Mp60000Bid0006Zpd800PplKD:02^nkTkQ0006DTg:0"},
    {"05Tf`?006jmRki100fP0Pl40020Umd90000OHgi200000To800JPZn^100Wi`L10", "0?WjjE004jhTep800YN0Fp?0000Sjn30000URjd000000Zp306NKPna004loiY60", "0BZpfK000hkPap<00PI0Hp@0003`hi00004PWpO000000bh00FTNXpR00IejhM00", "0;\\ppY500HpTWoW00;P01i^0000V_nA0000T[nQ000000bh00LZHOna00Okpo_>0", "04^ppj7008p\\Pkd001F90[o0000S\\pP0000KZlM000000`i01^aNPpb00Jbom\\>0", "00LffV6000hbWkb000:>0Vp5000TPjc0000H`p<009000mX08ldNYpO00B_lm\\60", "00DljV6000VjTgl300080Lp>000TVhj2000Dap<00G304pN0?mhPapJ00<WjiV00"},
    {"009lJ00000TpZ00006klj0000NiGpJH02g`^pp_0ApfYm]000:05eljB002jiVJ4", "000^d00000Epl40002ghp<000Mn@pF>06di^ppj29f]Vpd20000:jm_6004nhZS8", "000Cp@00001dpP0000VgpP000BpDfZ00:indnpp8:XXLjg@2000@fmX5007lhdX5", "0004d\\00000^p`0000Unj`000GpG``00<nl`ll`<8PPPphP8004@pd@000Gpppp0", "0001Pl40001Vpi1000Rodh000OnEZc00@ppjnjX54@@IpdX500EQpT6000Gdhl`0", "0000Cd<0000Jpp:001Vkco004ZnKRf005`kppjT00008p`S000VfpV4000DS^iH0", "0000CjP0000PnpN008`l[p@0:ipQOk306N]lpjP3000Bp^W004pfpD1000BS`o<0"},
    {"01>MdH005jn^J6000]]6C<000TnmppG00DlG<ci200000Qo700FDNma100[okR50", "3HP\\lX002dgRH8000Xd>K;000ZppppD00DX8:hd000000bi00:VMXpV009imhP00", "0GV``h400XlPPA100Xi>?:000XpppoC00IY8GnZ000000bf00GNHQnY00Snpp]20", "0@ppppT00@pRHH;00FpOH?000PppppO008H46hh000000Xp00S^HRo`02Mjpo`70", "00`f`\\L000h`PVV006lT@:000@pppiB002><<hh002000^k01^eJTp^00Fapm`:0", "00P`RI>000XhXfk400h\\800008ppph6000>:DpV00;100i`06kbLWpM00F_moZ60", "008lXI6000LpUhpB00gf808006mpp`900064JpR00K300lV09mhL\\pJ00:\\lkR00"},
    {"000Hh?0003cpZ9002Uj?00005jTQb\\507nm`Sjb01al10Ul40LpJHjc101Qmm\\80", "001Hhb0001ho_B000Vo<00006lZVf\\<06lp\\Qlc02dj00Rp00HnRKle000Vno`80", "001KVl2001XphP400Tm>00003faX`V808poTUp\\05hb00Zl00KnQKla002^kp[40", "002J^lP003^pcV@00NnE00004hi_hZ:08pnQLld05j`00Xp00PnQNlh002Wmpb:0", "008Lfpj204hp\\TK00TlE0000<lkgp]80@plJDke1@pZ00]l42YmNVpc002Spmf:0", "003Mbfd:02gpb^Z:0TnC00000lnjl[209pfBHp]00pP00bg00[nPZn[006\\mp\\:0", "009ZfjfF0=mp][\\E0`lB60006ppnnY40PpW6IpS0HpC04l^03lhT_pP00;\\mmX40"},
    {"0008KZT00Rhpfp^00Jo92pT009p?6pN00050DpC00000Ip800000No000000Tf00", "04@KRbd00_ofXp^00Ok07pP00Ae0Hp@00000Vp000000h`000003pT000008pH00", "0PP``lf00mlPTpa00Xh0ApN00BJ0Xl600000ld00000BpJ00000Tp800000]`000", "8pppppl08paHOp`08pX0NpD00:61jj20000FpN00000]l60000:pZ00000Ep6000", "0`n``TO02dbPSpj07nO0RpD00630lh00000SpI00005ma00000Sp?00000_X0000", "0PhXMF700\\dTapi05jT0MpP00049pg00001Zp80000GpR00001lb00000?i80000", "0L^M@0001bg`nnX08pN0Hp[0060=pd40004dk80001ZpF0000IpN00002[^00000"},
    {"09Xlb>004dkSji008pX0Vk002YpZl`8001f]Nlg00Kp00Pp00Gp_Rpc000TkhS80", "03XpjC000XoRhn004hd0Mo800Jp\\l]2006h\\Pn^00Vk00`k00MpXTp[000ZkhT00", "02ZpfN100VoTcp@00mi2HpH00Bpbcg500AhZ^pO00pi02df00gnPNm\\00>gnpa80", "00KlpY500@p`WoS00GpB1i^006ff_nA00Am\\[mP00jj00bh00_pPNma00:bppe?0", "00Gdpf7004ljPkc008pP0[o001[h\\pP00Bo^ZlI06ld00`i02^nONpb006\\pnd>0", "008WbT5000`nZmb000kZ0Vp300UpPhe00NpV\\p904j\\00mX00\\lNQpO008]mpa60", "009TdO2000\\oXnc000l\\0Np201\\nNld03bjSdm00HpR08pL00jlL\\pH008^lnU00"},
    {"00Qf`A000UpT`p=05ja00m\\00^jGRpj209dp\\Vj200004e^0000Fik<0002kZ;00", "03VhfE001XoT_p>06lX01pX04fjFOph00<doaZj000003l[0005Nlm:000OpW400", "00NphR100PpVXpH00gj00bd00RpNJnp004_k`cj000004c^000AWnh8000[gV:00", "02TpnP100VpZWoN00pi00ad00]oHGlh007_pgjf000007iZ002HYll;00>pjY:00", "02XnpV100Pp`RnR03aj00Sp02[p>>ip004\\pkjp00008;k]00:LNlp<00TpoZ@00", "01Ff`G200Cpg`pH00^i30^g00Xn@6dm004_pnpd00008>pN01LRZnj405dkkV400", "00B`hR100<on^pV00Qp<0Kp:0NpG1Rp>00_pppn0000>FmZ06RNTjl;0>jllb?00"},
    {"003i>00000Sd000002jD00000:p:000004nF000000Uc4000004f`@000003Xi40", "000M^00000<n@00000YY000000fJ000000^R000000Kh4000002cb8000003Uh00", "000;a400000jW00000Ke100000^R000000`P000000Im2000002`Z8000001]Y00", "0002\\R00000[c50000?n400000Vc000000Tb000000An5000000\\_4000001\\Q00", "0002^Z00000`^90000Im200000`R000000^P000000Me1000000jR0000009a500", "0002N`00000YjB0000Gj400000]T000000fM000000\\X000000:l;000000KY000", "0000L`50002ZjI1000Lj600001eL000004l@000003gJ000000Kc2000002aD000"},
    {"06nY700000<`i7000002^_000000?o4000000p<00000=n400000[\\000009h900", "00hZ3000008ae4000001dS000000Lf000000@i000000Rd00000;jF00000US000", "00Xa5000006[e1000000gP000000J`000000H_000000^T00000Gm900000c>000", "00Pa5000003]b0000001iG000000[W000000ZV000001jI00002]c10000Na4000", "000f?000000Im5000000^R000000J_000000H`000000gP00005[e40000W`4000", "000VW000000;lD000000Qa000000Bj000000Kf000002dR00008ag50000dY3000", "0009`4000001`V000000?l1000002p500000=o200002[_0000:_l70006dZ5000"},
    {"00Jm:00000XpL00000Fp`N^Z@J\\pppphlpppp_H0HZLZpP00000Bpb000006h`00", "00@pJ00000HpX00000@pbHPKPVdpppphpppppaTEHN@^pH00000NpR00000DpP00", "00:pZ00000@p`00000:pj:HE``hpppphpplppfXS@@8dp<00000XpH00000TpB00", "000gj000000pp000888pp887ppppppphhhhpphha000pp000000pp000000jl000", "000Rp?00000XpH00HH@gp@00pppppn`ZXX`ppiph008ph2@>00@p`00000<p\\000", "000BpN00000PpP00PVHapH00pppppf\\LHN^pnppf00@p`@HD00JpV00000DpL000", "0008pX00000Dp`00TgTapN00pppppdP>0?Vppppf00Hp\\FTN00ZpJ00000Tj<000"},
    {"000000000000001400006DTX5@N^ppppdpppn`PDSdVH00000000000000000000", "000000000000000000000<LL?LXdppppjppppd^PNXH<00000000000000000000", "0000000000000000000000PHRXappppppppppp``?H?000000000000000000000", "0000000000000000:@@@@@@<gppppppjjppppppp000000000000000000000000", "0000000000000000DPD00000ppppppXTZ`fppppp000000HH0000000000000000", "0000000000000000L`@80000mpppp^VDDT`hpppp00000BNN0000000000000000", "0000000056000000XhN@0000gpppmXH::HVdpppl00009LZZ0000000000000000"},
    {"00@d@00000LpX4T@6<8m^apX`pdjlpX:Zf`jpaL000<p\\ppN00`pFGhI00Hd<000", "006gP00000Dpf39B:@2p`Wn`^pjgdmjVJ``ppf>000DpbpkD06nm>apV04^e22G4", "005m[00000@pm073DX;egAodppppgpi]HPbppb4004[p]oX60Ipd6npE0;jD0JC0", "000_g600005mp>00Q^=ep9X\\ppolgnpp?J[pp^LB0<bngnE00hpXPpn60RnB3fb4", "000JpC00382_pU00`pKYpAJJjpolgnpp03Spp^XT0Mlljn>0?ppDdp\\00P^4Dlb0", "000HpB00<M1TpT00\\p_Tp:F<Rappjgpj08^ppbVP6kpbpY00?ng4hpO00H60Pf80", "000FpF00B\\;Pp\\00ppd^p8:0HVnpjjp`4Dbpj`dT^pnbmH23DnMDpe302608j_10"},
    {"0000Y;000002k600000:g100000D[000000MQ000000WG000000b>000004k0000", "0000PM000000_A000005p500000C\\000000RO000000h>000007k000000C[0000", "00006c000000QU000002h;00000Aj000000YN000002h:00000G^000000ZK0000", "00000d;00000Cf100000aM00000@k200000^N00000<j400000YS000006n70000", "00000MS00000<k<00000X]00000?k300000_O00000Lg000004gG00000O_00000", "00000=h400005dR00000Oh40000Dm<00003eP00000Y`00000Cn800002aM00000", "000003aA00002b`30000Uh80000Ml>0000@mD0000:mN00004e[00000La300000"},
};
int features[16][7][64];
void getfeat()
{
    for (int i = 0; i < 16; i++)
        for (int j = 0; j < 7; j++)
        {
            const char *s = featstring[i][j];
            for (int k = 0; k < 64; k++)
            {
                int val = 0;
                char c = s[k];
                val = c - 48;
                features[i][j][k] = val;
            }
        }
}
void commonest_filter(int h, int w);
struct BBox
{
    int x1, y1;
    int x2, y2;
};
int classify(BBox box);
BBox bfs_continuous_block(int h, int w, int x, int y);
int expr[300], expr_size = 0;
int vis[100][100000];
int calc(const std::string &s);
std::string tostring(int *expr, int size);
int main()
{
    getfeat();
    int T;
    std::cin >> T;
    int h, w;
    std::cin >> w >> h;
    for (int i = 0; i < h; i++)
    {
        std::cin >> IObuf;
        for (int j = 0; j < w; j++)
            bitmap[i][j] = IObuf[j] == '#';
    }
    commonest_filter(h, w);
    memset(vis, 0, sizeof(vis));
    for (int j = 0; j < w; j++)
        for (int i = 0; i < h; i++)
            if (bitmap[i][j] && !vis[i][j])
            {
                BBox box = bfs_continuous_block(h, w, i, j);
                if (box.x1 != -1)
                {
                    int cls = classify(box);
                    expr[expr_size++] = cls;
                }
            }
    // parse expr
    std::cout << calc(tostring(expr, expr_size)) << std::endl;
    return 0;
}
void commonest_filter(int h, int w)
{
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            buffer[i][j] = bitmap[i][j];
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
        {
            int cnt0 = 0, cnt1 = 0;
            for (int nx = i - 1; nx <= i + 1; nx++)
                for (int ny = j - 1; ny <= j + 1; ny++)
                    if (nx >= 0 && nx < h && ny >= 0 && ny < w)
                    {
                        if (bitmap[nx][ny])
                            cnt1++;
                        else
                            cnt0++;
                    }
            buffer[i][j] = cnt1 > cnt0;
        }
    memcpy(bitmap, buffer, sizeof(buffer));
}
BBox bfs_continuous_block(int h, int w, int x, int y)
{
    BBox box = {x, y, x, y};
    vis[x][y] = 1;
    std::queue<std::pair<int, int>> q;
    q.emplace(x, y);
    while (!q.empty())
    {
        auto [cx, cy] = q.front();
        q.pop();
        box.x1 = std::min(box.x1, cx);
        box.y1 = std::min(box.y1, cy);
        box.x2 = std::max(box.x2, cx);
        box.y2 = std::max(box.y2, cy);
        for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++)
            {
                int nx = cx + dx;
                int ny = cy + dy;
                if (nx >= 0 && nx < h && ny >= 0 && ny < w && bitmap[nx][ny] && !vis[nx][ny])
                {
                    vis[nx][ny] = 1;
                    q.emplace(nx, ny);
                }
            }
    }
    // check bbox's size
    if ((box.x2 - box.x1 + 1) * (box.y2 - box.y1 + 1) < MIN_BBOX_SIZE)
    {
        box.x1 = box.y1 = box.x2 = box.y2 = -1;
    }
    return box;
}
bool inside_box(int x, int y, BBox box)
{
    return x >= box.x1 && x <= box.x2 && y >= box.y1 && y <= box.y2;
}
// 等比例缩放，不足的地方补 0
void scale(BBox box)
{
    double scale_x = (box.x2 - box.x1 + 1) / 64.0;
    double scale_y = (box.y2 - box.y1 + 1) / 64.0;
    double scale = std::max(scale_x, scale_y);
    double cx = (box.x1 + box.x2) / 2.0;
    double cy = (box.y1 + box.y2) / 2.0;
    double tar_cx = 32;
    double tar_cy = 32;
    for (int i = 0; i < 64; i++)
        for (int j = 0; j < 64; j++)
        {
            int src_y = cy + (j - tar_cy) * scale + 0.5;
            int src_x = cx + (i - tar_cx) * scale + 0.5;
            if (inside_box(src_x, src_y, box))
                buffer[i][j] = bitmap[src_x][src_y];
            else
                buffer[i][j] = 0;
        }
}
// 分 patch 后存在 out 里
void serialize(int *out)
{
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
        {
            int sum = 0;
            for (int x = i * 8; x < (i + 1) * 8; x++)
                for (int y = j * 8; y < (j + 1) * 8; y++)
                    sum += buffer[x][y];
            out[i * 8 + j] = sum;
        }
}
// 余弦相似度
double similarity(int *a, int cls, int featnum)
{
    double dot = 0, norm_a = 0, norm_b = 0;
    const int *b = features[cls][featnum];
    for (int i = 0; i < 64; i++)
    {
        dot += a[i] * b[i];
        norm_a += a[i] * a[i];
        norm_b += b[i] * b[i];
    }
    return dot / (sqrt(norm_a) * sqrt(norm_b));
}
int classify(BBox box)
{
    // 1. scale to 64x64
    scale(box);
    // 2. serialized to 64
    static int serialized[64];
    serialize(serialized);
    // 3. classify
    double best_sim = -1;
    int best_cls = -1;
    for (int cls = 0; cls < 16; cls++)
    {
        for (int i = 0; i < 7; i++)
        {
            double sim = similarity(serialized, cls, i);
            if (sim > best_sim)
            {
                best_sim = sim;
                best_cls = cls;
            }
        }
    }
    return best_cls;
}
// 将表达式的数字和运算符转换为字符串
// 原本是给调试用的
std::string tostring(int *expr, int size)
{
    static const char *IDX2CHR = "0123456789()+-*/";
    std::string res;
    for (int i = 0; i < size; i++)
        res += IDX2CHR[expr[i]];
    return res;
}
// 计算表达式的值
int calc(const std::string &s)
{
    std::vector<int> stk1;
    std::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;
        }
    };
    auto level = [](char c)
    {
        switch (c)
        {
        case '(':
            return 0;
            break;
        case '+':
        case '-':
            return 1;
            break;
        case '*':
        case '/':
            return 2;
            break;
        }
        return -1;
    };
    for (const auto c : s)
    {
        if (c >= '0' and c <= '9')
        {
            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() and 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();
}

后记

这个卡了好久… 最开始打算用各种奇奇怪怪的手工特征（Hu 矩、投影直方图、Euler 数之类的）结合 GNB 来做分类，结果发现效果不行。后来想想干脆大力出奇迹直接切 patch…… 试了试 $4\times4$ 的 patch，399 分 WA，改成 $8\times8$ 的 patch 才过。