牛客小白月赛59题解（完整版）_弹珠碰撞 弹珠活动编程华为

A-我会开摆_牛客小白月赛59 (nowcoder.com)

思路：对于每一个位置，判断其右边，下边，右下边位置是否满足就行。

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    char a[4][4];
        for(int i=0;i<4;i++)
            scanf("%s",a[i]);
        int ans=0;
        for(int i=0;i<3;i++)
        {
            ans=0;
            for(int j=0;j<3;j++)
            {
                if(a[i][j]==a[i][j+1]&&a[i][j]==a[i+1][j]&&a[i][j]==a[i+1][j+1]) 
                {
                    cout<<"Yes\n";
                    return ;
                }
            }
        }
        cout<<"No\n";
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

总结：读题要认真、仔细一点。

B-走廊的灯_牛客小白月赛59 (nowcoder.com)

思路：思维题，当i大于等于2的时候，对于每一个位置，如果说前面那个和和当前这个状态满足同一个条件，就加1，否则，直接赋值为0就行，遍历所有位置，找到最大值。

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    string s;
    cin>>n>>s;
    //最长有多少盏灯不包含亮着的或者是不包含灭了的
    int dp1[100010]={0},dp2[100010]={0};
    s=' '+s;
    if(s[1]=='0')    dp1[1]=1;
    else if(s[1]=='1')    dp2[1]=1;
    else    dp1[1]=1,dp2[1]=1;
    for(int i=2;i<=n;i++)//一直到第i号位的时候最长是多少
    {
        if(s[i]=='0')//如果说当前是灭的
        {
            dp1[i]=dp1[i-1]+1;
            dp2[i]=0;
        }
        else if(s[i]=='1')
        {
            dp1[i]=0;
            dp2[i]=dp2[i-1]+1;
        }
        else
        {
             dp1[i]=dp1[i-1]+1;
            dp2[i]=dp2[i-1]+1;
        }
    }
    int ans=-1;
    for(int i=1;i<=n;i++)
        ans=max(ans,max(dp1[i],dp2[i]));
    cout<<ans<<endl;
    return ;
}
int main()
{
    int t;
    cin>>t;
    while(t--)    solve();
    return 0;
}

总结：就思维题 。多想想。

 C-输出练习_牛客小白月赛59 (nowcoder.com)

 思路：看数据范围，最大的时间复杂度也只是当k=2的时候，循环63次不到，最大也就是63*10的四次方。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll l,r,k;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>l>>r>>k;
        vector<ll>ans;
        bool f=false;
        if(k==0ll)
        {
            ans.push_back(0);
            ans.push_back(1);
        }
        else if(k==1ll)    ans.push_back(1);
        else
        {
            ll a=k;
            ans.push_back(1);
            ans.push_back(k);
            while(a<=r/k)//防止a爆long long
            {
                a*=k;
                ans.push_back(a);
            }
        }
        for(auto x:ans)
        {
            if(x>=l&&x<=r)
            {
                cout<<x<<' ';
                f=true;
            }
        }
        if(!f)    cout<<"None.\n";
        else    cout<<endl;
    }
    return 0;
}

总结：重点就是对于时间复杂度的计算，别看到2的63次方就慌了。其次就是在对极限，也就是最大值的处理上，要注意，不能爆long long ，重点，提前预算一下。

 D-国际象棋_牛客小白月赛59 (nowcoder.com)

 思路：在每一次棋子的时候都判断一下是否满足K子连珠了。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int book[N],a[N][N],n,m,k;
bool check(int x,int y)
{
    int t=a[x][y],count=0,i=y,j;
    if(y>=k)
    {
        while(i>0)
        {
            if(a[x][i--]==t)    count++;
            else    break;
        }
    }
    if(count>=k)    return true;
    else    count=0;
    i=x;
    while(i>0)
    {
        if(a[i--][y]==t)    count++;
        else    break;
    }
    i=x+1;
    while(i<=m)
    {
        if(a[i++][y]==t)    count++;
        else    break;
    }
    if(count>=k)    return true;
    else    count=0;
    i=x,j=y;
    while(i>0&&j>0)
    {
        if(a[i--][j--]==t)    count++;
        else    break;
    }
    if(count>=k)    return true;
    else    count=0;
    i=x+1,j=y+1;
    while(i<=n&&j<=m)
    {
        if(a[i++][j++]==t)    count++;
        else    break;
    }
    if(count>=k)    return true;
    else    count=0;
    i=x,j=y;
    while(i>0&&j<=m)
    {
        if(a[i--][j++]==t)    count++;
        else    break;
    }
    i=x+1;j=y-1;
    while(i<=n&&j<=m)
    {
        if(a[i++][j--]==t)    count++;
        else    break;
    }
    if(count>=k)    return true;
    else    return false;
}
int main()
{
    int t,zi;
    cin>>n>>m>>k>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>zi;
        a[zi][++book[zi]]=i%2+1;
        if(check(zi,book[zi]))
        {
            cout<<i<<endl;
            return 0;
        }
    }
}

总结：认真读题，先把题目读懂。

E-弹珠碰撞_牛客小白月赛59 (nowcoder.com)

 思路：两个球发生碰撞，则交换位置，交换位置球走的位置就相当于和他碰撞的那个球本来不碰撞需要走的位置，我们可以直接让所有的球都沿他们自己的方向去走就好了，但是并不会影响最后一个球出界的时间。所以我们只需要与处理一下每一个位置后面或者是前面和自己方向不一样的球的数量就好了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+7;
int dir[N],pre[N],last[N],pos[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)    cin>>dir[i];
    for(int i=1,x;i<=m;i++)
    {
        cin>>x;
        pos[x]=(dir[i]==0?-1:1);
    }
    for(int i=1;i<=n;i++)
        pre[i]=pre[i-1]+(pos[i]==1?1:0);
    for(int i=n;i>=1;i--)
        last[i]=last[i+1]+(pos[i]==-1?1:0);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(pos[i]==1)
            res=max(res,n-i+last[i]+1);
        else if(pos[i]==-1)
            res=max(res,i+pre[i]);
    }
    cout<<res<<endl;
    return 0;
}

总结：找规律，不用太纠结于过程是怎么样执行的，化繁为简。

F-困难卷积_牛客小白月赛59 (nowcoder.com)

思路：结论题目： 如果说b数组的和小于等于n，那么数组的种类数不会超过sqrt(n)!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n;
    cin>>n;
    //如果说b数组的和小于等于n，那么数组的种类数不会超过sqrt(n)!
    map<ll,ll>mp1;
    map<ll,ll>mp2;
    int a;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        mp1[a]++;
    }
    for(int j=1;j<=n;j++)
    {
        cin>>a;
        mp2[a]++;
    }
    ll sum=0;
    for(auto i:mp1)
        for(auto j:mp2)
            sum+=(i.second*j.second)*(ll)sqrt(abs(i.first-j.first));
    cout<<sum<<endl;
    return 0;
}

总结：结论题目，记住结论，减少时间复杂度。