寒假集训补题.md

考点目录

注：第三第四场大概还没看一题多解的题解实现和解法

第一场

• L 牛牛学走路

  签到

• E 炸鸡块君的高中回忆

  数学

• H 牛牛看云

  组合数学 桶排序

• J 小朋友做游戏

  排序

• A 九小时九个人九扇门

  背包DP

• F 中位数切分

  贪心

• D 牛牛做数论

  欧拉函数 素数

• C Baby's first attempt on CPU

  模拟 贪心

• I B站与各唱各的

  组合数学 逆元 数学 轮换对称性/拉格朗日乘数法

• B 炸鸡块君与FIFA22

  ST表

• K 冒险公社

  DP

• G ACM is all you need

  差分 离散化 数学

第二场

• A 小沙的步伐

  模拟

• D 小沙的杀球

  贪心

• H 小沙的数数

  位运算 组合数学

• F 小沙的算数

  分块 二分

• I 小沙的构造

  构造 模拟

• G 小沙的身法

  树上前缀和

• E 小沙的长路

  图论 欧拉回路

• A 小沙的炉石

  二分 / 数学

• L 小沙的remake(普通版)

  线段树/树状数组 组合数学 DP

• M 小沙的remake(竞速版)

  基数排序

• B 小沙的魔法

  并查集 离散化

• D 小沙的涂色

  构造

• J 小沙的Dota

  线段树 DP

第三场

• A 智乃的Hello XXXX

  签到

• D 智乃的01串打乱

  签到

• B 智乃买瓜

  背包DP

• L 智乃的数据库

  set 哈希表

• E 智乃的数字积木(easy version)

  模拟 排序

• G 智乃的树旋转(easy version)

  树

• C 智乃买瓜(another version)

  逆向 构造

• J 智乃的C语言模除方程

  前缀和 数学

• H 智乃的树旋转(hard version)

  splay单旋 构造

• K 智乃的C语言模除方程(another version)

  整除分块 数列

• F 智乃的数字积木(hard version)

  启发式合并 并查集

第四场

• E 真假签到题

  签到 数学

• H 真真真真真签到题

  签到 数学

• K 小红的真真假假签到题题

  进制 构造

• A R

  滑动窗口

• C 蓝彗星

  差分

• F 小红的记谱法

  签到 小模拟

• J 区间合数的最小公倍数

  LCM 唯一分解定理

• I 爆炸的符卡洋洋洒洒

  DP

• D 雪色光晕

  计算几何

• B 进制

  线段树 / 树状数组

• G 子序列权值乘积

  拓展欧拉定理 组合数学

• L 在这冷漠的世界里光光哭哭

  二分 前缀和

第五场

• J 三国小孩

  签到

• G 163小孩

  枚举 / DFS / 组合数学

• I 兔崽小孩

  二分 前缀和

• D 数位小孩

  数位DP / DFS

• A 疫苗小孩

  二分

• C 战棋小孩

  记忆化DFS + DP / 贪心 + 二进制枚举 + 排序

• E 复苏小孩

  线段树 矩阵乘法

• F 飞车小孩

  结构体排序 组合数学

• K 造梦小孩

  整除分块 前缀和 线段树/树状数组

• B 乒乓小孩

  思维

• H 一六三小孩

  构造 随机 枚举

第六场

• I A+B问题

  高精度 进制

• F +-串

  思维 贪心

• E 骑士

  排序 / 前缀和

• D 删除子序列

  思维 字符串(子序列匹配) 贪心

• J 牛妹的数学难题

  组合数学 生成函数 线性逆元

• H 寒冬信使2

  博弈论 记忆化DFS 二进制枚举

• B 价值序列

  思维 组合数学

• G 迷宫2

  BFS

• A 回文大师

  字符串哈希+二分+差分 / KMP树前缀和

• C 数组划分

  单调栈 二分 / 并查集

第一场

比赛日志：

开场看第一题，一眼没啥思路，然后瞬间切最后一题看，一眼签到有思路，马上写，刷新看到有人交了，证明确实是签到题，然后很容易过掉了，L题结束，语法题，三分钟过题排名大约18。然后看榜做题，看到E题，是个简单的数学规律题，花了一会儿很快推导出了规律，一交一个准，切掉了，截止目前八分钟，大概还是二十多。然后看榜，有好像多选了，这时候我先去看感觉比较能做的一道求和题，很快发现可以桶，然后发现很尴尬不会计数，一交一发WA，然后分奇偶，急了，没有仔细验证，又WA。然后又WA了一次，终于找对了规律，花了不少时间，终于切掉了这道H题，截止目前半小时。

然后去看J题，以为是简单的排序，然后WA掉了，仔细思考，发现会滑窗，不是均分的，然后把滑窗用数组合并优化掉，然后过掉了这道题，总用时45分钟。然后看A题去了，仔细思考几分钟，发现不过是个dp签到，然后很快debug一下签了，总用时60分钟。此时闲下功夫看榜，发现排27。

然后去搞过题很多的F题，我一直有在想一直没想出来，第一眼以为是两个堆维护中位数，然后二分长度，结果发现二分不出来，推过去直接得到结论的，然后过题人数越来越多，但是我发现自己一开始的结论就错了，我连样例都原来过不了，我的做法有问题，不能贪心顺推，然后仔细观察，猛然按与m的大小关系分为两类，然后很快发现直接计数即可。然后去猜结论，以为C很简单直接暴力猜一发，然后喜提炸掉了。然后分散精力去看数论D题，打表找规律，找了好一会儿，找出来了，然后写出来切掉了。然后C，发现比较麻烦，想了很久推了很多，发现有连带关系，在原图矩阵里，可以连带一个三角。我在想一开始看到这么小的数据就以为是可以DFS，记忆化乃至模拟退火，然后后来发现好像可以先把i-1的全部切掉，就这样个贪心法，对i-1,i-2,i-3都贪一下，然后喜提挂掉了。然后发现i-1可以不考虑后续，但是i-3时应该一有就搞，然后给我搞出来了切掉了。

然后去看过题人数比较少的I，仔细一看发现可以写出一个函数求最值，然后对数求导吧、一般求导吧都比较困难，然后观察发现符合轮换对称性，直接取0.5，然后验证了好一会儿，然后一交一个过，逆元裸题。F是110过的，D是157，C是202，然后紧接着I在217就过了，所以很快。

然后已经接近尾声了，看了看剩下的题目，生下三道题，压轴没思路，B怀疑是卷积或者DP，K怀疑是贪心，根据相似经验。然后K没想出来，专门去搞B，很开始一眼就怀疑前缀和，然后仔细思考了很久发现好像还是可以前缀和，虽然复杂度显然不敢恭维，只能期望数据弱，然后一交因为实现和各种问题一直在WA，反正就是无了。剩下这么久时间基本上啥都没过。终榜排名一路掉，从50多掉到84，一共三千多人。

L 牛牛学走路

直接模拟即可

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
ll t, n;
#define sc(x) scanf("%lld", &x)
signed main()
{
    sc(t), sc(n);
    while (t--)
    {
        sc(n);
        ll x = 0, y = 0;
        db d = 0;
        string t;
        cin >> t;
        for (int i = 0, ie = t.size(); i < ie; ++i)
        {
            if (t[i] == 'L')
            {
                --x;
            }
            else if (t[i] == 'R')
            {
                ++x;
            }
            else if (t[i] == 'U')
            {
                ++y;
            }
            else if (t[i] == 'D')
            {
                --y;
            }
            d = max(d, sqrt(x * x + y * y));
        }
        printf("%.12lf\n", d);
    }
    return 0;
}

E 炸鸡块君的高中回忆

若只有一个人带不走人。若卡比人多，不用带人。否则，第一次进 $m$ 人，接下来每次都进 $m-1$ 人，直接整除即可。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll t, n, m;
signed main()
{
    sc(t);
    while (t--)
    {
        sc(n), sc(m);
        if (m == 1 && n > 1)
        {
            printf("-1\n");
        }
        else if (m >= n)
        {
            printf("1\n");
        }
        else
        {
            printf("%lld\n", 1LL + 2 * (ll)ceil(1.0 * (n - m) / (m - 1)));
        }
    }
    return 0;
}

H 牛牛看云

原式即求两两组合，含自身重复。先桶排一下，然后对不自身重复部分，直接相乘就是数目。对相同的而言，有自己跟自己得 $n$ 种，自己跟另外的，有 $C_2^n=\dfrac{n(n-1)}2$ ，最后合起来有 $\dfrac{n(n+1)}2$ 种

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, bin[1024], ans, m = 1000;
signed main()
{
    sc(n);
    for (ll i = 1; i <= n; ++i)
    {
        ll x;
        sc(x);
        bin[x]++;
    }
    for (ll i = 0; i <= m; ++i)
    {
        for (ll j = i + 1; j <= m; ++j)
        {
            ans += abs(i + j - m) * (bin[i] * bin[j]);
        }
    }
    // printf("%lld\n", ans);
    for (ll i = 0; i <= m; ++i)
    {
        ans += abs(i + i - m) * ((bin[i] + 1) * bin[i] / 2);
    }
    printf("%lld", ans);
    return 0;
}

J 小朋友做游戏

对总人数 $n$ ，可以选 $\lfloor\dfrac n2\rfloor$ 个闹腾的人，穿插放(因为成环，所以不是上取整)，但是并不必然选这么多人，因为可能全选安静的人幸福度更大。所以在排序好 $a,b$ 后，再排序 $a$ 加上前 $\lfloor\dfrac n2\rfloor$ 个 $b$ ，然后再排序一次，然后取前 $n$ 大即可

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 20010
ll t, a, b, n, va[mn], vb[mn];
signed main()
{
    sc(t);
    while (t--)
    {
        sc(a), sc(b), sc(n);
        for (ll i = 0; i < a; ++i)
        {
            sc(va[i]);
        }
        sort(va, va + a);
        reverse(va, va + a);
        for (ll i = 0; i < b; ++i)
        {
            sc(vb[i]);
        }
        sort(vb, vb + b);
        reverse(vb, vb + b);
        if ((n + 1) / 2 > a || a + b < n)
        {
            printf("-1\n");
            continue;
        }
        ll nb = n / 2;
        if (nb > b)
        {
            nb = b;
        }
        ll na = n - nb;
        if (nb < 0 || na < 0)
        {
            printf("-1\n");
            continue;
        }
        for (ll i = 0; i < nb; ++i)
        {
            va[a + i] = vb[i];
        }
        sort(va, va + a + nb);
        reverse(va, va + a + nb);
        ll ans = 0;
        for (ll i = 0; i < n; ++i)
        {
            ans += va[i];
        }
        // printf("%lld %lld\n", na, nb);
        printf("%lld\n", ans);
    }
    return 0;
}

A 九小时九个人九扇门

直接对其推一个背包 DP 即可，比较板子的题目。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mod 998244353
ll n, a, dp[2][13];
ll root(ll x)
{
    if (x < 10)
    {
        return x;
    }
    ll r = 0;
    while (x > 0)
    {
        r += x % 10;
        x /= 10;
    }
    return root(r);
}
signed main()
{
    sc(n);
    dp[0][0] = 1;
    for (ll i = 1, now = 1, prev = 0; i <= n; ++i)
    {
        sc(a);
        a = root(a);
        memset(dp[now], 0, sizeof dp[now]);
        for (ll j = 0; j <= 9; ++j)
        {
            ll k = root(j + a);
            // printf("(%lld)", dp[prev][j]);
            dp[now][k] += dp[prev][j];
        }
        for (ll j = 0; j <= 9; ++j)
        {
            dp[now][j] = (dp[now][j] + dp[prev][j]) % mod;
            // printf("%lld ", dp[now][j]);
        }
        // printf("\n");
        now ^= 1, prev ^= 1;
    }
    for (ll i = 1; i <= 9; ++i)
    {
        printf("%lld ", dp[n & 1][i]);
    }
    return 0;
}

F 中位数切分

对于大于等于中位数的，每个自身可以划一段。对于小于的，为了让整一段凑够中位数，必须再找大于等于中位数的其他段借两个数，借的过程等于删掉一段，并和另一端组成一段。

可以直接贪心这个过程，即发现大于等于中位数的，若当前没有需要借的就自成一段，有就给借；对小于中位数的，一直找前面已有的借，找不到就记着先。最后等效于看有多少个大于等于 $m$ 的数减去小于的数，就是段数了。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll t, n, m, a[mn], k;
signed main()
{
    sc(t);
    while (t--)
    {
        sc(n), sc(m), k = 0;
        for (ll i = 1; i <= n; ++i)
        {
            sc(a[i]);
            k += a[i] >= m ? 1 : -1;
        }
        printf("%lld\n", k > 0 ? k : -1);
    }
    return 0;
}

D 牛牛做数论

打表可知，最大的是素数，最小的是素数乘积。

证明：$H(x)=\prod(1-\dfrac1{p_i})$ ，所以素数越多值越少。而对素数本身，只有一项目前已知最大的乘数，所以显然是最大的。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll t, n;
vector<ll> hmin;
bool isprime(ll p)
{
    if (p == 2 || p == 3)
        return true;
    if (p < 2 || (p % 6 != 1 && p % 6 != 5))
        return false;
    for (ll i = 5; i * i <= p; i += 6)
        if (p % i == 0 || p % (i + 2) == 0)
            return false;
    return true;
}
signed main()
{

    for (ll i = 0, lt = 2, p = 3; i < 12; ++i)
    {
        hmin.emplace_back(lt);
        lt *= p;
        ++p;
        while (!isprime(p))
        {
            ++p;
        }
    }
    sc(t);
    while (t--)
    {
        sc(n);
        if (n == 1)
        {
            printf("-1\n");
            continue;
        }
        ll lfi = lower_bound(hmin.begin(), hmin.end(), n) - hmin.begin();
        ll lf = hmin[lfi] > n ? hmin[lfi - 1] : hmin[lfi];
        ll rf = n;
        while (!isprime(rf))
            --rf;
        printf("%lld %lld\n", lf, rf);
    }
    return 0;
}

C Baby's first attempt on CPU

可以看作是模拟题。对于输入的矩阵，构造一个矩阵，设 $b_{i,j}$ 代表第 $i$ 条语句与 $i-j$ 语句是否有关联，如果有，需要插入多少条语句，即 $b_{i,j}$ 表示需要插入 $b_{i,j}$ 条语句才能消解联系。

如果在第 $i$ 条语句和上一条语句 $i-1$ 之间插入一条语句，那么所有 $b_{i,.}$ 都会减 $1$ ，即第 $i$ 条语句与 $i-1,i-2,i-3$ 的联系减 $1$ ，且下一条语句 $i+1 $和 $i-1, i-2$ 的联系也会减 $1$ ；相似地， $i+2$ 与 $i-1$ 的联系也减 $1$ 。在矩阵表达上，即在 $a_{i,1}$ 在左上角减去一个这样的矩阵： $$ \begin{bmatrix} 1&1&1\ 0&1&1\ 0&0&1 \end{bmatrix} $$ 不难举例子发现这个矩阵的合理性。

问题转化为对 $b$ 矩阵最少减多少次得到零矩阵。

可以发现第一列值有多少就一定要减多少，其他地方减的矩阵不可能帮到它，所以先扫第一列，有就全减了，然后得到新的矩阵 $b$ 。

第二列，上一行减的可以帮助这一行，所以如果有相邻的两个值，优先减上面的必然最优。

在考虑自己列的时候是不需要考虑它右边的列的，因为必然 $b_{i,j} \ge b_{i,j+k}$ ，只要自己消掉了，右边能消的也消完了。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, a[110][5], ans;
void f(ll &x, ll v)
{
    x = max(x - v, 0LL);
}
void cls(ll i, ll v)
{
    f(a[i][1], v);
    f(a[i][2], v);
    f(a[i][3], v);
    f(a[i + 1][2], v);
    f(a[i + 1][3], v);
    f(a[i + 2][3], v);
}
signed main()
{
    sc(n);
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 1; j <= 3; ++j)
        {
            sc(a[i][j]);
            if (a[i][j])
            {
                a[i][j] = 4 - j;
            }
        }
    }
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 1; j <= 3; ++j)
        {
            if (a[i][j] > 0)
            {
                ans += a[i][j];
                cls(i, a[i][j]);
            }
        }
    }
    printf("%lld", ans);
    return 0;
}

I B站与各唱各的

因为相互独立，所以设第 $i$ 句选择唱的概率为 $p$ ，根据独立性可知，每个 UP 主每一句都应当选择相同的 $p$ 。那么总成功率为 $m$ 倍每个句子成功率，即： $$ E=m(1-p^n-(1-p)^n) $$ 以 $p(0\le p\le 1)$ 为自变量的上述函数 $E(p)$ 的最值不好求。但是根据轮换对称性可知， $p=\dfrac12$ 时，会得到最值，且不难发现一定是函数最大值。

拉格朗日乘数法数学证明：

设 $L(x,y,\lambda)=1-x^n-y^n+\lambda(x+y-1)$

求偏导数，联立以 $x,y,\lambda$ 为未知数的三元方程： $$ \begin{cases} \dfrac{\partial L}{\partial x}&=-nx^{n-1}+\lambda&①\ \dfrac{\partial L}{\partial y}&=-ny^{n-1}+\lambda&②\ \dfrac{\partial L}{\partial\lambda}&=x+y-1&③\quad \end{cases} $$ $①-②$ ，移项得：$x=y$ ，联立 $③$ 得 $x=y=\dfrac12$

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, m, mod = 1e9 + 7, t;
ll qpow(ll a, ll b)
{
    ll r = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
        {
            r = r * a % mod;
        }
        a = a * a % mod;
    }
    return r;
}
ll inv(ll x)
{
    return qpow(x, mod - 2);
}
ll e(ll a, ll b)
{
    return m * (1 - qpow(a, n) * inv(qpow(b, n)) % mod - qpow(b - a, n) * inv(qpow(b, n)) % mod + 2 * mod) % mod;
}
signed main()
{
    sc(t);
    while (t--)
    {
        sc(n), sc(m);
        printf("%lld\n", e(1, 2));
    }
    return 0;
}

B 炸鸡块君与FIFA22

定义 $st_{k,i,j}$ 表示初试分数模 $3$ 余 $k$ 时，从 $i$ 出发，走 $2^j-1$ 步后得到的分数，那么接下来就是 ST 表裸题了。注意每次跳完后， $k$ 会变。

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 200010
#define lg 19
ll n, q, l, r, s, st[3][mn][lg], nx[mn][lg];
char t[mn];
signed main()
{
    sc(n), sc(q), scanf("%s", t + 1);
    for (ll i = 0; i < lg; ++i)
    {
        nx[n + 1][i] = n + 1;
    }
    for (ll i = 1; i <= n; ++i)
    {
        nx[i][0] = i + 1;
        for (ll k = 0; k < 3; ++k)
        {
            st[k][i][0] = (t[i] == 'W') + (-1) * (t[i] == 'L') * (k % 3 != 0);
        }
    }
    for (ll j = 1; j < lg; ++j)
    {
        for (ll i = 1; i <= n; ++i)
        {
            nx[i][j] = nx[nx[i][j - 1]][j - 1];
            for (ll k = 0; k < 3; ++k)
            {
                st[k][i][j] = st[k][i][j - 1] + st[(k + st[k][i][j - 1]) % 3][nx[i][j - 1]][j - 1]; //not [][1 << (j - 1)][]
            }
        }
    }
    while (q--)
    {
        sc(l), sc(r), sc(s);
        // for (ll d = r - l + 1, p = 63 - __builtin_clzll(d); d > 0; d >>= 1, --p)
        // {
        //     if (d & 1)
        //     {
        //         s += st[(s + 3) % 3][l][p];
        //         l += 1 << p;
        //     }
        // }
        for (ll i = lg - 1; i >= 0; --i)
        {
            if (nx[l][i] <= r + 1)
            {
                s += st[(s + 3) % 3][l][i];
                l = nx[l][i];
            }
        }
        printf("%lld\n", s);
    }
    return 0;
}

K 冒险公社

设 $dp_{i,j,k}$ 表示前 $i$ 个字符的子串里，最后两个字符是 $j,k$ 时，最多可能有多少个绿岛

递推 $i$ 时，枚举 $i,i-1,i-2$ 所有可能的字符，然后判断是否符合输入描述，是的话就把方案数加起来，最后统计 $dp_{n,any,any}$ 即可

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll n, dp[mn][3][3], r = 0, g = 1, b = 2, ans = -1;
char s[mn];
signed main()
{
    sc(n), scanf("%s", s + 1);
    memset(dp, -0x3f, sizeof dp);
    for (ll x = 0; x < 3; ++x)
    {
        for (ll y = 0; y < 3; ++y)
        {
            dp[1][x][y] = (x == g); //无关紧要
            dp[2][x][y] = (x == g) + (y == g);
        }
    }
    for (ll i = 3; i <= n; ++i)
    {
        for (ll x = 0; x < 3; ++x)
        {
            for (ll y = 0; y < 3; ++y)
            {
                for (ll z = 0; z < 3; ++z)
                {
                    ll gs = (x == g) + (y == g) + (z == g);
                    ll rs = (x == r) + (y == r) + (z == r);
                    if ((s[i] == 'R' && rs > gs) || (s[i] == 'G' && gs > rs) || (s[i] == 'B' && rs == gs))
                    {
                        dp[i][x][y] = max(dp[i][x][y], (x == g) + dp[i - 1][y][z]);
                    }
                }
            }
        }
    }
    for (ll x = 0; x < 3; ++x)
    {
        for (ll y = 0; y < 3; ++y)
        {
            ans = max(ans, dp[n][x][y]);
        }
    }
    printf("%lld", ans);
    return 0;
}

G ACM is all you need

可以发现，固定 $i$ ，对于变量 $b$ ，使得变换后满足是局部最小值情况，一定是 $b$ 取一个连续的区间。对于每个 $i$ ，可以求出使得 $i$ 成为局部最小值的 $b$ 区间。那么这样就得到了 $n-2$ 个 $b$ 区间。只需要求出所有整点(进一步地可以简化为所有区间边界)里 (也可以反求，即求局部最大值)，覆盖次数的最值即可，这可以用离散化+差分解决。

具体而言，设 $i$ 的邻点排序后为 $x,y(x\le y)$ ：

