前言

第一次参加牛客训练营，题目真的很有挑战性 （不会做） ，题目包含的知识面很广 （其实是我知识面太窄了） 补题就花了好长的时间 （其实是我摆烂，一天也就补个一两题） ，再加上正逢春节假期，当然要好好休息啦。于是这一场的补题，从去年拖到了今年。（不会吧不会吧，不会有人过年当晚、大年初一，初二还在学习吧）

九小时九个人九扇门

链接：https://ac.nowcoder.com/acm/contest/23106/A
思路：这里我们可以通过观察出一个结论数字根最后的值也就等于那个数模上9（如果结果是0，那么就是9），如果没推出这个结论，也可以写个函数来模拟一下，得到最后的值。然后再用dp的思想，
1.对于每个数我们有两种状态，选与不选。
2.选中的话需要考虑上一个数与当前数和的数字根
3.也可以不考虑上一个数，把当前数当做第一个选的数
4.不选的话，只要将i-1的数复制到当前i就行

#include<bits/stdc++.h>
using namespace std;
const int N=101000,M=998244353;
int dp[N][10];
int num[N];
int mod(int x)//求数字根函数
{    int res=x%9;
 if(res==0) res=9; 
    return res;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>num[i];
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)
    {
        int t=mod(num[i]);
        dp[i][t]++;//前面都没选，第一次选当前数
        for(int j=1;j<10;j++)
        {t=mod(num[i]+j);
         dp[i][j]=(dp[i-1][j]+dp[i][j])%M;//没选当前的数
            dp[i][t]=(dp[i-1][j]+dp[i][t])%M;//选了当前的数
        }
    }
    for(int i=1;i<10;i++)
        cout<<dp[n][i]<<" ";
}

炸鸡块君与FIFA22

链接：https://ac.nowcoder.com/acm/contest/23106/B
思路：这题难点在于存档点，当积分模3等于0时，就算是输也不会扣分。如果不考虑存档点，那么这就是一个区间求和问题，区间求和一般解决方法为
1.st表（离线修改，在线查询）
2.线段树（在线修改，在线查询）
这题的情况有点不同，所以我们要加一些东西，比如将st表分为三份，分别表示初始分数为0，1，2开始的不同情况。
st表：

#include<bits/stdc++.h>
using namespace std;
char s[200005];
int dp[3][200005][21];
int n,q;
int mod3(int x)
{
    return (x%3+3)%3;
}
int main()
{
    cin>>n>>q;
    scanf("%s",s+1);
    memset(dp,0,sizeof dp);
    for(int j=0;j<=20;j++)
        for(int i=1;i<=n;i++)
        {
            if(j==0)//预处理
            {
                if(s[i]=='W') dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=1;
                if(s[i]=='L') dp[1][i][j]=dp[2][i][j]=-1;
                            }
            else
            {
                int t=i,t1=i+(1<<(j-1));
                if(t1>n)
                {for(int k=0;k<3;k++)
                    dp[k][t][j]=dp[k][t][j-1];
                }
                else
                {for(int k=0;k<3;k++)
                        dp[k][t][j]=dp[k][t][j-1]+dp[mod3(k+dp[k][t][j-1])][t1][j-1];
                }
            }
        }
int l,r,ans;
    for(int i=0;i<q;i++){
        scanf("%d%d%d",&l,&r,&ans);
        int pos=l;
        while(pos<=r){
            int j=0;
            while(pos+(1<<j)-1<=r)    j++;
            j--;
            ans+=dp[ans%3][pos][j];
            pos+=(1<<j);
        }
        printf("%d\n",ans);
    }
}

线段树太过复杂，我没写出来，于是找了一个大佬的看了看

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l;
    int r;
    int a,b,c;
};
node t[1000000];
char s[200005];
int n;

