【解题报告】2022牛客寒假算法基础集训营1

• 2022牛客寒假算法基础集训营1 由于题目难度有些偏基础，太基础的今后就不细讲了。 话不多说，开冲！

• 由于字符超过 $20w20w$ 上限了，删了一些简单的内容，可以在CSDN端查看完整内容

A：九小时九个人九扇门

题意 | 简单

• 经典 999 游戏，之前就看过极限脱出系列的攻略全流程了...(咳咳 数字根：一个数字的各个位数字和，如果该和不是一位数，继续操作，直到一位数字，就是这个数字的数字根 比如 87->(8+7=15)15->(1+5=6)6 所以 87的数字根为6
• 有 $nn$ 个人，给定每个人的数字 $a_{i}a\_i$ 选出一些人的集合，求集合的数字根为 $1\sim 91\backslash sim\; 9$ 的集合选法，取模 $998244353998244353$ 集合的数字根：为集合的所有元素的和的数字根 $1\le n\le 10^{5}1\backslash le\; n\backslash le\; 10^5$ $1\le a_i\le 10^{9}1\backslash le\; a\_i\backslash le\; 10^9$

思路 | 数学 + dp

• 容易猜想或者得到，设 $f(x)f(x)$ 表示 $xx$ 的数字根，那么有：

还有一些性质：

这些都可以由上面 $(1)(1)$ 式推导出来。 如果让我证明的话，感觉不大好证，我会用反证法，先假设 $(1)(1)$ 式成立 然后我能得到 $f(x+y)=f(f(x)+f(y))f(x+y)=f(f(x)+f(y))$ 也是同时成立的，并且这个和数字根的定义相同 所以原 $(1)(1)$ 成立

• 不管怎么样，我们可以利用这个 $f(x+y)=f(f(x)+f(y))f(x+y)=f(f(x)+f(y))$ 设 $dp[i][x]dp[i][x]$ 表示考虑完前 $ii$ 个数字，数字根为 $x(x\le 9)x(x\backslash le9)$ 的方案数，然后转移即可。 随便计算数字根，用定义法 $O(1)O(1)$ 还是递归法 $O(\log )O(\backslash log\; )$ 都行

代码

• 时间复杂度：$O(n(10+O(\mathrm{算}\mathrm{一}\mathrm{个}\mathrm{数}\mathrm{字}\mathrm{根})))O(n(10+O(算一个数字根)))$ 空间复杂度：滚动数组了一下，$\mathrm{\Theta }(20)\backslash Theta(20)$

const int st = 0;

int cnt[15][2];

int cal(int a){		// 你当然可以写 return (x-1) % 9 + 1 更快速得到数字根
    if(a < 10)return a;
    return cal(cal(a / 10) + a % 10);
}

int main()
{
    cnt[0][st] = 1;
    int n;cin >> n;
    for(int i = 1;i <= n;++i){
        int t;cin >> t;
        for(int j = 0;j < 10;++j){
            int aim = cal(j + t);
            cnt[aim][st^1] = (cnt[aim][st^1] + cnt[j][st]) % MOD;
        }
        for(int j = 0;j < 10;++j){
            cnt[j][st] = (cnt[j][st] + cnt[j][st^1]) % MOD;
            cnt[j][st^1] = 0;
        }
    }

    for(int i = 1;i < 10;++i){
        cout << cnt[i][st] << ' ';
    }
    return 0;
}

B：炸鸡块君与FIFA22

题意 | 中等

• 给定一个长度为 $nn$ 的字符串 $SS$ ，和 $qq$ 个询问 字符串只包含三种字符：
  • $WW$ 表示赢，加一分。
  • $LL$ 表示输，扣一分。如果扣分前分数是三的倍数，则不扣分
  • $DD$ 表示平局，分数不变。
• 每组询问给定 $l,r,sl,r,s$ ，表示初始分数为 $ss$ ，经历 $S[l:r]S[l:r]$ 之后的分数为多少
• $1\le n,q\le 2\times 10^{5}1\backslash le\; n,q\backslash le\; 2\backslash times\; 10^5$ $1\le l\le r\le n1\backslash le\; l\backslash le\; r\backslash le\; n$ $0\le s\le 10^{9}0\backslash le\; s\backslash le10^9$

思路 | 数据结构 + 简单同余

• 容易想到，快速计算分数肯定要用能分治的数据结构。我这里使用倍增表。 倍增表就是：

它比线段树要内存小，更快，但是无法修改操作。同样要求操作满足结合律。

• 这里想到，分数是三的倍数扣分不记录，则按分数取余 $33$ 分别记录，就变成 $dp[i][j][0\mathrm{/}1\mathrm{/}2]dp[i][j][0/1/2]$ 想好转移。

• 容易得到整段的分数等于左边段的分数加上右边段的分数 这个时候 $k^{\mathrm{\prime }}k\text{'}$ 变成了什么呢？当然就是 $k^{\mathrm{\prime }}=(k+dp[i][j-1][k]\mathrm{\%}+3)\mathrm{\%}3k\text{'}=(k+dp[i][j-1][k]\backslash \%+3)\backslash \%3$，注意分数可能有负，所以要这么处理。
• 然后是查询。查询就是把 $[l:r][l:r]$ 分成不同个 $2^{p}2^p$ 的段，来让查询复杂度达到 $O(\log )O(\backslash log)$ 级别，具体可以看代码

代码

• 时间复杂度：$O((n+q)\log n)O((n+q)\backslash log\; n)$

int dp[MAX][22][3];
int p2[22];		// 预处理 2^p
int main()
{
    p2[0] = 1;
    for(int i = 1;i <= 20;++i)
        p2[i] = p2[i-1] * 2;

    int n,q;cin >> n >> q;
    string ss;
    cin >> ss;
    ss = " " + ss;
    for(int i = 1;i <= n;++i){
        for(int j = 0;j < 3;++j){			// 计算 dp 初值
            dp[i][0][j] = 0;
            if(ss[i] == 'W')dp[i][0][j]++;
            else if(ss[i] == 'L' && j != 0)dp[i][0][j]--;
        }
    }

    for(int i = 1;i <= 20;++i)			// 预处理转移 dp
    for(int p = 1;p <= n;++p){
        if(p + p2[i] - 1 > n)break;
        for(int j = 0;j < 3;++j){
            int f1 = dp[p][i-1][j];
            int f2 = dp[p+p2[i-1]][i-1][((j+f1)%3+3)%3];
            dp[p][i][j] = f1 + f2;
        }
    }

    for(int i = 1;i <= q;++i){
        int l,r,s;
        cin >> l >> r >> s;
        int delta = 0;
        int now = s % 3;
        for(int j = 20;j >= 0;--j){			// 查询
            if(l + p2[j] - 1 <= r){
                delta += dp[l][j][now];
                now = (now + dp[l][j][now] % 3 + 3) % 3;
                l += p2[j];
            }
        }
        cout << s + delta << '\n';
    }
    return 0;
}

D：牛牛做数论

题意 | 中等

• $H(x)=\frac{\phi (x)}{x}H(x)=\backslash frac\{\backslash varphi(x)\}\{x\}$

思路 | 数论

• 欧拉函数是积性函数，可以写成 $\phi (x)=x\prod ({\displaystyle \frac{p_i-1}{p_i}})\backslash varphi(x)=x\backslash prod\; (\backslash cfrac\{p\_i-1\}\{p\_i\})$ 所以得到 $H(x)=\prod ({\displaystyle \frac{p_i-1}{p_i}})H(x)=\backslash prod\; (\backslash cfrac\{p\_i-1\}\{p\_i\})$
• 那么最大值，就是 $[2,n][2,n]$ 中最大的质数取到的值 最小值，就是范围之内最多、尽量小的质数的乘积，暴力检查前 $1010$ 个质数即可。

E：炸鸡块君的高中回忆

• 签到题 先特判，再做下述操作： 操作1：花两步，校园里人少掉 $m-1m-1$。 操作2：花一步，校园里人少掉 $mm$，但是只能做一次。
• 设操作1 做了 $kk$ 次，答案就是最小的 $kk$ ，满足：

答案就是 $2k+12k+1$

F：中位数切分

题意 | 中等

• 把长度为 $nn$ 的序列划分成最多份，满足每份的中位数 $\ge m\backslash ge\; m$ 。若长度为偶数，中位数取中间的左边那个数字。
• $1\le n\le 10^{5}1\backslash le\; n\backslash le\; 10^5$ $1\le a_i,m\le 10^{9}1\backslash le\; a\_i,m\backslash le\; 10^9$

思路 | 数据结构 + dp

• 划分满足无后效性，想到 $dpdp$ ，则设：$dp[i]dp[i]$ 表示考虑玩前 $ii$ 个元素，最多划分的段数
• 看到中位数，想到把元素变化。若 $a_i\ge ma\_i\backslash ge\; m$ ，即为 $11$，否则记为 $-1-1$ 这样，序列的中位数 $\ge m\backslash ge\; m$ 转化为序列的和 $\ge 1\backslash ge\; 1$
• 想 $dpdp$ 的转移，如下：

• 元素和，想到前缀和。我们用 $prepre$ 数组记录前缀和，于是后面就变成了：

由于 $pre[i]pre[i]$ 是固定的，我们移动元素位置，得到：

• 于是，右边就变成了求区间最小值，线段树搞定。 最后答案当然就是 $dp[n]dp[n]$
• 注意到，$prepre$ 数组是可以为负数的，所以我们每个位置的元素增加一个增量 $O=1e5+2O=1e5+2$ 即可。 还注意到，有些位置的分隔是不可行的，因为求的是区间最大值，用 $-1-1$ 做初始化。

代码

• 时间复杂度：$O(n\log n)O(n\backslash log\; n)$

#define ls (p<<1)
#define rs (p<<1|1)
#define md ((l+r)>>1)

const int O = 1e5+2;
const int U = 2e5+4;
int tree[MAX*4];
inline void push_up(int p){
    tree[p] = max(tree[ls],tree[rs]);
}
inline void build(int p,int l,int r){
    if(l == r){
        tree[p] = -1;
        return;
    }
    build(ls,l,md);
    build(rs,md+1,r);
    push_up(p);
}
inline void add(int p,int l,int r,int k){
    tree[p] = k;
}
inline void update(int p,int l,int r,int ux,int uy,int k){
    if(ux <= l && uy >= r){
        add(p,l,r,k);
        return;
    }
    if(ux <= md)update(ls,l,md,ux,uy,k);
    if(uy >  md)update(rs,md+1,r,ux,uy,k);
    push_up(p);
}
inline int query(int p,int l,int r,int qx,int qy){
    int res = -1;
    if(qx <= l && r <= qy)return tree[p];
    if(qx <= md)res = max(res,query(ls,l,md,qx,qy));
    if(qy >  md)res = max(res,query(rs,md+1,r,qx,qy));
    return res;
}

int pre[100050];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;++i){
            int t;scanf("%d",&t);
            if(t >= m)t = 1;
            else t = -1;
            pre[i] = pre[i-1] + t;
        }
        build(1,1,U);
        update(1,1,U,O,O,0);
        int ans = -1;
        for(int i = 1;i <= n;++i){
            int dpj = query(1,1,U,1,O + pre[i] - 1);
            if(dpj != -1){
                int dpi = dpj + 1;
                if(i == n)ans = dpi;
                update(1,1,U,O + pre[i],O + pre[i],dpi);
            }
        }
        printf("%d\n",ans);
    }

    return 0;
}