• 如果 $f_i &lt; x$ ，则需要满足：$|f_i-b|+b < |x-b|+b$

  • 对 $b \le f_i$ ，两边直接去绝对值，得不等式恒成立

  • 对 $f_i &lt; b\le x$ ，去绝对值得到 $b-f_i &lt; x-b\Rightarrow b &lt; \dfrac{x+f_i}2$ ，因为 $b$ 是整数， 若右边本就是整数，即 $(x+f_i)\bmod 2=0$ ，则 $b$ 可取 $\le \dfrac{x+f_i}2-1$ ；否则，可取 $\le\lfloor\dfrac{x+f_i}2\rfloor$ ，合并为：$x\le \lfloor\dfrac{x+f_i}2\rfloor-(x+f_i\bmod 2\equiv 0)$

  • 对 $b\ge x$ ，得到恒不成立的不等式

  • 只要能满足 $|f_i-b|+b < |x-b|+b $ ，恒满足 $|f_i-b| +b&lt;|y-b|+b$ ，因为代入上述步骤同理计算得需要满足的是 $x\le \lfloor\dfrac{y+f_i}2\rfloor-(y+f_i\bmod 2\equiv 0)$

    稍加思索，发现函数 $\lfloor\dfrac p2\rfloor-(p\bmod 2\equiv0)=1-(p\bmod 2)+\lfloor\dfrac p2\rfloor$ ，同奇偶是单调增，从奇到奇 $+1$ 增了 $1$ ，所以是单调递增函数

• 如果 $f_i &gt; y$ ，同理：

  • $b\le y$ 恒不成立
  • $y &lt; b\le f_i$ ，得 $f_i-b &lt; b-y\Rightarrow b &gt;\dfrac{f_i+y}2$ ，本就是整数要 $+1$ ，本不是也要加，即 $b\ge \lfloor\dfrac{f_i+y}2\rfloor+1$
  • $b\ge f_i$ 恒成立
  • 同理，只要能满足这个不等式，另一个关于 $x$ 的恒满足

• 如果 $f_i=x$ 或 $f_i=y$ 至少其一成立，永远不可能成为最小值

• 否则，只能是夹在两者中间， $x &lt; f_i &lt; y$ ，需要同时满足： $$ \begin{cases} |f_i-b|+b < |x-b|+b\ |f_i-b|+b < |y-b|+b \end{cases} $$

  • $b\le x$ ，则不等式一恒不成立，不等式二恒成立，无解；同理， $b\ge y$ 也无解
  • $x &lt; b\le f_i$ ，$f_i-b < b-x\Rightarrow b\ge\lfloor\dfrac{f_i+x}2\rfloor+1$ ，不等式二恒成立
  • $f_i &lt; x\le y$ ，$b-f_i < y-b\Rightarrow b\le \lfloor\dfrac{y+f_i}2\rfloor-(y+f_i\bmod 2\equiv 0)$，不等式一恒成立