void build(int u,int x,int y){
    t[u].l=x;
    t[u].r=y;
    t[u].a==0;t[u].b=1;t[u].c=2;
    if(x==y){
         if(s[x]=='W'){
             t[u].a++;t[u].b++;t[u].c++;
         }else if(s[x]=='L'){
             t[u].b--;t[u].c--;
         }
         //cout<<"u="<<u<<" "<<x<<" "<<y<<" "<<t[u].a<<" "<<t[u].b<<" "<<t[u].c<<endl;

        return;
    }
    int mid=(x+y)>>1;
    build(2*u,x,mid);
    build(2*u+1,mid+1,y);
    //putup
    t[u].a=t[2*u].a;
    t[u].b=t[2*u].b;
    t[u].c=t[2*u].c;
    //if(u==8) cout<<t[u].b<<endl;
    if(t[u].a%3==0){
        t[u].a+=t[2*u+1].a;
    }else if(t[u].a%3==1){
        t[u].a+=t[2*u+1].b-1;
    }else{
        t[u].a+=t[2*u+1].c-2;
    }
    if(t[u].b%3==0){
        t[u].b+=t[2*u+1].a;
    }else if(t[u].b%3==1){
        t[u].b+=t[2*u+1].b-1;
    }else{
        t[u].b+=t[2*u+1].c-2;
        //if(u==8)cout<<"u"<<u<<" "<<t[2*u+1].c-2<<endl;
    }
    if(t[u].c%3==0){
        t[u].c+=t[2*u+1].a;
    }else if(t[u].c%3==1){
        t[u].c+=t[2*u+1].b-1;
    }else{
        t[u].c+=t[2*u+1].c-2;
    }
    //cout<<"u="<<u<<" "<<x<<" "<<y<<" "<<t[u].a<<" "<<t[u].b<<" "<<t[u].c<<endl;
}
int ans=0;
void qury(int p,int x,int y){
     //cout<<"21 "<<x<<" "<<y<<" "<<ans<<endl;
    if(t[p].l>=x&&t[p].r<=y){
        if(ans%3==0) ans+=t[p].a;
        else if(ans%3==1) ans+=t[p].b-1;
        else if(ans%3==2) ans+=t[p].c-2;
        //cout<<" "<<t[p].l<<" "<<t[p].r<<" "<<ans<<endl;
       // cout<<" "<<t[p].b<<" "<<t[p].c<<endl;
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid) qury(2*p,x,y);
    if(y>mid) qury(2*p+1,x,y);
}
int main(){
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    build(1,1,n);
    while(q--){
        int l,r,m;
        cin>>l>>r>>m;
        ans=m%3;
        qury(1,l,r);
        ans=m+ans-m%3;
        cout<<ans<<endl;
    }
}

Baby’s first attempt on CPU

链接：https://ac.nowcoder.com/acm/contest/23106/C
思路：这题的题面很复杂，当时还没看完就放弃了，比赛之后补题的时候才发现其实很简单。我们用gap数组来表示，我们在第i个语句前插入的空语句数量。然后对于每一行，我们只要判断当前位与目的位的空语句数量是否达到要求即可。

#include<bits/stdc++.h>
using namespace std;
 int a,b,c;
int gap[101];
void ch(int x,int y,int i)
{ if(x==1)
        { int k=i-y;
            int m=0;
            for(int j=k;j<i;j++)
                m+=gap[j];
            if(m<4-y)
            {
                gap[i-1]=4-y-m;
            }
        }
}
int main()
{  int n;
    cin>>n;
    memset(gap,0,sizeof gap);
    for(int i=1;i<=n;i++)
    {  cin>>a>>b>>c;
        if(!a&&!b&&!c) continue;
       ch(a,1,i),ch(b,2,i),ch(c,3,i);
    }
    int ans=0;
    for(int i=1;i<101;i++)
        ans+=gap[i];
    cout<<ans<<endl;
}

牛牛做数论

链接：https://ac.nowcoder.com/acm/contest/23106/D
思路：对于 $H (x) = ? (x) / x$ 来说，最大的一个就是从大到小数第一个质数，最小的一个是小于n的因数最多的一个，可以通过12357（为什么不乘6，因为6=2*3，我们要乘上质数）来找。

#include<bits/stdc++.h>
using namespace std;
bool find(int x)
{
    for(int i=2;i*i<=x;i++)
        if(x%i==0) return false;
    return true;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x;
        cin>>x;
        long long int ans=1;
        if(x==1) cout<<-1<<endl;
        else
        {
            for(int i=2;;i++)
            {
                if(!find(i)) continue;
                if(i*ans>x) break;
                ans*=i;
            }
            while(!find(x)) x--;
            cout<<ans<<" "<<x<<endl;
        }
        
    }
}

炸鸡块君的高中回忆

链接：https://ac.nowcoder.com/acm/contest/23106/E
思路：因为每次进去后，都要有个人带着卡出来，所以每一次实际进入的人数为m-1（当n<=m时不用考虑这个，直接就进去了），所以先减去一个m，然后依次除以m-1，这题由于数据问题，模拟的话会超时，不然的话模拟也是个好方法。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long int n,k,ans=0;
        cin>>n>>k;
        if(k==1&&n!=1)
        {
            cout<<-1<<endl;
            continue;
        }else
        {long long int a=0;
           if(n>k) 
           {
               a=n-k;
               if(a%(k-1)!=0)
                   a=a/(k-1)+1;
               else
                   a=a/(k-1);
               ans=a*2+1;
           }else
               ans=1;
        }
             cout<<ans<<endl;
        }
    }

中位数切分

链接：https://ac.nowcoder.com/acm/contest/23106/F
思路：这题由于题意说的不是很明白，看了半天样例，后来才知道，中位数是排序后求的。所以先要对数组排序。然后再从后向前遍历查找中位数，直到找到第一个比m小的中位数。思路很简单，但是还有很多的做法比如树状数组优化dp来做。

