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

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

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

A:九小时九个人九扇门

题意 | 简单

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

思路 | 数学 + dp

  • 容易猜想或者得到,设 f(x)f(x) 表示 xx 的数字根,那么有:
f(x)=(x1)mod9+1(1)f(x)=(x-1)\bmod 9+1\tag{1}

还有一些性质:

f(x+y)=f(f(x)+f(y))f(x+9)=f(x)f(9x)=9f(xy)=f(f(x)×f(y))f(x+y)=f(f(x)+f(y))\\ f(x+9)=f(x)\\ f(9x)=9\\ f(xy)=f(f(x)\times f(y))

这些都可以由上面 (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(x9)x(x\le9) 的方案数,然后转移即可。 随便计算数字根,用定义法 O(1)O(1) 还是递归法 O(log)O(\log ) 都行

代码

  • 时间复杂度:O(n(10+O()))O(n(10+O(算一个数字根))) 空间复杂度:滚动数组了一下,Θ(20)\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] 之后的分数为多少
  • 1n,q2×1051\le n,q\le 2\times 10^5 1lrn1\le l\le r\le n 0s1090\le s\le10^9

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

  • 容易想到,快速计算分数肯定要用能分治的数据结构。我这里使用倍增表。 倍增表就是:
dp[i][j]=p=iarrpdp[i][j]=\underset{p=i}{\overset{i+2^j-1}{\bigoplus}}arr_p

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

  • 这里想到,分数是三的倍数扣分不记录,则按分数取余 33 分别记录,就变成 dp[i][j][0/1/2]dp[i][j][0/1/2] 想好转移。
dp[i][j][k]=dp[i][j1][k]+dp[i+2j1][j1][k]dp[i][j][k]=dp[i][j-1][k]+dp[i+2^{j-1}][j-1][k^\prime]

alt

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

代码

  • 时间复杂度:O((n+q)logn)O((n+q)\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)=φ(x)xH(x)=\frac{\varphi(x)}{x}

在这里插入图片描述

思路 | 数论

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

E:炸鸡块君的高中回忆

  • 签到题 先特判,再做下述操作: 操作1:花两步,校园里人少掉 m1m-1。 操作2:花一步,校园里人少掉 mm,但是只能做一次。
  • 设操作1 做了 kk 次,答案就是最小的 kk ,满足:
(m1)k+mnknmm1(m-1)k+m\ge n\\ 即 \qquad k\ge \frac{n-m}{m-1}

答案就是 2k+12k+1

F:中位数切分

题意 | 中等

  • 把长度为 nn 的序列划分成最多份,满足每份的中位数 m\ge m 。若长度为偶数,中位数取中间的左边那个数字。
  • 1n1051\le n\le 10^5 1ai,m1091\le a_i,m\le 10^9

思路 | 数据结构 + dp

  • 划分满足无后效性,想到 dpdp ,则设:dp[i]dp[i] 表示考虑玩前 ii 个元素,最多划分的段数
  • 看到中位数,想到把元素变化。若 aima_i\ge m ,即为 11,否则记为 1-1 这样,序列的中位数 m\ge m 转化为序列的和 1\ge 1
  • dpdp 的转移,如下:
dp[i]=max{dp[j]+1}[j+1,i]1dp[i]=\max\{dp[j]+1\},满足[j+1,i] 这一段的元素和 \ge 1
  • 元素和,想到前缀和。我们用 prepre 数组记录前缀和,于是后面就变成了:
dp[i]=max{dp[j]+1}pre[i]pre[j]1dp[i]=\max\{dp[j]+1\},pre[i]-pre[j]\ge 1

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

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

代码

  • 时间复杂度:O(nlogn)O(n\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 个整数点 fif_i 定义 local minlocal\ min 表示满足 fi<min(fi1,fi+1)f_i<\min(f_{i-1},f_{i+1})
  • 变化,表示让所有的值 fif_i 变成 fi=fib+bf_i=|f_i-b|+b,其中 bb 是自己选择的一个整数 求经过一次变化,local minlocal\ min 的最小值是多少
  • n106\sum n\le 10^6 1fi1091\le f_i\le 10^9

思路 | 思维 + 差分

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

代码

  • 时间复杂度:O(nlogn)O(n\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,ain,a_i,求
i=1nj=inai+aj1000\sum_{i=1}^n \sum_{j=i}^n |a_i+a_j-1000|
  • 3n1063\le n\le 10^6 0ai10000\le a_i\le 1000

思路 | 思维

  • 第一个想法, 右侧的 \sum 中,ai1000a_i-1000 是一个常量,我们可以想做:
i=1nj=inajx\sum_{i=1}^n \sum_{j=i}^n |a_j-x|

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

  • 第二个想法,我们利用好 aia_i 的值域比较小,我们可以把题目化成:
ans=pairx×x1000ans=pair_x \times |x-1000|

其中 pairxpair_x 表示有多少对 (i,j)(i,j),满足 1ijn1\le i\le j\le n 满足 x=ai+ajx=a_i+a_j 我们可以记 cntxcnt_x 表示 nn 个数字中有多少个数字为 xx

  • 怎么算呢,如果 ai=aja_i=a_j ,合法对数明显为 cnt(cnt+1)2\frac{cnt(cnt+1)}{2} 如果 aiaja_i\ne a_j ,合法对数也明显为 cntai×cntajcnt_{a_i} \times cnt_{a_j}

I:B站与各唱各的

题意 | 中等

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

思路 | 数学

  • 我们随便想一想,容易得到一个策略:每个人对每句随机选择 12(\frac{1}{2} 概率) 唱与不唱,那么策略是最优的。 每句假设是独立的。如果每个人采取这样的策略,那么唱失败的概率只有 22n\cfrac{2}{2^n} 容易得到,答案即为:
m×2n22nm\times \frac{2^n-2}{2^n}

J:小朋友做游戏

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

K:冒险公社 (天了噜,简单题没人做?)

题意 | 简单

  • nn 个岛,每个岛为 RGBRGB 三色之一 在这里插入图片描述
  • 3n1053\le n\le 10^5

思路 | 简单dp

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

代码

  • 时间复杂度:O(n×34)O(n\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:牛牛学走路

  • 签到