A、智乃与瞩目狸猫、幸运水母、月宫龙虾

题意

给两个字符串，判断首字母忽略大小写后是否相同。

技巧

你可以使用std库函数std::tolower来将大写转换为小写。相应的，对于字符操作，也存在std::tolower、std::toupper。

在算法竞赛中，涉及到英文字母的字符操作一般使用位运算和空格字符来做。在某些需求中比使用库函数更加灵活，比较经典的例如将大小写英文字母转换为小大写，一般使用c^=' ';来实现。

在ASSIC编码中，英文字母所对应二进制的第6位表示大小写，该位为0时表示大写，为1时表示小写。，空格字符的ASSIC编码又恰好为。

char c='a';
if(c&' ')//判断是否为小写
if(~c&' ')//判断是否为大写
c|=' ';//转换为小写，等价于std::tolower
c^=' ';//如果原本是大写，转换为小写，原本是小写转换为大写。
c=(c|' ')^' ';//转换为大写字母，等价于std::toupper

核心代码

int main(int argc, char const *argv[])
{
    int T;
    char s[55], t[55];
    read(T);
    while (T--)
    {
        read(s, t);
        println((s[0] | ' ') == (t[0] | ' ') ? "Yes" : "No");
    }
    return 0;
}

B、智乃的数字手串

如果你看到数据范围被骗去写搜索或者DP，请立即下载国家反诈中心APP。

题意

两个人轮流在环上取数，要求只能取走相邻奇偶性相同数字的其中一个。取数后可以进行某些操作改变顺序，不能操作的人输掉游戏。

题解

是奇数先手必胜，偶数后手必胜。

这个操作其实并没有卵用，把题目改成允许取数后重新排序也是一样的结果。

考虑游戏最终的结果，无论是谁不能取数，最终剩下的数字一定按照[奇,偶,奇,偶,...,奇,偶]排列，即长度为偶数。所以无论数字的内容是什么，两人的决策是什么，都不影响起始回合到终局回合的奇偶性。

核心代码

int main(int argc, char const* argv[]) 
{
    int T, n, a;
    read(T);
    while (T--) 
    {
        read(n);
        println(n & 1 ? "qcjj" : "zn");
        while (n--)read(a);
    }
    return 0;
}

C、智乃的前缀、后缀、回文

题意

给两个字符串，分割成四个前后缀，要求互相的前缀和后缀两两相同且为回文。

题解

看着复杂，但其实是字符串入门级题目，只要能够熟练使用任意一种字符串匹配相关的算法就可以做。

算法一：manacher

马拉车算法(manacher)可以用于求一个字符串的所有回文中心，以及其延伸的长度。所以我们可以很方便的实现判断某字符串子串是否为回文的接口。 接下来同时枚举的前缀和的后缀，因为是回文，所以所以直接倒着匹配即可。然后记录所有能够完整匹配且前后缀为回文的位置。再反过来枚举的前缀和的后缀，使用类前缀和（前缀/后缀极值）的方法合并答案即可。

核心代码

int main()
{
    int ans = -1;
    vec_t<char, 1> s(MAXN), t(MAXN);
    vec_t<int, 1> suf(MAXN);
    int n, m;
    read(n, m, s.data(), t.data());
    if (n > m)
    {
        swap(n, m);
        swap(s, t);
    }
    chino::manacherWrapper manacher(s.data());
    int last = -1;
    int flag = 1;
    for (int i = 0; i < n; ++i)
    {
        if (t[i] != s[n - i - 1])flag = 0;
        if (flag && manacher.isPalindrome(n - i - 1, n - 1))last = i + 1;
        suf[n - i - 1] = last;
    }
    for (int i = 0; i + 1 < n; ++i)
    {
        if (s[i] != t[m - i - 1])break;
        if (manacher.isPalindrome(0, i) && suf[i + 1] != -1)
        {
            ans = max(ans, ((i + 1) + suf[i + 1]) << 1);
        }
    }
    println(ans);
    return 0;
}

算法二：z-function(exkmp)