#include<bits/stdc++.h>
using namespace std;
int find(int num[],int k)
{
    if(k%2==0)
        return num[k/2];
    else return num[k/2+1];
}
int main()
{ int t;
    cin>>t;
    while(t--)
    {int n,m;
        cin>>n>>m;
        int num[n+1];
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        num[0]=0;
        sort(num,num+n+1);
        int ans=0;
        while(find(num,n)>=m)
            ans++,n--;
        if(ans==0) ans=-1;
        cout<<ans<<endl;
    }
}

ACM is all you need

链接：https://ac.nowcoder.com/acm/contest/23106/G
思路：这题的题意就是找到一个b，使得变换后的local minimum的个数最少。然后对于这一个数组中的任意一个三元组（i-1,i,i+1），local mininum 即为num[i]比它左右两边的数都小。我们要求变换后，这样的三元组个数最小。然后对于 $f_ i =∣f_ i ?b∣+b$ ，我们由绝对值可以想到 $f_i$ 到b距离，然后对于每个距离都加上b，比较的时候等于无变化。于是可以等价于 $f_ i =∣f_ i ?b∣$ ，然后对于每一个三元组，我们求出能使这个三元组满足local mininum 的b的取值范围。存入一个数组，左端点加一，右端点减一，当遍历到左端点时表示之后的local mininum的数量加一（表示当前数又达到了一个三元组存在local mininum的值），遍历到右端点时local mininum的数量减一（表示当前数又走出了一个三元组存在local mininum的值），这里用map来存储，否则会爆数组。最后再遍历数组，来计数，维护一个最小值，即为最后答案。

#include<bits/stdc++.h>
using namespace std;
map<int, int> cnt;
map<int, int>::iterator it;
const int inf=1e9;
int main(){
    int t;
    cin>>t;
    while(t--)
    {cnt.clear();
        int n;
        cin>>n;
        int num[n+1];
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        for(int i=2;i<n;i++)
        {int a=num[i],b=num[i-1],c=num[i+1];
            if(a==b||a==c) continue;
         int L,R;
            if(a<b&&a<c){//大小大
                if(b>c)swap(b,c);
                L=1,R=(b+a)/2;
                if((b+a)%2==0)R--;
                cnt[L]++,cnt[R+1]--;
            }
            if(b<a&&a<c||c<a&&a<b){//大中小，小中大
                if(b>c)swap(b,c);
                L=(a+b)/2+1,R=(a+c)/2;
                if((a+c)%2==0)R--;
                cnt[L]++,cnt[R+1]--;
            }
            if(a>b&&a>c){//小大小
                if(b<c)swap(b,c);
                L=(a+b)/2+1,R=1e9;
                cnt[L]++,cnt[R+1]--;
            }
        }
     bool f1=0,f2=0;//防止1和1e9的位置被忽略，忽略就表示存在一个数b，使得不存在local mininum
     int sum=0,res=inf;
        for(it=cnt.begin();it!=cnt.end();it++)//遍历map
        {int a=(*it).first,b=(*it).second;
            if(a<=1) f1=1;
            if(a>=inf) f2=1;
         sum+=b;
         if(a<=inf)
         res=min(res,sum);
        }
     if(!f1||!f2) res=0;
     cout<<res<<endl;
    }
}

牛牛看云

链接：https://ac.nowcoder.com/acm/contest/23106/H
思路：由于本题给出的数的范围比较小，我们可以开一个数组（元素个数等于数的最大值），然后存入对应i的个数，再依次遍历，根据公式计算答案。
另外一种方法就是先存入，再排一下序，然后对于每一个数，找到和它相加等于1000的值的位置，该位置的左边即为与该数相加小于1000的数，右边为相加大于1000的数，然后再分别计算各自的值相加。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int q[n];
    for(int i=1;i<=n;i++)
        cin>>q[i],q[i]=q[i]-500;
    sort(q+1,q+n+1);
    int f[n];
    f[0]=0;
    for(int i=1;i<=n;i++)
        f[i]=f[i-1]+q[i];
    long long int ans=0;
    for(int i=1;i<=n;i++)
    {  int t=upper_bound(q+i,q+n+1, 0-q[i])-q;
        ans+=abs(-f[t-1]+f[i-1]-(t-i)*q[i]);
        ans+=abs(f[n]-f[t-1]+(n-t+1)*q[i]);
    }
    cout<<ans<<endl;
    }

B站与各唱各的