综上所述，可以写成代码。

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
#define big 0x7fffffff
ll n, a[mn], t, cnt;
map<ll, ll> m;
signed main()
{
    sc(t);
    while (t--)
    {
        sc(n), cnt = 0, m.clear();
        for (ll i = 1; i <= n; ++i)
        {
            sc(a[i]);
        }
        for (ll i = 2; i < n; ++i)
        {
            ll lt = min(a[i + 1], a[i - 1]), gt = max(a[i + 1], a[i - 1]);
            if (a[i] < lt)
            {
                ++cnt;
                m[(lt + a[i]) / 2 - ((lt + a[i]) % 2 == 0) + 1]--;
            }
            else if (a[i] > gt)
            { // removed plus infinity
                m[(gt + a[i]) / 2 + 1]++;
            }
            else if (!(a[i] == gt || a[i] == lt))
            {
                m[(lt + a[i]) / 2 + 1]++;
                m[(gt + a[i]) / 2 - ((gt + a[i]) % 2 == 0) + 1]--;
            }
        }
        ll ans = cnt;
        for (auto i : m)
        {
            cnt += i.second;
            ans = min(ans, cnt);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

第二场

比赛日志：

一开始我随机看了两道题，都没有一眼的思路，然后再退回去，发现榜单有一道题已经有不少人通过了，然后点进去一看一个签到题，大致锁定了题意然后马上开始做，一边做一边思考细节，把二维改成了一维，然后重新理解了纠正的题意，然后本地测试一下，对了，然后直接赶时间一交。一惊，竟然CE了。然后一看是本地给我自己加了cstring头的strlen，然后牛客没有(因为手机跑不了万能头，所以没开)。然后编译器写了一个，猛然发现牛客编辑器无法全选覆盖，然后只得再在网页再写一次，然后跑网页本地测试，一发一个AC。手机发出通告的音效和AC的音效。这时候已经10分钟了(手机写代码速度不敢恭维)，已经有九百多号人过了这道题了

然后到家了，手忙脚乱地打开好电脑的环境，然后仔细看过了签到K之后的C题，然后思考片刻，大概觉得是个0-1背包，然后写着写着发现是可以贪心的，即当前能杀球一定杀，不然留着也是等效的，然后平堆，然后本地对了一交一个段错误，好家伙我把1e6写成了1e5，天大的罪过，然后纠正过后切掉了C题，这时总用时是23分种(指正：不是总罚时，是过这道题时距开赛的时间差，上同)。排名自然一点都不好看。

然后按照榜单，去看H题。想了好一会的，虽然很快发现了异或肯定不会拆高位，然后这样往下想，发现好像不过是一个组合数学桶和球的问题，并且发现了答案。然后稳妥测试了几下，一交一个WA。然后思考片刻，发现是1e18乘法取模爆long long，然后改了一下，然后发现自己测试的时候前后结果一致，然后也不敢贸然交，然后猛然发现不能写(a%p*b%p)%p，后者内部还得括号多一次，然后果然不一样了，一交一发AC，此时总用时33，罚时上天。

然后看F题，一眼以为线段树，然后仔细思考，很快发现加号分割即可，乘法的连一块，然后编号上可以二分找，然后再用点逆元。实现了蛮久，debug了好一阵子，然后一交一发AC，总用时58。

然后看E题，没啥思路，是完全图的结论题。想写暴力验证答案，在位运算穷举下，先写了个floyd，然后求了半天发现都不会，不会改成最长路……负吧，发现带负环了，max吧，又答案不对。然后又用dijkstra重写，发现答案都差不多，并且发现自己建图一堆错误。然后还是不行，看了看johnson，没写，然后想了想干脆DFS吧。然后看了一下通告，发现最长路的定义完全不一样啊，然后写DFS，又发现了建图的一堆错误，然后跑了个暴力，但是结果跟自己推了半天的纸面结果的最小值不一样，然后我怀疑程序错了，debug了半天，但是6以上完全跑不出来。然后纸面也搞不出什么新的东西。试着猜了两次结论，都WA了。已经被过了这道题的反超了。

然后姑且放弃了这道题，看了看别的题目，看到一道比较少人做的I题，一看构造题，思考了片刻感觉有思路啊，然后实现了……有点久，大概是半小时切了这道题。然后一看总用时都205分钟了。不过我的排名还是没有上来。

然后E又在思考，想不出什么东西。A我也想不出来，一开始以为是斯特林数什么的，然后不行，又想了想，纠正了读题错误，然后发现是前n+m项和里挑走若干个数，没有思路。然后又发现了理解的错误，然后发现更难了，想不出来。

然后再往更深去看题目，看到一道G题，思索片刻，觉得可能是树剖+主席树，然后还惊呼怎么能这么难。然后想了想线段树不需要，然后再想了想，树上前缀和LCA也能做，然后综合考量，我还是选择了后者。然后从自己的洛谷AC记录里搞了一份LCA板子上手魔改，然后调试了半天，现推了树上前缀和，然后得到了代码。然后一发一个MLE，我惊了，计算后发现long long会炸空间，改成int毫不犹豫又交了一次，结果WA了。仔细思考，发现是改的时候有会爆long long的地方，还是得换回long long，然后通篇检查了一次，又交了一发，终于AC了。此时已经还剩十分钟不到就结束了。

想着最后再随便碰碰E题，但是还是没这么做。在看I之前自己还病急乱投医又猜了四次E题，都以失败告终。

K 小沙的步伐

要么在 $5$ 原地接球，要么走出然后走回 $5$ 接球。

赛时 AC 代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
char t[1000010];
ll cnt[12];
ll n, now=5;
signed main()
{
    scanf("%s", t);
    n=strlen(t);
    for(ll i=0;i<n;++i)
    {
        ll c=t[i]-'0';
        if (c==now)
        {
            continue;
        }
        else
        {
            cnt[5]++;
        }
        if (5!=c)
        {
            cnt[c]++;
        }
        now=5;
    }
    for (ll i=1;i<=9;++i)
    {
        printf("%lld ",cnt[i]);
    }
    return 0;
}

D 小沙的杀球

可以证明，只要能杀就杀的贪心是最优的。如果想攒体力蹲下一个球再杀，不会比现在就杀更优。因为如果还有球杀，就是等效的(只是把 $+a,-b$ 对换了而已)，没有就是更差的方案。那么明白这一点后，就可以直接顺推了。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1000010
ll n, a, b, dp[mn], hp[mn], x;
char t[mn];
signed main()
{
    scanf("%lld%lld%lld%s", &x, &a, &b, t + 1);
    dp[0] = 0;
    hp[0] = x;
    n = strlen(t + 1);
    for (ll i = 1; i <= n; ++i)
    {
        if (t[i] == '1')
        {
            if (hp[i - 1] >= a)
            {
                dp[i] = dp[i - 1] + 1;
                hp[i] = hp[i - 1] - a;
            }
            else
            {
                dp[i] = dp[i - 1];
                hp[i] = hp[i - 1] + b;
            }
        }
        else
        {
            dp[i] = dp[i - 1];
            hp[i] = hp[i - 1] + b;
        }
        // printf("%lld\n", dp[i]);
    }
    printf("%lld", dp[n]);
    return 0;
}

优化代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sc(x) scanf("%lld", &x)
ll x, a, b, n, ans;
char s[1000010];
signed main()
{
    sc(x), sc(a), sc(b), scanf("%s", s + 1), n = strlen(s + 1);
    for (ll i = 1; i <= n; ++i)
    {
        if (s[i] == '1' && x >= a)
        {
            ++ans, x -= a;
        }
        else
        {
            x += b;
        }
    }
    printf("%lld", ans);
    return 0;
}

H 小沙的数数

可以把 $m$ 拆分为 $n$ 个二进制数。由于异或的性质能消掉两个同位 $1$ ，所以在最优方案里，一定不会出现两个数在任一位相同，可以使得异或最大，此时最大值为 $m$ ，一种最大的方案是 $1$ 个 $m$ 和 $n-1$ 个 $0$。显然没有方案能比它更优

设 $m$ 有 $k$ 个位有 $1$ ，可以看作组合数学，每个 $1$ 都可以放到 $n$ 个位置的任何一个，所以方案数为 $n^k$ ，显然 $k\le \log m= 63$

特别注意 $n\le 10^{18}$ ，所以作取模时要小心

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, m, mod = 1e9 + 7, k = 0, r = 1;
signed main()
{
    scanf("%lld%lld", &n, &m);
    for (; m > 0; m /= 2)
    {
        if (m & 1)
        {
            ++k;
        }
    }
    for (ll i = 0; i < k; ++i)
    {
        r = (r % mod * (n % mod)) % mod;
    }
    printf("%lld", r);
    return 0;
}

F 小沙的算数

把等式按加号拆分为若干部分，那么每次修改只会影响一部分值；每次查询二分找到这部分的块，然后除一下逆元，再乘一下新值

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1000010
ll n, q, x, y, p, s[mn], mod = 1e9 + 7, lf[mn], rf[mn], nows, a[mn];
ll ans;
char sgn[mn];
ll qpow(ll a, ll b)
{
    ll r = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
        {
            r = r * a % mod;
        }
        a = a * a % mod;
    }
    return r;
}
ll inv(ll x)
{
    return qpow(x, mod - 2);
}
signed main()
{
    // printf("%lld\n", inv(2));
    scanf("%lld%lld%s", &n, &q, sgn + 1);
    sgn[0] = sgn[n] = '+'; //0+....+0
    lf[1] = 1;
    for (ll i = 1; i <= n + 1; ++i)
    {
        if (i <= n)
        {
            sc(x);
        }
        else
        {
            x = 0;
        }

        if (sgn[i - 1] == '+')
        {
            nows = (nows + x) % mod;
        }
        else
        {
            nows = (nows * x) % mod;
        }
        if (sgn[i] == '+')
        {
            ++p;
            rf[p] = i + 1;
            lf[p + 1] = i + 1;
            s[p] = nows;
            ans += nows;
            nows = 0;
        }
        a[i] = x;
        // printf("^ %lld %lld\n", i, a[i]);
    }
    // printf("[[%lld\n", ans);
    // printf("----- %lld\n", p);
    // for (ll i = 1; i <= p; ++i)
    // {
    //     printf("%lld %lld %lld\n", lf[i], rf[i], s[i]);
    // }
    while (q--)
    {
        scanf("%lld%lld", &x, &y);
        ll i = upper_bound(rf + 1, rf + 1 + p, x) - rf;
        // printf("-- %lld %lld %lld %lld ", i, s[i], a[x], inv(a[x]));
        ans = (ans - s[i] + mod) % mod;
        s[i] = s[i] * inv(a[x]) % mod;
        a[x] = y;
        s[i] = s[i] * a[x] % mod;
        ans = (ans + s[i]) % mod;
        // printf(" %lld\n", s[i]);
        printf("%lld\n", ans);
    }
    return 0;
}

I 小沙的构造

模拟+构造题。对称串除了中心位置外可以分为左右。一种构造思路是，尽可能多地凑类型，所以一开始把翻转对称的五对字符先用了，直到还剩 $1$ 个要凑没用过，就用另外的字符，如果不剩了，就随便用已经用过的填够长度。然后前五个位置对的对称串用完后，就用不翻转对称的串，直到用完为止。然后处理一下中心位置，用不翻转对称的字符填一下。

特别注意这种构造方法对有中心时，一开始会构造出 $1,3,5,7,9,11$ 这几种情况，而无法处理偶数。如果发现还有缺，可以回退掉一组翻转对称，然后把它用不翻转的补上，从而得到 $2,4,6,8,10$ 。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
char p1[] = "\"!'*+-.08:=^_WTYUIOAHXVM|", p2[] = "<>\\/[]{}()", r[10010];
ll n, m, t, s, suc, s1, s2;
signed main()
{
    scanf("%lld%lld", &n, &m);
    t = (n + 1) / 2;
    s = m <= 10 ? (m + 1) / 2 : m - 5;
    if (m == 36 || m > n)
    {
        // printf("??");
        printf("-1");
        return 0;
    }
    if (m == 1)
    {
        for (ll i = 1; i <= n; ++i)
        {
            printf("%c", '0');
        }
        return 0;
    }
    for (ll i = 1, j = n; i <= n / 2; ++i, --j)
    {
        if (i <= 5)
        {
            if (suc + 2 <= m)
            {
                r[i] = p2[s2];
                r[j] = p2[s2 + 1];
                suc += 2;
                s2 += 2;
            }
            else if (suc + 1 <= m)
            {
                r[i] = r[j] = p1[s1];
                s1++;
                suc++;
            }
            else //suc==m,m>=2
            {
                r[i] = p2[s2 - 2];
                r[j] = p2[s2 - 1];
            }
        }
        else
        {
            if (suc + 1 <= m)
            {
                r[i] = r[j] = p1[s1];
                s1++;
                suc++;
            }
            else if (s1)
            {
                r[i] = r[j] = p1[s1 - 1];
            }
            else
            {
                r[i] = p2[s2 - 2];
                r[j] = p2[s2 - 1];
            }
        }
    }
    if ((n & 1))
    {
        if (suc + 1 <= m)
        {
            r[n / 2 + 1] = p1[s1];
            s1++;
            suc++;
        }
        else if (s1)
        {
            r[n / 2 + 1] = p1[s1 - 1];
        }
        else if (n >= 3 && m >= 2)
        {
            // r[n / 2] = r[n / 2 + 2] = p1[0];
            for (ll i = n / 2, j = n / 2 + 2; i > 1 && r[i] == p2[s2 - 2]; --i, ++j)
            {
                r[i] = r[j] = p1[0];
            }
            r[n / 2 + 1] = p1[1];
            s1 += 2;
            s2 -= 2;
            suc++;
        }
    }
    if (suc < m)
    {
        // printf("%s %lld\n", r + 1, suc);
        printf("-1");
        return 0;
    }
    else
    {
        printf("%s", r + 1);
    }
    return 0;
}

G 小沙的身法

可以发现所求即为树上一条链的和，一开始想过树剖，但是发现直接上树上前缀和即可，维护正前缀和、反前缀和即可。于是写了个树上前缀和的板子，过掉了这道题

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ln;
typedef int ll;
#define il inline
#define re register
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define repe(i, a, b) for (ll i = a; i <= b; ++i)
#define red(i, a, b) for (ll i = a; i > b; --i)
#define rede(i, a, b) for (ll i = a; i >= b; --i)
il ll read()
{
    char p = 0;
    ll r = 0, o = 0;
    for (; p < '0' || p > '9'; o |= p == '-', p = getchar())
        ;
    for (; p >= '0' && p <= '9'; r = (r << 1) + (r << 3) + (p ^ 48), p = getchar())
        ;
    return o ? (~r) + 1 : r;
}
#define mn 1000010
#define mm 21
struct edge
{
    ll to, nx;
} e[mn << 1];
ll fa[mn][mm], n, m, hd[mn], cnt, d[mn], u, v, lg[mn], s, a[mn];
ln cnt1[mn], cnt2[mn];
il void adde(ll &u, ll &v)
{
    e[++cnt] = {v, hd[u]};
    hd[u] = cnt;
}
void dfs(ll h, ll faa)
{
    fa[h][0] = faa;
    d[h] = d[faa] + 1;
    repe(i, 1, lg[d[h]])
    {
        fa[h][i] = fa[fa[h][i - 1]][i - 1];
    }
    for (ll i = hd[h]; i; i = e[i].nx)
    {
        ll toi = e[i].to;
        if (toi != faa)
        {
            cnt1[toi] = cnt1[h] + (a[h] > a[toi] ? 0 : a[toi] - a[h]);
            cnt2[toi] = cnt2[h] + (a[h] < a[toi] ? 0 : a[h] - a[toi]);
            dfs(toi, h);
        }
    }
}
ll lca()
{
    if (d[u] < d[v])
        swap(u, v);
    while (d[u] > d[v])
        u = fa[u][lg[d[u] - d[v]] - 1];
    if (u == v)
        return u;
    rede(k, lg[d[u]] - 1, 0)
    {
        if (fa[u][k] != fa[v][k])
        {
            u = fa[u][k];
            v = fa[v][k];
        }
    }
    return fa[u][0];
}
signed main()
{
    n = read();
    m = read();
    s = 1;
    repe(i, 1, n)
    {
        a[i] = read();
    }
    rep(i, 1, n) u = read(), v = read(), adde(u, v), adde(v, u);
    repe(i, 1, n) lg[i] = lg[i - 1] + (i == 1 << lg[i - 1]);
    dfs(s, 0);
    // repe(i, 1, n)
    // {
    //     printf("-  %lld %lld\n", cnt1[i], cnt2[i]);
    // }
    while (m--)
    {
        u = read();
        v = read();
        ll ui = u, vi = v;
        ll f = lca();
        u = ui, v = vi;
        ll faa = f == 1 ? 0 : fa[f][0];
        ln res = a[u];
        // printf("%lld - %lld %lld ", res, f, f);
        // printf("(%lld %lld)", cnt2[u], cnt2[f]);
        res += cnt2[u] - cnt2[f];
        // printf("- %lld", res);
        // printf("(%lld %lld)\n", cnt1[v], cnt1[f]);
        res += cnt1[v] - cnt1[f];
        printf("%lld\n", res);
    }
    return 0;
}

E 小沙的长路

赛时差点猜对了结论，已经推导出了一半了，赛时一直想打表枚举，但是一直没实现出来。特别注意是每条边只能走一次，而不是每个点只能走一次。赛时最后做成了素数合数分类讨论，而答案是奇偶分类讨论。

对完全图，每个点有 $n-1$ 条边相连。每连一条边，消耗两个点的一个度。连一个环的话，消耗每个点一次出度和入度，所以消耗 $2$ 度。因为都是消耗 $2$ 度，然后因为不能重边，环其实也最多只能画 $\dfrac{n-1}2$ 个(每画一次每个点消耗两个可以连的点)，第 $i$ 个环，第 $x$ 条边与它隔 $i$ 距离的边相连，可以发现，在上述条件下，不可能产生冲突。

当 $n$ 是奇数时，刚好利用完了每一条边，由于每条环有 $n$ 个边，画 $\dfrac{n-1}2$ 个环。当 $n$ 是偶数时，只能画 $\lfloor\dfrac{n-1}2\rfloor$ 个环，画了之后，计算得每个点都只剩一个点可以连，且能够连的那个点也只剩下原本那个点可以连。换言之最多再加多一条边，所以答案为 $\lfloor\dfrac{n-1}2\rfloor\times n+1$

特别需要注意地，这里的环并不必然是完整的环，比如 $n=6$ 时隔 $2$ 可以是两个三点环，在走路的时候，可以把它穿插到完整的环里走，就不会断开了

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n;
signed main()
{
    sc(n);
    printf("%lld ", n - 1);
    if (n % 2 == 1)
    {
        printf("%lld", n * (n - 1) / 2);
        //(n-1)/2次环，遍历全部边
    }
    else
    {
        printf("%lld", (n - 1) / 2 * n + 1);
        //少一次环遍历，最后还能抢救一次
    }
    return 0;
}

A 小沙的炉石

解法一：

假设用 $a$ 张攻击牌， $b$ 张回复牌；因为攻击耗蓝，所以必须有 $a\le b+1$ ，其中 $1$ 代表初始有 $1$ 点法力

不难发现，最小攻击一定是攻回交替。总和为等差数列，值为： $$ \sum_{i=1}^a(2i-1)=a^2 $$ 交换任意一个相邻的攻回，不难发现使得总攻击 $+1$ 。不断相邻交换，最后得到的最大值为全回后全攻，值为： $$ \sum_{i=1}^a(b+i)=ab+\dfrac{a(a+1)}2 $$ 因此，对定值 $a$ ，可以得到定区间 $[a^2,ab+\dfrac{a(a+1)}2]$ 内必然 YES ，低于 $a^2$ 伤自尊，高于 $ab+\dfrac{a(a+1)}2$ 打不死。

那么可以二分 $a\in [1,\min(n,m+1)]$ ，如果 $x$ 在区间左边就缩小 $a$ ，在区间右边就放大 $a$ ，复杂度为 $O(q\log x)$ ；为使区间范围尽可能大，应当让 $b$ 尽可能大，即直接拉满 $m$ 作为 $b$ 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sc(x) scanf("%lld", &x)
ll n, m, k, x;
signed main()
{
    sc(n), sc(m), sc(k);
    while (k--)
    {
        sc(x);
        ll lf = 1, rf = min(m + 1, n), cf;
        bool suc = false;
        while (lf <= rf)
        {
            cf = (lf + rf) >> 1;
            if (x < cf * cf)
            {
                rf = cf - 1;
            }
            else if (x > cf * m + cf * (cf + 1) / 2)
            {
                lf = cf + 1;
            }
            else
            {
                suc = true;
                break;
            }
        }
        printf(suc ? "YES\n" : "NO\n");
    }
    return 0;
}

解法二：

对 $a,b$ 确定的区间，其上一个区间 $a-1,b$ 为： $[(a-1)^2,(a-1)b+\dfrac{a(a-1)}2]$ ，在整数区间内，若上一个区间右端点大于等于下一个区间左端点$-1$，则可以直接合并两个区间。那么联立： $$ \begin{cases} (a-1)b+\dfrac{a(a-1)}2\ge a^2-1\ a\le b+1 \end{cases} $$ 由于 $b\ge a-1$ ，放缩一下第一条式子，有： $$ (a-1)^2+\dfrac{a(a-1)}2\ge a^2-1\Rightarrow a\ge 4 $$ 也就是说哪怕是最小的 $b$ ，都能让 $a\ge 4$ 时恒可以合并，恒可以合并的结果是 $[16,ab+\dfrac{a(a+1)}2]$ ，然后再枚举一下 $a\in [1,3]$ 即可

事实上实际发现运行时间与解法一几乎没差别

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, m, k, x;
signed main()
{
    sc(n), sc(m), sc(k);
    n = min(m + 1, n);
    while (k--)
    {
        sc(x);
        if (n >= 4)
        {
            if (x <= n * m + n * (n + 1) / 2)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
        else
        {
            bool suc = false;
            for (ll i = 1; i <= n; ++i)
            {
                if (x >= i * i && x <= i * m + i * (i + 1) / 2)
                {
                    suc = true;
                    break;
                }
            }
            if (suc)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
    }
    return 0;
}

L 小沙的remake(普通版)

按照权值排序后遍历，可以保证当前遍历时已经记录的方案都可以不降。可以使用树状数组维护区间和，意义是只考虑前 $i$ 点的方案数有多少。对当前遍历的每一个 $a,b$ ，设它排序前的下标为 $i$ ，则区间 $[i,i-b]$ 内的全部之前算过的方案数都可行。递推方程为要么选 $[i,i-b]$ 内的一个气运，方案数是区间和；要么前面的都不选，从 $i$ 开始，方案数是 $1$

为了更快，可以用基数排序。基数排序要避免负数，所以先偏移。

补题 AC 代码：

#include <bits/stdc++.h>
namespace GenHelper
{
    int z1, z2, z3, z4, z5, u, res;
    int get()
    {
        z5 = ((z1 << 6) ^ z1) >> 13;
        z1 = ((int)(z1 & 4294967) << 18) ^ z5;
        z5 = ((z2 << 2) ^ z2) >> 27;
        z2 = ((z2 & 4294968) << 2) ^ z5;
        z5 = ((z3 << 13) ^ z3) >> 21;
        z3 = ((z3 & 4294967) << 7) ^ z5;
        z5 = ((z4 << 3) ^ z4) >> 12;
        z4 = ((z4 & 4294967) << 13) ^ z5;
        return (z1 ^ z2 ^ z3 ^ z4);
    }
    int read(int m)
    {
        u = get();
        u >>= 1;
        if (m == 0)
            res = u;
        else
            res = (u / 2345 + 1000054321) % m;
        return res;
    }
    void srand(int x)
    {
        z1 = x;
        z2 = (~x) ^ (0x23333333);
        z3 = x ^ (0x12345798);
        z4 = (~x) + 51;
        u = 0;
    }
}
using namespace GenHelper;
using namespace std;
const int N = 2e6 + 7, mod = 1e9 + 7;
typedef long long ll;
struct node
{
    ll id, a, b;
    bool operator<(const node &x) const { return a < x.a; }
} c[N];
ll lowbit(ll x) { return x & (-x); }
int n, seed;
ll b[N], t[N];
ll a[N], id[N];
void add(ll i, ll v)
{
    for (; i < N; i += lowbit(i))
    {
        (t[i] += v) %= mod;
    }
}
ll ask(ll i)
{
    ll res = 0;
    for (; i; i -= lowbit(i))
    {
        res += t[i];
    }
    return res % mod;
}
// void add(int x, ll c)
// {
//     for (; x < N; x += lowbit(x)) //注意不是n
//     {
//         t[x] += c;
//         if (t[x] >= mod)
//             t[x] -= mod;
//     }
// }
// ll ask(ll x)
// {
//     ll res = 0;
//     for (; x; x -= lowbit(x))
//         res += t[x];
//     return res - res / mod * mod;
// }
void sorts()
{
    static const int C = 16, D = 1 << C, mask = D - 1;
    static int cnt[D], tmp[N];
    {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)
            ++cnt[a[i] & mask];
        for (int i = 1; i < D; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--)
            tmp[cnt[a[i] & mask]--] = i;
    }
    {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)
            ++cnt[a[i] >> C];
        for (int i = 1; i < D; i++)
            cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--)
            id[cnt[a[tmp[i]] >> C]--] = tmp[i];
    }
}
int main()
{
    scanf("%d %d", &n, &seed);
    srand(seed);
    for (int i = 1; i <= n; i++)
    {
        // c[i].a = read(0), c[i].b = read(i), b[i] = c[i].b;
        // c[i].id = i;
        a[i] = read(0) + 2147483648ull, b[i] = read(i), id[i] = i;
    }
    // sort(c + 1, c + 1 + n);
    sorts();
    for (int i = 1; i <= n; i++)
    {
        // ll id = c[i].id;
        // ll x = (ask(id) - ask(id - b[id] - 1) + 1 + mod) % mod;
        // add(id, x);
        int c = id[i];
        ll x = (ask(c) - ask(c - b[c] - 1) + 1 + mod) % mod;
        add(c, x);
    }
    printf("%lld", ask(n));
    return 0;
}
//2000000 123456789
// 231324385

M 小沙的remake(竞速版)

在原本的基础上，用上各种优化，如基数排序即可。直接参考上一题的代码。

B 小沙的魔法

首先明确这题是可以无限连并查集的，要多少有多少，因为其实等效于可以执行边数次合并。

先进行去重和离散化，升序记录每个不同的值下的节点。然后从大到小遍历每个不同的值，对于这些值的全部顶点，从每个顶点出发，如果邻点权值大于等于它的权值，那证明这些邻点可以跟它合并，然后一起继续上升。

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define range(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const double PI = acos(-1.0);
inline ll read()
{
    char ch;
    ll x = 0;
    bool f = true;
    for (ch = getchar(); !isdigit(ch); ch = getchar())
        if (ch == '-')
            f ^= f;
    for (; isdigit(ch); ch = getchar())
        x = (x << 3) + (x << 1) + ch - 48;
    return f ? x : -x;
}
const int N = 5e5 + 7;
int s[N];
vector<int> son[N], ans[N], mp;
void add(int a, int b) { son[a].pb(b), son[b].pb(a); }
int fin(int x) { return lower_bound(range(mp), x) - mp.begin(); }
int f[N];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
int main()
{
    ll n = read(), m = read(), res = 0, cnt = 0;
    mp.resize(n + 1, 0);
    for (int i = 1; i <= n; i++)
        mp[i] = s[i] = read(), f[i] = i;
    sort(range(mp)), mp.erase(unique(range(mp)), mp.end());
    for (int i = 1; i <= n; i++) //神奇离散化写法
        ans[fin(s[i])].pb(i);
    for (int i = 1; i <= m; i++)
        add(read(), read());
    // printf("%lld\n", mp.size());
    for (int i = mp.size() - 1; i; i--)
    {
        for (int x : ans[i])
        {
            cnt++; //有多少个连通块
            for (int j : son[x])
            {
                if (s[j] < s[x]) //找大于等于自己的邻边
                    continue;
                int fa = find(x), fb = find(j);
                if (fa != fb) //操作1
                    cnt--, f[fa] = fb;
            }
        }
        res += (mp[i] - mp[i - 1]) * cnt;
        // printf("%lld %lld\n", res, cnt);
    }
    cout << res;
    return 0;
}

D 小沙的涂色

问题即给定正方形，问能否填小三角，使其只差一格就满。是的话给出一个构造方案。

使得还差一格，每次填 $3$ 格，这意味着 $n^2-1$ 被 $3$ 整除。即 $n^2\equiv 1(\bmod 3)$ ，设 $n$ 是 $1,4,7,\cdots$ ，有： $(3m+1)^2=9m^2+6m+1$ 显然余 $1$ ；设 $n=2,5,8,\cdots$ ，有 $(3m+2)^2=9m^2+12m+4$ ，也余 $1$ ，但 $(3m)^2=9m^2$ 余 $0$ 。因此，三的倍数一定无法构造。

根据上述结论，可知对余 $1$ 时，可以构造宽度为 $6$ ，长度为 $2k$ (既由 $4$ 个基本单位组成的 $6\times 2$ )对称地填满外围(感觉理论上 $3\times 2$ 也行) ，发现边长为 $6+2k$ ，厚度为 $6$ ，这样可以一直维持余 $1$ ，直到最后的基本情况

对余 $2$ 时，可以构造宽度为 $4$ ，长度为 $3k$ (即由四个基本单位组成 $4\times 3$)，对称地填满外围，可以发现其边长为 $4+3k$ ，厚度为 $4$ 。这样一次之后就余 $1$ 了，然后就可以向上面一样继续处理了。之所以不 $2\times 3$ 是因为会余 $0$ 无解

枚举可知 $n=1,2,4$ 必然有解。 $n &gt; 4$ 时可以按照上述余数规则消到基本情况，因此可以得出结论： $n\bmod 3\neq 0$ 必然有解

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
#define fre(z) freopen(z ".in", "r", stdin), freopen(z ".out", "w", stdout)
#define sto                           \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);            \
    std::cout.tie(nullptr);
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const double PI = acos(-1.0);
inline ll read()
{
    char ch;
    ll x = 0;
    bool f = true;
    for (ch = getchar(); !isdigit(ch); ch = getchar())
        if (ch == '-')
            f ^= f;
    for (; isdigit(ch); ch = getchar())
        x = (x << 3) + (x << 1) + ch - 48;
    return f ? x : -x;
}
const int N = 1e3 + 7;
int s[N][N];
int t[10][10][10];
int n;
void dfs(int l, int r, int idx)
{
    int x = r - l + 1;
    if (x < 5)
    {
        for (int i = 0; i < x; i++)
            for (int j = 0; j < x; j++)
                s[l + i][l + j] = t[x][i + 1][j + 1] + (t[x][i + 1][j + 1] ? idx : 0);
        return;
    }
    else if (x % 3 == 1)
    {
        for (int k = 0; k <= 2; k += 2)
        {
            for (int i = l; i <= r - 4; i += 3)
            {
                s[l + k][i] = s[l + 1 + k][i] = s[l + k][i + 1] = idx++;
                s[l + 1 + k][i + 1] = s[l + k][i + 2] = s[l + 1 + k][i + 2] = idx++;
                s[r - 1 - k][i + 4] = s[r - k][i + 4] = s[r - 1 - k][i + 5] = idx++;
                s[r - k][i + 5] = s[r - 1 - k][i + 6] = s[r - k][i + 6] = idx++;
                s[i + 4][l + k] = s[i + 4][l + 1 + k] = s[i + 5][l + k] = idx++;
                s[i + 5][l + 1 + k] = s[i + 6][l + k] = s[i + 6][l + 1 + k] = idx++;
                s[i][r - k] = s[i][r - 1 - k] = s[i + 1][r - k] = idx++;
                s[i + 1][r - 1 - k] = s[i + 2][r - k] = s[i + 2][r - 1 - k] = idx++;
            }
            // for (int i = 1; i <= n; i++)
            // {
            //     for (int j = 1; j <= n; j++)
            //         printf("%02d ", s[i][j]);
            //     cout << "\n";
            // }
            // cout << "\n";
        }

        dfs(l + 4, r - 4, idx);
    }
    else
    {
        for (int i = l; i <= r - 3; i += 3)
        {
            s[l][i] = s[l + 1][i] = s[l][i + 1] = idx++;
            s[l + 1][i + 1] = s[l][i + 2] = s[l + 1][i + 2] = idx++;
            s[r - 1][i + 2] = s[r][i + 2] = s[r - 1][i + 3] = idx++;
            s[r][i + 3] = s[r - 1][i + 4] = s[r][i + 4] = idx++;
            s[i + 2][l] = s[i + 2][l + 1] = s[i + 3][l] = idx++;
            s[i + 3][l + 1] = s[i + 4][l] = s[i + 4][l + 1] = idx++;
            s[i][r] = s[i][r - 1] = s[i + 1][r] = idx++;
            s[i + 1][r - 1] = s[i + 2][r] = s[i + 2][r - 1] = idx++;
        }
        // for (int i = 1; i <= n; i++)
        // {
        //     for (int j = 1; j <= n; j++)
        //         printf("%02d ", s[i][j]);
        //     cout << "\n";
        // }
        // cout << "\n";
        dfs(l + 2, r - 2, idx);
    }
}
signed main()
{
    n = read();
    if (n % 3 == 0)
        return printf("NO"), 0;
    cout << "YES\n";

    t[2][1][1] = t[2][1][2] = t[2][2][1] = 1; //n=2
    t[4][1][1] = t[4][1][2] = t[4][2][1] = 1; //n=4
    t[4][4][4] = t[4][3][4] = t[4][4][3] = 2;
    t[4][1][4] = t[4][1][3] = t[4][2][4] = 3;
    t[4][4][1] = t[4][4][2] = t[4][3][1] = 4;
    t[4][2][2] = t[4][2][3] = t[4][3][2] = 5;

    dfs(1, n, 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << s[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

J 小沙的Dota

先预处理任意两个技能的合并，以及每个技能有多少种形态。然后对三个技能的合并，枚举左所有形态到中所有形态的转变，然后对中当前枚举的形态，枚举右所有形态的转变，从中找到最小的进行合并

可以用线段树维护这样的合并，那么最终变成两个相邻区间的合并，事实上可以化简为左边区间跟右边左端点进行一次三技能合并，得到一个两技能，然后再跟右边右端点进行一个三技能合并即可

预处理两技能合并复杂度是 $(3!)^2$ ，三技能合并复杂度是 $(3!)^3$ ，线段树节点合并等效于两个三技能合并；线段树只涉及单点修改和区间查询，所以可以不用懒标签，且可知复杂度为建线段树 $O((3!)^3n\log n)$ ，查询总复杂度为 $O((3!)^3m\log n)$ ，思维难度不算特别高

补题 AC 代码：

#include <bits/stdc++.h>
#define fre(z) freopen(z ".in", "r", stdin), freopen(z ".out", "w", stdout)
#define lowit(x) (x & -x)

#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

#define sto                           \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);            \
    std::cout.tie(nullptr);

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<ll, ll> PII;
typedef pair<double, int> PDL;

const int INF = 0x3f3f3f3f;
const int base = 131;
const double eps = 1e-6;
const double PI = acos(-1);

inline ll read()
{
    ll x = 0;
    char ch;
    bool f = true;
    for (ch = getchar(); !isdigit(ch); ch = getchar())
        if (ch == '-')
            f ^= f;
    for (; isdigit(ch); ch = getchar())
        x = (x << 3) + (x << 1) + (ch ^ 48);
    return f ? x : -x;
}

#define space putchar(' '), void(0)
#define enter putchar('\n'), void(0)

void wr(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar(x % 10 + 48);
}
void wr(char *s)
{
    printf("%s", s);
}
// <------------------------------->
const int N = 1e5 + 7;
char ch[11][4] = {"", "aaa", "aac", "aab", "bbb", "bba", "bbc", "ccc", "cca", "ccb", "abc"};
int w[30][30];
int s[N];
vector<int> node[11];
bool p(int i, const char *s)
{ // i是否是s的一种排列
    int cnt[3] = {0};
    for (int x = 0; x < 3; x++, i /= 3) //出现次数是否抵消
        cnt[i % 3]++, cnt[s[x] - 'a']--;
    for (int x = 0; x < 3; x++)
        if (cnt[x])
            return false;
    return true;
}
void init()
{
    for (int i = 0; i < 27; i++)
        for (int t = 1; t <= 10; t++) //每个技能有几种情况
            if (p(i, ch[t]))
                node[t].pb(i);
    for (int i = 0; i < 27; i++) // i状态到j状态要扔几个球
        for (int j = 0; j < 27; j++)
        {
            w[i][j] = 3;
            for (int k = 0, c = 27; k < 3; k++, c /= 3)
                if (i % c == j * c / 27) // i的前3-k个字符和j的后3-k个字符
                {
                    w[i][j] = k;
                    break;
                }
        }
}
struct T
{
    int w[6][6]; // A(3,3)=6
    int ls, rs;  //技能区间左端点右端点分别有多少种技能的排列
    void init(int c)
    {
        memset(w, INF, sizeof w);
        ls = rs = c;
        for (int i = 0; i < node[c].size(); i++)
            w[i][i] = 0;
    }
    int money()
    {
        int ans = INF;
        for (int i = 0; i < node[ls].size(); i++)
            for (int j = 0; j < node[rs].size(); j++)
                ans = min(ans, w[i][j]); //从i技能切到j技能怎样最便宜
        return ans + 3;
    }
} tr[N << 2];
int a[6][6];
void up(T &v, const T &l, const T &r) //合并相邻技能区间
{
    memset(a, INF, sizeof a);
    memset(v.w, INF, sizeof v.w);
    for (int i = 0; i < node[l.ls].size(); i++)
        for (int j = 0; j < node[l.rs].size(); j++)
            for (int k = 0; k < node[r.ls].size(); k++) //单点连接
                a[i][k] = min(a[i][k], l.w[i][j] + w[node[l.rs][j]][node[r.ls][k]]);
    for (int i = 0; i < node[l.ls].size(); i++) //(a,b,c,d)=(a,b,c)(d)
        for (int j = 0; j < node[r.ls].size(); j++)
            for (int k = 0; k < node[r.rs].size(); k++)
                v.w[i][k] = min(v.w[i][k], a[i][j] + r.w[j][k]);
    v.ls = l.ls, v.rs = r.rs;
}
#define lson (o << 1)
#define rson (o << 1 | 1)
#define mid (l + r >> 1)
void build(int o, int l, int r)
{
    if (l == r)
        return tr[o].init(s[l]);
    build(lson, l, mid), build(rson, mid + 1, r);
    up(tr[o], tr[lson], tr[rson]);
}
void add(int o, int l, int r, int X, int c)
{
    if (l == r)
        return tr[o].init(c);
    if (X <= mid)
        add(lson, l, mid, X, c);
    else
        add(rson, mid + 1, r, X, c);
    up(tr[o], tr[lson], tr[rson]);
}
T ask(int o, int l, int r, int L, int R)
{
    if (l == L && R == r)
        return tr[o];
    if (R <= mid)
        return ask(lson, l, mid, L, R);
    else if (L > mid)
        return ask(rson, mid + 1, r, L, R);
    T now;
    up(now, ask(lson, l, mid, L, mid), ask(rson, mid + 1, r, mid + 1, R));
    return now;
}
void solve()
{
    int n = read(), m = read();
    for (int i = 1; i <= n; i++)
        s[i] = read();
    init();
    build(1, 1, n);
    while (m--)
    {
        int op = read(), l = read(), r = read();
        if (op == 1)
            wr(ask(1, 1, n, l, r).money()), enter;
        else
            add(1, 1, n, l, r);
    }
}

int main()
{
    solve();
}

第三场

比赛日志：

开局真·签到题A题hello world，瞬间过题。然后一道很签的简单操作题D，第三分钟过掉了。然后是一道背包变式。我竟然捣鼓了很久才过，总用时19分过了这道题。然后这时候有两道题可以选择，我选了一道当时还比较少人，但我更有思路的L，发现直接手写哈希秒了，总用时42分钟。然后是I，一开始就觉得是双指针。然后想具体怎么实现，一边想一边写，然后做掉了这道题，总用时70分。然后到E题，思考了之后发现不难，就排序和取模。然后过掉了，总用时90分钟。然后又陷入了两难选择。我又选择了看着更有思路更少人的G。这道题要手写树旋转，我就写逐个判断遍历旋转后怎样，但是代码功夫很差，在代码上花了很长时间，第131分钟才过。然后回去再看C，是根据背包推原数据。思考了下发现是矩阵关系，然后一边想一边做，过掉了。自此共166分钟，过了8题，全部都是一发过。排名也很前，都是前几十。然后已经可以半场开香槟了，只有一道J能做。其实看完之后我很快就有思路了。但是……实现起来，思考起来，都不简单，思维难度有，是很烦人的数学题，然后WA了一发。然后我改了个绝对值，又WA了一发，然后我尝试重写逻辑，终于反复测试，并且我意识到可以暴力对拍……然后也找出了之前的出现了负数的bugs，总之写到我头皮发麻，然后再交，对了，262分钟。之后垃圾时间，剩下三道题没有一道有思路。摆了。

不过排名倒是很乐观的。第一场是rating1570，原地从灰破紫破蓝，飙到绿名(我发现这玩意是跟洛谷难度颜色逆着来的)。然后第二场排名从之前的场内84掉到了200，但是rating却升到了1708。第三场场内排名53，rating飙到了1866。

A 智乃的Hello XXXX

真签到

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
signed main()
{
    printf("hello chino");
    return 0;
}

D 智乃的01串打乱

任意找到一个 $1$ 和 $0$ ，对换即可

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, f0, f1;
char s[100010];
signed main()
{
    sc(n);
    scanf("%s", s + 1);
    for (ll i = 1; i <= n; ++i)
    {
        if (s[i] == '0')
        {
            f0 = i;
        }
        else if (s[i] == '1')
        {
            f1 = i;
        }
    }
    swap(s[f0], s[f1]);
    printf("%s", s + 1);
    return 0;
}

B 智乃买瓜

背包 DP 题，基本上改一下板子就能过了，注意不要把决策 1 和决策 2 用 if-else

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 2048
ll n, m, w[mn], dp[2][mn], mod = 1e9 + 7;
signed main()
{
    sc(n), sc(m);
    dp[1][0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        sc(w[i]);
    }
    sort(w + 1, w + 1 + n);
    for (ll i = 1, now = 1, pre = 1; i <= n; ++i, now = 1, pre = 1)
    {
        for (ll j = mn - 1; j >= 0; --j)
        {
            if (j + w[i] < mn)
            {
                (dp[now][j + w[i]] += dp[pre][j]) %= mod;
            }
            if (j + w[i] / 2 < mn)
            {
                (dp[now][j + w[i] / 2] += dp[pre][j]) %= mod;
            }
            // (dp[now][j] += 1) %= mod;
        }
        // for (ll j = 1; j <= m; ++j)
        // {
        //     printf("%lld ", dp[now][j]);
        // }
        // printf("\n");
    }
    for (ll i = 1; i <= m; ++i)
    {
        printf("%lld ", dp[1][i]);
    }
    return 0;
}

L 智乃的数据库

一道哈希表 set STL 的签到题，哈希函数很好写

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1010
ll n, m, a[mn][mn], p = 13331;
map<string, ll> col;
map<ull, ll> cnt;
set<ll> se;
string s, t;
signed main()
{
    sc(n), sc(m);
    for (ll i = 1; i <= m; ++i)
    {
        cin >> s;
        col[s] = i;
    }
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 1; j <= m; ++j)
        {
            sc(a[i][j]);
        }
    }
    cin >> t >> t >> t >> t >> t >> t >> t;
    t[t.size() - 1] = ',';
    for (ll i = 0, ie = t.size(), h = 0; i < ie; ++i)
    {
        if (t[i] == ',')
        {
            s = t.substr(h, i - h);
            se.insert(col[s]);
            h = i + 1;
        }
    }
    for (ll i = 1; i <= n; ++i)
    {
        ull v = 0;
        for (ll j : se)
        {
            v = v * p + (1 + a[i][j]);
        }
        cnt[v]++;
    }
    printf("%lld\n", cnt.size());
    for (auto i : cnt)
    {
        printf("%lld ", i.second);
    }
    return 0;
}

I 智乃的密码

滑动窗口。考虑维护四个单调栈对应大小写、数字、特殊字符。对于枚举的右边界，看看当前长度内(大于长度不断pop即可)，如果四个栈有长度的把最近的一个拉进去，然后按先后排序一下，如果发现有三个或以上存在的，可以记一下贡献。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, l, r, len, ans, lf = 1;
char s[100010];
deque<ll> ty[4];
ll ck(char c)
{
    if (isupper(c))
    {
        return 0;
    }
    if (islower(c))
    {
        return 1;
    }
    if (isdigit(c))
    {
        return 2;
    }
    return 3;
}
signed main()
{
    sc(n), sc(l), sc(r), scanf("%s", s + 1);
    for (ll i = 1; i <= n; ++i)
    {
        ll t = ck(s[i]);
        ty[t].push_back(i);
        while (i - lf + 1 > r)
        {
            ll tt = ck(s[lf]);
            ty[tt].pop_front();
            lf += 1;
        }
        ll suc = 0;
        vector<ll> idx;
        for (ll j = 0; j < 4; ++j)
        {
            if (ty[j].size())
            {
                ++suc;
                idx.push_back(ty[j][ty[j].size() - 1]);
                // printf("%lld ", idx[idx.size() - 1]);
            }
        }
        sort(idx.begin(), idx.end());
        if (suc >= 3 && i - lf + 1 >= l)
        {
            ll k = idx[idx.size() - 3];
            k = min(k, i - l + 1);
            // ans += i - k + 1;
            ans += k - lf + 1;
        }
        // printf(" :(%lld) %lld\n", lf, ans);
    }
    printf("%lld", ans);
    return 0;
}

E 智乃的数字积木(easy version)

对同色部分先内部排个序，每次更改后，对更改后的颜色部分排个序，然后暴力输出即可。预处理最差复杂度是 $O(n\log n)$ ，由于只有 $10$ 种颜色，所以最多染 $10$ 下就趋同了，就可以不再排序了，复杂度大概不会高于 $O(10n\log n)$

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll n, m, k, c[mn], p, q, mod = 1e9 + 7;
char v[mn];
bool cmp(char x, char y) { return x > y; }
void sorts(ll cmd = 0)
{
    for (ll i = 1, lf = 1; i <= n; ++i)
    {
        if (c[i] != c[i + 1])
        {
            if (cmd == 0 || (cmd == 1 && c[i] == q))
            {
                sort(v + lf, v + i + 1, cmp);
            }
            lf = i + 1;
        }
    }
    ll r = 0;
    for (ll i = 1; i <= n; ++i)
    {
        r = (r * 10 + v[i] - '0') % mod;
    }
    printf("%lld\n", r);
}
signed main()
{
    sc(n), sc(m), sc(k), scanf("%s", v + 1);
    for (ll i = 1, lf = 1; i <= n; ++i)
    {
        sc(c[i]);
    }
    sorts();
    while (k--)
    {
        sc(p), sc(q);
        for (ll i = 1; i <= n; ++i)
        {
            if (c[i] == p)
            {
                c[i] = q;
            }
        }
        sorts(1);
    }
    return 0;
}

G 智乃的树旋转(easy version)

解法一：直接按题意模拟平衡树操作即可，因为只有 $1$ 次操作，所以枚举各个节点旋转后的树，跟原树比较即可，复杂度 $O(n^2)$

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1024
ll n;
struct tr
{
    ll fa, lc, rc;
} ta[mn], tb[mn], tc[mn];
void rotate(ll a)
{
    ll b = tc[a].fa;
    ll fa = tc[b].fa;
    if (tc[b].lc == a) //右旋
    {
        tc[b].lc = tc[a].rc;
        // tc[tc[a].rc].fa = b;
        tc[a].rc = b;
        // tc[b].fa = a;
    }
    else
    {
        tc[b].rc = tc[a].lc;
        tc[a].lc = b;
    }
    if (fa)
    {
        if (tc[fa].lc == b)
        {
            tc[fa].lc = a;
        }
        else
        {
            tc[fa].rc = a;
        }
    }
}
bool ck()
{
    for (ll i = 1; i <= n; ++i)
    {
        if (tc[i].lc != ta[i].lc || tc[i].rc != ta[i].rc)
        {
            // printf("-- %lld\n", i);
            return false;
        }
    }
    return true;
}
void scc(tr *t)
{
    for (ll i = 1, l, r; i <= n; ++i)
    {
        sc(l), sc(r);
        t[i].lc = l, t[i].rc = r;
        t[l].fa = t[r].fa = i;
    }
}
// void prt(tr *t)
// {
//     for (ll i = 1; i <= n; ++i)
//     {
//         printf("%lld %lld %lld\n", t[i].lc, t[i].rc, t[i].fa);
//     }
//     printf("\n");
// }
signed main()
{
    sc(n), scc(ta), scc(tb);
    memcpy(tc, tb, sizeof ta);
    if (ck())
    {
        printf("0\n");
        return 0;
    }
    for (ll i = 1; i <= n; ++i)
    {
        if (tb[i].fa)
        {
            // printf("<< %lld\n", i);
            memcpy(tc, tb, sizeof ta);
            rotate(i);
            // prt(tc);
            if (ck())
            {
                printf("1\n%lld", i);
                return 0;
            }
        }
    }
    return 0;
}
// ll firot(tr *t)
// {
//     for (ll i = 1; i <= n; ++i)
//     {
//         if (t[i].fa == 0)
//         {
//             return i;
//         }
//     }
//     return 0;
// }

解法二：事实上，题意有一句话说： 树旋转的本质是二叉树旋转轴节点与其父节点父子关系的改变 ，分析后可以发现，旋转前后会出现互为父子的现象，直接找即可。题解说是 $O(n^2)$ ，但是可以优化成 $O(n)$ ，个人优化后的题解代码如下：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
struct tree
{
    int fa;
    int ch[2];
} t[MAXN], a[MAXN];
int input_tree(tree *t, int n)
{
    int x, y;
    std::vector<bool> v(n + 1, true);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &x, &y);
        v[x] = v[y] = false;
        t[i].ch[0] = x;
        t[i].ch[1] = y;
        if (x)
            t[x].fa = i;
        if (y)
            t[y].fa = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (v[i])
            return i;
    }
    return -1;
}
int n, root_a, root_t;
vector<int> vv;
int main()
{
    scanf("%d", &n);
    root_a = input_tree(a, n);
    root_t = input_tree(t, n);
    for (int i = 1; i <= n; ++i)
    {
        int j = t[i].fa;
        if (j && a[j].fa == i)
        {
            printf("1\n%d\n", i);
            return 0;
        }
    }
    printf("0\n");
}

C 智乃买瓜(another version)

对于正着来的过程，设本来的向量是 $a$ ，买了一个重为 $w$ 的瓜，设 $a$ 全体右移 $\dfrac w2$ 得到 $a'$ ，全体右移 $w$ 得到 $a''$，得到的新向量是 $a+a'+a''$ ，分别对应不买、买半个和买一个。初始向量为 $(1,0,0,\cdots)$

那么要逆这个过程，就可以从 $1$ 开始顺着扫，如果第 $i$ 位有值，代表肯定有一个 $2i$ 瓜，设新向量为 $b$ ，有 $b_j=a_j+a_{j-i}+a_{j-2i}$ ，即执行一次 $a_j=b_j-a_{j-i}-a_{j-2i}$ 就可以还原一次上述矩阵移动，不断执行这样的操作即可。题意描述保证最多还原 $10^3$ 次，所以 $O(10^3n)$

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 2048
ll n, m, a[mn], w[mn], mod = 1e9 + 7, b[mn];
signed main()
{
    sc(m);
    for (ll i = 1; i <= m; ++i)
    {
        sc(a[i]);
    }
    a[0] = b[0] = 1;
    for (ll i = 1; i <= m; ++i)
    {
        while (a[i] != 0)
        {
            w[++n] = i * 2;
            for (ll j = i; j <= m; ++j)
            {
                a[j] = (a[j] - a[j - i] + mod) % mod;
                if (j - 2 * i >= 0)
                {
                    a[j] = (a[j] - a[j - 2 * i] + mod) % mod;
                }
            }
        }
        // for (ll j = 1; j <= m; ++j)
        // {
        //     printf("%lld ", a[j]);
        // }
        // printf("\n");
    }
    // for (ll i = m; i >= 1; --i)
    // {
    //     if (w[i] != 0)
    //     {
    //         n = i;
    //         break;
    //     }
    // }
    printf("%lld\n", n);
    for (ll i = 1; i <= n; ++i)
    {
        printf("%lld ", w[i]);
    }
    return 0;
}

J 智乃的C语言模除方程

思路很快出，但答案很晚才算出来，思维和实现难度较大

核心思路是不断拆分，先求 $[1,R]$ 内 $[0,r]$ 的答案，这个很好求，把 $[1,R]$ 按 $p$ 个一行地分行，然后取前 $r$ 列即可。具体而言有至少 $\lfloor\dfrac Rp\rfloor$ 整行，每行能取 $\min(r+1,p)$ 个；最后还残下 $\min(r+1, (R\bmod p)+1)$ 行(可能是残缺的也可能是整的)

对 $[1,R]$ 的任意区间 $[l,r]$ ，用前缀和思维减一下即可；负数部分忽略不计，当且仅当 $l-1\ge 0$ 有减的必要

特别地，若 $R &lt; 0$ ，可以等效于对称一下，$[l,r]$ 和 $R$ 都取相反一下。其他情况是 $0$

拓展到 $[L,R]$ ，当 $R\ge 0$ 时，先按上面的算个 $[1,R]$ ，如果 $L-1 \ge 0$ ，减去再多算的一部分。如果 $L &lt; 0 $，发现把负的部分可以让负的 $(l,r)$ 去接，对称一下。若 $R &lt; 0 $，两个区间都对称一下，那么 $[L,R]$ 对称后一定是正区间，不会陷入无限递归。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll p, l, r, L, R;
ll cal(ll r, ll R) //r>=0,R>=0
{
    // printf("%lld %lld %lld\n", r, R, R / p * min(r + 1, p) + min(r + 1, R % p));
    // printf("cal %lld %lld\n", r, R);
    if (r < 0)
    {
        return 0;
    }
    return R / p * min(r + 1, p) + min(r + 1, R % p + 1);
}
ll cal2(ll l, ll r, ll R) //l,r,R>=0
{
    // printf("cal2 %lld %lld %lld\n", l, r, R);
    if (R < 0)
    {
        return cal2(-r, -l, -R);
    }
    ll ans = cal(r, R);
    if (l > 0)
    {
        ans -= cal(l - 1, R);
    }
    return ans;
}
ll cal3(ll l, ll r, ll L, ll R) //l,r,L,R>=0
{
    // printf("cal3 %lld %lld %lld %lld\n", l, r, L, R);
    if (R < 0)
    {
        return cal3(-r, -l, -R, -L);
    }
    ll ans = cal2(l, r, R);
    if (L > 0)
    {
        ans -= cal2(l, r, L - 1);
    }
    if (L < 0)
    {
        ans += cal3(-r, -l, 1, -L);
    }
    return ans;
}
// ll pal(ll l, ll L) //[l,0], [L,0],l<0,L<0
// {
//     return cal(-l, -L);
// }
// ll pal2(ll l, ll r, ll L)
// {
//     ll ans = pal(l, L);
//     if (r < 0)
//     {
//         ans -= pal(r + 1, L);
//     }
//     return ans;
// }
// ll pal3(ll l, ll r, ll L, ll R)
// {
//     r = min(r, 0LL);
//     ll ans = pal2(l, r, L);
//     if (R < 0)
//     {
//         ans -= pal2(l, r, R + 1);
//     }
//     return ans;
// }
ll res, nl, nr, pl, pr;
signed main()
{
    sc(p), sc(l), sc(r), sc(L), sc(R);
    p = abs(p);
    printf("%lld", cal3(l, r, L, R));
    // if (R <= 0)
    // {
    //     res = cal3(-r, -l, -R, -L);
    // }
    // else if (L < 0)
    // {
    //     res = cal3(l, r, 1, R) + pal3(l, r, L, 0);
    //     // printf("%lld %lld\n", cal3(l, r, 0, R), pal3(l, r, L, -1));
    // }
    // else
    // {
    //     res = cal3(l, r, L, R);
    // }
    // printf("%lld", res);
    return 0;
}
/*
5 1 1 -10 12
3

3 0 1 -7 9
9

123 -10000 10000 -10000 10000
20001

67 -7 3 -100 -11

-82 -111 -2 -7 9999
*/

H 智乃的树旋转(hard version)

注意到一点：不是任给两棵树都能把它们旋转到一样的，例如对输入：

5
2 3  0 0  4 5  0 0  0 0
2 3  4 0  0 0  0 0  1 0

不能找到任何一个解法。

理解了旋转的本质是父子对换后，就可以发现类似于不断在树上跑插入排序了。一开始已插入好的部分只有根节点的父亲(空)。先序遍历排好序后的树，如果发现当前遍历到的节点在乱树里的父亲节点没有到位(不在排序好的集合里)，证明这个点没有排序好，可以不断旋转这个点为父亲节点，直到它的父亲排好了，证明它也排好了，这样一定能在 $n$ 次内把这个点提升到父亲在排好序的里面。

用子问题的思维来解释上面过程的原因的话，对一个节点不断转，它就会变成根。在上述 DFS 先序遍历过程中，当前子树里，若排好的树的根没有就位，那就在乱树里强行让它就位，暂时不管其他的点，那么这次 DFS 就把排好子树里这个子树根节点就位了。然后再同理处理左右子树。因为题目保证有解，所以这么做一定能得到解。

代码实际上是 $O(n^2)$ 的，用 vis 集合标记已排好的话，可以不用重构整棵树。

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1010
struct tr
{
    ll fa, ch[2];
} t[mn], a[mn];
ll n, rota, rott;
ll scc(tr *t)
{
    bool vis[mn] = {};
    for (ll i = 1, u, v; i <= n; ++i)
    {
        sc(u), sc(v);
        t[i].ch[0] = u;
        t[i].ch[1] = v;
        t[u].fa = t[v].fa = i;
        vis[u] = vis[v] = true;
    }
    for (ll i = 1; i <= n; ++i)
    {
        if (!vis[i])
        {
            return i;
        }
    }
    return -1;
}
void rotate(ll a)
{
    ll b = t[a].fa;
    ll fa = t[b].fa;
    ll aisrf = (a == t[b].ch[1]);
    ll bisrf = (b == t[fa].ch[1]);
    ll ac = t[a].ch[1 ^ aisrf];
    t[a].fa = fa;
    t[a].ch[1 ^ aisrf] = b;
    t[b].ch[0 ^ aisrf] = ac;
    t[b].fa = a;
    t[ac].fa = b;
    t[fa].ch[0 ^ bisrf] = a;
}
vector<ll> ans;
bool v[mn] = {true};
void splay(ll rot)
{
    while (!v[t[rot].fa])
    {
        ans.push_back(rot);
        rotate(rot);
    }
}
void dfs(ll rot)
{
    if (!rot)
    {
        return;
    }
    splay(rot);
    v[rot] = true;
    dfs(a[rot].ch[0]);
    dfs(a[rot].ch[1]);
}
signed main()
{
    sc(n), rota = scc(a), rott = scc(t);
    dfs(rota);
    printf("%lld\n", ans.size());
    for (ll i : ans)
    {
        printf("%lld\n", i);
    }
    return 0;
}

K 智乃的C语言模除方程(another version)

整除分块：对 $\dfrac Ni,i\in[1,N]$ ，结果仅有 $\sqrt N$ 种

可以作等价变换： $N\bmod i=N-\lfloor\dfrac Ni\rfloor\times i$

枚举取值仅有 $\sqrt N$ 种可能性的变量 $c=\lfloor\dfrac Ni\rfloor$

原式化为 $P-cx=Q,x\in [L,R],Q\in[l,r]$ ，对左边可以看成等差数列，在第 $[L,R]$ 项中问有多少项在 $[l,r]$ 内

使得 $c$ 相同的 $i\in[lf,rf]$ ，满足：$rf=\lfloor\dfrac Pc\rfloor$ ，其 $lf$ 为上一次计算的 $rf+1$ 。初始有 $lf=1$ ，这样可以 $O(\sqrt N)$ 枚举每一段同 $c$ 的区间端点

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll p, ans, l, r, L, R;
ll it(ll a1, ll b1, ll a2, ll b2)
{ //[a1,b1]∩[a2,b2]的长度
    return max(0LL, min(b1, b2) - max(a1, a2) + 1);
}
ll ap(ll a, ll d, ll lf, ll rf) //数列首项，公差，区间范围
{
    ll n = rf - lf + 1;
    if (d == 0) //其实应该只有一次执行到这里
    {
        if (a >= l && a <= r) // p在[l,r]，这一段恒成立
        {
            // printf("%lld %lld\n", lf, lf + n);
            //负数根据题目描述，可知确实是这样的(拿掉符号再来一次)
            return it(L, R, lf, lf + n) + it(L, R, -lf - n, -lf);
        }
        else
        {
            return 0;
        }
    }
    ll s = 0, t = -1; //空区间初始
    //数列a-dx
    if (a > r) //开始值偏移
    {          //即(a-r)/d的上取整,使得偏移后首项一定在[l,r]内
        s = (a - r + d - 1) / d;
    }
    if (a >= l) //长度为a-l,公差为d,可得项数为t
    {
        t = (a - l) / d;
    }
    // printf("%lld %lld %lld %lld %lld %lld\n", a, d, lf, rf, s, t);
    return it(L, R, lf + s, lf + t) + it(L, R, -lf - t, -lf - s);
}
signed main()
{
    sc(p), sc(l), sc(r), sc(L), sc(R);

    //显而易见不大难理解的的特判(参考J题)
    if (p < 0)
    {
        p = -p, l = -l, r = -r, swap(l, r);
    }
    l = max(l, 0LL);

    // p%i=p-(p/i)*i的p/i相同时，p/i公差d,首项a,值域[lf,rf]
    for (ll lf = 1, rf; lf <= p; lf = rf + 1)
    {
        rf = p / (p / lf);
        ll a = p % lf, d = p / lf;
        // printf("%lld %lld %lld %lld\n", a, d, lf, rf);
        //可以发现P%x的值域实际上是以a为首项-d为公差的等差数列
        ans += ap(a, d, lf, rf);
    }
    // p%x(x>p)的范围是[1,1e9]
    ans += ap(p, 0, p + 1, 1e9);
    printf("%lld", ans);
    return 0;
}

F 智乃的数字积木(hard version)

启发式合并，核心思路是每次把较少块的颜色并到较多颜色的块上。

快速计算值：对 $m$ 位数字： $\overline{xx\cdots x}$ ，表达式为 $\dfrac x9(10^m-1)$ ，对这个数字移高位可以乘以 $10^p$ 。因此在桶排基础上，可以用 $O(1)$ 计算任意一块的值

因为合并时按多寡不按题意，所以需要把题目给的颜色可逆映射成一个 ID ，具体而言，每次目标颜色的 ID 映射成较多的那一个 ID，源颜色映射为较少的那一个 ID

为了能够快速根据下标找到每一块，可以使用并查集，并且可以设每块有一个范围外的根下标，可以记为 $n+1$ 开始递增的计数变量分配这个下标。强行维护让它作为并查集的根，即从不将它指向别的下标，那么可以用 $\pm(n+1)$ 直接与块下标一一对应

对于合并过程，枚举要被染掉的颜色，对于这个颜色的每一块，查找其左右相邻的块，如果是目标颜色(能找到一定不是空块)，直接合并两个块，然后答案减掉本来的部分，加上合并后的部分

最坏情况有 $n$ 个块，最快进行 $n$ 次合并，复杂度可以看做 $O(n)$ ，因为整个过程实际上没有涉及对数复杂度的运算。(但是其实常数还是有点大)

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll n, m, k, fa[mn * 2], itc[mn], cti[mn], pw[mn], mod = 1e9 + 7;
ll c[mn], inv9 = 111111112, ans, p, q;
char s[mn];
ll findf(ll x)
{
    while (x != fa[x])
    {
        x = fa[x] = fa[fa[x]];
    }
    return x;
}
struct block
{
    ll lf, rf, b[11] = {}, alive = 1, c;
    ll get()
    {
        ll res = 0;
        for (ll i = 9; i >= 0; --i)
        {
            ll v = (pw[b[i]] - 1 + mod) * inv9 % mod * i % mod;
            res = (res * pw[b[i]] % mod + v) % mod;
        }
        return res * pw[n - rf] % mod;
    }
};
block operator+(const block &lfs, const block &rfs)
{
    block r;
    r.lf = min(lfs.lf, rfs.lf), r.rf = max(lfs.rf, rfs.rf);
    r.c = lfs.c, r.alive = 1;
    for (ll i = 0; i <= 9; ++i)
    {
        r.b[i] = lfs.b[i] + rfs.b[i];
    }
    return r;
}
vector<block> v;
vector<ll> cb[mn];
void solve(vector<ll> &from, vector<ll> &to, ll &c_to)
{
    for (auto &i : from)
    {
        if (v[i].alive != 1)
        {
            continue;
        }
        v[i].c = c_to;
        ans = (ans - v[i].get() + mod) % mod;
        if (v[i].lf > 1)
        {
            block &vl = v[findf(v[i].lf - 1) - (n + 1)];
            if (vl.c == c_to)
            {
                ans = (ans - vl.get() + mod) % mod;
                fa[findf(v[i].lf - 1)] = findf(n + 1 + i);
                v[i] = vl + v[i];
                vl.alive = 0;
            }
        }
        if (v[i].rf < n)
        {
            block &vr = v[findf(v[i].rf + 1) - (n + 1)];
            if (vr.c == c_to)
            {
                ans = (ans - vr.get() + mod) % mod;
                fa[findf(v[i].rf + 1)] = findf(n + 1 + i);
                v[i] = v[i] + vr;
                vr.alive = 0;
            }
        }
        ans = (ans + v[i].get()) % mod;
        to.emplace_back(i);
    }
    from.clear();
}
signed main()
{
    sc(n), sc(m), sc(k);
    for (ll i = 1; i <= 2 * n; ++i)
    {
        fa[i] = i;
    }
    for (ll i = 1; i <= m; ++i)
    {
        itc[i] = cti[i] = i;
    }
    pw[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        pw[i] = pw[i - 1] * 10 % mod;
    }

    scanf("%s", s + 1);
    for (ll i = 1; i <= n; ++i)
    {
        sc(c[i]);
    }
    for (ll lf = 1, rf = 1; lf <= n; lf = rf + 1, rf = lf)
    {
        while (rf + 1 <= n && c[rf + 1] == c[lf])
        {
            ++rf;
        }
        block nw;
        nw.lf = lf, nw.rf = rf, nw.alive = 1, nw.c = c[lf];
        memset(nw.b, 0, sizeof nw.b);
        for (ll i = lf, des = n + 1 + v.size(); i <= rf; ++i)
        {
            ++nw.b[s[i] - '0'];
            fa[findf(i)] = findf(des);
        }
        cb[c[lf]].emplace_back(v.size());
        v.emplace_back(nw);
    }
    for (auto &i : v)
    {
        ans = (ans + i.get()) % mod;
    }
    printf("%lld\n", ans);

    while (k--)
    {
        sc(p), sc(q);
        if (p == q)
        {
            printf("%lld\n", ans); // cao
            continue;
        }
        ll i_from = cti[p], i_to = cti[q], i_dest, i_emp;
        vector<ll> &from = cb[i_from], &to = cb[i_to];
        if (from.size() < to.size())
        {
            i_dest = i_to, i_emp = i_from;
            solve(from, to, i_to);
        }
        else
        {
            i_dest = i_from, i_emp = i_to;
            solve(to, from, i_from);
        }
        cti[p] = i_emp, itc[i_emp] = p;
        cti[q] = i_dest, itc[i_dest] = q;
        printf("%lld\n", ans);
    }
    return 0;
}

第四场

比赛日志：

一开始直接秒了E题，一眼递归TLE，放了几个例子猜结论猜对了，1分钟。然后看H题，因为方程推导上自己出了点问题，即右边没有开方，所以一直没算对。然后卡了几分钟才对，就A掉了，6分钟。然后K题，观察样例提示得出规律，然后很快切掉了，11分钟。然后好像是二选一(这场比赛很多时候都是两题过题数差不多的)。然后我捡了个A，很快滑窗思路有了，思考了一会儿然后实现，就交了就AC了，21分钟。然后C题，裸差分题，一下子平推掉了，26分钟。然后看F，一道小模拟，也是一下子平推掉了，32分钟。然后J题，想了一会儿之后想到了欧拉筛+lcm的唯一分解定理表达式，不会TLE地写，然后对了，切掉了,47分钟。然后二选一，我选了个比较有把握代码量较小的DP先写，I题，又是01背包变式，思考了一下，然后就过掉了，59分钟。然后回头写计算几何题，套板子过掉了，76分钟。至此，一个钟多一会的时间过了9道题，剩下又是一个二选一，我对比较少人的B反而一下有思路，跟之前的某题题解有点像，维护长数字的某一段查询，然后加上了进制而已，用树状数组维护不同进制的长数字，然后再开一个维护区间最小值。然后想错了，改成了最大值，又修了点bugs之类的，然后一交一个惨。然后自查样例，发现区间最大值不能用树状数组维护，要修改无法实现单点修改(更小的值无法覆盖之前更大的值)，于是写了线段树，然后发现不用懒标记，然后过掉了。150分钟了。然后G，很快发现了公式，但是一交一个WA。然后我百思不得其解，改了个幂取模，然后得出了不一样的答案，又交一个WA。我更郁闷了，思考了很久，然后猛然发现一个事实，幂指数不能够直接取模，即 $a^{b\ \bmod\ p}$ 不等于 $a^{(b\ \bmod\ p)\bmod\ p}$ 。于是思考怎么实现，然后想来想去，又得出了不能用交换律改$a^{(b^c)}$为 $(a^b)^c$。然后终于猛然想起，之前做过的疾速幂，即拓展欧拉定理，然后切掉了。219分钟。然后坐牢，剩下蛮长时间，但是最后一题没思路。一边摆一边想，注意到了空间很宽，但是没想出怎么维护。然后摆掉了。这是唯一一场过了11题的目前以来，一度排名挤进十多，但是后来B,G题的时候这两题掉下去了，然后最后就不怎么动了。

E 真假签到题

可以看出函数是把一个数不断二分，最后拆分是满足恒等性的(即 $2\lfloor\dfrac x2\rfloor+x\bmod 2=x$ ，偶数易证；奇数时左半部分缺 $1$ ，模数补上了)

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
long long f(long long x)
{
    if (x == 1)
        return 1;
    return f(x / 2) + f(x / 2 + x % 2);
}
signed main()
{
    ll x;
    sc(x);
    printf("%lld", x);
    return 0;
}

H 真真真真真签到题

解方程：$(2x)^2=3a^2$ 得 $a=\sqrt{\dfrac{4x^2}{3}}$ ，然后输出 $a^3$ ；赛时因为没两边平方(只平方了一边)卡了几分钟

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
signed main()
{
    ll x;
    db a = 0;
    sc(x);
    a = sqrt(4.0 * x * x / 3.0);
    printf("%lf", a * a * a);
    return 0;
}

K 小红的真真假假签到题题

由于 $x\le 10^9, x^2\le10^{18}$ ，且根据题目解释和样例，不难想到构造方法，即设 $x=\overline{x_1x_2\cdots x_n}$ ，可以构造 $y=\overline{x_1x_2\cdots x_nx_1x_2\cdots x_n}$ ，设 $x$ 位长为 $m$ ，则显然 $y=(2^m+1)x$

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, x;
signed main()
{
    sc(x);
    for (ll i = x; i > 0; i >>= 1)
    {
        ++n;
    }
    printf("%lld\n", x * ((1 << n) + 1));
    return 0;
}

A R

滑动窗口算法。每次遇到 $P$ 更新左边界；枚举右边界，一个 vector 记录历史上遇到的全部 $R$ ，每次对当前右边界，枚举当前的第前 $k$ 个 $R$ ，可以在 $O(n)$ 实现

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 2000010
ll n, k, ans, rs, lf, rpos[mn], ri = 100;
char c[mn];
signed main()
{
    sc(n), sc(k);
    scanf("%s", c + 1);
    lf = 1;
    for (ll i = 1; i <= n; ++i)
    {
        if (c[i] == 'P')
        {
            rs = 0;
            lf = i + 1;
        }
        else
        {
            if (c[i] == 'R')
            {
                rpos[ri++] = i;
            }
            ll lt = rpos[ri - k];
            if (lt >= lf)
            {
                ans += (lt - lf + 1);
            }
        }
    }
    printf("%lld", ans);
    return 0;
}

C 蓝彗星

很显然是差分裸题，直接叠差分然后计算一次前缀和即可过题

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 200010
ll n, t, x, b[mn], r[mn], ans;
char c[mn];
signed main()
{
    sc(n), sc(t), scanf("%s", c + 1);
    for (ll i = 1; i <= n; ++i)
    {
        sc(x);
        if (c[i] == 'B')
        {
            b[x]++;
            b[x + t]--;
        }
        else
        {
            r[x]++;
            r[x + t]--;
        }
    }
    for (ll i = 1; i < mn; ++i)
    {
        b[i] += b[i - 1];
        r[i] += r[i - 1];
        if (b[i] > 0 && r[i] == 0)
        {
            ans++;
        }
    }
    printf("%lld", ans);
    return 0;
}

F 小红的记谱法

小模拟，真·签到题

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
map<char, ll> m;
char c[1010];
ll n, s;
signed main()
{
    m['C'] = 1;
    m['D'] = 2;
    m['E'] = 3;
    m['F'] = 4;
    m['G'] = 5;
    m['A'] = 6;
    m['B'] = 7;
    scanf("%s", c);
    n = strlen(c);
    for (ll i = 0; i < n; ++i)
    {
        if (c[i] == '<')
        {
            --s;
        }
        else if (c[i] == '>')
        {
            ++s;
        }
        else
        {
            printf("%lld", m[c[i]]);
            if (s < 0)
            {
                for (ll i = 0, ie = -s; i < ie; ++i)
                {
                    printf(".");
                }
            }
            else
            {
                for (ll i = 0, ie = s; i < ie; ++i)
                {
                    printf("*");
                }
            }
        }
    }
    return 0;
}

J 区间合数的最小公倍数

唯一分解定理 + 质因数分解求 LCM 的板子题

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 30010
ll l, r, k, prm[mn], he, p[mn];
bool vis[mn];
void euler(ll n = 30000)
{
    vis[0] = vis[1] = true;
    for (ll i = 2; i <= n; ++i)
    {
        if (!vis[i])
        {
            prm[++k] = i;
        }
        for (ll j = 1; j <= k; ++j)
        {
            if (prm[j] * i > n)
            {
                break;
            }
            vis[prm[j] * i] = true; //合数
            if (i % prm[j] == 0)
            {
                break;
            }
        }
    }
}
ll mod = 1e9 + 7, ans = 1;
ll qpow(ll a, ll b)
{
    ll res = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
    }
    return res;
}
signed main()
{
    // printf("%lld", qpow(2, 10));
    euler();
    // for (ll i = 1; i <= 10; ++i)
    // {
    //     printf("%lld ", prm[i]);
    // }
    sc(l), sc(r);
    l = max(4LL, l);
    for (ll i = l; i <= r; ++i)
    {
        if (vis[i])
        {
            ++he;
            ll x = i;
            ll a = 2;
            while (a * a <= x)
            {
                if (x % a == 0)
                {
                    ll cnt = 0;
                    while (x % a == 0)
                    {

                        ++cnt;
                        x /= a;
                    }
                    p[a] = max(p[a], cnt);
                }
                ++a;
            }
            if (x > 1)
            {
                p[x] = max(p[x], 1LL);
            }
        }
    }
    if (he == 0)
    {
        printf("-1");
        return 0;
    }
    for (ll i = 1; i <= 30000; ++i)
    {
        if (p[i])
        {
            // printf("%lld %lld\n", i, p[i]);
            ans = ans * qpow(i, p[i]) % mod;
        }
    }
    printf("%lld", ans);
    return 0;
}