z-function(exkmp)可以预处理出字符串所有的后缀与目标字符串前缀是否匹配。由于本题的字符串是一个前缀回文，所以相当于从回文中心切开，然后让这个后缀与前缀进行一个字符串匹配，而这个地方恰好就是z-function(exkmp)ex数组的定义。接下来的过程就同算法一了。

算法三：kmp

按照题意，由于求的是的前缀和的后缀匹配，所以直接将在前在后拼接到一起，发现问题变为，找到新字符串的一个子串，使得该子串既是一个前缀，同时也是一个后缀，并且前后缀匹配，这实际上就是KMP的Next数组定义，所以可以直接求Next数组。然后同理，再将在前在后拼接到一起，求Next数组。最后双指针合并两Next数组即可求出答案。

算法四：hash

本质和算法二相同、不讲了

算法五：后缀数组

原理同算法二、四，不讲了。

D、E、F chino's bubble sort and maximum subarray sum

题意

先交换相邻元素次，然后求最大子段和。

题解

easy

方法比较多，由于数据范围较小，所以你可以枚举所有交换的可能性，然后扫一遍求最大子段和。

或者考虑，先求最大子段和，在过程中考虑因为反正只能交换0-1次，那就必然是跳过一个负数在两端多加上一个正数。所以也可以贪心。

hard

基于easy版本的贪心思路，我们继续考虑交换操作只能发生在所选的最大子段和头尾两侧，不会在最大子段和的中间产生。（）

相邻交换具有不交叉性质，该性质可以在“模拟费用流”类算法中有所体现。

具体来讲，当存存在如图所示的情况时，如果AD等价，BC等价。那么交换时一定不交叉。（可以按网络流理解，相当于增广路时被取消）。

在已知交换不产生交叉的前提下，我们可以将问题拆成左右两部分，变为两个新的问题：

从左往右进行冒泡排序，至多进行次交换，如果需要选中某个数字，就将其冒泡排序到最右侧，否则冒泡排序交换到左侧。（这个过程是一个典型的二维01背包）

接下来从右往左做一遍，同理。

已知不交叉，所以可以枚举断点，然后枚举交换次数合并两数组。

核心代码

const int MAXN = 10005;
const int MAXK = 1005;
const long long INF = 1LL << 60;
using namespace std;

long long dp[2][MAXK][MAXK];
long long pre[MAXN][MAXK];
long long suf[MAXN][MAXK];
long long a[MAXN];

int main()
{
    int n, K;
    vec_t<long long, 1> a(MAXN);
    //这种超大数组不建议开vector，vec_t_create常数较大

    read(n, K);
    vread(a.data() + 1, a.data() + 1 + n);
    auto dpf = [&n, &K, &a](auto &dp,auto&pre)
    {
        int cur=0;
        for (int j = 0; j <= K; ++j)
        {
            for (int k = 0; k <= K; ++k)
            {
                dp[0][j][k]=dp[1][j][k]=-INF;
            }
        }
        dp[cur][0][0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            cur^=1;
            for (int j = 0; j <= K; ++j)
            {
                for (int k = 0; k <= K; ++k)
                {
                    dp[cur][j][k]=-INF;
                }
                for (int k = 0; k <= K; ++k)
                {
                    if (j - k >= 0)
                        dp[cur][j][k] = max(dp[cur][j][k], dp[cur^1][j - k][k]);//不取，消耗k的代价
                    if (k > 0)
                        dp[cur][j][k] = max(dp[cur][j][k], dp[cur^1][j][k - 1] + a[i]);//取，k++
                }
                pre[i][j]=-INF;
                for (int k = 0; k <= K; ++k)
                {
                    pre[i][j]=max(pre[i][j],dp[cur][j][k]);
                }
            }
        }
    };
    //正着求dp，倒过来求idp
    dpf(dp,pre);
    reverse(a.data() + 1, a.data() + 1 + n);
    dpf(dp,suf);
    reverse(a.data() + 1, a.data() + 1 + n);
    for (int i = 1; i <= n / 2; ++i)
    {
        for (int j = 0; j <= K; ++j)
        {
            swap(suf[i][j], suf[n - i + 1][j]);
        }
    }

    vec_t<long long, 1> pre_max(K + 1, 0);
    long long pre_sum = 0, ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= K; ++j)
        {
            ans = max(ans, pre_sum + suf[i][j] + pre_max[K - j]);
        }
        pre_sum += a[i];
        for (int j = 0; j <= K; ++j)
        {
            pre_max[j] = max(pre_max[j], -pre_sum + pre[i][j]);
            if (j > 0)
            {
                pre_max[j] = max(pre_max[j], pre_max[j - 1]);
            }
        }
    }
    //最后一个参与向右排序的情况，或许并不需要这个处理，是一段冗余代码
    //因为显然，若最后一个参与排序，它一定是参与向左排序，向右排序无意义（如果不要就不动，反之向左排序）
    for (int j = 0; j <= K; ++j)
    {
        ans = max(ans, pre_sum + pre_max[K - j]);
    }

    if (ans == 0)
    {
        ans = -INF;
        for (int i = 1; i <= n; ++i)
        {
            ans = max(ans, a[i]);
        }
    }
    println(ans);

    return 0;
}

