题解：P16706 [SEATST 2026] 三重电路 / Triple Circuit

WightyIflia · 2026-11-08 19:51:31 · 题解

解题思路

由于要求门数非常少（不超过 215 个），我们不能使用复杂的算法电路，而是要利用分治与组合逻辑，通过按行、按列的 OR 运算和少量的 AND 运算，快速汇总出全图信息。

整体解题结构分为以下几个步骤喵：

输入预处理

将 64 个输入位看作 8×8 的矩阵，行列下标均为 [0,7]。

第一步用 64 个 OR 门做初步合并，将部分格子两两配对，为后续的行列合并做准备。

    for(ll p=0;p<64;++p)
    {
        cout << "OR " << p << " " << (p+64) << endl;
    }
    for(ll a=0;a<8;++a)
    {
        ll ps=128+a*8;
        ll te=192+a*7;
        cout << "OR " << ps << " " << (ps+1) << endl;
        for(ll j=2;j<8;++j)
        {
            cout << "OR " << te << " " << (ps+j) << endl;
            te++;
        }
    }
    for(ll b=0;b<8;++b)
    {
        ll te=248+b*7;
        cout << "OR " << 128+b << " " << 136+b << endl;
        for(ll a=2;a<8;++a)
        {
            cout << "OR " << te << " " << (128+a*8+b) << endl;
            te++;
        }
    }
    //堕ちた世界の終焉で 絶間ない赤を抱く
    //贖罪を掻き分けて 白蓮の意思は阡年回廊
    //忽然､視界の中心で 揺れる感情と裏腹に
    //真直ぐな銀色線は 只、掌で囁いて居た

按行列求 OR

对每一行（共 8 行），将其中的 8 个格子依次做 OR，得到 8 个行非空标志，用 F_1 存储。

同理，对每一列（共 8 列），得到 8 个列非空标志，用 F_2 存储。

消耗了 112 个 OR 门。

    vector<ll> f1(10);
    vector<ll> f2(10);
    for(ll a=0;a<8;++a)
    {
        f1[a]=192+a*7+6;
    }
    for(ll b=0;b<8;++b)
    {
        f2[b]=248+b*7+6;
    }
    //「…きっと其んな意図なんだ。」
    //蜘蛛を掴む様なモノガタリ

分治合并行列信息

对 F_1，F_2 进行分治。

用较少的 OR 门得到多种行区间的非空信息（20 个）。

这个过程是我手打的。

    cout << "OR " << f1[0] << " " << f1[1] << endl;
    cout << "OR 304 " << f1[2] << endl;
    cout << "OR 305 " << f1[3] << endl;
    cout << "OR " << f1[4] << " " << f1[5] << endl;
    cout << "OR 307 " << f1[6] << endl;
    cout << "OR 308 " << f1[7] << endl;
    cout << "OR " << f1[0] << " " << f1[4] << endl;
    cout << "OR " << f1[1] << " " << f1[5] << endl;
    cout << "OR " << f1[2] << " " << f1[6] << endl;
    cout << "OR " << f1[3] << " " << f1[7] << endl;
    //貴方が何様なんだとしても 救いの亡い莫迦だったとしても
    //千断れそうな愛の様な"賽"を 手繰り寄せたんだ
    //其の糸が地獄に照り返る "赤色"なんだと気付いて居ても
    //―僕は其れに縋る事しか 出来なかった訳ですから。
    cout << "OR " << f2[0] << " " << f2[1] << endl;
    cout << "OR 314 " << f2[2] << endl;
    cout << "OR 315 " << f2[3] << endl;
    cout << "OR " << f2[4] << " " << f2[5] << endl;
    cout << "OR 317 " << f2[6] << endl;
    cout << "OR 318 " << f2[7] << endl;
    cout << "OR " << f2[0] << " " << f2[4] << endl;
    cout << "OR " << f2[1] << " " << f2[5] << endl;
    cout << "OR " << f2[2] << " " << f2[6] << endl;
    cout << "OR " << f2[3] << " " << f2[7] << endl;
    //堕ちた世界の中心で 絶え間ない夢掴む
    //ふと底を見下ろす 幾千の四肢が縋っていた
    //どれだけ伝って来たのか？ どれだけ足掻いて来たのか？
    //咽び泣くは血の池の様 蠢き喚くは罪人模様

将行列区间组合

将行区间信息与列区间信息进行交叉 OR，得到更大的行列组合信息。