G：ACM is all you need

题意 | 中偏难

• 给定一维函数上 $nn$ 个整数点 $f_{i}f\_i$ 定义 $localminlocal\backslash \; min$ 表示满足
• 变化，表示让所有的值 $f_{i}f\_i$ 变成 $f_i=\mathrm{\mid }{f}_i-b\mathrm{\mid }+bf\_i=|f\_i-b|+b$，其中 $bb$ 是自己选择的一个整数 求经过一次变化，$localminlocal\backslash \; min$ 的最小值是多少
• $\sum n\le 10^6\backslash sum\; n\backslash le\; 10^6$ $1\le f_i\le 10^{9}1\backslash le\; f\_i\backslash le\; 10^9$

思路 | 思维 + 差分

• 首先，每个点都加 $bb$ 当然不影响 $localminlocal\backslash \; min$ ，我们把变化看做 $f_i=\mathrm{\mid }{f}_i-b\mathrm{\mid }f\_i=|f\_i-b|$ 看到几何意义，就是这个函数上的每个点距离 $y=by=b$ 的直线的距离。 我们可以当做把这个函数沿着某个 $yy$ 向上翻折，但是这样对整体答案不好考虑。
• 我们只考虑单独一个位置。 由于 $localminlocal\backslash \; min$ 只和当前位置与前后两个相邻位置有影响。 且仔细分析，我们只用关注增减情况即可，只有四种抽象情况：
• 因为如果存在 $f_i=f_{i-1}f\_i=f\_\{i-1\}$ 或者 $f_i=f_{i+1}f\_i=f\_\{i+1\}$，这个点变化前和变化后当然都不会是 $localminlocal\backslash \; min$ 接下来，我们分析当 $yy$ 处于什么情况下，$localminlocal\backslash \; min$ 的变化值 我们记录成一个段 $[L,R,D][L,R,D]$ ，表示 $y\in [L,R]y\backslash in\; [L,R]$ 时候，$localminlocal\backslash \; min$ 的变化值为 $DD$ 当然，$RR$ 可以是正无穷，我们使用一个正大值 $INFINF$ 表示。（为什么 $LL$ 不用负大值记录，可以仔细想想）
• 于是问题就变成，给定许多个段，求处于哪个位置，$localminlocal\backslash \; min$ 是最小的 我们只要对段排序，位置肯定是某个端点处的位置。 这个时候我们可能会想到，退出某个段，$DD$ 的影响就没了，应该把 $DD$ 退回，这样就写成滑动窗口了，我们可以用简单差分：再累加一个 $[R+1,INF,-D][R+1,INF,-D]$ 的段把影响去掉即可。