very hard

考虑线段树求合并逆序对时的情况。我们认为0表示不选这个数，1表示选这个数。

考虑如下这种情况，假设从左往右进行冒泡排序，0代表不选这个数，1代表选择这个数。

000000010101｜0101011111111111

总逆序对k=左侧区间的贡献+右侧区间的贡献+左边的1数目*右边的0数目。

显然则有k<=左边的1数目*右边的0数目。

令a=左边的1数目，b=右边的0数目。 则当a>时，b必须<。 逆序对有两种求法：

①求0前面的1

②求1后面的0

dp[n][k][p][2]表示前n个数，当前代价为k，当前增量为p，左侧还是右侧区间。 则当前半段dp时，每碰到一个1，我们让p++，每碰到0，我们计算当前代价。当p=时停止。 对于右侧区间倒过来假定其增量为p=x，每次遇到0的时候p--，同时因为我们已知左侧有个1是定值，所以还要再计算左右区间合并的代价。每次遇到1就计算右区间代价即可。

核心代码

template<typename T>
void check_max(T &x, const T &val)
{
    x = max(x, val);
}

int main()
{
    int n, K;
    read(n, K);
    vread(a + 1, a + 1 + n);
    auto dpf = [&n, &K](auto &dp, auto &pre)
    {
        int p = 1, cur = 0;
        while (p * p < K)++p;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j <= K; ++j)
            {
                for (int k = 0; k <= p; ++k)
                {
                    dp[cur][j][k][0] = dp[cur][j][k][1] = dp[cur ^ 1][j][k][0] = dp[cur ^ 1][j][k][1] = -INF;
                }
            }
        }
        dp[cur][0][0][0] = 0;
        //前面取p个1切换阶段
        //000000000...1010|1010...111111111
        for (int i = 1; i <= n; ++i)
        {
            cur ^= 1;
            for (int j = 0; j <= K; ++j)
            {
                for (int k = 0; k <= p; ++k)
                {
                    dp[cur][j][k][0] = dp[cur][j][k][1] = -INF;
                }
                for (int k = 0; k <= p; ++k)
                {
                    if (j >= k)
                        check_max(dp[cur][j][k][0], dp[cur ^ 1][j - k][k][0]);//不取，消耗k的代价
                    if (k > 0)
                        check_max(dp[cur][j][k][0], dp[cur ^ 1][j][k - 1][0] + a[i]);//取，k++
                }
                //先0后1，后效性问题
                for (int k = 0; k <= p; ++k)
                {
                    check_max(dp[cur][j][k][1], dp[cur][j][p][0]);
                }
                //必须首先确定p是一个常数c的值，否则结合时仍然是sqrt*sqrt=K的复杂度，不解决问题。
                for (int k = 0; k <= p; ++k)
                {
                    if (j >= k)
                        check_max(dp[cur][j][k][1], dp[cur ^ 1][j - k][k][1] + a[i]);//取，消耗k的代价
                    if (j > p && k < p)
                        check_max(dp[cur][j][k][1], dp[cur ^ 1][j - p][k + 1][1]);//不取，已知前面确定取p个，所以k--的同时，消耗p的代价
                }
                //统计合法的状态，dp[i][j][k][0]和dp[i][j][0][1]均为合法。（0阶段任意增量，1阶段必须保证增量为0）
                pre[i][j] = dp[cur][j][0][1];
                for (int k = 0; k <= p; ++k)
                {
                    check_max(pre[i][j], dp[cur][j][k][0]);
                }
            }
        }
    };
    //正着求dp，倒过来求idp
    dpf(dp, pre);
    reverse(a + 1, a + 1 + n);
    dpf(dp, suf);
    reverse(a + 1, a + 1 + n);
    for (int i = 1; i <= n / 2; ++i)
    {
        for (int j = 0; j <= K; ++j)
        {
            swap(suf[i][j], suf[n - i + 1][j]);
        }
    }

    vec_t<long long, 1> pre_max(K + 1, 0);
    long long pre_sum = 0, ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= K; ++j)
        {
            ans = max(ans, pre_sum + suf[i][j] + pre_max[K - j]);
        }
        pre_sum += a[i];
        for (int j = 0; j <= K; ++j)
        {
            pre_max[j] = max(pre_max[j], -pre_sum + pre[i][j]);
            if (j > 0)
            {
                pre_max[j] = max(pre_max[j], pre_max[j - 1]);
            }
        }
    }
    //最后一个参与向右排序的情况，或许并不需要这个处理，是一段冗余代码
    //因为显然，若最后一个参与排序，它一定是参与向左排序，向右排序无意义（如果不要就不动，反之向左排序）
    for (int j = 0; j <= K; ++j)
    {
        ans = max(ans, pre_sum + pre_max[K - j]);
    }

    if (ans == 0)
    {
        ans = -INF;
        for (int i = 1; i <= n; ++i)
        {
            ans = max(ans, a[i]);
        }
    }
    println(ans);

    return 0;
}