I 爆炸的符卡洋洋洒洒

由于 $k\le 10^3$ ，数据比较小，可以考虑直接上背包 DP ，可以压缩数组(也可以不，反正不会 MLE)，记 $dp_{i,j}$ 表示考虑前 $i$ 张符卡，消耗和模 $k$ 为 $j$ 的方案数。记 $s_{i,j}$ 表示当前模数的方案是否曾出现过。初始仅 $s_{0,0}=1$ ，每次递推让 $i-1$ 下的全部曾出现过的进行加法原理相加记得，比较简单的 DP 题

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1024
ll dp[2][mn], n, k, a, b, s[2][mn], ans;
signed main()
{
    sc(n), sc(k);
    s[0][0] = 1;
    for (ll i = 1, now = 1, prev = 0; i <= n; ++i, now ^= 1, prev ^= 1)
    {
        sc(a), sc(b);
        for (ll j = 0; j < k; ++j)
        {
            s[now][j] = s[prev][j];
            dp[now][j] = dp[prev][j];
        }
        for (ll j = 0; j < k; ++j)
        {
            ll h = (j - a % k + k) % k;
            if (s[prev][h])
            {
                dp[now][j] = max(dp[now][j], dp[prev][h] + b);
                s[now][j] = 1;
            }
        }
    }
    ans = dp[n & 1][0];
    if (ans == 0)
    {
        printf("-1");
    }
    else
    {
        printf("%lld", ans);
    }
    return 0;
}