代码

• 时间复杂度：$O(n\log n)O(n\backslash log\; n)$

int aa[MAX];

int cnt;
struct node{
    ll L,R;
    int delta;
    bool operator<(const node &ND)const{
        if(L != ND.L)return L < ND.L;
        return R < ND.R;
    }
}seg[2 * MAX];

int main()
{
    int T = read();
    while(T--){
        int n = read();
        for(int i = 1;i <= n;++i){
            aa[i] = read();
        }

        int ans1 = 0;
        cnt = 0;
        for(int i = 2;i <= n-1;++i){
            if(aa[i] == aa[i-1] || aa[i] == aa[i+1])continue;
            ll L,R,D;
            if(aa[i-1] < aa[i] && aa[i] < aa[i+1]){
                L = (aa[i] + aa[i-1]) / 2 + 1;
                R = (aa[i] + aa[i+1] + 1) / 2 - 1;
                D = 1;
                cnt++;
                seg[cnt].L = L;
                seg[cnt].R = R;
                seg[cnt].delta = D;

                cnt++;
                seg[cnt].L = R+1;
                seg[cnt].R = INF;
                seg[cnt].delta = -D;

            }else if(aa[i-1] < aa[i] && aa[i] > aa[i+1]){
                int L1 = (aa[i] + aa[i-1]) / 2 + 1;
                int L2 = (aa[i] + aa[i+1]) / 2 + 1;
                L = max(L1,L2);
                R = INF;
                D = 1;

                cnt++;
                seg[cnt].L = L;
                seg[cnt].R = R;
                seg[cnt].delta = D;

            }else if(aa[i-1] > aa[i] && aa[i] > aa[i+1]){
                L = (aa[i] + aa[i+1]) / 2 + 1;
                R = (aa[i] + aa[i-1] + 1) / 2 - 1;
                D = 1;

                cnt++;
                seg[cnt].L = L;
                seg[cnt].R = R;
                seg[cnt].delta = D;

                cnt++;
                seg[cnt].L = R+1;
                seg[cnt].R = INF;
                seg[cnt].delta = -D;
            }else{
                ans1++;
                int L1 = (aa[i] + aa[i-1] + 1) / 2;
                int L2 = (aa[i] + aa[i+1] + 1) / 2;
                L = min(L1,L2);
                R = INF;
                D = -1;

                cnt++;
                seg[cnt].L = L;
                seg[cnt].R = R;
                seg[cnt].delta = D;
            }

        }

        sort(seg+1,seg+1+cnt);
        int ans = ans1;
        int delta = 0;

        for(int i = 1;i <= cnt;++i){
            delta += seg[i].delta;
            if(i == cnt || (seg[i].L != seg[i+1].L))ans = min(ans,ans1+delta);		// 可以想想为什么要这个if
        }

        cout << ans << '\n';

    }
    return 0;
}