G、H、智乃的比较函数

easy

因为只有两个条件，所以可以用逻辑直接分情况讨论。

核心代码

int main(int argc, char *argv[])
{
    int T, n;
    read(T);
    auto a = vec_t_create<int, 3, 3>(-1);
    while (T--)
    {
        read(n);
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
 
                a[i][j] = -1;
            }
        }
        bool f=true;
        while (n--)
        {
            int x, y, z;
            read(x, y, z);
            if(z==1&&a[y - 1][x - 1]==1)
            {
            	f=false;
			}
			if(z==1&&a[x - 1][y - 1]==0)
			{
			    f=false;
			}
			if(z==0&&a[x - 1][y - 1]==1)
            {
            	f=false;
			}
			if(x==y&&z==1)
			{
				f=false;
			}
            a[x - 1][y - 1] =z;
        }
        println(f ? "Yes" : "No");
    }
    return 0;
}

hard

hard其实有两种做法的，一种是摁做，还是通过逻辑判断。不过还是有一定技巧的，就是构造bitflag，使用二进制位来表示该种情况是否存在可能性，1表示还具有可能性，0表示不可能，则可以设计如下的枚举类

enum BITFLAG : int
    {
        invalid = 0,                 // 没有合法关系
        less = 1 << 0,               // 严格小于
        equal = 1 << 1,              // 严格等于
        greate = 1 << 2,             // 严格大于
        leq = less | equal,          // 小于等于
        geq = equal | greate,        // 大于等于
        neq = less | greate,         // 不等于
        full = less | equal | greate // 所有关系均可
    };

核心代码