题解可以通过把无方案(即 $s=0$ 设 $dp$ 为无穷小，那么可以省掉

D 雪色光晕

计算几何求点到线段距离的纯板子题

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lf", &x)
#define mn 200010
ll n;
db dx, dy;
struct point
{
    db x, y;
    point(db x = 0, db y = 0) : x(x), y(y) {}
    point(const point &p) : x(p.x), y(p.y) {}
    db norm() { return x * x + y * y; }
    point operator+(point p) { return point(x + p.x, y + p.y); }
    point operator-(point p) { return point(x - p.x, y - p.y); }
};
db abst(point p) { return sqrt(p.norm()); }
db cross(point a, point b)
{
    return a.x * b.y - a.y * b.x;
}
db dot(point a, point b)
{
    return a.x * b.x + a.y * b.y;
}
db solve(point a, point b, point p) //ab与p距离
{
    if (dot(b - a, p - a) < 0.0)
    {
        return abst(p - a);
    }
    if (dot(a - b, p - b) < 0.0)
    {
        return abst(p - b);
    }
    return abst(cross(b - a, p - a) / abst(b - a));
}
db ans = 1e18;
point now, prv, cmp;
signed main()
{
    scanf("%lld", &n);
    sc(now.x), sc(now.y), sc(cmp.x), sc(cmp.y);
    while (n--)
    {
        sc(dx), sc(dy);
        prv = now;
        now.x = prv.x + dx;
        now.y = prv.y + dy;
        // printf("%lf %lf %lf %lf\n", prv.x, prv.y, now.x, now.y);
        ans = min(ans, solve(prv, now, cmp));
    }
    printf("%.12lf", ans);
    return 0;
}

B 进制

受第三第二场集训题解的启发，得以在赛时想出。

不难发现，为了使得表示的值最小，应当贪心地选择允许的最小进制，即所查询的 $[x,y]$ 区间里最大值 $+1$ 进制。维护单点任意修改、区间查询最小值，特别注意不能使用树状数组，只能用线段树来维护。这是因为树状数组只能维护历史上最小的最小值，如果先出现小的，再改成大的，就会无法维护。

然后可以开多个线段树或树状数组维护进制区间和。由于长为 $m$ 的 $k$ 进制数 $x$ 可以表示为： $$ x=k^0x_0+k^1x_1+\cdots+k^mx_m $$ 如果要将这个数字整体放大，向高位移动 $p$ 位，则可以将其乘以 $k^p$

根据这个性质，可以用较优的复杂度维护区间进制数，然后再移动即可，因为涉及单点修改和区间查询，可以直接使用树状数组或不带懒标记的线段树

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll mod = 1e9 + 7, n, q, iv[11][mn], pw[11][mn], b[mn], op, x, y;
ll qpow(ll a, ll b)
{
    ll res = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
    }
    return res;
}
ll inv(ll a)
{
    return qpow(a, mod - 2);
}
ll lowbit(ll &k) { return k & -k; }
struct szsz
{
    ll a[mn];
    void update(ll i, ll v)
    {
        for (; i <= n; i += lowbit(i))
        {
            a[i] = (a[i] + v + mod) % mod;
        }
    }
    ll ask(ll rf)
    {
        ll ans = 0;
        for (; rf != 0; rf -= lowbit(rf))
        {
            ans = (ans + a[rf]) % mod;
        }
        return ans;
    }
    ll query(ll lf, ll rf)
    {
        return (ask(rf) - ask(lf - 1) + mod) % mod;
    }
} s[11];
ll mx[mn << 2], laz[mn << 2];
#define lfs r << 1
#define rfs r << 1 | 1
#define mkcf ll cf = (lf + rf) >> 1
void build(ll r, ll lf, ll rf)
{
    if (lf == rf)
    {
        mx[r] = b[lf];
        laz[r] = -1;
        return;
    }
    mkcf;
    build(lfs, lf, cf);
    build(rfs, cf + 1, rf);
    mx[r] = max(mx[lfs], mx[rfs]);
    laz[r] = -1;
}
void pushdown(ll r, ll lf, ll rf)
{
    if (laz[r] == -1)
    {
        return;
    }
    mkcf;
    mx[lfs] = max(mx[lfs], laz[r]);
    mx[rfs] = max(mx[rfs], laz[r]);
    laz[lfs] = laz[rfs] = laz[r];
    laz[r] = -1;
}
void update_mx(ll r, ll lf, ll rf, ll i, ll v)
{
    if (lf == rf)
    {
        laz[r] = -1;
        mx[r] = v;
        return;
    }
    mkcf;
    // pushdown(r, lf, rf);
    if (i <= cf)
    {
        update_mx(lfs, lf, cf, i, v);
    }
    else
    {
        update_mx(rfs, cf + 1, rf, i, v);
    }
    mx[r] = max(mx[lfs], mx[rfs]);
}
ll query_mx(ll r, ll lf, ll rf, ll lc, ll rc)
{
    if (lf >= lc && rf <= rc)
    {
        return mx[r];
    }
    ll res = 0;
    mkcf;
    if (cf >= lc)
    {
        res = max(res, query_mx(lfs, lf, cf, lc, rc));
    }
    if (cf < rc)
    {
        res = max(res, query_mx(rfs, cf + 1, rf, lc, rc));
    }
    return res;
}
char ss[mn];
void init()
{
    sc(n), sc(q), scanf("%s", ss + 1);
    for (ll i = 1; i <= n; ++i)
    {
        b[i] = ss[n - i + 1] - '0';
    }
    for (ll i = 2; i <= 10; ++i)
    {
        iv[i][0] = 1;
        pw[i][0] = 1;
    }
    for (ll i = 2; i <= 10; ++i)
    {
        for (ll j = 1; j <= n; ++j)
        {
            pw[i][j] = pw[i][j - 1] * i % mod;
            iv[i][j] = inv(pw[i][j]);
        }
    }
    build(1, 1, n);
    for (ll i = 2; i <= 10; ++i)
    {
        for (ll j = 1; j <= n; ++j)
        {
            s[i].update(j, b[j] * pw[i][j - 1] % mod);
        }
    }
}
signed main()
{
    init();
    while (q--)
    {
        sc(op), sc(x), sc(y);
        x = n - x + 1;
        if (op == 1)
        {
            for (ll i = 2; i <= 10; ++i)
            {
                s[i].update(x, mod - (b[x] * pw[i][x - 1] % mod));
            }
            b[x] = y;
            for (ll i = 2; i <= 10; ++i)
            {
                s[i].update(x, y * pw[i][x - 1] % mod);
            }
            update_mx(1, 1, n, x, y);
        }
        else
        {
            y = n - y + 1;
            swap(x, y);
            ll bs = query_mx(1, 1, n, x, y) + 1;
            bs = max(bs, 2LL);
            ll v = s[bs].query(x, y);
            // printf("[%lld] %lld\n", bs, v);
            v = v * iv[bs][x - 1] % mod;
            printf("%lld\n", v);
        }
    }
    return 0;
}

G 子序列权值乘积

显然排序原数组后不影响结果。在排序之后，排在第 $i$ 位的数是 $a_i$ ，设它前后分别有 $x,y$ 个数，则以 $a_i$ 为最大值的子序列有它自己以及前 $x$ 个数组成的所有子序列与 $a_i$ 的并，这样的子序列有 $2^x-1$ 个，加上它自己是 $2^x$ 个；同理，以 $a_i$ 为最小值贡献 $2^y$ 个，这意味着最终对答案的积累为 $a_i^{2^x+2^y}$

特别注意在取模意义下1，由于下面的等式不成立： $$ a^x\bmod p=a^{x\ \bmod\ p}\bmod p $$ 所以不能直接对幂取模。可以想到利用拓展欧拉定理，实现： $$ a^x\bmod p=a^{x\ \bmod\ \varphi(p)}\bmod p $$ 对质数 $p$ ，其欧拉函数值为 $\varphi(p)=p-1$ ，可解出本题。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll mod = 1e9 + 7, phi = mod - 1;
ll qpow(ll a, ll b)
{
    ll res = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
    }
    return res;
}
#define mn 200010
ll n, a[mn], ans = 1, pw[mn];
ll qqpow(ll a, ll b) //a^(2^b)
{
    return qpow(a, pw[b] + phi);
}
signed main()
{
    sc(n);
    pw[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        sc(a[i]);
        pw[i] = pw[i - 1] * 2 % phi;
    }
    sort(a + 1, a + 1 + n);
    for (ll i = 1; i <= n; ++i)
    {
        ans = ans * qqpow(a[i], i - 1) % mod * qqpow(a[i], n - i) % mod;
    }
    printf("%lld", ans);
    return 0;
}

L 在这冷漠的世界里光光哭哭

这是一道比较神奇的枚举题。赛时想出了一半的步骤，但是剩下的没想出来。问题即求静态数组任意子区间的长为 $3$ 的字符可重复的子序列的数目，要求单次查询复杂度为 $O(1)$ 或 $O(\log n)$

对第 $k$ 个字符 $s_k$ ，在前 $k$ 个字符的子串里，设包含子序列 $(i,s_k,j)$ 的数量是 $dp_{k,i,j}$ ，首先预处理前缀和、后缀和 $op_{i,j}, ed_{i,j}$ ，分别代表前 $i$ 个字符的子串里，字符 $j$ 出现的个数，以及从第 $i$ 到结尾的子串里 $j$ 出现的个数；那么对位置 $k$ ，其子序列 $(i,s_k,j)$ 的数量为 $op_{i-1,j}\times ed_{i+1,j}$ ；对 $dp$ 的计算可以等于对上述计算叠一个前缀和

那么对查询 $[l,r]$ 内的子序列 $(a,b,c)$ ，升序记录下每个字母出现的下标，可以二分找到 $[l,r]$ 内第一个 $b$ 的位置的上一个位置；找到 $[l,r]$ 内最后一个 $b$ 的位置的下一个位置，分别记作 $id_l, id_r$ ，那么根据前缀和的性质，计算 $dp_{id_r,a,c}-dp_{id_l,a,c}$ 可以得到一个范围内的子序列值，但是仍存在 $a,c$ 越界，不在 $[l,r]$ 内的情况，需要减去，具体有三种：