H：牛牛看云

题意 | 简单偏中等

• 给定 $n,a_{i}n,a\_i$，求

• $3\le n\le 10^{6}3\backslash le\; n\backslash le\; 10^6$ $0\le a_i\le 10000\backslash le\; a\_i\backslash le\; 1000$

思路 | 思维

• 第一个想法， 右侧的 $\sum \backslash sum$ 中，$a_i-1000a\_i-1000$ 是一个常量，我们可以想做：

其中 $x=a_i-1000x=a\_i-1000$ 可以转化成这 $n-i+1n-i+1$ 个点到某个点 $xx$ 之间的距离和，但是貌似挺复杂的，我们有更简单的方法

• 第二个想法，我们利用好 $a_{i}a\_i$ 的值域比较小，我们可以把题目化成：

其中 $pai{r}_{x}pair\_x$ 表示有多少对 $(i,j)(i,j)$，满足 $1\le i\le j\le n1\backslash le\; i\backslash le\; j\backslash le\; n$ 满足 $x=a_i+a_{j}x=a\_i+a\_j$ 我们可以记 $cn{t}_{x}cnt\_x$ 表示 $nn$ 个数字中有多少个数字为 $xx$

• 怎么算呢，如果 $a_i=a_{j}a\_i=a\_j$ ，合法对数明显为 $\frac{cnt(cnt+1)}{2}\backslash frac\{cnt(cnt+1)\}\{2\}$ 如果 $a_i\mathrm{\ne }{a}_{j}a\_i\backslash ne\; a\_j$ ，合法对数也明显为 $cn{t}_{a_i}\times cn{t}_{a_j}cnt\_\{a\_i\}\; \backslash times\; cnt\_\{a\_j\}$