int main(int argc, char *argv[])
{
    enum BITFLAG : int
    {
        invalid = 0,                 // 没有合法关系
        less = 1 << 0,               // 严格小于
        equal = 1 << 1,              // 严格等于
        greate = 1 << 2,             // 严格大于
        leq = less | equal,          // 小于等于
        geq = equal | greate,        // 大于等于
        neq = less | greate,         // 不等于
        full = less | equal | greate // 所有关系均可
    };
    auto a = vec_t_create<int, 3, 3>(BITFLAG::invalid);
    // 是否包含某种关系
    auto contain_flag = [](auto x, auto flag)
    {
        return (x & flag) == flag;
    };
    int T, n;
    read(T);
    while (T--)
    {
        read(n);
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
                // 初始状态，显然只有当x=y的时候才知道ax=ay，不然所有关系都可以。
                a[i][j] = i == j ? BITFLAG::equal : BITFLAG::full;
            }
        }
        while (n--)
        {
            int x, y, z;
            read(x, y, z);
            // 如果ax<ay，那么就知道ay>ax，发过来如果知道ax>=ay，也知道ay<=ax。
            a[x - 1][y - 1] &= z ? BITFLAG::less : BITFLAG::geq;
            a[y - 1][x - 1] &= z ? BITFLAG::greate : BITFLAG::leq;
        }
 
        bool flag = true;
        for (int i = 0; i < 3; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
                for (int k = 0; k < 3; ++k)
                {
                    auto x = a[i][j] & a[j][k] & a[k][i]; // a=b=c
                    auto y = a[i][j] | a[j][k] | a[k][i]; // not (a=b=c)
                    if (!contain_flag(x, BITFLAG::equal) && !contain_flag(y, BITFLAG::neq))
                    {
                        flag = false;
                    }
                }
            }
        }
        println(flag ? "Yes" : "No");
    }
    return 0;
}

这样说实话是比较自找麻烦的，还有另一种方法。

暴力枚举所有情况，看是否有符合所有约束条件的，如果存在至少一种情况能够符合所有的约束条件，就是合法的，否则不合法。

核心代码

int main()
{
    vec_t<int, 2> v;
    for (auto i = 0; i < 3; ++i)
    {
        for (auto j = 0; j < 3; ++j)
        {
            for (auto k = 0; k < 3; ++k)
            {
                v.push_back({i, j, k});
            }
        }
    }
    int T;
    read(T);
    while (T--)
    {
        vec_t<int, 1> f(v.size(), 1);
        int n;
        read(n);
        while (n--)
        {
            int x, y, z;
            read(x, y, z);
            for (auto i = 0; i < f.size(); ++i)
            {
                if ((v[i][x - 1] < v[i][y - 1]) != z)
                {
                    f[i] = 0;
                }
            }
        } 
        println(*max_element(f.begin(), f.end()) ? "Yes" : "No");
    }
    return 0;
}

I chino's infinite infinite strings without xyz

题意

初始数组模23的情况下不停地做前缀和，问前个数组两两之间的之和是多少

因为相当于求s串的n-1次前缀和，然后与所有过程中产生串的lcp。

题解

如果你OEIS到一个错误的数列，或者你认为有循环节，或者大于529无解，请下载国家反诈中心APP。

虽然实际上在代码中并没有体现卢卡斯定理、卷积、组合数，但是实际上这道题考的就是这些知识点。

所以先考虑，对一个数组求前缀和，本质为求恒函数的自卷积。

卷积后出现相当于组合数C(n,0),C(n,1),C(n,2)...C(n,m)...C(n,n)

因为模数为23，为小模数，考虑卢卡斯定理 C(n,m)=C(n/p,m/p)*C(n%p,m%p)

因为这个题是求一个数组，所以变量m其实是要枚举的，姑且只关注n，即C(n)=C(n/p)*C(n%p)。这个式子形似一个23进制的进制转换算法。

即观察到对于a=在模23下，求若干次前缀和的a[1],a[23],a[23*23]...a[23^k]可以表示一个23进制数

所以答案为求n-1在23进制下，各个数位的数字分段出现的次数*段长(段长为23^(k-1)*22)+前导a的贡献+s0的贡献。

核心代码