1. $a$ 在 $[l,r]$ 左边， $b$ 在 $[l,r]$ 内， $c$ 在 $[l,r]$ 右边
2. $a$ 在 $[l,r]$ 左边， $bc$ 在 $[l,r]$ 内
3. $ab$ 在 $[l,r]$ 内， $c$ 在 $[l,r]$ 右边

对第一种情况，根据上面类似的算法，可以很快得出公式为： $$ op_{l-1,a}\times ed_{r+1,c}\times(op_{r,b}-op_{l-1,b}) $$ 对剩下两种情况，可以再多预处理一个 $sum_{k,a,b}$ 代表前 $k$ 个字符的子串里，包含子序列 $(a,b)$ 的数目；这可以通过滑动窗口算法比较快地求出来，那么对后两种情况，直接计算前缀和查询即可

预处理时间复杂度为 $O(26^2n)$。由于涉及二分，查询复杂度为 $O(q\log n)$ ，空间复杂度为 $O(26^2 n)$

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 80010
#define al 26
ll op[mn][al], ed[mn][al], sum2[mn][al][al], dp[mn][al][al];
ll tmp[al][al][al], n, q, l, r;
char s[mn], cmd[10];
vector<ll> ids[al];
ll find(ll l, ll r, ll x, ll y) //在区间[l,r]内有子序列<x,y>多少个
{
    return sum2[r][x][y] - sum2[l - 1][x][y] - op[l - 1][x] * (op[r][y] - op[l - 1][y]); //[1,r]<x,y>-[1,l-1]<x,y>-[1,l-1]<x>[l,r]<y>
}
signed main()
{
    sc(n), sc(q), scanf("%s", s + 1);
    for (ll i = 0; i < al; ++i)
    {
        ids[i].emplace_back(0);
    }
    for (ll i = 1; i <= n; ++i)
    {
        ll ci = s[i] - 'a';
        ids[ci].emplace_back(i);
        for (ll j = 0; j < al; ++j)
        {
            op[i][j] = op[i - 1][j];
        }
        ++op[i][ci]; //顺前缀和
        for (ll j = 0; j < al; ++j)
        {
            for (ll k = 0; k < al; ++k)
            {
                sum2[i][j][k] = sum2[i - 1][j][k];
            }
            sum2[i][j][ci] += op[i - 1][j];
            //前i个字符的子串，子序列(j,ci)的数目(简单的滑窗)
        }
    }
    for (ll i = n; i; --i)
    {
        for (ll j = 0; j < al; ++j)
        {
            ed[i][j] = ed[i + 1][j];
        }
        ++ed[i][s[i] - 'a']; //逆前缀和
    }
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 0; j < al; ++j)
        {
            for (ll k = 0; k < al; ++k)
            {
                tmp[s[i] - 'a'][j][k] += op[i - 1][j] * ed[i + 1][k];
                dp[i][j][k] = tmp[s[i] - 'a'][j][k];
                //第i个字母是s[i]-'a',子序列<j,ci,k>的数目是dp[i][j][k]
                //对j,k考虑全长，对s[i]-'a'只考虑到当前位置
                //tmp的本质是压缩掉i之后的dp
                //这是个比较简单的滑窗
            }
        }
    }
    while (q--)
    {
        sc(l), sc(r), scanf("%s", cmd + 1);
        ll x1 = cmd[1] - 'a', x2 = cmd[2] - 'a', x3 = cmd[3] - 'a';
        if (op[r][x2] - op[l - 1][x2] == 0) //[l,r]没有x2
        {
            printf("0\n");
            continue;
        }
        ll lf = lower_bound(ids[x2].begin(), ids[x2].end(), l) - ids[x2].begin() - 1; //大于等于l的第一个位置的前一个位置
        ll rf = upper_bound(ids[x2].begin(), ids[x2].end(), r) - ids[x2].begin() - 1; //超出r的第一个位置的前一个位置
        ll res = dp[ids[x2][rf]][x1][x3] - dp[ids[x2][lf]][x1][x3];
        res -= op[l - 1][x1] * find(l, r, x2, x3);
        res -= ed[r + 1][x3] * find(l, r, x1, x2);
        res -= op[l - 1][x1] * (op[r][x2] - op[l - 1][x2]) * ed[r + 1][x3];
        //先剪掉(?b)[?](?) ?即any
        //再剪掉三种不合理为(a)[bc](),()[ab](c),(a)[b](c),只希望保留()[abc]()
        printf("%lld\n", res);
    }
    return 0;
}

第五场

比赛日志：

这次比赛比较有难度……签到J五分钟过了之后第二题就给我整不会了，重读题目发现是选不重复的问题，我想不出组合数学的式子，然后猜测记忆化搜索复杂度比较低，但是没写出来，debug有问题，然后索性心一横，试试直接上个暴力DFS试试，然后就把G这道题给过掉了，30分钟，不过排名很难看。然后往后是I，这道题一开始想了一会儿，然后发现了只需要考虑相邻区间，那么就直接试着上了个空隙和，一交一发WA。然后仔细思考，发现减得不均匀，然后发现可以用前缀和+二分来做，然后试着交了一发，A掉了，53分钟。然后有两道这时候差不多过题数，但是远低于前三题的题，比较高的A题我去看了，仔细想了，暂时没想出什么办法，只会两针疫苗，不会三针。然后去看D，说是数位DP，于是我就试着推了一下，写了很久很久的实现，用暴力对拍，改了很多版，思考了很久究竟要怎么细节实现(虽然整体思路大概是对的)。然后一交一个WA，然后发现了点问题，如发现l=1不行，修了修又交又WA，然后又错了，然后自己又跑了更多例子，发现尾处理不行，比如11的r=1没有处理上，r=67的7没有处理上，然后又修又交，终于过了，223分钟，大坐牢。然后我倒回去看A，然后有思路了，发现可以枚举中间，把本来的思路往左边复刻一次，就行了，然后实现了下，255分钟过掉了A题。然后我还是比不上他，罚时高，排名也很落后。然后看了看，E题没啥思路，C题有思路(过A之前我甚至在想C)，然后不顺次的DP，想想不就是记忆化DFS嘛，搜索一下，过掉了，卡得比较紧张(debug花了点时间)，最后八分钟过了题，第292分钟。然后时间已经不够看下面的题目了，我就直接原地结束了。

J 三国小孩

对方的最优解是全部是桃，如果自己的杀+决斗能耗完血+桃就必胜。

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n, m, k;
signed main()
{
    sc(n), sc(m), sc(k);
    if (n + m > k)
    {
        printf("YES");
    }
    else
    {
        printf("NO");
    }
    return 0;
}

G 163小孩

解法一：即求长为13的4重集抽6个元素的所有结果可能有多少种(去重,组合)，暴力搜索即可

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll n = 13, m = 6, k = 4;
// ll n = 3, m = 3, k = 2;
struct stt
{
    ll a[15];
} ori;
ll h(const stt &s)
{
    ll r = 0;
    for (ll i = 1; i <= n; ++i)
    {
        // printf("%lld ", s.a[i]);
        r = r * 10 + s.a[i];
    }
    // printf("\n");
    return r;
}
set<ll> s,s2;
ll ans;
void dfs(stt &x, ll lf)
{
    if (lf == 0)
    {
        ++ans;
        // for (ll i = 1; i <= n; ++i)
        // {
        //     printf("%lld ", x.a[i]);
        // }
        // printf("\n");
        ll hs = h(x);
        s2.insert(hs);
        return;
    }
    // ll hs = h(x);
    // if (s.find(hs) != s.end())
    // {
    //     return;
    // }
    // s.insert(hs);
    for (ll i = 1; i <= n; ++i)
    {
        stt nw;
        if (x.a[i] < k)
        {
            for (ll j = 1; j <= n; ++j)
            {
                nw.a[j] = x.a[j];
            }
            ++nw.a[i];
        }
        else
        {
            continue;
        }
        ll hsw = h(nw);
        // printf("%lld\n", hsw);
        s.insert(hsw);
        dfs(nw, lf - 1);
    }
}
signed main()
{
    // dfs(ori, m);
    // printf("%lld\n", ans);
    // ll ans2 = s.size();
    // printf("%lld\n", ans2);
    // ll ans3 = s2.size();
    // printf("%lld", ans3);
    printf("18395");
    return 0;
}
//78416
//4825860
//26949
//18395

解法二：神奇模拟 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (ll i = a; i <= b; ++i)
ll ans;
signed main()
{
    rep(a1,0,4)
    rep(a2,0,4)
    rep(a3,0,4)
    rep(a4,0,4)
    rep(a5,0,4)
    rep(a6,0,4)
    rep(a7,0,4)
    rep(a8,0,4)
    rep(a9,0,4)
    rep(a10,0,4)
    rep(a11,0,4)
    rep(a12,0,4)
    rep(a13,0,4)
    if(a1+a2+a3+a4+a5+a6+a7+a8+a9+a10+a11+a12+a13==6)++ans;
    printf("%lld",ans);
    return 0;
}

解法三：也可以纯组合数学推导，具体推导看代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll c(ll uf, ll df)
{
    ll res = 1;
    for (ll i = df - uf + 1; i <= df; ++i)
        res *= i;
    for (ll i = 1; i <= uf; ++i)
        res /= i;
    return res;
}
ll ans;
signed main()
{
    ans += c(6, 13);                     // 1 1 1 1 1 1 -> 13组选6组，每组都是1个
    ans += c(5, 13) * c(1, 5);           // 2 1 1 1 1 -> 先选5组,再选1组分两个
    ans += c(4, 13) * c(2, 4);           // 2 2 1 1
    ans += c(3, 13);                     // 2 2 2
    ans += c(4, 13) * c(1, 4);           // 3 1 1 1
    ans += c(3, 13) * c(1, 3) * c(1, 2); // 3 2 1
    ans += c(2, 13);                     // 3 3
    ans += c(3, 13) * c(1, 3);           // 4 1 1
    ans += c(2, 13) * c(1, 2);           // 4 2
    printf("%lld", ans);
    return 0;
}

解法四 (another version of 解法二) 我自己推的枚举表达式：

按组合方式单调枚举，可以发现超过 $4$ 张牌有且仅有三种情况： $$ (a,a,a,a,a,b),(a,b,b,b,b,b),(a,a,a,a,a,a) $$ 除此之外都是合法的，故 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define repe(i, a, b) for (ll i = a; i <= b; ++i)
ll cnt;
void check(ll a1, ll a2, ll a3, ll a4, ll a5, ll a6)
{
    if (a1 == a5 || a2 == a6 || a1 == a6) //重复
    {
        return;
    }
    ++cnt;
}
signed main()
{
    repe(a1, 1, 13)
        repe(a2, a1, 13)
            repe(a3, a2, 13)
                repe(a4, a3, 13)
                    repe(a5, a4, 13)
                        repe(a6, a5, 13)
                            check(a1, a2, a3, a4, a5, a6);
    printf("%lld", cnt);
    return 0;
}

I 兔崽小孩

每一条说说只影响下一条说说之前的睡眠时间(轮不到它影响下下一条，因为下一条对下下一条的影响更早)，所以把原数组分割为若干个上一条说说和这一条说说的时间差，然后按升序排序。每次查询时，小于等于k的时间段全部睡不着，其余时间段都睡得着。所以叠前缀和，先用整体和减去小于等于k的前缀和段，然后再减去k倍剩余段长(大于k的各自要花k分钟睡着)，然后跟p比大小

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1000010
ll n, q, t[mn], k, p, s[mn], cnt, a[mn], s2;
signed main()
{
    sc(n), sc(q);
    for (ll i = 1; i <= n; ++i)
    {
        sc(t[i]);
    }
    for (ll i = 1; i < n; ++i)
    {
        ll v = t[i + 1] - t[i];
        a[++cnt] = v;
    }
    sort(a + 1, a + 1 + cnt);
    for (ll i = 1; i <= n; ++i)
    {
        s[i] = s[i - 1] + a[i];
    }
    s2 = s[1 + cnt];
    while (q--)
    {
        sc(k), sc(p);
        ll idx = lower_bound(a + 1, a + 1 + cnt, k) - a;
        // printf("-%lld\n", idx);
        ll ans = s2 - s[idx - 1];
        ans -= k * (cnt - idx + 1);
        // printf("%lld\n", ans);
        if (ans >= p)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}

D 数位小孩

解法一：直接上数位 DP ，设 $dp[i][j][k]$ 表示从个位开始数的 i 位，最大的位数字是 j ， k 表示是否出现过 1，相邻数位和都是数组的方案数，即 $i$ 位数区间 $[\overline{j0\cdots 0},\overline{j9\cdots 9}]$ 范围

根据定义，初始化为 $dp[1][1][1]=1$ , $dp[1][j][0]=1 (0\le j\le 9, j\neq 1)$ ，表示十个个位数的情况

递推方程为若 $j+j'$ 是素数，那么 $k'=k\cup k'\cup j==1\cup j'==1$ 时可以加上去(具体看代码)

特别地，设 $dd[i]$ 表示区间 $[1,10^{i-1}-1]$ 的答案，则： $$ dd[i]=dd[i-1]+\sum_{j=1}^9dp[i-1][j][1] $$ 对 $[1, r]$ 的区间内的答案计数，对 $r=\overline{a_k\cdots a_2a_1}$ ，先用 $dd[k]$ 计数前 $k$ 位数的答案，然后讨论 $k$ 位数答案，对第 $i$ 位，$> i$ 的位都取 $r$ 值即 $a_h(h &gt; i)$，第 $i$ 位进行枚举 $[0, a_i)$ ，得到一个范围内的答案；注意若 $&gt; i$ 时出现过 $1$ ，则 $dp$ 第三维度任取，否则只能取 $1$

答案为 $[1,r]$ 内答案减去 $[1,l-1]$ 内答案

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll dp[12][12][2]; //后i位,最高位为j,是否出现过1,相邻数位和为素数的方案数
ll prime[] = {2, 3, 5, 7, 11, 13, 17}, ps = 7;
ll l, r, res;
ll dd[12]; //[1,10^(i-1)-1]内的答案
ll ispr(ll x)
{
    for (ll i = 0; i < ps; ++i)
    {
        if (x == prime[i])
        {
            return 1;
        }
    }
    return 0;
}
ll ask(ll rf)
{
    res = 0;
    if (rf <= 9 && rf >= 1)
    {
        return 1;
    }
    ll bs = 0;
    ll b[12] = {};
    for (ll i = rf; i; i /= 10)
    {
        ++bs;
        b[bs] = i % 10;
    }
    ll ever1 = 0, ever2 = 0;
    for (ll i = bs; i >= 1; --i)
    {
        ll je = b[i] + (i == 1);
        if (je > 0 && i > 1 && !ever2)
        {
            res += dd[i];
            ever2 = 1;
            // printf("%lld:%lld\n", i, dd[i]);
        }
        ll jb = 1 - (i != bs);
        for (ll j = jb; j < je; ++j)
        {
            ll k = (i > 1) ? 1 : ((j == 1) ? 1 : !ever1);
            if (i != bs && !ispr(b[i + 1] + j))
            {
                continue;
            }
            // printf("%lld %lld %lld %lld\n", i, j, k, dp[i][j][k]);
            res += dp[i][j][k];
            if (ever1)
            {
                res += dp[i][j][k ^ 1];
            }
        }
        ever1 |= (b[i] == 1);
        if (i != bs && !ispr(b[i] + b[i + 1]))
        {
            break;
        }
    }
    return res;
}
ll bfcheck(ll lf, ll rf)
{
    ll cnt = 0;
    for (ll h = lf; h <= rf; ++h)
    {
        ll has1 = 0;
        ll bs = 0;
        ll b[12] = {};
        for (ll j = h; j; j /= 10)
        {
            ++bs;
            b[bs] = j % 10;
            has1 |= (b[bs] == 1);
        }
        if (bs == 1)
        {
            cnt += (h == 1);
            continue;
        }
        ll ok = 1;
        for (ll i = 1; i < bs; ++i)
        {
            ll isprime = ispr(b[i] + b[i + 1]);
            if (isprime == 0)
            {
                ok = 0;
                break;
            }
        }
        if (ok && has1)
        {
            // printf("%lld\n", h);
            ++cnt;
        }
    }
    return cnt;
}
signed main()
{
    dp[1][1][1] = 1;
    for (ll i = 2; i <= 9; ++i)
    {
        dp[1][i][0] = 1; //没有相邻，条件1恒成立
    }
    dp[1][0][0] = 1;
    for (ll i = 2; i <= 11; ++i)
    {
        for (ll x = 0; x <= 9; ++x)
        {
            ll now0 = (x == 1);
            for (ll y = 0; y <= 9; ++y)
            {
                for (ll pr = 0; pr <= 1; ++pr)
                {
                    ll has0 = now0 || ((y == 1) || pr);
                    ll s = x + y;
                    ll isprime = 0;
                    for (ll j = 0; j < ps; ++j)
                    {
                        if (s == prime[j])
                        {
                            isprime = 1;
                            break;
                        }
                    }
                    if (!isprime)
                    {
                        continue;
                    }
                    // printf("%lld %lld %lld %lld %lld %lld %lld %lld [%lld]\n",
                    //        i, x, has0, i - 1, y, pr, dp[i][x][has0], dp[i - 1][y][pr], s);
                    dp[i][x][has0] += dp[i - 1][y][pr];
                }
            }
        }
    }
    // dd[2] = 1;
    for (ll i = 2; i <= 11; ++i)
    {
        dd[i] = dd[i - 1];
        for (ll j = 1; j <= 9; ++j)
        {
            dd[i] += dp[i - 1][j][1];
        }
    }
    sc(l), sc(r);
    ll ar = ask(r), al = ask(l - 1);
    printf("%lld", ar - al);
    // printf("\n%lld %lld %lld", bfcheck(l, r), ar, al);
    return 0;
}

解法二：可以打表注意到 $10^{10}$ 内答案数量级为 $10^6$ ，意味着有可能直接枚举所有答案

为了避免无限 $0$ ，从 $[1,9]$ 各自开始搜索，直到大于 $r$ 为止，每次不断扩大一位

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sc(x) scanf("%lld", &x)
bool p[20];
ll ans, lf, rf;
void dfs(ll x, ll has1)
{
    if (x > rf)
    {
        return;
    }
    if (x >= lf && has1)
    {
        ++ans;
    }
    for (ll i = 0; i <= 9; ++i)
    {
        if (p[x % 10 + i])
        {
            dfs(x * 10 + i, has1 || (i == 1));
        }
    }
}
signed main()
{
    p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17] = true;
    sc(lf), sc(rf);
    for (ll i = 1; i <= 9; ++i)
    {
        dfs(i, i == 1);
    }
    printf("%lld", ans);
    return 0;
}

A 疫苗小孩

显然离 $k$ 越近越好，假设打三针，那么从每个 $0$ 为第二针，向左向右二分找最接近 k 的两个 0 (如果找得到就打，找不到就不打)，实现上找大于等于它的第一个 0 和该位置的前一个位置即可，分别计算得哪个更好，然后计算打针效果

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1000010
char c[mn];
ll a[mn], n, m, k, w, q, ans, nx[mn], pr[mn];
ll cal(ll x, ll y)
{
    ll p = y - x;
    if (x < 1 || y > n || y <= x)
    {
        return 0;
    }
    return w - abs(k - p) * q;
}
signed main()
{
    sc(n), scanf("%s", c + 1), sc(k), sc(w), sc(q), ++m;
    a[0] = -0x3fffffff;
    for (ll i = 1; i <= n; ++i)
    {
        if (c[i] == '0')
        {
            a[++m] = i;
        }
    }
    a[m + 1] = 0x3ffffffff;
    for (ll i = 2; i <= m; ++i)
    {
        ll j = a[i];
        ll nxi = lower_bound(a + 1, a + 1 + m, j + k) - a;
        ll nx = max(cal(j, a[nxi]), cal(j, a[nxi - 1]));
        ll pri = lower_bound(a + 1, a + 1 + m, j - k) - a;
        ll pr = max(cal(a[pri], j), cal(a[pri - 1], j));
        // printf("%lld %lld %lld\n", j, nx, pr);
        ans = max(ans, nx + pr);
    }
    printf("%lld", ans);
    return 0;
}

C 战棋小孩

解法一：可以用记忆化 DFS 的 DP 方法，设 $dp[i][j][k]$ 是打了 $i$ 场，当前分数为 $j$ ，已经用了 $k$ 次礼遇，此时的高兴次数是多少次；所求即 $dp[n][any][any]$ 的最值，搜索时对比当前更差的结果剪枝(而不是 vis 剪枝，因为最先 vis 的不能证明是最优的)，因为乱序，所以搜索全排列

一个实现细节是避免负数下标，可以把所有分数偏差 $100n$ 分

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 22
#define mm 18010
ll n, k, s, p[mn], ca[mn], cb[mn], dt = 2001, ans;
ll dp[mn][mm][mn]; //打了i场,现在分数是j,用了k次礼遇
set<ll> me;
void dfs(ll now, ll po, ll ly, ll cn)
{
    if (dp[now][po][ly] >= cn)
    {
        return;
    }
    // printf("%lld %lld %lld %lld\n", now, po - dt, ly, cn);
    // for (auto i : me)
    // {
    //     printf("%lld ", i);
    // }
    // printf("\n");
    dp[now][po][ly] = cn;
    if (n == now)
    {
        return;
    }
    for (ll i = 1; i <= n; ++i)
    {
        if (me.find(i) != me.end())
        {
            continue;
        }
        // printf("<%lld\n", i);
        me.insert(i);
        ll poa = po + ca[i];
        dfs(now + 1, poa, ly, cn + (poa >= p[now + 1]));
        me.erase(i);
        if (ly > 0)
        {
            me.insert(i);
            ll pob = po + cb[i];
            // printf("?? %lld %lld\n", pob, p[now]);
            dfs(now + 1, pob, ly - 1, cn + (pob >= p[now + 1]));
            me.erase(i);
        }
    }
}
signed main()
{
    sc(n), sc(k), sc(s), s += dt;
    for (ll i = 1; i <= n; ++i)
    {
        sc(p[i]);
        p[i] += dt;
    }
    for (ll i = 1, a, b, c, d; i <= n; ++i)
    {
        sc(a), sc(b), sc(c), sc(d);
        ca[i] = max(a, b);
        cb[i] = max(ca[i], max(c, d));
    }
    dfs(0, s, k, 1);
    // printf("??%lld\n", dp[3][8093 + dt][0]);
    for (ll i = 1; i <= 18000; ++i)
    {
        for (ll j = 0; j <= k; ++j)
        {
            ans = max(ans, dp[n][i][j]);
        }
    }
    printf("%lld", ans - 1);
    return 0;
}

解法二：已确定哪些局使用礼遇时，贪心是最优的(按增加分数从大到小排序打游戏)，因为这样的前缀和是最大的，任意对换后得到的结果都不会比这个更优(可证)