最后用 OR 门将所有“可能满足条件”的情况汇总为一个输出。

    cout << "OR 310 311" << endl;
    cout << "OR 312 313" << endl;
    cout << "OR 310 312" << endl;
    cout << "OR 311 313" << endl;
    cout << "OR 320 321" << endl;
    cout << "OR 322 323" << endl;
    cout << "OR 320 322" << endl;
    cout << "OR 321 323" << endl;
    cout << "AND 306 309" << endl;
    cout << "AND 324 325" << endl;
    cout << "AND 326 327" << endl;
    cout << "AND 316 319" << endl;
    cout << "AND 328 329" << endl;
    cout << "AND 330 331" << endl;
    cout << "OR 332 333" << endl;
    cout << "OR 338 334" << endl;
    cout << "OR 339 335" << endl;
    cout << "OR 340 336" << endl;
    cout << "OR 341 337" << endl;
    //手を差し伸べた訳じゃ亡いのだろう 貴方は僕が足掻く様を見て
    //嘲笑っておられたのだろう？ かつて僕が"そうした"様に
    //「…其れでも愛していたんだ。」
    //蜘蛛を掴む様なモノガタリ

刚刚好卡死 215 个。

完整版献上：

void solve()
{
    cout << 215 << endl;
    for(ll p=0;p<64;++p)
    {
        cout << "OR " << p << " " << (p+64) << endl;
    }
    for(ll a=0;a<8;++a)
    {
        ll ps=128+a*8;
        ll te=192+a*7;
        cout << "OR " << ps << " " << (ps+1) << endl;
        for(ll j=2;j<8;++j)
        {
            cout << "OR " << te << " " << (ps+j) << endl;
            te++;
        }
    }
    for(ll b=0;b<8;++b)
    {
        ll te=248+b*7;
        cout << "OR " << 128+b << " " << 136+b << endl;
        for(ll a=2;a<8;++a)
        {
            cout << "OR " << te << " " << (128+a*8+b) << endl;
            te++;
        }
    }
    vector<ll> f1(10);
    vector<ll> f2(10);
    for(ll a=0;a<8;++a)
    {
        f1[a]=192+a*7+6;
    }
    for(ll b=0;b<8;++b)
    {
        f2[b]=248+b*7+6;
    }
    //复制粘贴粘爽了……
    cout << "OR " << f1[0] << " " << f1[1] << endl;
    cout << "OR 304 " << f1[2] << endl;
    cout << "OR 305 " << f1[3] << endl;
    cout << "OR " << f1[4] << " " << f1[5] << endl;
    cout << "OR 307 " << f1[6] << endl;
    cout << "OR 308 " << f1[7] << endl;
    cout << "OR " << f1[0] << " " << f1[4] << endl;
    cout << "OR " << f1[1] << " " << f1[5] << endl;
    cout << "OR " << f1[2] << " " << f1[6] << endl;
    cout << "OR " << f1[3] << " " << f1[7] << endl;
    cout << "OR " << f2[0] << " " << f2[1] << endl;
    cout << "OR 314 " << f2[2] << endl;
    cout << "OR 315 " << f2[3] << endl;
    cout << "OR " << f2[4] << " " << f2[5] << endl;
    cout << "OR 317 " << f2[6] << endl;
    cout << "OR 318 " << f2[7] << endl;
    cout << "OR " << f2[0] << " " << f2[4] << endl;
    cout << "OR " << f2[1] << " " << f2[5] << endl;
    cout << "OR " << f2[2] << " " << f2[6] << endl;
    cout << "OR " << f2[3] << " " << f2[7] << endl;
    cout << "OR 310 311" << endl;
    cout << "OR 312 313" << endl;
    cout << "OR 310 312" << endl;
    cout << "OR 311 313" << endl;
    cout << "OR 320 321" << endl;
    cout << "OR 322 323" << endl;
    cout << "OR 320 322" << endl;
    cout << "OR 321 323" << endl;
    cout << "AND 306 309" << endl;
    cout << "AND 324 325" << endl;
    cout << "AND 326 327" << endl;
    cout << "AND 316 319" << endl;
    cout << "AND 328 329" << endl;
    cout << "AND 330 331" << endl;
    cout << "OR 332 333" << endl;
    cout << "OR 338 334" << endl;
    cout << "OR 339 335" << endl;
    cout << "OR 340 336" << endl;
    cout << "OR 341 337" << endl;
}
//貴方が神様なんだとしても "救い"と云う釈迦だったとしても
//千断れそうな愛の様な"賽"に しがみついたんだ
//"赤色"なんだと気付いて居ても 救いの亡い莫迦だったとしても
//千断れそうな賽の様な“愛”を 求めてしまったんだ

//『この糸は己の意図だ！』と 叫んで断れた雲の異図､ああ
//―僕は其れに縋る事さえ 出来無かった訳ですから。

//                             ----《蜘蛛糸モノポリー》 sasakure.UK ,miku