int main()
{
    using Mint = chino::ModInt<998244353>;
    long long n;
    int m;
    vec_t<char, 1> s(MAXN);
    read(n, m, s.data());
    if (n == 1)
    {
        println(0);
        return 0;
    }
    Mint prea = 0ll;
    for (auto i = 0; i < m; ++i)
    {
        prea += s[i] == 'a';
        if (s[i] != 'a')break;
    }
    if (prea.get() == m)
    {
        println(-1);
        return 0;
    }

    auto log23 = [](long long n)
    {
        long long ans = 0;
        while (n)
            n /= 23, ++ans;
        return ans;
    };
    auto C2 = [](Mint n)
    {
        return n * (n - 1) / 2;
    };
    auto ans = (prea + 1) * C2(n);
    auto lim = log23(n - 1);
    auto sum = vec_t_create<Mint, 100, 3>(0);
    auto val = vec_t_create<Mint, 100>(0);
    long long base = 1;
    for (auto i = 0; i < lim; ++i)
    {
        val[i] = base * 22;
        base *= 23;
    }
    base = 23;
    for (auto i = 0; i < lim; ++i)
    {
        sum[i][0] = (n - 1) / base;  //group[cnt]
        sum[i][1] = (n - 1) % base;  //group[cnt]++
        sum[i][2] = base;            //total group
        base *= 23;
    }
    for (auto i = 0; i < lim; ++i)
    {
        ans = (ans + C2(sum[i][0]) * (sum[i][2] - sum[i][1]) * val[i]);
        ans = (ans + C2(sum[i][0] + 1) * sum[i][1] * val[i]);
        ans = (ans + sum[i][0] * val[i]);
    }
    println(ans.get());
    return 0;
}

J、智乃的相亲活动

题意

给定无向二分图，每个点随机选择对面集合中的一个有边相连的点，问所选点去重后个数的期望。

题解

经典高考问题

期望公式：

注意期望的加法公式并不要求变量与是独立的。

无论和是否存在一些互斥或者由于其他关系产生影响，你都可以通过这个公式计算。

虽然有点反直觉，但请务必记住：和的期望等于期望的和。

所以只要单独计算每个人成为心动男/女嘉宾的期望，直接求和就可以了。

以男嘉宾为例，答案为：，其中表示第个男嘉宾，表示第个女嘉宾，表示第个男嘉宾与第个女嘉宾存在好感关系，表示与第个女嘉宾存在好感关系的男嘉宾数目。

核心代码

int main()
{
    int n, m, k;
    using Mint = chino::ModInt<int(1e9 + 7)>;
    read(n, m, k);
    auto g = vec_t_create<int, MAXN, 0>(0);
    auto G = vec_t_create<int, MAXN, 0>(0);
    Mint ans1(0), ans2(0);
    for (int i = 1; i <= k; ++i)
    {
        int u, v;
        read(u, v);
        g[u].push_back(v);
        G[v].push_back(u);
    }
    auto calc = [](int n, const vec_t<int, 2> &g, const vec_t<int, 2> &ig) -> Mint
    {
        Mint ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            Mint p(1);
            for (auto &j: g[i])
            {
                p = p*(Mint(1) - Mint((long long) ig[j].size()).inverse());
            }
            ans = ans + 1 - p;
        }
 
        return ans;
    };
    println("modint");
    println(calc(n, g, G).get(), calc(m, G, g).get());
    return 0;
}

K、智乃的“黑红树”

题意

构造一颗二叉树，深度为奇数的节点有个深度为偶数的节点有个，且二叉树结点要么同时拥有孩子，要么为叶节点。

有两种方法，bfs或者直接构造，直接构造更困难。所以这里推荐用bfs法。

算法一：bfs

创建两个队列，队列中存放当前作为黑色和红色的叶子节点，不断循环直到无法再往下多构造一层时终止。如果此时恰好二叉树满足条件，则输出，否则无解。

核心代码

struct solver_ 
{
    int total{};
    vec_t<int, 1> lch, rch;
    int _b, _r;