链接：https://ac.nowcoder.com/acm/contest/23106/I
思路：对于每一位阿婆猪，在当前这句，它都有两种选择即为唱和不唱。对于某一句歌词，都有 $2^n$ 种不同的结果，然后去掉全都没唱和全都唱了这两种可能。所以对于每一句都有 $\frac{2^n-2}{2^n}$ 的概率唱成功。然后有m句，所以期望就是 $\frac{2^n-2}{2^n}*m$ ，然后在计算时数值过大会模上一个数，对于除法没有直接的模的方法，只有转化为逆元计算。对于一个数mod，a的逆元就是 $a^{(mod-2)}$ ，计算的过程使用快速幂，快速幂还是不熟啊，还要多敲敲。

#include<iostream>
using namespace std;
const int MOD=1e9+7;
long long  pow(long long  a,long long  b)
{long long int ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%MOD;
        a=(a*a)%MOD;
        b=b>>1;
    }
 return ans%MOD;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long  n,m;
        cin>>n>>m;
        long long  ans=1;
        n=pow(2,n);
    ans=m*(n-2)%MOD*pow(n,MOD-2)%MOD;
        cout<<ans%MOD<<endl;
    }
}

小朋友做游戏

链接：https://ac.nowcoder.com/acm/contest/23106/J
思路：先将两种小朋友排个序，然后算出最少需要多少个安静的小朋友从大到小先放入，之后再从大到小比较闹腾的小朋友和安静的小朋友的幸福值，放入大的那个，直到一方为空，或者凑足人数。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b,n;
        cin>>a>>b>>n;
        int p[a+1],q[b+1];
        p[0]=0,q[0]=0;
        for(int i=1;i<=a;i++)
            cin>>p[i];
        for(int i=1;i<=b;i++)
            cin>>q[i];
        sort(p,p+a+1);
        sort(q,q+b+1);
        long long int ans=0;
        int k=0;
        if(n%2==1) k=n/2+1;
        else k=n/2;
         int l=a-k,r=b;
        if(a<k) 
        {  cout<<-1<<endl;
            continue; }
        for(int i=a;i>a-k;i--)
            ans+=p[i];
        n=n-k;
        while(n--)
            if(p[l]>q[r])
                ans+=p[l],l--;
            else
                ans+=q[r],r--;
        cout<<ans<<endl;
    }
}

冒险公社

链接：https://ac.nowcoder.com/acm/contest/23106/K
思路：这题的题面有点多，但读完过后可以发现整个过程中涉及到了多个状态，那么可以用dp的思想来解决。先从第三个数开始，每次关注i，i+1，i+2这三个位置上的岛的颜色（每个岛有三种，所以对于每个位置有27种变化），如果颜色不符合字符的描述那就跳过，符合就说明存在符合条件的选项。然后符合条件的绿岛个数就等于上一个位置的最大绿岛数加上当前位关注的·最后一位是否是绿的，是就加一，不是就不加。
状态转移方程： $d p [i] [m] [l] [k] = m a x (d p [i] [m] [l] [k], d p [i ? 1] [l] [k] [j] + (m = = 0));$
m,l,k分别表示i+2,i+1,i的岛的颜色，j表示i-1的岛的颜色。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dp[N][3][3][3];
int count(int i,int j,int k)
{    int a=0,b=0;
     if(i==0) a++;
     if(i==2) b++;
     if(j==0) a++;
     if(j==2) b++;
     if(k==0) a++;
     if(k==2) b++;
 return a-b;
}
int main()
{
    int n;
    cin>>n;
    char s[n+5];
    cin>>s+1;
    for(int i=0;i<=n;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++)
                    dp[i][j][k][l]=-1;
    for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++)
                {
                    if(count(j,k,l)<=0&&s[2]=='G') continue;
                    if(count(j,k,l)!=0&&s[2]=='B') continue;
                    if(count(j,k,l)>=0&&s[2]=='R') continue;
                    dp[2][j][k][l]=(j==0)+(k==0);
                }
    for(int i=3;i<=n;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++)
                    for(int m=0;m<3;m++)
                    {    if(dp[i-1][l][k][j]==-1) continue;
                        if(count(k,l,m)<=0&&s[i]=='G') continue;
                        if(count(k,l,m)!=0&&s[i]=='B') continue;
                        if(count(k,l,m)>=0&&s[i]=='R') continue;
                        dp[i][m][l][k]=max(dp[i][m][l][k],dp[i-1][l][k][j]+(m==0));
                    }
    int res=-1;
    for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++)
            res=max(res,dp[n][j][k][l]);
    cout<<res<<endl;
}

牛牛学走路

链接：https://ac.nowcoder.com/acm/contest/23106/L
思路：签到题，先根据字符加减，每次变化后求一下距离，要注意下最后的答案的精度。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        double x=0,y=0;
        double ans=0;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='L') x--;
            else if(s[i]=='R') x++;
            else if(s[i]=='D') y--;
            else y++;
            ans=max(ans,sqrt(x*x+y*y));
        }
        printf("%.8lf\n",ans);
    }
}