2021牛客月赛40 题解

牛客小白月赛比赛传送门:

牛客小白月赛40_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ牛客小白月赛是面向ACM/CSP/NOI/ICPC/CCPC比赛备战选手,初级选手第一次参加编程比赛,ACM基础训练,编程入门学习的基础比赛。https://ac.nowcoder.com/acm/contest/11217

目录

A.数字游戏

B.跳跳跳

 C.数字匹配

D.优美字符串

E.分组

F.过桥

G.空调遥控

H.来点gcd

I.体操队形


A.数字游戏

思路:

硬模拟题,分情况考虑结尾为1,0时,长度分别为奇数或者偶数的情况;

代码:

#include
using namespace std;
inline int read()
{
	int x = 0, y = 1;char c = getchar();
	while (c < '0' || c>'9') { if (c == '-') y = -1;c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * y;
}
int main()
{
    int t;
    t=read();
    while(t--)
    {
        int n,k=0,m;
        n=read();
        m=n;
        while(n>0)
        {
            if(n%2==1)k++;
            n/=2;
        }
        if(m%2==1&&(k-1)%2==0&&m!=1)printf("%d\n",(k-1)*2+1);
        else if(m%2==1&&(k-1)%2==1&&m!=1)printf("%d\n",(k-1)*2);
        else if(m==1)printf("1\n");
        else if(m%2==0&&k%2==0)printf("%d\n",k*2);
        else if(m%2==0&&k%2==1)printf("%d\n",k*2+1);
    }
    return 0;
}

B.跳跳跳

思路:

区间dp板子题,只要遍历一遍区间长度即可,因为可以向着左右两边跳跃,我们求出状态转移方程为:dp[i][j]=max(arr[i]*len+dp[i+1][j],arr[j]*len+dp[i][j-1]);取从左和从右区间边界跳过来的最大值.

代码:

#include
using namespace std;
int arr[4004],dp[4004][4004];
int main()
{
    int n,ans=0;  
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
        arr[i+n]=arr[i];
        dp[i][i]=dp[i+n][i+n]=arr[i] ; 
    }
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=2*n;i++)
        {
            int j=len+i-1;
            dp[i][j]=max(arr[i]*len+dp[i+1][j],arr[j]*len+dp[i][j-1]);
        }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i][i+n-1]);
    printf("%d",ans);
    return 0;
}

 C.数字匹配

思路:

我的思路是暴力卡常,只要把n内每两个数进行判断,如果包含长度等于k的相同子串,则匹配数++.稍微进行一些剪枝就能过.

代码:

#include
#include
using namespace std;
int a[70],b[70];
int main()
{
    int n,t,anss=0;
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int lx=1,ly=1,x=i,y=j;
            while(x!=0)
            {
                a[lx]=x%2;
                lx++;
                x/=2;
            }
            if(lx=t)anss++;
        }
    }
    printf("%d",anss);
    return 0;
}

D.优美字符串

思路:

遍历查找相邻两边字符相等的间隔数.

代码:

#include
#include
using namespace std;
int main()
{
    string str;
    int t;
    cin>>t;
    while(t--)
    {
        int k=0;
        cin>>str;
        for(int i=1;i

E.分组

思路:

二分题,二分一个人数最多的小组的人数mid,并且以此来分组,当一个组人数小于mid那么通过对该组人数+mid-1来进行处理再去/mid计算分了组,这样可以保证他们分为1组.

代码:

#include
using namespace std;
int t,n,m,sum[100005];
int check(int x)
{
    int su=0;
    for(int i=1;i<=n;i++)
    {
        su+=(sum[i]+x-1)/x;
    }
    return su<=m;
}
int main()
{
    int ans=-1;
    scanf("%d%d",&n,&m);
    for(int i=0;i>1;
        if(check(mid))
            ans=mid,r=mid-1;
        else 
            l=mid+1;
    }
    printf("%d",ans);
    return 0;
}

F.过桥

思路:

裸bfs,注意标记和不要越界就行.

代码:

#include
#include
using namespace std;
int arr[2003],vis[2003],n;
struct node
{
    int x,step;
};
queuequ;
void bfs()
{
    qu.push({1,0});
    while(qu.size())
    {
        node bef=qu.front();
        qu.pop();
        int id=bef.x;
        if(id==n)
        {
            printf("%d",bef.step);
            return ;
        }
        if(bef.x+arr[bef.x]<1)continue;
        if(arr[id]>0)
        {
            for(int i=id;i<=id+arr[id]&&i<=n;i++)
            {
                if(!vis[i])
                {
                	vis[i]=1;
					qu.push({i,bef.step+1});
				}
            }
        }
        else
        {
            for(int i=2;i<=id+arr[id];i++)
            {
                if(!vis[i])
                {
                	vis[i]=1;
					qu.push({i,bef.step+1});
				}
            }
        }
    }
    printf("-1");
    return ;   
}
int main()
{ 
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    bfs();
    return 0;
}

G.空调遥控

思路:

此题做法很多,二分,线段树,滑动窗口等.题目主旨是要维护一个区间最大值.这属于滑动窗口板子题.

代码:

#include
#include
#define int long long
using namespace std;
int arr[1000006];
bool cmp(int a,int b)
{
    return a

H.来点gcd

思路:

求s子集的gcd是否为题目所给的x,我一开始没有进行预处理,而是在询问是进行处理,导致tle,后来进行了预处理.此题找子集gcd为x,肯定要尽量找所有x的倍数,然后求他们的gcd,然后用一个数组去记录这个gcd,当此gcd等于x时答案为YES.

代码:

#include
#include
using namespace std;
int edg[1000006],dk[1000006];
int t,n,k,q,x;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i=0;i<=n;i++)edg[i]=0,dk[i]=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&x),edg[x]++;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j+=i)
            {
                if(edg[j])
                {
                    dk[i]=__gcd(j,dk[i]);
                }
            }
        }
        while(k--)
        {
            scanf("%d",&q);
            if(dk[q]==q)printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

I.体操队形

思路:

乍看上去有点top序的意思,仔细一看,n<=10,直接求1到n的全排列,对每种排队情况进行check,如果符合题目要求,ans++.最后输出暗杀.

代码:

#include 
#include 
#include 
#include 
#include 
using namespace std;
int a[20],pos[20];
int main()
{
	int i,j,n,sum=0;
	scanf("%d",&n);
    for(int i=0;i