    void init(int b, int r) 
    {
        _b = b;
        _r = r;
        lch = vec_t<int, 1>(b + r + 1, -1);
        rch = vec_t<int, 1>(b + r + 1, -1);
    }
    bool _build(queue<int>& q_out, queue<int>& q_in, int& cnt) 
    {
        if (!q_out.empty() && cnt >= 2) 
        {
            auto root = q_out.front();
            q_out.pop();
            lch[root] = ++total;
            q_in.push(total);
            rch[root] = ++total;
            q_in.push(total);
            cnt -= 2;
            return true;
        }
        return false;
    }
    int build() 
    {
        queue<int>qb, qr;
        total = 1;
        _b--;
        qb.push(1);
        while (_build(qr, qb, _b) || _build(qb, qr, _r));
        return !(_b | _r);
    }
};

算法二：直接构造

考虑这么一个更简单的判定性问题，使用个黑、个红点构造的可行性。

问题可以转化成，个节点完全二叉树，深度为偶数的节点最多有多少个、最少有多少个。合法的

如此，我们可以设计一个校验器检查某个构造步骤的合法性。

struct checker_
    {
        int get_sequence_length(int n)
        {
            return ((n + 1) / 2 - 1) / 3 + 1;
        }

        int get_sequence_begin(int n)
        {
            return ((n + 1) / 6 + 1) * 2 - 1;
        }

        int get_sequence_end(int n)
        {
            return get_sequence_begin(n) + 2 * (get_sequence_length(n) - 1);
        }

        bool legal(int a, int b)
        {
            if (a < 0 || b < 0 || !((a + b) & 1) || (b & 1))
            {
                return false;
            }
            int n = a + b;
            return get_sequence_begin(n) <= a && a <= get_sequence_end(n);
        }
    } checker;

接下来我们想一种方式固定构造，由于题目限制只和深度有关，所以可以考虑用左子树递归扩展，右子树构造的方式。（因为两个子树等价，所以相当于递归构建的是二叉树的最长链，把它直接放到左子树）。接下来右子树其实只有两种情况，要么放一层，要么放两层。其他情况都可以被这两种情况表示。

核心代码

int build(int a, int b)
    {
        int root = ++total;
        if (a == 1 && b == 0)return root;
        // b,a-1
        if (checker.legal(b - 1, a - 1))
        {
            lch[root] = build(b - 1, a - 1);
            rch[root] = build(1, 0);
        } else
        {
            lch[root] = build(b - 1, a - 3);
            rch[root] = build(1, 2);
        }
        return root;
    }

完整代码

#include <bits/stdc++.h>

using namespace std;
///------------------ c++ -------------------
void read()
{
}

void read(int &x)
{
    scanf("%d", &x);
}

void read(long long &x)
{
    scanf("%lld", &x);
}

void read(char *x)
{
    scanf("%s", x);
}

void print(const int &x)
{
    printf("%d", x);
}

void print(const long long &x)
{
    printf("%lld", x);
}

void print(const char *x)
{
    printf("%s", x);
}

///------------------ c++11 -------------------
template<typename T, std::size_t N>
struct _vec : public _vec<std::vector<T>, N - 1>
{
};

template<typename T>
struct _vec<T, 0>
{
    using type = T;
};
template<typename T, std::size_t N>
using vec_t = typename _vec<T, N>::type;

template<typename T>
vec_t<T, 0> vec_t_create(const T &data)
{
    return data;
}

template<typename T, size_t arg0, size_t... args>
vec_t<T, sizeof...(args) + 1> vec_t_create(const T &data)
{
    return vec_t<T, sizeof...(args) + 1>(arg0, vec_t_create<T, args...>(data));
}

template<typename T>
void vread(T *begin, T *end)
{
    for (T *i = begin; i != end; ++i)
    {
        read(*i);
    }
}

template<typename T>
void print(std::vector<T> &v)
{
    for (auto i = 0; i < v.size(); ++i)
    {
        print(v[i]);
        if (i + 1 != v.size())putchar(' ');
    }
}

template<typename T>
void read(std::vector<T> &v)
{
    for (auto &i: v)
    {
        read(i);
    }
}