I：B站与各唱各的

题意 | 中等

• $TT$ 组样例，每组给定 $n,mn,m$ 表示有 $nn$ 个人，$mm$ 句歌词。每个人可以选择每句歌词唱不唱，不能与他人沟通。 若某句歌词被所有人唱了，或者所有人都没唱，那么这句是失败的，否则是成功的。 每个人都十分聪明，求唱成功的句的期望取模 $1e9+71e9+7$

思路 | 数学

• 我们随便想一想，容易得到一个策略：每个人对每句随机选择 $\mathrm{（}\frac{1}{2}\mathrm{概}\mathrm{率}\mathrm{）}（\backslash frac\{1\}\{2\}\; 概率）$ 唱与不唱，那么策略是最优的。 每句假设是独立的。如果每个人采取这样的策略，那么唱失败的概率只有 ${\displaystyle \frac{2}{2^n}}\backslash cfrac\{2\}\{2^n\}$ 容易得到，答案即为：

J：小朋友做游戏

• 签到。考虑选 $aa$ 个吵的，$bb$ 个不吵的，满足 $a+b=na+b=n$ 且 $a\le \frac{n}{2}a\backslash le\; \backslash frac\{n\}\{2\}$ 选吵的 $xx$ 个，只要选幸福度最高的 $xx$ 个吵的即可。做一个排序然后一个前缀和即可。