所以可以二进制枚举所有礼遇状况，然后计算即可

AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 22
ll n, k, s, p[mn], x[mn], y[mn], z[mn], ans, res;
bool cmp(ll x, ll y) { return x > y; }
signed main()
{
    sc(n), sc(k), sc(s);
    for (ll i = 1; i <= n; ++i)
    {
        sc(p[i]);
    }
    for (ll i = 1, a, b, c, d; i <= n; ++i)
    {
        sc(a), sc(b), sc(c), sc(d);
        x[i] = max(a, b);
        y[i] = max(x[i], max(c, d));
    }
    for (ll h = 0, he = 1 << n; h < he; ++h)
    {
        ll cnt = 0, v = h;
        for (ll i = 1; i <= n; ++i, v >>= 1)
        {
            if (v & 1)
            {
                ++cnt;
                z[i] = y[i];
            }
            else
            {
                z[i] = x[i];
            }
        }
        if (cnt <= k)
        {
            sort(z + 1, z + 1 + n, cmp);
            ll r = s;
            res = 0;
            for (ll i = 1; i <= n; ++i)
            {
                r += z[i];
                res += (r >= p[i]);
            }
            ans = max(ans, res);
        }
    }
    printf("%lld", ans);
    return 0;
}

E 复苏小孩

初始三者能力值为矩阵 $(1,1,1)$ ，经历字符 1,2,3 后，分别等效于将其乘以矩阵： $$ \begin{bmatrix} 1&0&0\ \dfrac12&\dfrac12&0\ \dfrac12&0&\dfrac12 \end{bmatrix} \quad \begin{bmatrix} \dfrac12&\dfrac12&0\ 0&1&0\ 0&\dfrac12&\dfrac12 \end{bmatrix} \quad \begin{bmatrix} \dfrac12&0&\dfrac12\ 0&\dfrac12&\dfrac12\ 0&0&1\ \end{bmatrix} $$ 使用线段树维护单点修改和区间查询，每个节点都是矩阵

实现上，查询时用单位矩阵乘以左查询和右查询的结果；注意到只有单点修改，所以不需要设懒标签

本题很诡异，内存实际限制得很死(虽然显示256MB)，开 $4\times 10^5$ 个 long long 矩阵会 CE ，但开 int 就没事

时间复杂度为 $O(3^3n\log n)$ ，空间复杂度为 $O(4\cdot 3^3\cdot n)$

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll mod = 998244353, n, m, inv2 = 499122177, cmd, x, y;
struct matrix
{
    int v[4][4] = {};
    ll n = 3, m = 3;
    matrix operator*(const matrix &p) const
    {
        matrix r;
        memset(r.v, 0, sizeof r.v);
        r.n = n, r.m = p.m;
        for (ll i = 1; i <= n; ++i)
        {
            for (ll j = 1, x = 0; j <= p.m; ++j, x = 0)
            { //因为忘记最后补上 ,x=0 导致一直 debug 没 de 出来
                for (ll k = 1; k <= m; ++k)
                {
                    x = (x + 1LL * v[i][k] * p.v[k][j]) % mod;
                }
                r.v[i][j] = x;
            }
        }
        return r;
    }
    void init(ll x = 3, ll y = 3)
    {
        n = x, m = y;
        memset(v, 0, sizeof v);
        for (ll i = 1; i <= 3; ++i)
        {
            v[i][i] = 1;
        }
    }
} a[mn << 2], b[4];
char c[mn];
#define lfs p << 1
#define rfs p << 1 | 1
#define mkcf ll cf = (lf + rf) >> 1
void build(ll p, ll lf, ll rf)
{
    if (lf == rf)
    {
        memcpy(a[p].v, b[c[lf] - '0'].v, sizeof a[p].v);
        return;
    }
    mkcf;
    build(lfs, lf, cf);
    build(rfs, cf + 1, rf);
    a[p] = a[lfs] * a[rfs];
}
void update(ll p, ll lf, ll rf, ll s)
{
    if (lf == rf)
    {
        memcpy(a[p].v, b[c[lf] - '0'].v, sizeof a[p].v);
        return;
    }
    mkcf;
    if (s <= cf)
    {
        update(lfs, lf, cf, s);
    }
    else
    {
        update(rfs, cf + 1, rf, s);
    }
    a[p] = a[lfs] * a[rfs];
}
matrix query(ll p, ll lf, ll rf, ll lc, ll rc)
{
    if (lf >= lc && rf <= rc)
    {
        return a[p];
    }
    matrix q;
    q.init();
    mkcf;
    if (cf >= lc)
    {
        q = q * query(lfs, lf, cf, lc, rc);
    }
    if (cf < rc)
    {
        q = q * query(rfs, cf + 1, rf, lc, rc);
    }
    return q;
}
signed main()
{
    b[1].v[1][1] = 1;
    b[1].v[2][1] = b[1].v[2][2] = b[1].v[3][1] = b[1].v[3][3] = inv2;
    b[2].v[2][2] = 1;
    b[2].v[1][1] = b[2].v[1][2] = b[2].v[3][2] = b[2].v[3][3] = inv2;
    b[3].v[3][3] = 1;
    b[3].v[1][1] = b[3].v[1][3] = b[3].v[2][2] = b[3].v[2][3] = inv2;
    sc(n), sc(m), scanf("%s", c + 1);
    build(1, 1, n);
    while (m--)
    {
        sc(cmd), sc(x), sc(y);
        if (cmd == 1)
        {
            c[x] = '0' + y;
            update(1, 1, n, x);
        }
        else
        {
            matrix ans;
            ans.n = 1, ans.m = 3, ans.v[1][1] = ans.v[1][2] = ans.v[1][3] = 1;
            matrix md = query(1, 1, n, x, y);
            ans = ans * md;
            printf("%d %d %d\n", ans.v[1][1], ans.v[1][2], ans.v[1][3]);
        }
    }
    return 0;
}

F 飞车小孩

将对局信息按先后排序后；可以发现，每次已知一个对局信息，就可以唯一地确定截止目前对局双方分别选了多少张图(由选图规则易知)，那么在两个已知之间隔的未知区间里，设双方分别选了 $x,y$ 次，那么区间长为 $x+y$ ，等价于先让一方选再让另一方选，得： $$ C_{x+y}^xC_{x+y-x}^y = C_{x+y}^x=C_{x+y}^y $$ 那么设最后还剩下的长度为 $m$ ，由于没有下一个已知，则最后的序列只需要满足一方选的九峰胜率递增，一方选的九峰胜率递减即可，可以找规律得出答案为 $2^m$ ；

严格证明可以这么推导：每一局可以由双方选择，方案数为 $2$ ，共 $m$ 局，乘法原理；然后只要确定了每一局分别由谁选，就可以唯一确定先后顺序，即排列顺序是唯一的

特别注意：不能省略掉胜率，胜率是有用信息。需要事先排序胜率，然后做一个离散化对应，把输入的 $y$ 转换成排名。因为这里理解错误导致卡了很久

补题 AC 代码(其一)：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll n, k, pw[mn], fac[mn], inv[mn], mod = 998244353, h[mn];
ll ans = 1, mp[mn], my[mn], mx, p1, p2, len1, len2, pr;
ll qpow(ll a, ll b = mod - 2)
{
    ll r = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
        {
            r = r * a % mod;
        }
        a = a * a % mod;
    }
    return r;
}
ll c(ll uf, ll df)
{
    return fac[df] * inv[uf] % mod * inv[df - uf] % mod;
}
struct frac
{
    ll z, m, i;
    bool operator<(const frac &p) const
    {
        return z * p.m > m * p.z;
    }
} a[mn];
signed main()
{
    sc(n), sc(k), p2 = n + 1;
    pw[0] = fac[0] = inv[0] = fac[1] = inv[1] = 1, pw[1] = 2;
    for (ll i = 2; i <= n; ++i)
    {
        pw[i] = pw[i - 1] * 2 % mod;
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = qpow(fac[i]);
    }
    for (ll i = 1; i <= n; ++i)
    {
        sc(a[i].z), sc(a[i].m), a[i].i = i;
    }
    sort(a + 1, a + 1 + n);
    for (ll i = 1; i <= n; ++i)
    {
        h[a[i].i] = i;
    }
    for (ll i = 1, op, x, y; i <= k; ++i)
    {
        sc(op), sc(x), sc(y), mp[x] = op, my[x] = h[y], mx = max(x, mx);
    }
    for (ll i = 1; i <= n; ++i)
    {
        if (mp[i] == 1)
        {
            len1 = my[i] - p1 - 1, p1 = my[i];
            len2 = i - pr - 1 - len1, p2 -= len2;
        }
        else if (mp[i] == 2)
        {
            len2 = p2 - my[i] - 1, p2 = my[i];
            len1 = i - pr - 1 - len2, p1 += len1;
        }
        if (mp[i] >= 1)
        {
            pr = i;
            ans = ans * c(len1, len1 + len2) % mod;
        }
    }
    printf("%lld", ans * pw[n - mx] % mod);
    return 0;
}

K 造梦小孩

对操作 $1$ 直接用树状数组维护即可

考虑以下核心问题：区间里等差数列值的下标都加上定值 (显然对题目中心点等效于多一次逆操作 $1$ )

将区间分块，块长为 $n_2=\sqrt n$ ，对 $len \ge n_2$ 时，操作次数不大于 $\sqrt n$ ，直接暴力转化为至多 $\sqrt n$ 次操作 $1$ ，那么总复杂度为 $O(m\sqrt n\log n)\approx 5\times10^8$ ，题给 $2$ 秒，能过

对 $len &lt; n_2$ ，将区间按倍数分块，对 $1\le j\le n_2 ,1\le i\le j$ ，分成首项为 $i$ 公差为 $j$ 的区间； 对于每次操作，首项为： $$ c=(x\bmod len)+(x\bmod len=0)\times len $$ 那么这一段区间值都加上 $y$ ，设用 $t_{i,j}$ 维护这些区间，则加到这上面去

进一步地，以 $i$ 这一坐标叠前缀和，设 $s_{i,j}=\sum_{i'=1}^it_{i',j}$ ，那么 $s_{i,j}$ 的意义为公差为 $len$ 的前 $i$ 个区间的和；每次修改 $t$ 时可以以 $O(n_2)$ 的复杂度重新计算 $s_{.,len}$ 前缀和

对于查询 $[l,r]$ ，显然可以拆解为 $[1,r]-[1,l-1]$ ，那么对子问题 $[1,x]$ ，可以枚举公差 $i$ ：

当公差为 $i$ 时，前面的 $\lfloor\dfrac xi\rfloor$ 段，即区间 $[1,i]\cup [i+1,2i]\cup\cdots\cup [\lfloor\dfrac xi\rfloor i-i-1,\lfloor\dfrac xi\rfloor i]$ 都是成周期的，单个周期的和为 $s_{i,i}$ ，所以贡献 $\lfloor\dfrac xi\rfloor s_{i,i}$ ；剩下的残区间最多有 $1$ 段，这一段到 $x\bmod i$ 为止，所以再贡献多 $s_{x\ \bmod\ i,i}$ 的值，即有，对区间 $[1,x]$ ，答案为： $$ \sum_{i=1}^{n_2}\lfloor\dfrac xi\rfloor\cdot s_{i,i}+s_{x\ \bmod\ i,i} $$ 所以查询的复杂度为 $O(\sqrt n)$ ，本题总复杂度最差为 $O(m\sqrt n\log n)$

补题代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
#define sqr 333
ll lowbit(ll &x)
{
    return x & -x;
}
ll n, m, op, x, y, len, t[mn], b[sqr][sqr], s[sqr][sqr], n2;
void update(ll i, ll v)
{
    for (; i <= n; t[i] += v, i += lowbit(i))
        ;
}
ll query(ll i)
{
    ll res = 0;
    for (; i; res += t[i], i -= lowbit(i))
        ;
    return res;
}
ll query2(ll x)
{
    ll res = 0;
    for (ll i = 1; i <= n2; ++i)
    {
        res += x / i * s[i][i] + s[x % i][i];
    }
    return res;
}
signed main()
{
    sc(n), sc(m), n2 = sqrt(n);
    while (m--)
    {
        sc(op), sc(x), sc(y);
        if (op == 1)
        {
            update(x, y);
        }
        else if (op == 2)
        {
            sc(len);
            if (len >= n2)
            {
                for (ll i = x % len + (x % len == 0 ? len : 0); i <= n; i += len)
                {
                    if (i != x)
                    {
                        update(i, y);
                    }
                }
            }
            else
            {
                ll c = x % len + (x % len == 0) * len;
                b[c][len] += y;
                for (ll i = 1; i <= n2; ++i)
                {
                    s[i][len] = s[i - 1][len] + b[i][len];
                }
                update(x, -y);
            }
        }
        else
        {
            ll ans = query(y) - query(x - 1);
            ans += query2(y) - query2(x - 1);
            printf("%lld\n", ans);
        }
    }
    return 0;
}

B 乒乓小孩

下面代码比较直观易懂，不多做额外解释了；另外本题有一个结论： $x,y$ 都大于 $11$ 时，一定有解，这是因为可以通过一次 $11: x$ 一方分数强行约为 $11$ 的倍数，两次这样的操作后双方都是 $11$ 的倍数(或 $0$ )了；一方小于 $11$ 时直接暴力枚举即可

所以在解法时，先把相差甚远安全地降到相差在 $[0,12]$ 之内，这是因为于有 $12:10$ 这样的局面，这样可以保证在两步内解决掉问题 (枚举小步)

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
ll t, x, y, rev;
vector<pair<ll, ll>> ans;
void insert(ll x, ll y)
{
    if (!rev)
    {
        ans.emplace_back(x, y);
        return;
    }
    ans.emplace_back(y, x);
}
bool check(ll x, ll y)
{
    if (x < y)
    {
        swap(x, y);
    }
    return ((x - y == 2 && x >= 11) || (x - y > 2 && x == 11)) && (x >= 0) && (y >= 0);
}
bool solve(ll x, ll y)
{
    for (ll i = 0; i <= 11; ++i)
    {
        for (ll j = 0; j <= 11; ++j)
        {
            if (check(i, j) && check(x - i, y - j))
            {
                insert(i, j), insert(x - i, y - j);
                return true;
            }
        }
    }
    return false;
}
signed main()
{
    for (sc(t); t; --t)
    {
        sc(x), sc(y), rev = 0, ans.clear();
        if (x < y)
        {
            swap(x, y), rev = 1;
        }
        while (x - y >= 13)
        {
            insert(11, 0), x -= 11;
        }
        bool res = false;
        if ((res = check(x, y)) == true)
        {
            insert(x, y);
        }
        if (!res)
        {
            res = solve(x, y);
        }
        if (!res)
        {
            printf("NO\n");
        }
        else
        {
            printf("YES\n%lld\n", ans.size());
            for (auto &i : ans)
            {
                printf("%lld %lld\n", i.first, i.second);
            }
        }
    }
    return 0;
}

H 一六三小孩

一个 80%+ 的解法：

首先打表发现绝大部分数据都可以只用加减乘，且163是质数；所以可以构造出三个数结果加减三个数结果。其中三个数结果两两加减乘有九种情况，括号内加减再乘有四种结果，所以可以用 $O(13^4)$ 枚举每个三元组及其字符串表达。

然后对每次输入，获得前三个元素的组和后三个元素的组，然后作小数量次打乱(如10次)，每次打乱后获得两个组，尝试加减这两个组，如果等于 169 就输出答案

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) cin >> x
#define repe(i, a, b) for (ll i = a; i <= b; ++i)
#define mn 15
ll v[mn][mn][mn][mn], t, hv[256], a[6];
string s[mn][mn][mn][mn];
char hc[256], b;
void f()
{
    for (ll i = 0; i < 6; ++i)
    {
        cin >> b;
        a[i] = hv[b];
    }
    for (ll i = 0; i < 10; ++i)
    {
        random_shuffle(a, a + 6);
        for (ll j = 0; j < 13; ++j)
        {
            for (ll k = 0; k < 13; ++k)
            {
                ll x = v[a[0]][a[1]][a[2]][j];
                ll y = v[a[3]][a[4]][a[5]][k];
                string &sx = s[a[0]][a[1]][a[2]][j];
                string &sy = s[a[3]][a[4]][a[5]][k];
                if (x + y == 163)
                {
                    cout << sx << '+' << sy << '\n';
                    return;
                }
                if (x - y == 163)
                {
                    cout << sx << '-' << sy << '\n';
                    return;
                }
                if (y - x == 163)
                {
                    cout << sy << '-' << sx << '\n';
                    return;
                }
                if (x * y == 163)
                {
                    cout << sx << '*' << sy << '\n';
                    return;
                }
            }
        }
    }
    cout << "1+1\n";
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    for (ll i = 2; i <= 9; ++i)
    {
        hv[i + '0'] = i;
        hc[i] = i + '0';
    }
    hc[1] = 'A', hc[10] = 'T', hc[11] = 'J', hc[12] = 'Q', hc[13] = 'K';
    hv['A'] = 1, hv['T'] = 10, hv['J'] = 11, hv['Q'] = 12, hv['K'] = 13;
    repe(i, 1, 13) repe(j, 1, 13) repe(k, 1, 13)
    {
        string ii(1, hc[i]), jj(1, hc[j]), kk(1, hc[k]);
        ll h = 0;
        v[i][j][k][h++] = i + j + k;
        v[i][j][k][h++] = i + j - k;
        v[i][j][k][h++] = i + j * k;
        v[i][j][k][h++] = i - j + k;
        v[i][j][k][h++] = i - j - k;
        v[i][j][k][h++] = i - j * k;
        v[i][j][k][h++] = i * j + k;
        v[i][j][k][h++] = i * j - k;
        v[i][j][k][h++] = i * j * k;
        v[i][j][k][h++] = (i + j) * k;
        v[i][j][k][h++] = (i - j) * k;
        v[i][j][k][h++] = i * (j + k);
        v[i][j][k][h++] = i * (j - k);
        repe(l, 0, 12) s[i][j][k][l].push_back('(');
        h = 0;
        s[i][j][k][h++] += (ii + "+" + jj + "+" + kk);
        s[i][j][k][h++] += (ii + "+" + jj + "-" + kk);
        s[i][j][k][h++] += (ii + "+" + jj + "*" + kk);
        s[i][j][k][h++] += (ii + "-" + jj + "+" + kk);
        s[i][j][k][h++] += (ii + "-" + jj + "-" + kk);
        s[i][j][k][h++] += (ii + "-" + jj + "*" + kk);
        s[i][j][k][h++] += (ii + "*" + jj + "+" + kk);
        s[i][j][k][h++] += (ii + "*" + jj + "-" + kk);
        s[i][j][k][h++] += (ii + "*" + jj + "*" + kk);
        s[i][j][k][h++] += ("(" + ii + "+" + jj + ")*" + kk);
        s[i][j][k][h++] += ("(" + ii + "-" + jj + ")*" + kk);
        s[i][j][k][h++] += (ii + "*(" + jj + "+" + kk + ")");
        s[i][j][k][h++] += (ii + "*(" + jj + "-" + kk + ")");
        repe(l, 0, 12) s[i][j][k][l].push_back(')');
    }
    for (sc(t); t; --t)
    {
        f();
    }
    return 0;
}

第六场

比赛日志：

开局I题高精度，手写WA了，咯噔一下，然后修了一下，又交又WA，然后开始气急败坏，然后在明知python会超时的情况下失去理智又交了一发。然后改代码，发现是少打了一个0，然后终于对了。开幕雷击，直接把我心态打崩了，整个人都不好了。16分钟。

然后F题，想出了规律，交，WA。然后造多几个样例，发现是1到-1不行，然后再改再交，对了。32分钟。然后E题，一秒出思路，WA掉了。然后我怀疑题意是另外的样子，然后对这写，又WA了，改了改又WA了，然后改回本来的思路再试试，修正了bugs，然后终于对了，63分钟。我的心态已经更加分崩离析了。整个一小时内不断地大声叫骂。然后D题，一开始看错题目，以为最多删两次(思维定势+眼瞎+心态不好所以状态低下了)，然后WA了一次，然后改然后对。79分钟。

最多人过的B题不会写，然后比较少人的J有点思路，然后分析出生成函数，然后得到了表达式，然后用已经过了的题目自测跑，发现TLE，阶乘逆元不好求。然后思来想去无法解决，然后查了下百度，然后会线性复杂度求了，然后就过了这道题，125分钟，第一个一发过的题目。然后B还是不会，但是少人的H一眼一个爆搜DFS博弈论，实现好了，一交一个WA，发现是测试时n=4没改回来，一改瞬间A掉了，154分钟。然后B题，终于有点思路了，但是实现出了问题，还有就是细节问题了，然后改来改去，重写了三版代码，终于过了，一发，236分钟。终于成功反超了，但是排名还是不算特别高。后来剩下的题，G题没思路，可能是并查集我猜，然后A题也没思路，C题没细看，A读懂之后猛然想可不可能是字符串卷积，但是不会计数，然后剩下时间就都没进展了。最后排名109……

I A+B问题

高精度裸题，能实现就行

赛时AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 200010
ll k, as, bs, v1, v2;
char a[mn], b[mn], c[mn];
ll get(char x)
{
    if (isdigit(x))
    {
        return x - '0';
    }
    return 0;
}
signed main()
{
    sc(k), scanf("%s%s", a + 1, b + 1);
    as = strlen(a + 1);
    bs = strlen(b + 1);
    reverse(a + 1, a + 1 + as);
    reverse(b + 1, b + 1 + bs);
    // puts(a + 1);
    // puts(b + 1);
    for (ll i = 1; i < 200003; ++i)
    {
        v1 += get(a[i]) + get(b[i]);
        v2 = v1 / k;
        v1 = v1 % k;
        c[i] = v1 + '0';
        v1 = v2;
        v2 = 0;
    }
    ll ed = 0;
    for (ll i = 200005; i >= 1; --i)
    {
        if (isdigit(c[i]) && c[i] != '0')
        {
            ed = i;
            break;
        }
    }
    // printf("%lld %lld\n",ed,c[ed]);
    for (ll i = ed; i >= 1; --i)
    {
        putchar(c[i]);
    }
    return 0;
}

题解思路：转置，然后先不处理进位地逐个加，然后逐个处理进位

int main()
{
  sc(k);
  sc(a+1);sc(b+1);
  int n=strlen(a+1),m=strlen(b+1);
  reverse(a+1,a+1+n);
  reverse(b+1,b+1+m);
  rep(i,1,max(n,m))
  {
    if(i<=n) c[i]+=a[i]-'0';
    if(i<=m) c[i]+=b[i]-'0';
  }
  n=max(n,m);
  rep(i,1,n)
  {
    c[i+1]+=c[i]/k;
    c[i]%=k;
    if(c[n+1]) n++;
  }
  for(int i=n;i>=1;i--) putchar(c[i]+'0');
}