template<typename T, typename... Args>
void read(T &&arg0, Args &&...args)
{
    read(arg0);
    read(args...);
}

void println()
{
}

template<typename T, typename... Args>
void println(T &&arg0, Args &&...args)
{
    print(arg0);
    if (sizeof...(args))
    {
        printf(" ");
        println(args...);
    } else
    {
        printf("\n");
    }
}

//-----------------------------------------
struct solver_
{
    int a_, b_;
    bool legal;
    int total{};
    vec_t<int,1> lch, rch;

    void init(int a, int b)
    {
        a_ = a;
        b_ = b;
        legal = checker.legal(a, b);
        if (legal)
        {
            lch = vec_t<int,1>(a + b + 1, -1);
            rch = vec_t<int,1>(a + b + 1, -1);
        }
    }

    int build(int a, int b)
    {
        int root = ++total;
        if (a == 1 && b == 0)return root;
        // b,a-1
        if (checker.legal(b - 1, a - 1))
        {
            lch[root] = build(b - 1, a - 1);
            rch[root] = build(1, 0);
        } else
        {
            assert(checker.legal(b - 1, a - 3));
            lch[root] = build(b - 1, a - 3);
            rch[root] = build(1, 2);
        }
        return root;
    }

    void solve()
    {
        if (!legal)return;
        total = 0;
        build(a_, b_);
    }

    struct checker_
    {
        int get_sequence_length(int n)
        {
            return ((n + 1) / 2 - 1) / 3 + 1;
        }

        int get_sequence_begin(int n)
        {
            return ((n + 1) / 6 + 1) * 2 - 1;
        }

        int get_sequence_end(int n)
        {
            return get_sequence_begin(n) + 2 * (get_sequence_length(n) - 1);
        }

        bool legal(int a, int b)
        {
            if (a < 0 || b < 0 || !((a + b) & 1) || (b & 1))
            {
                return false;
            }
            int n = a + b;
            return get_sequence_begin(n) <= a && a <= get_sequence_end(n);
        }
    } checker;
};

int main()
{

    int T, a, b;
    solver_ solver;
    read(T);

    while (T--)
    {
        read(a,b);
        solver.init(a, b);
        if (solver.legal)
        {
            println("Yes");
            solver.solve();
            for (int i = 1; i <= a + b; ++i)
            {
                println(solver.lch[i], solver.rch[i]);
            }
        } else
        {
            println("No");
        }
    }
    return 0;
}

L、M智乃的36倍数

easy

暴力枚举，或者只需要统计、、 这三种情况即可

核心代码

int main() {
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        a[x]++;
    }
    printf("%d\n",a[3]*a[6]+a[7]*a[2]+a[10]*a[8]);
    return 0;
}

hard

实际上有两种思路，一种是利用模的性质，另一种不用。如果不知道模的性质，可以考虑36实际上就是4的倍数和9的倍数。通过小学数奥，我们知道4的倍数就是后两位可以被4整除，9的倍数就是所有数位的和可以被9整除所以可以开桶统计，然后枚举桶的情况合并即可。

另一种做法，根据模的性质，两个数字求和模36实际上就是每一部分分别模36求和后再模36，所以可以直接开桶统计每个数字模36后是几，然后36还有个特殊性质，即不论多少位的，只要，剩下的数都为28。所以只需要知道它是不是10位数即可。

核心代码

int main(int argc, char const *argv[])
{
    int n;
    long long ans = 0;
    read(n);
    vec_t<long long, 1> a(n);
    vread(a.data(), a.data() + n);
    auto calc = [&]()
    {
        auto sum = vec_t_create<long long, 36>(0);
        for (auto &i : a)
        {
            for (int j = 0; j < 36; ++j)
            {
                if ((j * (i < 10LL ? 10LL : 28LL) + i) % 36 == 0)
                {
                    ans += sum[j];
                }
            }
            sum[i % 36]++;
        }
    };
    calc();
    reverse(a.begin(), a.end());
    calc();
    println(ans);
    return 0;
}