K：冒险公社 （天了噜，简单题没人做？）

题意 | 简单

• $nn$ 个岛，每个岛为 $RGBRGB$ 三色之一
• $3\le n\le 10^{5}3\backslash le\; n\backslash le\; 10^5$

思路 | 简单dp

• 发现，第 $ii$ 个预测和 $[1,i-3][1,i-3]$ 的所有岛都没有关系，明显符合 dp 的无后效性 答案求的是绿色岛的最大值。 发现和每个岛的颜色有关，直接设 $dp[i][j][k][p]dp[i][j][k][p]$ 表示走完前 $ii$ 个岛，其中岛 $i,i-1,i-2i,i-1,i-2$ 的颜色分别为 $j,k,pj,k,p$ ，合法方案中绿色岛最多的值
• 然后考虑转移，每次多走一格岛，明显转移是从 $dp[i-1][i2][i3][i4]dp[i-1][i2][i3][i4]$ 转移到 $dp[i][i1][i2][i3]dp[i][i1][i2][i3]$ 什么时候转移呢？合法转移，看这个位置的罗盘预测是否满足即可

代码

• 时间复杂度：$O(n\times 3^4)O(n\backslash times\; 3^4)$

/**
0 1 2
R G B
*/
int dp[MAX][3][3][3];

int main()
{
    int n;cin >> n;
    string ss;cin >> ss;

    for(int i = 2;i < n;++i)
    for(int i1 = 0;i1 < 3;++i1)
    for(int i2 = 0;i2 < 3;++i2)
    for(int i3 = 0;i3 < 3;++i3)
        dp[i][i1][i2][i3] = -1;

    for(int i = 0;i < 3;++i)
    for(int i2 = 0;i2 < 3;++i2)
    for(int i3 = 0;i3 < 3;++i3){
        dp[1][i][i2][i3] = 0;
        if(i == 1)dp[1][i][i2][i3]++;
        if(i2 == 1)dp[1][i][i2][i3]++;
    }

    int ans = -1;

    for(int i = 2;i < n;++i)
    for(int i1 = 0;i1 < 3;++i1)
    for(int i2 = 0;i2 < 3;++i2)
    for(int i3 = 0;i3 < 3;++i3)
    for(int i4 = 0;i4 < 3;++i4)
    if(dp[i-1][i2][i3][i4] != -1){
        int pre = dp[i-1][i2][i3][i4];
        int R = 0,G = 0;

        if(i1 == 0)R++;
        else if(i1 == 1)G++;

        if(i2 == 0)R++;
        else if(i2 == 1)G++;

        if(i3 == 0)R++;
        else if(i3 == 1)G++;

        int now = 0;
        if(i1 == 1)now++;

        if(ss[i] == 'G' && G > R){
            dp[i][i1][i2][i3] = max(dp[i][i1][i2][i3],pre + now);
        }else if(ss[i] == 'R' && R > G){
            dp[i][i1][i2][i3] = max(dp[i][i1][i2][i3],pre + now);
        }else if(ss[i] == 'B' && R == G){
            dp[i][i1][i2][i3] = max(dp[i][i1][i2][i3],pre + now);
        }

        if(i == n-1)ans = max(ans,dp[i][i1][i2][i3]);
    }

    cout << ans;

    return 0;
}

L：牛牛学走路

• 签到