F +-串

每次更改可以让原式+2或-2，先计算原式结果，然后让其不断往0靠拢，因为必须要用完，如果刚好到0且多出机会还需要再加大一次，到1(或-1)，需要变成-1(或1)

处理上可以直接看绝对值，先靠拢到0或1 (如果够)，然后再处理残余并对1(+2=3)特判为1

赛时AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll t, k, n;
char s[mn];
signed main()
{
    sc(t);
    while (t--)
    {
        scanf("%s", s + 1);
        sc(k);
        ll cp = 0, cn = 0;
        n = strlen(s + 1);
        for (ll i = 1; i <= n; ++i)
        {
            if (s[i] == '+')
            {
                cp++;
            }
            else
            {
                cn++;
            }
        }
        ll v = cp - cn;
        // printf("%lld\n", v);
        v = abs(v);
        ll t = abs(v) / 2;
        if (t >= k)
        {
            printf("%lld\n", v - 2 * k);
        }
        else
        {
            v %= 2;
            k -= t;
            if (k % 2 == 1)
            {
                v += 2;
            }
            if (v > 2)
            {
                v -= 2;
            }
            printf("%lld\n", v);
        }
    }
    return 0;
}

题解思路类似

E 骑士

题意：对每个骑士，求使得除自己之外的最高攻击下能够存活(剩血>0)所额外需要的血量，输出需求血量和

个人解法：数据范围允许，可以直接结构体排序，若第一名不是自己，用第一名打自己；否则用第二名打自己

赛时AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 200010
ll t, n;
struct knight
{
    ll a, h, i;
    bool operator<(const knight &x) const { return a > x.a; }
} k[mn];
signed main()
{
    sc(t);
    while (t--)
    {
        sc(n);
        for (ll i = 1, a, b, h; i <= n; ++i)
        {
            sc(a), sc(b), sc(h);
            k[i].i = i;
            k[i].a = a;
            k[i].h = b + h;
        }
        sort(k + 1, k + 1 + n);
        ll ans = 0;
        for (ll i = 1; i <= n; ++i)
        {
            ll mx = k[i].i == k[1].i ? k[2].a : k[1].a;
            ans += max(mx - k[i].h + 1, 0LL);
            // printf("%lld %lld ", k[i].i, mx);
            // printf("<%lld\n", ans);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

题解思路：维护前缀max和后缀max，对每个骑士，求他前面的前缀max和他后面的后缀max更大者跟自己的差值，题解代码：

const int N=2e5+5,mod=998244353;
int n,a[N],b[N],h[N];
int main()
{
  int t;sc(t);
  int sum=0;
  while(t--)
  {
    sc(n);
    sum+=n;
    rep(i,1,n) 
    vector<int>pre(n+2),bk(n+1);
    rep(i,1,n) pre[i]=max(pre[i-1],a[i]);
    nep(i,n,1) bk[i]=max(bk[i+1],a[i]);
    ll ans=0;
    rep(i,1,n)
    {
      ll s=1ll*max(pre[i-1],bk[i+1])-b[i]+1;
      ans+=max(0ll,s-h[i]);
    }
    out(ans);
  }
}

D 删除子序列

个人思路：贪心，一有就马上匹配，同时开尽可能多的匹配线程。由于 t 互不相同，故遍历 s ，如果它为 t 的第 j 个字符，且第 j-1 个字符已匹配次数大于第 j 个字符匹配次数，那么可以匹配第 j 个字符；思路类似 SCNUOJ 的一道题(匹配子序列)

复杂度 $O(nm)$

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1000010
ll ts, n, m;
char s[mn], t[30];
ll cnt[30];
signed main()
{
    sc(ts);
    while (ts--)
    {
        sc(n), sc(m);
        scanf("%s%s", s + 1, t + 1);
        memset(cnt, 0, sizeof cnt);
        cnt[0] = n + 1;
        for (ll i = 1; i <= n; ++i)
        {
            for (ll j = 1; j <= m; ++j)
            {
                if (s[i] == t[j])
                {
                    if (cnt[j] < cnt[j - 1])
                    {
                        ++cnt[j];
                    }
                    break;
                }
            }
        }
        ll ans = n + 1;
        for (ll i = 1; i <= m; ++i)
        {
            ans = min(ans, cnt[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

J 牛妹的数学难题

使用生成函数化简原题，设原式有 $a_1$ 个 $1$ , $a_2$ 个 $2$ ，那么所求为下面表达式的 $x^k$ 的系数： $$ (1+0x)^{a_0}(1+x)^{a_1}(1+2x)^{a_2} $$ 即分别 $a_0$ 次选与不选(不影响结果)， $a_1$ 次选与不选， $a_2$ 次选与不选

由二项式定理化简，原式为： $$ \sum_{y=\max(0,k-a_1)}^{\max(0,a_2)}C_{a_1}^{k-y}C_{a_2}^y2^y $$ 需要在 $O(1)$ 求出组合数，使用阶乘表达式，则需要在 $O(1)$ 求出逆元。

记 $x!$ 的逆元为 $(x!)^{-1}$ ，则 $(x-1)!\cdot x=x!$ ，而 $(x!)(x!)^{-1}=1$ , $(x-1)!((x-1)!)^{-1}=1$ ，联立得：$((x-1)!)^{-1}=x\cdot (x!)^{-1}$ ，所以可以线性递推

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 10000010
ll mod = 998244353, n, k, a1, a2, modp2 = mod - 2, ans;
ll pw[mn], fac[mn];
ll inv[mn];
ll qpow(ll a, ll b)
{
    ll res = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
    }
    return res;
}
ll c(ll uf, ll df)
{
    // printf("%lld %lld %lld\n", fac[df], inv[uf], inv[df - uf]);
    return fac[df] * inv[uf] % mod * inv[df - uf] % mod;
}
signed main()
{
    sc(n), sc(k);
    for (ll i = 1, v; i <= n; ++i)
    {
        sc(v);
        a1 += (v == 1);
        a2 += (v == 2);
    }
 
    pw[0] = fac[0] = 1; // = inv[0] = 1;
    inv[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        pw[i] = pw[i - 1] * 2 % mod;
    }
    for (ll i = 1; i <= n; ++i)
    {
        fac[i] = fac[i - 1] * i % mod;
        // inv[i] = qpow(fac[i], modp2);
    }
    inv[n] = qpow(fac[n], modp2);
    for (ll i = n - 1; i >= 1; --i)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod;
        // printf("| %lld %lld\n", inv[i], inv[i + 1]);
    }
    // printf("%lld", c(2, 5));
    for (ll y = max(0LL, k - a1); y <= a2; ++y)
    {
        if (k - y < 0)
        {
            continue;
        }
        ans = ans + c(k - y, a1) * c(y, a2) % mod * pw[y] % mod;
        ans %= mod;
        // printf("%lld %lld\n", y, ans);
    }
    printf("%lld", ans);
    return 0;
}

H 寒冬信使2

直接二进制枚举并记忆化搜索所有可能的结果，然后再询问即可

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
map<string, ll> m;
ll dfs(string &now)
{
    // cout << now << '\n';
    if (m[now] != 0)
    {
        return m[now];
    }
    ll whites = 0;
    bool haslose = false; //下一局能赢吗
    // vector<ll> ws;
    for (ll i = 0, ie = now.size(); i < ie; ++i)
    {
        if (now[i] == 'w')
        {
            ++whites;
            string nw = now;
            nw[i] = 'b';
            if (i > 0)
            {
                // for (ll &j : ws)
                for (ll j = 0; j < i; ++j)
                {
                    string nw2 = nw;
                    nw2[j] = nw[j] == 'w' ? 'b' : 'w';
                    haslose |= (2 == dfs(nw2));
                }
            }
            else
            {
                haslose |= (2 == dfs(nw));
            }
            // haswin |= (1 == dfs(nw));
            // ws.emplace_back(i);
        }
    }
    ll res = 0;
    if (!whites)
    {
        res = 2; // lose
    }
    else
    {
        res = haslose ? 1 : 2;
    }
    m[now] = res;
    return res;
}
signed main()
{
    for (ll h = 1; h <= 10; ++h)
    {
        for (ll i = 0, ie = 1 << h; i < ie; ++i)
        {
            string s;
            s.resize(h);
            for (ll j = 0, v = i; j < h; ++j, v >>= 1)
            {
                s[j] = (v & 1) ? 'w' : 'b';
            }
            dfs(s);
            // cout << s << ' ' << m[s] << ' ' << s.size() << '\n';
        }
    }
    // printf("Done\n");
    ll t, n;
    cin >> t;
    while (t--)
    {
        string c;
        cin >> n >> c;
        // cout << c << ':';
        // printf("%lld\n", m[c]);
        if (m[c] == 2)
        {
            printf("No\n");
        }
        else
        {
            printf("Yes\n");
        }
    }
    return 0;
}

题解用 SG 函数来做，且题解有结论：操作 1 恒让结果值变小(使得可以线性枚举)，题解代码：

using namespace std;
const int N=15,mod=998244353;
int n,sg[1<<10];
char s[N];
bitset<105>vis;
int main()
  for(int i=1;i<1<<10;i++)
  {
    vis.reset();
    for(int j=0;j<10;j++)
      if(i>>j&1)
      {
        if(j==0) vis[sg[i^(1<<j)]]=true;
        else
        {
          for(int k=0;k<j;k++) vis[sg[i^(1<<j)^(1<<k)]]=true;
        }
      }
      while(vis[sg[i]]) sg[i]++;
  }
  int t;scanf("%d",&t);
  while(t--)
  {
    sc(n);
    sc(s+1);
    int st=0;
    for(int i=1;i<=n;i++)
      if(s[i]=='w') st|=1<<(i-1);
    printf(sg[st]?"Yes\n":"No\n");
  }
}

B 价值序列

可以发现对严格单调递增或递减的一段，为了使得结果不变，首尾不可以删，中间的所有值可删可不删(即乘以 $2$ )；对相同值的连续长为 $m$ 的一段，若在首尾，那么至少要留一个，即方案数为 $2^{m}-1$

实现上，可以先把相同的一段全部合在一起，化简原数列为一个加权权重，然后找到所有的拐点，两拐点之间都可以删，拐点内部都可以删

赛时 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 100010
ll t, n, a[mn], mod = 998244353, b[mn], m, pw[mn], c[mn], v[mn], lf[mn], rf[mn];
signed main()
{
    pw[0] = 1;
    for (ll i = 1; i < mn; ++i)
    {
        pw[i] = pw[i - 1] * 2 % mod;
    }
    sc(t);
    while (t--)
    {
        sc(n);
        ll ans = 1;
        for (ll i = 1; i <= n; ++i)
        {
            sc(a[i]);
            v[i] = 0;
        }
        if (n == 1)
        {
            printf("1\n");
            continue;
        }
 
        b[1] = a[1], c[1] = 1, m = 1; //分块
        lf[1] = 1;
        for (ll i = 2; i <= n; ++i)
        {
            if (a[i] == a[i - 1])
            {
                ++c[m];
            }
            else
            {
                rf[m] = i - 1;
                ++m;
                lf[m] = i;
                b[m] = a[i];
                c[m] = 1;
            }
        }
        rf[m] = n;
        vector<ll> d;
        d.emplace_back(1);
        for (ll i = 2; i < m; ++i)
        {
            if ((b[i] < b[i - 1] && b[i] < b[i + 1]) || (b[i] > b[i - 1] && b[i] > b[i + 1]))
            {
                d.emplace_back(i);
                v[i] = 1;
            }
        }
        d.emplace_back(m);
        v[1] = v[m] = 1;
        for (ll i = 1, ie = d.size(); i < ie; ++i)
        {
            ll len = lf[d[i]] - rf[d[i - 1]] - 1;
            // printf("(%lld)", len);
            ans = ans * max(1LL, pw[len]) % mod;
        }
        // printf("%lld::", ans);
        for (ll i = 1; i <= m; ++i)
        {
            if (v[i] != 1)
            {
                continue;
            }
            // printf("%lld(%lld %lld) ", b[i], c[i], pw[c[i]] - 1);
            // printf("<%lld %lld>\n", lf[i], rf[i]);
            ans = ans * (pw[c[i]] - 1 + mod) % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

G 迷宫2

从起点开始拓展到终点，若本来可以走，那么代价是 0 ，新状态可以直接原地放回队首(使得队列必然按代价递增)，否则，拓展时按照拓展方向修改当前格，加入队尾，并且保存下一个格子是怎么到达的(可以四方向减法还原路径)，并且标记格子已经访问过(因为 BFS 的特性，先访问到的点必然是子图内最优的)，最后沿着终点一路逆回去，发现需要代价时输出即可

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1024
ll t, n, m, dp[mn][mn], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
char c[mn][mn], rh[] = "UDLR";
ll pr[mn][mn], h[mn], vis[mn][mn];
signed main()
{
    h['U'] = 0, h['D'] = 1, h['L'] = 2, h['R'] = 3;
    sc(t);
    while (t--)
    {
        sc(n), sc(m);
        for (ll i = 1; i <= n; ++i)
        {
            scanf("%s", c[i] + 1);
        }
        for (ll i = 1; i <= n; ++i)
        {
            for (ll j = 1; j <= m; ++j)
            {
                dp[i][j] = 0x7ffffff, vis[i][j] = 0;
            }
        }
        deque<pair<ll, ll>> q;
        q.push_front({1, 1});
        dp[1][1] = 0;
        while (!q.empty())
        {
            auto t = q.front();
            q.pop_front();
            ll ax = t.first, ay = t.second;
            // printf("%lld %lld %lld %c\n", ax, ay, dp[ax][ay], rh[pr[ax][ay]]);
            // if (ax == n && ay == m)
            // {
            //     break;
            // } 这个要不要都行，要了因为跑这个if反而更慢了一些些
            if (vis[ax][ay])
            {
                continue;
            }
            vis[ax][ay] = 1;
            for (ll i = 0; i < 4; ++i)
            {
                ll bx = ax + dx[i], by = ay + dy[i];
                if (bx < 1 || bx > n || by < 1 || by > m)
                {
                    continue;
                }
                ll v = dp[ax][ay] + (rh[i] != c[ax][ay]);
                // printf("%lld %lld(%lld %lld) %lld %c %c %lld %lld\n", ax, ay, bx, by, i, rh[i], c[ax][ay], v, dp[bx][by]);
                if (v < dp[bx][by])
                {
                    dp[bx][by] = v;
                    pr[bx][by] = i;
                    // printf("?%lld %lld\n", dp[bx][by], dp[ax][ay]);
                    if (dp[bx][by] == dp[ax][ay])
                    {
                        // printf("<%lld %lld %c\n", bx, by, rh[i]);
                        q.push_front({bx, by});
                    }
                    else
                    {
                        q.push_back({bx, by});
                    }
                }
            }
        }
        printf("%lld\n", dp[n][m]);
        for (ll x = n, y = m; !(x == 1 && y == 1);)
        {
            ll nx = x - dx[pr[x][y]];
            ll ny = y - dy[pr[x][y]];
            if (dp[nx][ny] != dp[x][y])
            {
                printf("%lld %lld %c\n", nx, ny, rh[pr[x][y]]);
            }
            x = nx, y = ny;
        }
    }
    return 0;
}

A 回文大师

解法一：字符串哈希+二分+差分

设原串为 a ，反串为 b，枚举 b 的子串左端点，二分右端点，找到与 a 匹配的最长前缀，这一段值都可以作 i ，其 j 就是 b 这个子串起始点，将这一段 a 部分区间用差分加 1

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1000010
ll n, a[mn], b[mn], s[mn];
ull ah[mn], bh[mn], p = 1e9 + 7, pw[mn];
signed main()
{
    sc(n);
    for (ll i = 1, j = n; i <= n; ++i, --j)
    {
        sc(a[i]);
        b[j] = a[i];
    }
    pw[0] = 1;
    for (ll i = 1; i <= n; ++i)
    {
        pw[i] = pw[i - 1] * p;
        ah[i] = ah[i - 1] * p + a[i];
        bh[i] = bh[i - 1] * p + b[i];
    }
    for (ll i = 1; i <= n; ++i)
    {
        ll lf = i, rf = n, cf, ans = 0;
        while (lf <= rf)
        {
            ll cf = (lf + rf) >> 1;
            ll av = ah[cf - i + 1], bv = bh[cf] - bh[i - 1] * pw[cf - i + 1];
            if (av == bv)
            {
                ans = max(ans, cf);
                lf = cf + 1;
            }
            else
            {
                rf = cf - 1;
            }
        }
        // printf("<%lld\n", max(0LL, ans - i + 1));
        s[0]++;
        s[max(0LL, ans - i + 2)]--;
    }
    for (ll i = 1; i <= n; ++i)
    {
        s[i] += s[i - 1];
        printf("%lld ", s[i]);
    }
    return 0;
}

解法二：KMP树前缀和

跑 KMP 找以 i 为反串起点的最长相等(需要动手模拟可以理解下面的过程)，最长相等的其所有子串对应相等，以 next 数组建树，表现为其可以一路向根走，所以最后叠一个 KMP 树上前缀和即可；难以理解的话画图造例子示意一下

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 1000010
ll n, kmp[mn], a[mn], b[mn], ans[mn];
signed main()
{
    sc(n);
    for (ll i = 1, j = n; i <= n; ++i, --j)
    {
        sc(a[i]), b[j] = a[i];
    }
    for (ll i = 2, j = 0; i <= n; ++i)
    {
        while (j && a[i] != a[j + 1])
        {
            j = kmp[j];
        }
        if (a[j + 1] == a[i])
        {
            ++j;
        }
        kmp[i] = j;
        // printf("%lld ", kmp[i]);
    }
    kmp[0] = -1;
    // printf("\n");
    for (ll i = 1, j = 0; i <= n; ++i)
    {
        while (j != -1 && a[j + 1] != b[i])
        {
            j = kmp[j];
        }
        ++j, ++ans[j];
        // printf("%lld ", j);
        // a[1->j]和a[i->i-(j-1)]构成回文
    }
    // printf("\n");
    for (ll i = n; i >= 1; --i)
    {
        ans[kmp[i]] += ans[i];
    }
    for (ll i = 1; i <= n; ++i)
    {
        printf("%lld ", ans[i]);
    }
    return 0;
}

C 数组划分

解法一：单调栈+二分

解法二：单调栈+并查集

对原数组叠前缀和，根据贪心，每一块都是前缀和单调不减区域；用严格单调递增栈逆序遍历数组，那么当前下标时单调栈的元素数就是美丽子数组数。每个询问保证按 pair 顺序排序。可以二分单调栈，对每个左端点，找到第一个大于等于 r 的位置，子数组数为左端点单调栈元素数减该位置元素数+1。

参考代码：(用户 yjsp114514 代码)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 998244353
 
int i,j,k,n,m,t,s[5005000],nxt[5005000],it,l[5005000],r[5005000],res[5005000],ql,qr,md,ans,cur;
ll a[5005000];
 
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
    if(head==tail) {
        int l=fread(buffer,1,BufferSize,stdin);
        tail=(head=buffer)+l;
    }
    return *head++;
}
inline int rd() {
    int x=0,f=1;char c=Getchar();
    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
    return x*f;
}
void print(int x)
{
    if(x>9) print(x/10);
    putchar(x%10|'0');
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    t=rd();
    while(t--){
        n=rd();m=rd();
        it=0;
        for(i=1;i<=n;i++){
            a[i]=rd();
            a[i]+=a[i-1];
            s[++it]=i;
            while(it&&a[i]<a[s[it]-1]){
                nxt[s[it]]=i+1;it--;
            }
            //for(j=1;j<=it;j++){cout<<s[j]<<' ';}cout<<endl;
        }
        while(it){
            nxt[s[it]]=n+1;it--;
        }
        //for(i=1;i<=n;i++){printf("a%d %d\n",i,nxt[i]);}
        for(i=1;i<=m;i++){
            l[i]=rd();r[i]=rd();
        }
        cur=n+1;
        for(i=m;i>=1;i--){
            while(cur>l[i]){
                cur--;
                while(it&&s[it]<=nxt[cur]){
                    it--;
                }
                s[++it]=nxt[cur];
                //printf("NMSL%d\n",cur);for(j=1;j<=it;j++){cout<<s[j]<<' ';}cout<<endl;
            }
            //printf("a%d %d\n",l[i],r[i]);
            ql=1;qr=it+1;md=0;ans=11451419;
            while(ql<=qr){
                md=(ql+qr)/2;
                if(s[it+1-md]>r[i]){
                    ans=min(ans,md);qr=md-1;
                }
                else{
                    ql=md+1;
                }
            }
            res[i]=ans;
        }
        for(i=1;i<=m;i++){
            //cout<<res[i]<<'\n';
            print(res[i]);putchar('\n');
        }
    }
}

也可以用并查集，对已经出栈的元素，指向让它出栈的这个元素。每次找到 r-1 的父亲即可。

补题 AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define sc(x) scanf("%lld", &x)
#define mn 5000010
ll t, n, q, a[mn], x, y;
ll lf[mn], rf[mn], fa[mn], s[mn], rk[mn], ans[mn];
ll findf(ll x)
{
    while (x != fa[x])
    {
        x = fa[x] = fa[fa[x]];
    }
    return x;
}
const int BufferSize = 1 << 16;
char buffer[BufferSize], *head, *tail;
inline char Getchar()
{
    if (head == tail)
    {
        int l = fread(buffer, 1, BufferSize, stdin);
        tail = (head = buffer) + l;
    }
    return *head++;
}
inline int read()
{
    int x = 0, f = 1;
    char c = Getchar();
    for (; !isdigit(c); c = Getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = Getchar())
        x = x * 10 + c - '0';
    return x * f;
}
void print(int x)
{
    if (x > 9)
        print(x / 10);
    putchar(x % 10 | '0');
}
signed main()
{
    for (t = read(); t; --t)
    {
        n = read(), q = read();
        for (ll i = 1; i <= n; ++i)
        {
            a[i] = read(), a[i] += a[i - 1];
            fa[i] = i;
        }
        for (ll i = 1; i <= q; ++i)
        {
            lf[i] = read(), rf[i] = read();
            --lf[i], --rf[i];
        }
        ll top = 0;
        for (ll i = n, j = q; i >= 0; --i)
        {
            while (top && a[s[top]] >= a[i])
            {
                fa[s[top]] = i;
                --top;
            }
            s[++top] = i;
            rk[i] = top;
            while (j >= 1 && lf[j] == i)
            {
                ans[j] = top - rk[findf(rf[j])] + 1;
                --j;
            }
        }
        for (ll i = 1; i <= q; ++i)
        {
            print(ans[i]), putchar('\n');
        }
    }
    return 0;
}